En teoría de grafos , los grafos de Laman son una familia de grafos dispersos que describen los sistemas mínimamente rígidos de varillas y uniones en el plano. Formalmente, una gráfica de Laman es una gráfica en n vértices tal que, para todo k , cada subgrafo de k- vértice tiene como máximo 2 k - 3 aristas, y tal que toda la gráfica tiene exactamente 2 n - 3 aristas. Los gráficos de Laman llevan el nombre de Gerard Laman , de la Universidad de Amsterdam , quien en 1970 los utilizó para caracterizar estructuras planas rígidas. [1]Esta caracterización, sin embargo, ya había sido descubierta en 1927 por Hilda Geiringer . [2]
Rigidez
Los gráficos de Laman surgen en la teoría de la rigidez : si uno coloca los vértices de un gráfico de Laman en el plano euclidiano , en posición general , en general no habrá movimiento simultáneo de todos los puntos, salvo las congruencias euclidianas , que conserve las longitudes de todos los puntos. bordes del gráfico. Un gráfico es rígido en este sentido si y solo si tiene un subgrafo de Laman que abarca todos sus vértices. Por lo tanto, los gráficos de Laman son exactamente los gráficos mínimamente rígidos y forman las bases de las matroides de rigidez bidimensionales .
Si se dan n puntos en el plano, entonces hay 2 n grados de libertad en su ubicación (cada punto tiene dos coordenadas independientes), pero una gráfica rígida tiene solo tres grados de libertad (la posición de uno solo de sus vértices y la rotación del gráfico restante alrededor de ese vértice). Intuitivamente, agregar un borde de longitud fija a un gráfico reduce su número de grados de libertad en uno, por lo que los 2 n - 3 bordes en un gráfico de Laman reducen los 2 n grados de libertad de la ubicación del punto inicial a los tres grados de libertad. de un gráfico rígido. Sin embargo, no todos los gráficos con 2 n - 3 aristas son rígidos; la condición en la definición de un gráfico Laman de que ningún subgrafo puede tener demasiados bordes asegura que cada borde contribuya a reducir el número total de grados de libertad y no se desperdicie dentro de un subgrafo que ya es rígido debido a sus otros bordes.
Planaridad
Una pseudotriangulación puntiaguda es un dibujo de línea recta plana de un gráfico, con las propiedades de que la cara exterior es convexa, que cada cara delimitada es un pseudotriangulo , un polígono con solo tres vértices convexos, y que las aristas incidentes a cada vértice abarcan un ángulo de menos de 180 grados. Las gráficas que se pueden dibujar como pseudotriangulaciones puntiagudas son exactamente las gráficas planas de Laman. [3] Sin embargo, los gráficos de Laman tienen incrustaciones planas que no son pseudotriangulaciones, y hay gráficos de Laman que no son planos, como el gráfico de utilidad K 3,3 .
Escasez
Lee y Streinu (2008) y 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. Por lo tanto, en su notación, los gráficos de Laman son exactamente los gráficos ajustados (2,3), y los subgráficos de los gráficos de Laman son exactamente los gráficos dispersos (2,3). La misma notación se puede utilizar para describir otras familias importantes de gráficos dispersos , incluidos árboles , pseudoforestales y gráficos de arboricidad limitada . [4] [5]
Con base en esta caracterización, es posible reconocer gráficos de Laman de n -vértices en el tiempo O ( n 2 ) , simulando un "juego de guijarros" que comienza con un gráfico con n vértices y sin aristas, con dos guijarros colocados en cada vértice, y realiza una secuencia de los siguientes dos tipos de pasos para crear todos los bordes del gráfico:
- Cree un nuevo borde dirigido que conecte dos vértices que tengan dos guijarros y elimine un guijarro del vértice inicial del nuevo borde.
- Si un borde apunta desde un vértice u con como máximo un guijarro a otro vértice v con al menos un guijarro, mueva un guijarro de v a u e invierta el borde.
Si estas operaciones pueden usarse para construir una orientación del gráfico dado, entonces es necesariamente (2,3) -espacio, y viceversa. Sin embargo, son posibles algoritmos más rápidos que se ejecutan en el tiempo, basado en probar si duplicar un borde del gráfico dado da como resultado un multigraph que es (2,2) -tight (de manera equivalente, si se puede descomponer en dos árboles de expansión disjuntos de bordes ) y luego usar esta descomposición para verificar si el La gráfica dada es una gráfica de Laman. [6]
Construcción Henneberg
Antes del trabajo de Laman y Geiringer, Lebrecht Henneberg [7] Henneberg mostró que los gráficos mínimamente rígidos en dos o más vértices son exactamente los gráficos que se pueden obtener, comenzando desde un solo borde, mediante una secuencia de operaciones de los dos tipos siguientes:
caracterizó los gráficos bidimensionales mínimamente rígidos (es decir, los gráficos de Laman) de una manera diferente.- Agregue un nuevo vértice al gráfico, junto con los bordes que lo conectan a dos vértices previamente existentes.
- Subdivida un borde del gráfico y agregue un borde que conecte el vértice recién formado con un tercer vértice previamente existente.
Una secuencia de estas operaciones que forma un gráfico dado se conoce como construcción de Henneberg del gráfico. Por ejemplo, el gráfico bipartito completo K 3,3 se puede formar usando la primera operación para formar un triángulo y luego aplicando la segunda operación para subdividir cada borde del triángulo y conectar cada punto de subdivisión con el vértice del triángulo opuesto.
Referencias
- ^ 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.
- ^ Pollaczek ‐ Geiringer, Hilda (1927), "Über die Gliederung ebener Fachwerke", Zeitschrift für Angewandte Mathematik und Mechanik , 7 (1): 58–72.
- ^ Haas, Ruth ; Orden, David; Rote, Günter; Santos, Francisco ; Servacio, Brigitte ; Servacio, Herman; Souvaine, Diane ; Streinu, Ileana ; Whiteley, Walter (2005), "Gráficos planos mínimamente rígidos y pseudo-triangulaciones", Teoría y aplicaciones de la geometría computacional , 31 (1-2): 31-61, arXiv : math / 0307347 , doi : 10.1016 / j.comgeo.2004.07 0.003 , MR 2131802.
- ^ Lee, Audrey; Streinu, Ileana (2008), "Algoritmos de juegos de guijarros y gráficos dispersos", Matemáticas discretas , 308 (8): 1425–1437, arXiv : math / 0702129 , doi : 10.1016 / j.disc.2007.07.104 , MR 2392060.
- ^ 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.
- ^ Daescu, O .; Kurdia, A. (2009), "Hacia un algoritmo óptimo para reconocer gráficos de Laman", Proc. 42a Conferencia Internacional de Hawái sobre Ciencias de Sistemas (HICSS '09) , IEEE, págs. 1–10, arXiv : 0801.2404 , doi : 10.1109 / HICSS.2009.470.
- ^ Henneberg, L. (1911), Die graphische Statik der starren Systeme , Leipzig