Matroide de rigidez

En las matemáticas de la rigidez estructural , un matroide de rigidez es un matroide que describe el número de grados de libertad de un grafo no dirigido con aristas rígidas de longitud fija, incrustado en el espacio euclidiano . En un matroide de rigidez para un grafo con n vértices en un espacio d -dimensional, un conjunto de aristas que define un subgrafo con k grados de libertad tiene rango de matroide dn − k . Un conjunto de aristas es independiente si y solo si, para cada arista del conjunto, eliminarla aumentaría el número de grados de libertad del subgrafo restante. ^{[ 1 ] [ 2 ] [ 3 ]}  

Un marco es un grafo no dirigido , incrustado en un espacio euclidiano d- dimensional mediante la asignación de una d -tupla de coordenadas cartesianas a cada vértice del grafo. A partir de un marco con n vértices y m aristas, se puede definir una matriz con m filas y nd columnas, una versión expandida de la matriz de incidencia del grafo denominada matriz de rigidez . En esta matriz, la entrada en la fila e y la columna ( v , i ) es cero si v no es un extremo de la arista e . Si, por otro lado, la arista e tiene los vértices u y v como extremos, entonces el valor de la entrada es la diferencia entre las coordenadas i de v y u . ^{[ 1 ] [ 3 ]}

El matroide de rigidez del marco dado es un matroide lineal cuyos elementos son las aristas del grafo. Un conjunto de aristas es independiente, en el matroide, si corresponde a un conjunto de filas de la matriz de rigidez que es linealmente independiente . Un marco se denomina genérico si las coordenadas de sus vértices son números reales algebraicamente independientes . Dos marcos genéricos cualesquiera sobre el mismo grafo G determinan el mismo matroide de rigidez, independientemente de sus coordenadas específicas . Este es el matroide de rigidez ( d -dimensional) de G. ^{[ 1 ] [ 3 ]}

Una carga sobre una estructura es un sistema de fuerzas en los vértices (representadas como vectores). Una tensión es un caso especial de carga, en la que se aplican fuerzas iguales y opuestas a los dos extremos de cada arista (que puede imaginarse como un resorte) y las fuerzas formadas de esta manera se suman en cada vértice. Toda tensión es una carga de equilibrio , una carga que no impone ninguna fuerza de traslación sobre todo el sistema (la suma de sus vectores de fuerza es cero) ni ninguna fuerza de rotación. Una dependencia lineal entre las filas de la matriz de rigidez puede representarse como una autotensión , una asignación de fuerzas iguales y opuestas a los extremos de cada arista que no es idénticamente cero, pero que se anula en cada vértice. Por lo tanto, un conjunto de aristas forma un conjunto independiente en el matroide de rigidez si y solo si no tiene autotensión. ^{[ 3 ]}

El espacio vectorial de todas las cargas posibles, en un sistema de n vértices, tiene dimensión dn , entre las cuales las cargas de equilibrio forman un subespacio de dimensión ${\displaystyle dn-{\binom {d+1}{2}}}$. Un conjunto independiente en el matroide de rigidez tiene un sistema de cargas de equilibrio cuya dimensión es igual a la cardinalidad del conjunto, por lo que el rango máximo que puede tener cualquier conjunto en el matroide es${\displaystyle dn-{\binom {d+1}{2}}}$Si un conjunto tiene este rango, se deduce que su conjunto de tensiones es el mismo que el espacio de cargas de equilibrio. De forma alternativa y equivalente, en este caso toda carga de equilibrio sobre la estructura puede resolverse mediante una tensión que genera un conjunto de fuerzas iguales y opuestas, y se dice que la estructura es estáticamente rígida. ^{[ 3 ]}

