En las matemáticas de la rigidez estructural , una matroide de rigidez es una matroide que describe el número de grados de libertad de un gráfico no dirigido con bordes rígidos de longitudes fijas, incrustado en el espacio euclidiano . En una matroide de rigidez para un gráfico con n vértices en un espacio d -dimensional, un conjunto de aristas que define un subgrafo con k grados de libertad tiene un rango matroide dn - k . Un conjunto de aristas es independiente si y solo si, para cada arista del conjunto, la eliminación de la arista aumentaría el número de grados de libertad del subgrafo restante.[1] [2] [3]
Definición
Un marco es un gráfico no dirigido , incrustado en un espacio euclidiano d- dimensional al proporcionar una tupla d de coordenadas cartesianas para cada vértice del gráfico. 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 ampliada de la matriz de incidencia del gráfico llamada matriz de rigidez . En esta matriz, la entrada en la fila e y la columna ( v , i ) es cero si v no es un punto final de la arista e . Si, por otro lado, la arista e tiene vértices u y v como puntos finales, entonces el valor de la entrada es la diferencia entre las i- ésimas coordenadas de v y u . [1] [3]
La matroide de rigidez del marco dado es una matroide lineal que tiene como elementos los bordes del gráfico. Un conjunto de aristas es independiente, en la matroide, si corresponde a un conjunto de filas de la matriz de rigidez que es linealmente independiente . Un marco se llama genérico si las coordenadas de sus vértices son números reales algebraicamente independientes . Dos marcos genéricos cualesquiera en el mismo gráfico G determinan la misma matroide de rigidez, independientemente de sus coordenadas específicas. Este es el ( d -dimensional) rigidez matroid de G . [1] [3]
Estática
Una carga en un marco es un sistema de fuerzas sobre los vértices (representados como vectores). Una tensión es un caso especial de una carga, en la que se aplican fuerzas iguales y opuestas a los dos extremos de cada borde (que se puede imaginar como un resorte) y las fuerzas formadas de esta manera se suman en cada vértice. Todo esfuerzo 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 se puede representar como una auto-tensión , una asignación de fuerzas iguales y opuestas a los puntos finales de cada borde que no es idénticamente cero pero que suma cero en cada vértice. Por lo tanto, un conjunto de bordes forma un conjunto independiente en la matroide de rigidez si y solo si no tiene autoestres. [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. Un conjunto independiente en la 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 la matroide es. Si un conjunto tiene este rango, se deduce que su conjunto de tensiones es el mismo que el espacio de cargas de equilibrio. Alternativamente y de manera equivalente, en este caso, cada carga de equilibrio en 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]
Cinemática
Si los vértices de un marco están en movimiento, entonces ese movimiento puede describirse en pequeñas escalas de distancia por 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 la que cada punto se mueve a velocidad constante en línea recta. El gradiente puede describirse como un vector de fila que tiene una coordenada numérica real para cada par dónde es un vértice del marco y es el índice de una de las coordenadas cartesianas de -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 de la estructura son barras rígidas que no pueden expandirse ni contraerse (pero pueden girar libremente), cualquier movimiento que respete esta rigidez debe preservar las longitudes de los bordes: la derivada de la longitud, en función del tiempo transcurrido. en el que se produce 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. Así, la familia de gradientes de movimientos rígidos (infinitesimalmente) está dada por el espacio nulo de la matriz de rigidez. [1] [3] Para los 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 los gradientes de ningún movimiento continuo, pero esto no puede suceder para los marcos genéricos. [2]
Un movimiento rígido del marco es un movimiento tal que, en cada momento, el marco es congruente con su configuración original. Los movimientos rígidos incluyen traslaciones y rotaciones del espacio euclidiano; los gradientes de movimientos rígidos forman un espacio lineal que tiene las traslaciones y rotaciones como bases, de dimensión, 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, la rigidez matroide puede tener rango como máximo, y cuando tiene este rango, los únicos movimientos que preservan las longitudes de los bordes de la estructura son los movimientos rígidos. En este caso, se dice que el marco es de primer orden (o infinitesimalmente) rígido. [1] [3] De manera más general, una ventaja Pertenece a la operación de cierre matroide de un conjunto si y solo si no existe un movimiento continuo del marco que cambia la longitud de pero deja las longitudes de los bordes en sin alterar. [1]
Aunque se definen en términos diferentes (vectores de columna versus vectores de fila, o fuerzas versus 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, la matroide de rigidez genérica también describe el número de grados de libertad de un tipo diferente de movimiento, en el que cada borde está obligado a permanecer paralelo a su posición original en lugar de estar obligado a mantener la misma longitud; sin embargo, la equivalencia entre rigidez y movimiento paralelo se rompe en dimensiones superiores. [3]
Realización única
Un marco tiene una realización única en el espacio d -dimensional si cada ubicación del mismo gráfico con las mismas longitudes de borde es congruente con él. Tal marco debe ser necesariamente rígido, porque de lo contrario existe un movimiento continuo que lo lleva a una ubicación no congruente con las mismas longitudes de borde, pero la realizabilidad única es más fuerte que la rigidez. Por ejemplo, el gráfico de diamante (dos triángulos que comparten un borde) es rígido en dos dimensiones, pero no se puede realizar de forma única porque tiene dos realizaciones diferentes, una en la que los triángulos están en lados opuestos del borde compartido y otra en la que ambos están del mismo lado. Los gráficos de realización ú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 a través de espectroscopia de resonancia magnética nuclear . [4]
Bruce Hendrickson definió que un gráfico es redundantemente rígido si permanece rígido después de eliminar cualquiera de sus bordes. En términos matroidales, esto significa que la rigidez matroide tiene el rango completoy que el matroide no tiene coloops. Hendrickson demostró que cada marco realizable de forma única (con longitudes de borde genéricas) es un gráfico completo o un- grafo redundantemente rígido, conectado por vértices, y conjeturó que se trata de una caracterización exacta de los marcos realizables de forma única. [6] La conjetura es cierta para una y dos dimensiones; en el caso unidimensional, por ejemplo, un gráfico es únicamente realizable si y solo si está conectado y sin puentes . [7] Sin embargo, la conjetura de Henrickson es falsa para tres o más dimensiones. [8] Para los marcos que no son genéricos, es NP-difícil determinar si un marco dado es realizable de forma única. [9]
Relación con la escasez
Streinu y Theran (2009) definen un gráfico como-espacio si cada subgrafo no vacio con vértices tiene como máximo bordes, y -apretado si es -espacio y tiene exactamente bordes. [10] De la consideración de cargas y tensiones se puede observar que un conjunto de aristas que es independiente en la rigidez matroide forma una-Gráfico disperso, pues si no 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 un autoesfuerzo. Con un razonamiento similar, un conjunto de aristas que es tanto independiente como rígido forma una-Gráfica ajustada. Por ejemplo, en una dimensión, los conjuntos independientes forman los conjuntos de bordes de bosques, gráficos (1,1) dispersos, y los conjuntos rígidos independientes forman los conjuntos de árboles de bordes, gráficos ajustados (1,1). En este caso, la matroide de rigidez de un marco es la misma que la matroide gráfica del gráfico correspondiente. [2]
En dos dimensiones, Laman (1970) mostró que la misma caracterización es cierta: los conjuntos independientes forman los conjuntos de bordes de gráficos (2,3) -sparse y los conjuntos rígidos independientes forman los conjuntos de bordes de (2,3) -sight-graphs . [11] Con base en este trabajo, los gráficos ajustados (2,3) (los gráficos de marcos genéricos mínimamente rígidos en dos dimensiones) se conocen como gráficos de Laman . La familia de Laman grafica sobre un conjunto fijo devértices forma el conjunto de bases de la rigidez matroide de un grafo completo , y más generalmente para cada grafo que forma un marco rígido en dos dimensiones, los subgrafos de Laman que abarcan son las bases de la rigidez matroide de .
Sin embargo, en dimensiones superiores no todos El gráfico estrecho es mínimamente rígido, y caracterizar los gráficos mínimamente rígidos (las bases de la rigidez matroide del gráfico completo) es un problema abierto importante. [12]
Referencias
- ^ a b c d e f g Graver, Jack E. (1991), "Matroides de rigidez", SIAM Journal on Discrete Mathematics , 4 (3): 355-368, doi : 10.1137 / 0404032 , MR 1105942.
- ^ a b c Whiteley, Walter (1992), "Matroides y estructuras rígidas", Aplicaciones de Matroides , Enciclopedia de las matemáticas y sus aplicaciones, 40 , Cambridge: Cambridge Univ. Prensa, págs. 1–53, doi : 10.1017 / CBO9780511662041.002 , MR 1165538.
- ^ a b c d e f g h yo Whiteley, Walter (1996), "Algunas matroides de la geometría aplicada discreta", Teoría Matroide (Seattle, WA, 1995) , Matemáticas contemporáneas, 197 , Providence, RI: American Mathematical Society, págs. 171–311, doi : 10.1090 / conm / 197/02540 , MR 1411692.
- ^ a b Hendrickson, Bruce (1995), "El problema de la molécula: explotar la estructura en la optimización global", SIAM Journal on Optimization , 5 (4): 835–857, CiteSeerX 10.1.1.55.2335 , doi : 10.1137 / 0805040 , MR 1358807.
- ^ Eren, T .; Goldenberg, de acuerdo; Whiteley, W .; Yang, YR; Morse, AS; Anderson, BDO; Belhumeur, PN (2004), "Rigidez, cálculo y aleatorización en la localización de redes", Proc. Vigésima tercera Conferencia Conjunta Anual de las Sociedades de Computación y Comunicaciones del IEEE (INFOCOM 2004) , 4 , págs. 2673–2684, doi : 10.1109 / INFCOM.2004.1354686.
- ^ Hendrickson, Bruce (1992), "Condiciones para la realización de gráficos únicos", SIAM Journal on Computing , 21 (1): 65–84, doi : 10.1137 / 0221008 , MR 1148818.
- ^ Jackson, Bill; Jordán, Tibor (2005), "Matroides de rigidez conectada y realizaciones únicas de gráficos", Journal of Combinatorial Theory , Serie B, 94 (1): 1–29, doi : 10.1016 / j.jctb.2004.11.002 , MR 2130278.
- ^ Connelly, Robert (1991), "Sobre la rigidez global genérica", Geometría aplicada y matemáticas discretas , Serie DIMACS sobre matemáticas discretas e informática teórica, 4 , Providence, RI: American Mathematical Society, págs. 147-155, MR 1116345.
- ^ Saxe, JB (1979), La incrustabilidad de gráficos ponderados en el espacio k es fuertemente NP-difícil , Informe técnico, Pittsburgh, PA: Departamento de Ciencias de la Computación, Universidad Carnegie-Mellon. Citado por Jackson & Jordán (2005) .
- ^ Streinu, I .; Theran, L. (2009), "Hipergrafos dispersos y algoritmos de juegos de guijarros", European Journal of Combinatorics , 30 (8): 1944-1964, arXiv : math / 0703921 , doi : 10.1016 / j.ejc.2008.12.018.
- ^ Laman, G. (1970), "Sobre los gráficos y la rigidez de las estructuras esqueléticas planas", J. Engineering Mathematics , 4 (4): 331–340, Bibcode : 1970JEnMa ... 4..331L , doi : 10.1007 / BF01534980 , MR 0269535.
- ^ Jackson, Bill; Jordán, Tibor (2006), "Sobre la función de rango de la matriz de rigidez tridimensional" (PDF) , International Journal of Computational Geometry & Applications , 16 (5–6): 415–429, doi : 10.1142 / S0218195906002117 , MR 2269396.