Lamanov gróf

A Laman-gráf a ritka gráfok családjából származó gráf, amely egy síkon lévő szegmensek és csuklópántok minimális merev rendszereit Formálisan a csúcsokkal rendelkező Laman-gráf egy olyan gráf , amely egyrészt a gráf minden egyes részgráfjához, amely csúcsokat tartalmaz, legfeljebb élekkel rendelkezik, másrészt magának a gráfnak is pontosan vannak élei. $n$ $G$ $k$ $n$ $k$ $2k-3$ $G$ $2n-3$

Nevét Gerard Lamanról , az Amszterdami Egyetem professzoráról kapta , aki 1970 -ben használta őket lapos merev szerkezetek leírására [1] .

Merevség

A Lámán-gráfok a merevségelméletben a következőképpen jönnek létre: ha egy Laman-gráf csúcsait az euklideszi síkon úgy helyezzük el, hogy azok általános helyzetben legyenek , és a csúcsokat úgy mozgatjuk, hogy az összes él hossza változatlan maradjon, akkor ez a mozgás szükségszerűen euklideszi izometria lesz. Ráadásul minden ezzel a tulajdonsággal rendelkező minimális gráf szükségszerűen Laman-gráf. Intuitív szempontból jól látható, hogy a gráf minden éle eggyel csökkenti a neki megfelelő csuklórúd rendszer szabadsági fokát . Ezért egy Laman-gráfban 2 n − 3 él egy n csúcsból álló rendszer 2 n szabadságfokát háromra csökkenti, ami a sík izometrikus transzformációjának felel meg. Egy gráf ebben az értelemben akkor és csak akkor merev, ha tartalmaz egy Lámán részgráfot, amely a gráf összes csúcsát tartalmazza. Így a Laman-gráfok minimális merev gráfok, és a kétdimenziós merevségi matroidok alapját képezik .

Adott n pont a síkban, az elrendezésükben 2n szabadságfok van (minden pontnak két független koordinátája van), de egy merev gráfnak csak három szabadságfoka van (egy pont meghatározása és e pont körüli forgása). Intuitív módon világos, hogy egy rögzített hosszúságú él hozzáadása a gráfhoz eggyel csökkenti a szabadságfokát, így a Laman-gráf 2n − 3 éle a kezdeti elrendezés 2n szabadságfokát egy merev három szabadságfokra csökkenti. grafikon. Azonban nem minden 2n − 3 élű gráf merev. A Laman-gráf definíciójában szereplő feltétel, hogy egyik részgráf sem tartalmaz túl sok élt, biztosítja, hogy minden él valóban hozzájáruljon a szabadsági fok általános csökkenéséhez, és ne részese legyen egy olyan részgráfnak, amely a többi éle miatt már merev.

Síkság

A Lámán-gráfok az pszeudotrianguláció fogalmához is kapcsolódnak . Ismeretes, hogy minden pszeudo-háromszögelés Laman-gráf, és fordítva, minden síkbeli Laman-gráf megvalósítható pszeudo-háromszögelésként. [2] Azonban szem előtt kell tartani, hogy vannak nem síkbeli Laman-gráfok, például egy teljes kétrészes gráf . $K_{{3,3}}$

Sparity

Shteinu és Teran [3] a gráfot -sparse-ként definiálja, ha bármely nem üres részgráf csúcsokkal rendelkezik , és -dense-ként, ha -ritka és pontosan élei vannak. Így ebben a jelölésben a Laman-gráfok pontosan (2,3)-sűrűségű gráfok, a Laman-gráfok részgráfjai pedig pontosan (2,3)-ritka gráfok. Ugyanez a jelölés használható a ritka gráfok más fontos családjainak leírására is , beleértve a fákat , az álerdőket és a korlátos fagráfokat . [3] $(k,l)$ $n$ $kn-l$ $(k,l)$ $(k,l)$ $kn-l$

Hennenberg konstrukciója

Lebrecht Henneberg jóval Laman munkája előtt leírta a kétdimenziós minimális merev gráfokat (vagyis a Laman-gráfokat) különféle módokon [4] . Hennenberg megmutatta, hogy a két vagy több csúcsú minimális merev gráfok pontosan azok a gráfok, amelyeket egyetlen élről indulva kétféle művelettel kaphatunk:

Egy új csúcs kerül hozzáadásra a két meglévő csúcshoz csatlakozó élekkel együtt.
Az él felosztásra kerül, és egy új élt adunk hozzá, összekötve az újonnan megjelenő csúcsot a meglévővel.

Az ilyen műveletek sorozatát, amely egy adott gráfot alkot, Hennenberg-konstrukciónak nevezzük . Például egy teljes kétrészes gráf összeállítható úgy, hogy először háromszor alkalmazzuk az első műveletet háromszögek megalkotásához, majd két második típusú műveletet alkalmazunk a háromszög két oldalának felosztására. $K_{{3,3}}$

Irodalom

G. Laman. A gráfokról és a sík vázszerkezetek merevségéről // 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. Síkbeli, minimálisan merev gráfok és pszeudo-háromszögelések // Számítógépes geometria elmélete és alkalmazásai. - 2005. - T. 31 , sz. 1-2 . - S. 31-61 . - doi : 10.1016/j.comgeo.2004.07.003 .
I. Streinu, L. Theran. Ritka hipergráfok és kavicsos játékalgoritmusok // European Journal of Combinatorics . - 2009. - T. 30 , sz. 8 . - S. 1944-1964 . - doi : 10.1016/j.ejc.2008.12.018 . — arXiv : math/0703921 .
L. Henneberg. Die graphische Statik der starren Systeme . - Lipcse: BG Teubner, 1911. - 755 p.