Si los vértices de una estructura están en movimiento, dicho movimiento puede describirse en pequeñas escalas de distancia mediante su gradiente , un vector para cada vértice que especifica su velocidad y dirección. El gradiente describe una aproximación linealizada al movimiento real de los puntos, en el que cada punto se mueve a velocidad constante en línea recta. El gradiente puede describirse como un vector fila que tiene una coordenada numérica real para cada par.${\displaystyle (v,i)}$dónde${\displaystyle v}$es un vértice del marco y${\displaystyle i}$es el índice de una de las coordenadas cartesianas de${\displaystyle d}$espacio -dimensional; es decir, la dimensión del gradiente es la misma que el ancho de la matriz de rigidez. ^{[ 1 ] [ 3 ]}

Si se supone que los bordes del marco son barras rígidas que no pueden expandirse ni contraerse (pero sí rotar libremente), entonces cualquier movimiento que respete esta rigidez debe preservar las longitudes de los bordes: la derivada de la longitud, en función del tiempo durante el cual ocurre el movimiento, debe permanecer cero. Esta condición puede expresarse en álgebra lineal como una restricción de que el vector gradiente del movimiento de los vértices debe tener un producto interno cero con la fila de la matriz de rigidez que representa el borde dado. Por lo tanto, la familia de gradientes de movimientos (infinitesimalmente) rígidos viene dada por el espacio nulo de la matriz de rigidez. ^{[ 1 ] [ 3 ]} Para marcos que no están en posición genérica, es posible que algunos movimientos infinitesimalmente rígidos (vectores en el espacio nulo de la matriz de rigidez) no sean gradientes de ningún movimiento continuo, pero esto no puede ocurrir para marcos genéricos. ^{[ 2 ]}

Un movimiento rígido de la estructura es un movimiento tal que, en cada instante, la estructura es congruente con su configuración original. Los movimientos rígidos incluyen traslaciones y rotaciones del espacio euclidiano; los gradientes de los movimientos rígidos forman un espacio lineal que tiene como bases las traslaciones y rotaciones, de dimensión${\displaystyle {\binom {d+1}{2}}}$, que siempre debe ser un subespacio del espacio nulo de la matriz de rigidez. Debido a que el espacio nulo siempre tiene al menos esta dimensión, el matroide de rigidez puede tener rango como máximo${\displaystyle dn-{\binom {d+1}{2}}}$y cuando tiene este rango, los únicos movimientos que preservan las longitudes de las aristas del marco son los movimientos rígidos. En este caso, se dice que el marco es rígido de primer orden (o infinitesimalmente). ^{[ 1 ] [ 3 ]} De manera más general, una arista${\displaystyle e}$pertenece a la operación de cierre de matroides de un conjunto${\displaystyle S}$si y solo si no existe un movimiento continuo del marco que cambie la longitud de${\displaystyle e}$pero deja las longitudes de los bordes en${\displaystyle S}$sin cambios. ^{[ 1 ]}

Aunque se definen en términos diferentes (vectores columna frente a vectores fila, o fuerzas frente a movimientos), la rigidez estática y la rigidez de primer orden se reducen a las mismas propiedades de la matriz subyacente y, por lo tanto, coinciden entre sí. En dos dimensiones, el matroide de rigidez genérico también describe el número de grados de libertad de un tipo diferente de movimiento, en el que cada arista está restringida a permanecer paralela a su posición original en lugar de estar restringida a mantener la misma longitud; sin embargo, la equivalencia entre rigidez y movimiento paralelo se rompe en dimensiones superiores. ^{[ 3 ]}

Un marco tiene una realización única en un espacio d -dimensional si cada colocación del mismo grafo con las mismas longitudes de arista es congruente con él. Dicho marco debe ser necesariamente rígido, porque de lo contrario existe un movimiento continuo que lo lleva a una colocación no congruente con las mismas longitudes de arista, pero la realizabilidad única es más fuerte que la rigidez. Por ejemplo, el grafo diamante (dos triángulos que comparten una arista) es rígido en dos dimensiones, pero no es realizable de forma única porque tiene dos realizaciones diferentes, una en la que los triángulos están en lados opuestos de la arista compartida y otra en la que ambos están en el mismo lado. Los grafos realizables de forma única son importantes en aplicaciones que implican la reconstrucción de formas a partir de distancias, como la triangulación en topografía, ^{[ 4 ]} la determinación de las posiciones de los nodos en una red de sensores inalámbricos , ^{[ 5 ]} y la reconstrucción de conformaciones de moléculas mediante espectroscopia de resonancia magnética nuclear . ^{[ 4 ]}

