gráfico de lamán

En teoría de grafos , los gráficos de Laman son una familia de gráficos dispersos que describen los sistemas mínimamente rígidos de varillas y uniones en el plano. Formalmente, un gráfico de Laman es un gráfico en 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 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 continuo simultáneo de todos los puntos, aparte de las congruencias euclidianas , que preserve las longitudes de todos. los bordes del gráfico. Un gráfico es rígido en este sentido si y sólo 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 sólo 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 una arista de longitud fija a un gráfico reduce su número de grados de libertad en uno, por lo que las 2 n − 3 aristas en un gráfico de Laman reducen los 2 n grados de libertad de la ubicación inicial del punto 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 de Laman de que ningún subgrafo puede tener demasiadas aristas garantiza que cada arista 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 otras aristas.

Planaridad

Una pseudotriangulación puntiaguda es un dibujo plano de línea recta de un gráfico, con las propiedades de que la cara exterior es convexa, que cada cara acotada es un pseudotriángulo , un polígono con sólo tres vértices convexos, y que las aristas incidentes en cada vértice abarcan un Ángulo inferior a 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 -escaso 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 subgrafos de los gráficos de Laman son exactamente los gráficos (2,3) dispersos. La misma notación se puede utilizar para describir otras familias importantes de gráficos dispersos , incluidos árboles , pseudobosques y gráficos de arboricidad acotada . ^[4]^[5] $(k,\ell )$ $n$ $kn-\ell$ $(k,\ell )$ $(k,\ell )$ $kn-\ell$

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 cualesquiera 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 como máximo un guijarro a otro vértice $v$ con al menos un guijarro, mueva un guijarro de $v$ a $u$ e invierta la arista.

Si estas operaciones se pueden utilizar para construir una orientación del gráfico dado, entonces es necesariamente (2,3)-escaso, y viceversa. Sin embargo, son posibles algoritmos más rápidos, que se ejecutan en el tiempo , y se basan en probar si duplicar un borde del gráfico dado da como resultado un multigrafo ajustado a (2,2) (de manera equivalente, si se puede descomponer en dos árboles de expansión con bordes 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 utilizar para probar si un gráfico plano es un gráfico de Laman más rápidamente y en el tiempo . ^[7] $O(n^{3/2}{\sqrt {\log n}})$ $O(n\log ^{3}n)$

construcción henneberg

Antes del trabajo de Laman y Geiringer, Lebrecht Henneberg 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 sobre 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 dos tipos siguientes:

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.

Ver también

Teorema de Geiringer-Laman

Referencias

^ Laman, G. (1970), "Sobre gráficos y la rigidez de estructuras esqueléticas planas", J. Engineering Mathematics , 4 (4): 331–340, Bibcode :1970JEnMa...4..331L, doi :10.1007/ BF01534980, SEÑOR 0269535, S2CID 122631794.
^ 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.
^ Haas, Rut ; Orden, David; De memoria, Günter; Santos, Francisco ; Servacio, Brigitte ; Servacio, Herman; Souvaine, Diane ; Streinu, Ileana ; Whiteley, Walter (2005), "Pseudotriangulaciones y gráficos planos mínimamente rígidos", Teoría y aplicaciones de la geometría computacional , 31 (1–2): 31–61, arXiv : math/0307347 , doi :10.1016/j.comgeo.2004.07 .003, SEÑOR 2131802, S2CID 38637747.
^ Lee, Audrey; Streinu, Ileana (2008), "Algoritmos del juego Pebble y gráficos dispersos", Matemáticas discretas , 308 (8): 1425–1437, arXiv : math/0702129 , doi :10.1016/j.disc.2007.07.104, MR 2392060, S2CID 2826.
^ 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, S2CID 5477763.
^ Daescu, O.; Kurdia, A. (2009), "Hacia un algoritmo óptimo para reconocer gráficos de Laman", Proc. 42ª Conferencia Internacional de Hawaii sobre Ciencias de Sistemas (HICSS '09) , IEEE, págs. 1–10, arXiv : 0801.2404 , doi :10.1109/HICSS.2009.470.
^ Rollin, Jonathan; Schlipf, Lena; Schulz, André (2019), "Reconocimiento de gráficos planos de Laman", en Bender, Michael A.; Svensson, Ola; Herman, Grzegorz (eds.), 27.º Simposio europeo anual sobre algoritmos (ESA 2019) , Leibniz International Proceedings in Informatics (LIPIcs), vol. 144, Dagstuhl, Alemania: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, págs. 79:1–79:12, doi :10.4230/LIPIcs.ESA.2019.79, ISBN 978-3-95977-124-5
^ Henneberg, L. (1911), Die graphische Statik der starren Systeme , Leipzig{{citation}}: CS1 maint: location missing publisher (link)