Gráfico de Laman

De Wikipedia, la enciclopedia libre
El huso de Moser, un gráfico plano de Laman dibujado como una pseudotriangulación puntiaguda
El grafo bipartito completo K 3,3, un grafo de Laman no plano

En la teoría de grafos, los grafos de Laman son una familia de gráficos dispersos que describen los sistemas mínimamente rígidos de varillas y articulaciones en el plano. Formalmente, un grafo de Laman es un grafo de n vértices tal que, para todo k, cada subgrafo de k vértices tiene como máximo 2 k − 3 aristas, y tal que todo el gráfico tiene exactamente 2 n − 3 bordes. 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[editar]

Los gráficos de Laman surgen en la teoría de la rigidez: si se colocan los vértices de un gráfico de Laman en el plano euclidiano, en posición general, en general no habrá movimiento continuo simultáneo de todos los puntos, aparte de las congruencias euclidianas, que preserva las longitudes de todos los bordes del gráfico. Un grafo es rígido en este sentido si y solo si tiene un subgrafo de Laman que abarca todos sus vértices. Así, los gráficos de Laman son exactamente los gráficos mínimamente rígidos, y forman las bases de las matrices de rigidez bidimensional .

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 un gráfico rígido 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 el 2 n − 3 aristas en un gráfico de Laman reducen los 2 n grados de libertad de la colocació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 bordes es rígido; la condición en la definición de un gráfico de Laman de que ningún subgráfico puede tener demasiados bordes garantiza que cada borde contribuya a reducir el número total de grados de libertad y no se desperdicie dentro de un subgráfico que ya es rígido debido a sus otros bordes.

Planaridad[editar]

Una pseudotriangulación puntiaguda es un dibujo en línea recta plana de un gráfico, con las propiedades de que la cara exterior es convexa, que cada cara delimitada es un pseudotriángulo, un polígono con solo tres vértices convexos, y que las aristas incidentes en cada vértice abarcan un ángulo de menos de 180 grados. Los gráficos que se pueden dibujar como pseudotriangulaciones puntiagudas son exactamente los gráficos planos 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[editar]

Se define un grafo como -disperso si cada subgrafo no vacío con 𝑛 vértices tiene como máximo aristas, y -apretado si es -escaso y tiene exactamente aristas. Por lo tanto, en su notación, los gráficos de Laman son exactamente los gráficos (2,3) ajustados, y los subgráficos de los gráficos de Laman son exactamente los gráficos (2,3) dispersos. La misma notación se puede usar para describir otras familias importantes de gráficos dispersos, incluidos árboles, pseudobosques y gráficos de arboricidad acotada.[4][5]

Con base en esta caracterización, es posible reconocer gráficos de Laman de n vértices en el tiempo O(n2), simulando un "juego de guijarros" que comienza con un gráfico con n vértices y sin bordes, 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 una arista apunta desde un vértice u con al menos una piedra a otro vértice v con al menos una piedra, mueva una piedra de v a u e invierta la arista.

Si estas operaciones se pueden usar para construir una orientación del gráfico dado, entonces es necesariamente (2,3)-disperso 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 multigrafo que es (2,2) ajustado (equivalentemente, si se puede descomponer en dos árboles de expansión disjuntos) y luego usar esta descomposición para verificar si el gráfico dado es un gráfico de Laman.[6]​ Las técnicas de flujo de red se pueden usar para probar si un gráfico plano es un gráfico de Laman más rápidamente, en el tiempo. .[7]

Construcción Henneberg[editar]

Henneberg construcción del husillo Moser

Antes de la obra de Laman y Geiringer, se caracterizó los gráficos bidimensionales mínimamente rígidos (es decir, los gráficos de Laman) de una manera diferente.[8]​ Henneberg demostró que los gráficos mínimamente rígidos en dos o más vértices son exactamente los gráficos que se pueden obtener, a partir de un solo borde, mediante una secuencia de operaciones de los siguientes dos tipos:

  1. Agregue un nuevo vértice al gráfico, junto con los bordes que lo conectan a dos vértices previamente existentes.
  2. 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[editar]

  1. Laman, G. (1970), «On graphs and the rigidity of plane skeletal structures», J. Engineering Mathematics 4 (4): 331-340, Bibcode:1970JEnMa...4..331L, doi:10.1007/BF01534980 ..
  2. Pollaczek‐Geiringer, Hilda (1927), «Über die Gliederung ebener Fachwerke», Zeitschrift für Angewandte Mathematik und Mechanik 7 (1): 58-72, Bibcode:1927ZaMM....7...58P, doi:10.1002/zamm.19270070107 ..
  3. Haas, Ruth; Orden, David; Rote, Günter; Santos, Francisco; Servatius, Brigitte; Servatius, Herman; Souvaine, Diane; Streinu, Ileana (2005), «Planar minimally rigid graphs and pseudo-triangulations», Computational Geometry Theory and Applications 31 (1–2): 31-61, doi:10.1016/j.comgeo.2004.07.003 ..
  4. Lee, Audrey; Streinu, Ileana (2008), «Pebble game algorithms and sparse graphs», Discrete Mathematics 308 (8): 1425-1437, doi:10.1016/j.disc.2007.07.104 ..
  5. Streinu, I.; Theran, L. (2009), «Sparse hypergraphs and pebble game algorithms», European Journal of Combinatorics 30 (8): 1944-1964, doi:10.1016/j.ejc.2008.12.018 ..
  6. Daescu, O.; Kurdia, A. (2009), «Towards an optimal algorithm for recognizing Laman graphs», Proc. 42nd Hawaii International Conference on System Sciences (HICSS '09), IEEE, pp. 1-10, doi:10.1109/HICSS.2009.470 ..
  7. Rollin, Jonathan; Schlipf, Lena; Schulz, André (2019), «Recognizing planar Laman graphs», en Bender, Michael A.; Svensson, Ola; Herman, eds., 27th Annual European Symposium on Algorithms (ESA 2019), Leibniz International Proceedings in Informatics (LIPIcs) 144, Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, pp. 79:1-79:12, ISBN 978-3-95977-124-5, doi:10.4230/LIPIcs.ESA.2019.79 .
  8. Henneberg, L. (1911), Die graphische Statik der starren Systeme, Leipzig .