Bruce Hendrickson definió un grafo como redundantemente rígido si permanece rígido después de eliminar cualquiera de sus aristas. En términos matroidales, esto significa que el matroide de rigidez tiene el rango completo.${\displaystyle dn-{\binom {d+1}{2}}}$y que el matroide no tiene ningún coloops. Hendrickson demostró que todo marco realizable de forma única (con longitudes de arista genéricas) es un grafo completo o un${\displaystyle (d+1)}$- vértice-conectado , grafo redundantemente rígido, y conjeturó que esta es una caracterización exacta de los marcos realizables de forma única. ^{[ 6 ]} La conjetura es verdadera para una y dos dimensiones; en el caso unidimensional, por ejemplo, un grafo es realizable de forma única si y solo si es conectado y sin puentes . ^{[ 7 ]} Sin embargo, la conjetura de Henrickson es falsa para tres o más dimensiones. ^{[ 8 ]} Para marcos que no son genéricos, es NP-difícil determinar si un marco dado es realizable de forma única. ^{[ 9 ]}

Streinu y Theran (2009) definen un gráfico como${\displaystyle (k,l)}$-disperso si cada subgrafo no vacío con${\displaystyle n}$vértices tiene como máximo${\displaystyle kn-l}$bordes y${\displaystyle (k,l)}$-apretado si lo es${\displaystyle (k,l)}$-escaso y tiene exactamente${\displaystyle kn-l}$bordes. ^{[ 10 ]} A partir de la consideración de cargas y tensiones se puede ver que un conjunto de bordes que es independiente en el matroide de rigidez forma un${\displaystyle (d,{\binom {d+1}{2}})}$-grafo disperso, porque de lo contrario existiría un subgrafo cuyo número de aristas excedería la dimensión de su espacio de cargas de equilibrio, de lo cual se deduce que tendría una autotensión. Por un razonamiento similar, un conjunto de aristas que es a la vez independiente y rígido forma un${\displaystyle (d,{\binom {d+1}{2}})}$-grafo ajustado. Por ejemplo, en una dimensión, los conjuntos independientes forman los conjuntos de aristas de los bosques, grafos (1,1)-dispersos, y los conjuntos rígidos independientes forman los conjuntos de aristas de los árboles, grafos (1,1)-ajustados. En este caso, el matroide de rigidez de un marco es el mismo que el matroide gráfico del grafo correspondiente. ^{[ 2 ]}

En dos dimensiones, Laman (1970) demostró que la misma caracterización es cierta: los conjuntos independientes forman los conjuntos de aristas de los grafos (2,3)-dispersos y los conjuntos rígidos independientes forman los conjuntos de aristas de los grafos (2,3)-apretados. ^{[ 11 ]} Basándose en este trabajo, los grafos (2,3)-apretados (los grafos de marcos genéricos mínimamente rígidos en dos dimensiones) han llegado a conocerse como grafos de Laman . La familia de grafos de Laman en un conjunto fijo de${\displaystyle n}$vértices forma el conjunto de bases del matroide de rigidez de un grafo completo y, más generalmente, para cada grafo${\displaystyle G}$que forma un marco rígido en dos dimensiones, los subgrafos de Laman que abarcan${\displaystyle G}$son las bases del matroide de rigidez de${\displaystyle G}$.

Sin embargo, en dimensiones superiores no todos${\displaystyle (d,{\binom {d+1}{2}})}$-El grafo ajustado es mínimamente rígido, y caracterizar los grafos mínimamente rígidos (las bases del matroide de rigidez del grafo completo) es un importante problema abierto. ^{[ 12 ]}