Grev Lamanov

En Laman-graf er en graf fra familien af sparsomme grafer , der beskriver minimale stive systemer af segmenter og hængsler på et plan. Formelt set er en Laman-graf med hjørner en sådan graf , at for det første, for hver undergraf af grafen, der indeholder hjørner, højst har kanter, og for det andet har selve grafen nøjagtigt kanter. $n$ $G$ $k$ $n$ $k$ $2k-3$ $G$ $2n-3$

De er opkaldt efter Gerard Laman , professor ved universitetet i Amsterdam , som brugte dem i 1970 til at beskrive flade stive strukturer [1] .

Rigiditet

Laman-grafer opstår i teorien om stivhed som følger: Hvis du placerer hjørnerne af en Laman-graf på det euklidiske plan, så de er i generel position og flytter hjørnerne, så længderne af alle kanter forbliver uændrede, så bevægelse vil nødvendigvis være en euklidisk isometri. Desuden er enhver minimal graf med denne egenskab nødvendigvis en Laman-graf. Fra et intuitivt synspunkt er det klart, at hver kant af grafen reducerer frihedsgraden af det hængselstangsystem, der svarer til det, med én. Derfor reducerer 2 n − 3 kanter i en Laman-graf de 2 n frihedsgrader for et system med n hjørner til tre, hvilket svarer til en isometrisk transformation af planet. En graf er stiv i denne forstand, hvis og kun hvis den indeholder en Laman-undergraf, der indeholder alle grafens hjørner. Således er Laman-grafer minimale stive grafer og danner grundlaget for todimensionelle stivhedsmatroider .

Givet n punkter i planet, er der 2n frihedsgrader i deres arrangement (hvert punkt har to uafhængige koordinater), men en stiv graf har kun tre frihedsgrader (placerer et punkt og roterer omkring det punkt). Det er intuitivt klart, at tilføjelse af en kant med fast længde til en graf reducerer frihedsgraden med én, således at 2n − 3 kanter af Laman-grafen reducerer de 2n frihedsgrader af det indledende arrangement til tre frihedsgrader for en stiv kurve. Imidlertid er ikke hver graf med 2n − 3 kanter stiv. Betingelsen i definitionen af en Laman-graf, at ingen undergraf indeholder for mange kanter, sikrer, at hver kant faktisk bidrager til det samlede fald i frihedsgraden og ikke er en del af en undergraf, der allerede er stiv på grund af dens andre kanter.

Planaritet

Laman-grafer er også relateret til begrebet pseudotriangulering . Det er kendt, at enhver pseudo-triangulering er en Laman-graf og omvendt, enhver plan Laman-graf kan realiseres som en pseudo-triangulering. [2] Det skal dog huskes, at der er ikke-planære Laman-grafer, for eksempel en komplet todelt graf . $K_{{3,3}}$

Sparsitet

Shteinu og Teran [3] definerer en graf som -sparsom, hvis en ikke-tom undergraf med hjørner har et maksimum af kanter, og -tæt, hvis den er -sparsom og har nøjagtige kanter. I denne notation er Laman-grafer således nøjagtigt (2,3)-tætte grafer, og undergrafer af Laman-grafer er nøjagtigt (2,3)-sparsomme grafer. Den samme notation kan bruges til at beskrive andre vigtige familier af sparsomme grafer , herunder træer , pseudoskove og grafer med afgrænsede træer . [3] $(k,l)$ $n$ $kn-l$ $(k,l)$ $(k,l)$ $kn-l$

Hennenbergs konstruktion

Længe før Lamans arbejde beskrev Lebrecht Henneberg todimensionelle minimale stive grafer (det vil sige Laman-grafer) på forskellige måder [4] . Hennenberg viste, at minimale stive grafer med to eller flere hjørner er præcis de grafer, der kan opnås ved at starte ved en enkelt kant ved hjælp af to slags operationer:

Et nyt toppunkt tilføjes sammen med kanter, der forbinder det med to eksisterende toppunkter.
Kanten opdeles, og en ny kant tilføjes, der forbinder det nyligt dukkede toppunkt med det eksisterende.

En sekvens af sådanne operationer, der danner en given graf, kaldes en Hennenberg-konstruktion . For eksempel kan en komplet todelt graf bygges ved først at anvende den første operation tre gange for at konstruere trekanter og derefter anvende to operationer af type to for at opdele trekantens to sider. $K_{{3,3}}$

Litteratur

G. Laman. Om grafer og stivheden af plane skeletstrukturer // J. Engineering Mathematics. - 1970. - T. 4 . - S. 331-340 . - doi : 10.1007/BF01534980 .
Ruth Haas, David Orden, Günter Rote, Francisco Santos, Brigitte Servatius, Herman Servatius, Diane Souvaine, Ileana Streinu, Walter Whiteley. Plane minimalt stive grafer og pseudo-trianguleringer // Computational Geometry Theory and Applications. - 2005. - T. 31 , no. 1-2 . - S. 31-61 . - doi : 10.1016/j.comgeo.2004.07.003 .
I. Streinu, L. Theran. Sparsomme hypergrafer og småstenspilsalgoritmer // European Journal of Combinatorics . - 2009. - T. 30 , no. 8 . - S. 1944-1964 . - doi : 10.1016/j.ejc.2008.12.018 . — arXiv : math/0703921 .
L. Henneberg. Den grafiske Statik der Starren Systeme . - Leipzig: BG Teubner, 1911. - 755 s.