En las matemáticas de la rigidez estructural , el arriostramiento de rejilla es un problema de agregar refuerzos transversales a una rejilla cuadrada para convertirla en una estructura rígida. Puede resolverse de manera óptima traduciéndolo a un problema de teoría de grafos sobre la conectividad de grafos bipartitos . [1] [2] [3]
El problema considera un marco en forma de cuadrícula , 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 de 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 rejilla. Un movimiento continuo válido de esta estructura es una forma de variar continuamente la ubicación de sus bordes y uniones en el plano de tal manera que mantengan las mismas longitudes y las mismas uniones, pero sin necesidad de 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 formados por varillas rígidas y uniones flexibles no pueden cambiar de forma: dos triángulos cualesquiera con lados de la misma longitud deben ser congruentes (este es el postulado SSS ). Si un cuadrado está arriostrado agregando una de sus diagonales como otra barra rígida, la diagonal lo 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 del marco arriostrado. (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 plegada no se puede obtener mediante un movimiento continuo). Por lo tanto, si todos los cuadrados del plano dado la rejilla tiene refuerzos transversales, la rejilla no puede 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 rígida la rejilla, añadiendo tirantes transversales a todos sus cuadrados, utiliza muchos más tirantes transversales de los necesarios. El problema del arriostramiento de la rejilla requiere una descripción de los conjuntos mínimos de arriostramientos transversales que tienen el mismo efecto de hacer rígida toda la estructura. [1] [2] [3]
Como observaron originalmente Ethan Bolker y Henry Crapo (1977), el problema del arriostramiento de la cuadrícula se puede traducir a un problema de 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 una arista para cada cuadrado arriostrado de la rejilla. Demostraron que la rejilla cruzada es rígida si y sólo si este grafo bipartito es conexo. De ello se deduce que los arriostramientos mínimos de la cuadrícula corresponden a los árboles que conectan todos los vértices del gráfico, y que tienen cuadrados exactamente arriostrados. Cualquier arriostramiento transversal rígido pero sobre arriostrado (con más de este número de cuadrados arriostrados) se puede reducir a un arriostramiento transversal mínimo al encontrar un árbol de expansión de su gráfico. [1] [2] [3] [4]
De manera más general, supongamos que una rejilla con refuerzos transversales no es rígida. Entonces, el número de grados de libertad en su familia de formas es igual al número de componentes conectados del gráfico bipartito, menos uno. Si una rejilla parcialmente arriostrada se va a volver rígida arriostrando más cuadrados, el número mínimo de cuadrados adicionales que deben arriostrarse es este número de grados de libertad. Se puede obtener una solución con este número de cuadrados sumando este número de aristas al gráfico bipartito, conectando pares de sus componentes conectados de modo que después de la suma solo quede un componente. [1] [2] [3] [4]
Otra versión del problema solicita un "doble arriostramiento", un conjunto de tirantes transversales que es lo suficientemente redundante como para permanecer rígido incluso si se elimina una de las diagonales. Esta versión permite utilizar ambas diagonales de un solo cuadrado, pero no es obligatorio. [1]
En la misma vista de gráfico bipartito utilizada para resolver el problema de refuerzo, un doble refuerzo de una cuadrícula corresponde a un multigrafo bipartito no dirigido que está conectado y sin puentes , lo que significa que 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 igual número de filas y columnas, los únicos arriostramientos dobles de este tamaño mínimo son los ciclos hamiltonianos . Los ciclos hamiltonianos son fáciles de encontrar en los gráficos bipartitos completos que representan el problema de arriostramiento, pero encontrarlos en otros gráficos bipartitos es NP-completo . Debido a esto, encontrar el subconjunto de doble arriostramiento más pequeño de un arriostramiento más grande es NP-duro . Sin embargo, es posible aproximar este subconjunto doble arriostrado más pequeño dentro de una relación de aproximación constante . [5]
Jenny Baglivo y Jack Graver (1983) descubrieron una teoría análoga, utilizando grafos dirigidos , para el arriostramiento por tensión , en la que los cuadrados están apuntalados por alambres o cuerdas (que no pueden expandirse más allá de su longitud inicial, pero pueden doblarse o colapsar a una longitud más corta). ) en lugar de mediante varillas rígidas. Para hacer rígido un solo cuadrado mediante arriostramiento por tensión, es necesario arriostrar ambas diagonales, en lugar de solo una diagonal. [1] [2]
Se puede representar un arriostramiento de tensión 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á arriostrado por la diagonal con pendiente positiva, y un borde desde un vértice de 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 sólo si el gráfico resultante está fuertemente conexo . [1] [2]
Si un conjunto determinado de tirantes es insuficiente, es necesario agregar refuerzos adicionales, lo que corresponde en la vista del gráfico a agregar aristas que conectan entre sí los componentes fuertemente conectados de un gráfico. De esta manera, el problema de encontrar un conjunto mínimo de llaves adicionales para agregar puede verse como un ejemplo de fuerte aumento de la conectividad y puede resolverse en tiempo lineal . [6] Según el teorema de Robbins , los grafos no dirigidos que pueden conectarse fuertemente dirigiendo sus aristas son exactamente los grafos sin puente; Reinterpretando este teorema en términos de arriostramiento de rejilla, un arriostramiento mediante varillas rígidas forma un arriostramiento doble si y solo si cada una de sus varillas puede ser reemplazada por un solo alambre (posiblemente en la otra diagonal de su cuadrado) para formar un arriostramiento de tensión rígido. [7]
