Refuerzo de rejilla
En las matemáticas de la rigidez estructural , el arriostramiento de la rejilla es un problema de agregar arriostramientos transversales a una rejilla cuadrada para convertirla en una estructura rígida. Se puede resolver de manera óptima traduciéndolo en un problema de teoría de grafos sobre la conectividad de grafos bipartitos . [1] [2] [3]
Planteamiento del problema
El problema considera un marco en forma de cuadrícula cuadrada , con filas y columnas de cuadrados. La cuadrícula tiene bordes, cada uno de los cuales tiene una unidad de longitud y se considera una varilla rígida, libre para moverse continuamente dentro del plano euclidiano pero incapaz de cambiar su longitud. Estas varillas están unidas entre sí mediante juntas flexibles en los vértices de la cuadrícula. Un movimiento continuo válido de esta estructura es una forma de variar continuamente la colocación de sus bordes y juntas en el plano de tal manera que mantengan las mismas longitudes y los mismos aditamentos, pero sin requerir que formen cuadrados. En cambio, cada cuadrado de la cuadrícula puede deformarse para formar un rombo., y toda la cuadrícula puede formar una estructura irregular con una forma diferente para cada una de sus caras, como se muestra en la figura. [1] [2] [3]
A diferencia de los cuadrados, los triángulos hechos de varillas rígidas y uniones flexibles no pueden cambiar sus formas: dos triángulos cualesquiera con lados de la misma longitud deben ser congruentes (este es el postulado SSS ). Si un cuadrado tiene riostrasal agregar una de sus diagonales como otra barra rígida, la diagonal la divide en dos triángulos que de manera similar no pueden cambiar de forma, por lo que el cuadrado debe permanecer cuadrado a través de cualquier movimiento continuo de la estructura de refuerzo cruzado. (El mismo marco también podría colocarse en el plano de una manera diferente, doblando sus dos triángulos entre sí sobre su diagonal compartida, pero esta ubicación doblada no se puede obtener mediante un movimiento continuo). la cuadrícula se arriostraron de la misma manera, la cuadrícula no podía cambiar de forma; sus únicos movimientos continuos serían rotarlo o trasladarlo como un solo cuerpo rígido. Sin embargo, este método de hacer que la cuadrícula sea rígida, agregando refuerzos transversales a todos sus cuadrados, utiliza muchos más refuerzos cruzados de los necesarios. El problema de los arriostramientos de la rejilla pide una descripción de los conjuntos mínimos de arriostramientos transversales que tienen el mismo efecto, de hacer que todo el marco sea rígido. [1] [2] [3]
Solución teórica de grafos
Como observaron originalmente Ethan Bolker y Henry Crapo ( 1977 ), el problema de arriostramiento de la cuadrícula se puede traducir a un problema en la teoría de grafos al considerar un grafo bipartito no dirigido que tiene un vértice para cada fila y columna de la cuadrícula dada, y un borde para cada uno. cuadrado de refuerzo transversal de la cuadrícula. Demostraron que la cuadrícula cruzada es rígida si y solo si este gráfico bipartito está conectado. De ello se deduce que los refuerzos transversales mínimos de la cuadrícula corresponden a los árboles que conectan todos los vértices en el gráfico, y que tienen exactamentecuadrados con tirantes cruzados. Cualquier arriostramiento transversal pero rígido (con más de este número de cuadrados arriostrados) se puede reducir a un arriostramiento transversal mínimo encontrando un árbol de expansión en su gráfico. De manera más general, el número de grados de libertad en la forma de una cuadrícula cruzada es igual al número de componentes conectadosdel gráfico bipartito, menos uno. Si una cuadrícula parcialmente arriostrada se va a hacer rígida mediante arriostramientos transversales más cuadrados, el número mínimo de cuadrados adicionales que necesitan ser arriostrados es este número de grados de libertad, y se puede obtener una solución con este número de cuadrados mediante agregando este número de aristas al gráfico bipartito, conectando pares de sus componentes conectados de modo que después de la adición solo quede un componente restante. [1] [2] [3] [4]
Otra versión del problema pide un "doble arriostramiento", un conjunto de tirantes transversales lo suficientemente redundantes como para permanecer rígidos incluso si se quita una de las diagonales. Esta versión permite utilizar ambas diagonales de un solo cuadrado, pero no es obligatorio. En esta versión, un doble arriostramiento de una rejilla corresponde de la misma forma a un multigrafo bipartito no dirigido, conectado y sin puentes (cada borde pertenece al menos a un ciclo ). El número mínimo de diagonales necesarias para un doble arriostramiento es . [1] En el caso especial de cuadrículas con el mismo número de filas y columnas, los únicos arriostramientos dobles de este tamaño mínimo son los ciclos hamiltonianos., por lo que determinar si existe uno dentro de un arriostramiento más grande es NP-completo . Sin embargo, es posible aproximar el subconjunto de arriostramiento doble más pequeño de un arriostramiento dado dentro de una relación de aproximación constante . [5]
Jenny Baglivo y Jack Graver ( 1983 ) descubrieron una teoría análoga, utilizando gráficos dirigidos , para los refuerzos de tensión., en el que los cuadrados están reforzados por alambres o cuerdas (que no pueden expandirse más allá de su longitud inicial, pero pueden doblarse o colapsarse a una longitud más corta) en lugar de varillas rígidas. Para hacer un solo cuadrado rígido de esta manera, es necesario apuntalar sus dos diagonales, en lugar de solo una diagonal. Una vez más, se puede representar tal arriostramiento mediante un gráfico bipartito, que tiene un borde dirigido desde un vértice de fila a un vértice de columna si el cuadrado compartido de esa fila y columna está reforzado por la diagonal de pendiente positiva y un borde desde el vértice de una columna. a un vértice de fila si el cuadrado compartido está reforzado por la diagonal de pendiente negativa. La estructura arriostrada es rígida si y solo si el gráfico resultante está fuertemente conectado . [1] [2]De lo contrario, es necesario agregar refuerzos adicionales para conectar sus componentes fuertemente conectados . El problema de encontrar un conjunto mínimo de llaves adicionales para agregar es una instancia de fuerte aumento de conectividad y se puede resolver en tiempo lineal . [6] De acuerdo con el teorema de Robbins , las gráficas no dirigidas que se pueden hacer fuertemente conectadas dirigiendo sus bordes son exactamente las gráficas sin puentes; Reinterpretando este teorema en términos de arriostramiento de rejilla, un arriostramiento por varillas rígidas forma un arriostramiento doble si y solo si sus varillas pueden ser reemplazadas por alambres (posiblemente en las otras diagonales de sus cuadrados) para formar un arriostramiento rígido a tensión. [7]
Referencias
- ↑ a b c d e f Baglivo, Jenny A .; Graver, Jack E. (1983), "3.10 Estructuras de arriostramiento", Incidencia y simetría en el diseño y la arquitectura , Cambridge Urban and Architectural Studies, Cambridge, Reino Unido: Cambridge University Press, págs. 76–87, ISBN 9780521297844
- ^ a b c d e Graver, Jack E. (2001), Contando con marcos: Matemáticas para ayudar al diseño de estructuras rígidas , The Dolciani Mathematical Expositions, 25 , Washington, DC: Asociación Matemática de América, ISBN 0-88385-331-0, MR 1843781. Véanse en particular las secciones 1.2 ("El problema del arriostramiento de la red", págs. 4-12), 1.5 ("Más sobre el problema de la red", págs. 19-22), 2.6 ("La solución al problema de la red", págs. 50-55) y 4.4 ("Tensegridad: tirantes de tensión", en particular págs. 158-161).
- ^ a b c d Kappraff, Jay (2001), "4.18 Estructuras de arriostramiento" , Conexiones: El puente geométrico entre el arte y la ciencia , Serie sobre nudos y todo, 25 (2ª ed.), Singapur: World Scientific, págs. 154– 159, ISBN 9789810245856, Señor 1868159
- ^ Bolker, ED; Crapo, H. (1977), "Cómo reforzar un edificio de un piso", Medio ambiente y planificación B: Planificación y diseño , 4 (2): 125-152, doi : 10.1068 / b040125
- ^ Cheriyan, J .; Sebő, A .; Szigeti, Z. (2001), "Improving on the 1.5- Approximation of a small -edge connected spanning subgraph", SIAM Journal on Discrete Mathematics , 14 (2): 170–180, doi : 10.1137 / S0895480199362071 , MR 1856004
- ^ Gabow, Harold N .; Jordán, Tibor (2000), "Cómo hacer rígido un entramado de rejilla cuadrada con cables", SIAM Journal on Computing , 30 (2): 649–680, doi : 10.1137 / S0097539798347189 , MR 1769375
- ^ Robbins, HE (1939), "Un teorema sobre gráficos, con una aplicación a un problema de control de tráfico", American Mathematical Monthly , 46 (5): 281-283, doi : 10.2307 / 2303897 , JSTOR 2303897
enlaces externos
- Whitty, Robin, "Un teorema sobre tensegridades rectangulares" (PDF) , Teorema del día
- Matemáticas de rigidez
- Árbol de expansión
- Gráficos específicos de la aplicación
