Laman-gráf

A matematika, azon belül a gráfelmélet területén a Laman-gráfok olyan ritka gráfcsaládot alkotnak, melyek síkbeli rúd-csuklók alkotta minimális merev rendszereket írnak le. Formálisan egy Laman-gráf olyan n csúcsú gráf, melyben tetszőleges k-ra minden k csúcsú részgráf legfeljebb 2k − 3 éllel rendelkezik és a teljes gráfnak is pontosan 2n − 3 éle van. A Laman-gráfok nevüket az Amszterdami Egyetemen oktató Gerard Lamanról kapták, aki 1970-ben a merev síkszerkezetek jellemzésére használta fel őket.^[1]

Merevség

A 20. század elejétől ismert, hogy rúdszerkezetek statikai tulajdonságai gráfelméleti módszerekkel vizsgálhatók. Ebben a megközelítésben a rúdszerkezet modellje egy gráf, valamint annak előírt élhosszakkal történő beágyazása a térbe. A merevség alapkérdése, hogy adott sík- vagy térbeli rúdszerkezetnek létezik-e folytonos vagy infinitezimális deformációja. Globálisan merev-e, azaz egybevágó-e a rúdszerkezet minden beágyazása? Egy gráf generikusan merev, ha van infinitezimálisan merev beágyazása. A statikai alkalmazásokon túlmenően a gráfelméleti merevség számos kutatási területen hasznosnak bizonyult: járműflották elosztott irányítása, fehérjemolekulák szerkezeti flexibilitása, csukló-rúd szerkezetek mozgatása.

A globális merevség 2 dimenzióban generikus tulajdonság, azaz csak a gráftól függ.^[2]

A Laman-gráfok is a merevségelméletben játszanak szerepet: egy az euklideszi síkon általános helyzetű csúcsokkal rendelkező Laman-gráf esetén az egybevágósági transzformációkon kívül nem lehet az összes pontot egyszerre elmozgatni a gráf élhosszúságainak megtartásával. Egy gráf ebben az értelemben pontosan akkor merev, ha van az összes csúcsra ráfeszülő Laman-részgráfja. Tehát a Laman-gráfok pontosan a minimálisan merev gráfok, melyek a kétdimenziós merevségi matroidok bázisát alkotják.

Ha n pont adott a síkban, elhelyezésüknek szabadságfoka 2n (mivel minden pontnak két független koordinátája van), egy merev gráfnak azonban csak három a szabadságfoka (egy csúcs pozícíója és a megmaradó gráf elforgatásának mértéke azon csúcs körül). Intuitívan, egy gráfhoz fix hosszúságú élt adva szabadságfoka eggyel csökken, ezért egy Laman-gráf 2n − 3 éle az eredeti pontelhelyezést 2n szabadságfokkal csökkenti, egy merev gráf megfelelő értékére. Azonban nem minden, 2n − 3 élű gráf merev; a Laman-gráf definíciójában szerepel a kitétel, hogy egyetlen részgráf sem tartalmazhat túl sok élt, ami biztosítja azt, hogy minden egyes él hozzájárul az egész rendszer szabadságfokainak csökkenéséhez, és nem pazaroljuk el egy olyan részgráfban, ami más éleiből kifolyólag már egyébként is merev.

Síkbarajzolhatóság

Egy gráf hegyes pszeudoháromszögelése a gráf olyan egyenes élekkel történő síkba rajzolása, melyben a külső tartomány konvex, és minden korlátos tartomány pszeudoháromszög, azaz olyan sokszög, melynek csak három konvex csúcsa van, és a csúcsokból kiinduló élek 180 foknál kisebb szöget zárnak be. A hegyes pszeudoháromszögeléssel lerajzolható gráfok éppen a síkbarajzolható Laman-gráfok.^[3] A Laman-gráfoknak azonban léteznek nem pszeudoháromszögelésként megjelenő síkba rajzolásaik is, továbbá nem minden Laman-gráf síkba rajzolható, amire a legkisebb példa a K_3,3 három ház–három kút-gráf.

Ritkaság

(Lee & Streinu 2008) és (Streinu & Theran 2009) definíciója szerint egy gráf $(k,l)$ -ritka, ha minden nem üres részgráfjának $n$ csúcsa között legfeljebb $kn-l$ él húzódik, egy $(k,l)$ -éles gráf (tight graph)^[4] pedig $(k,l)$ -ritka és pontosan $kn-l$ éllel rendelkezik. Ebben a jelölésben a Laman-gráfoka (2,3)-éles gráfokkal egyeznek meg, részgráfjaik pedig éppen a (2,3)-ritka gráfok. Ugyanez a jelölés alkalmas más ritka gráfcsaládok jellemzésére is, köztük a fák, azaz (1,1)-éles gráfok, pszeudoerdők, azaz (1,0)-ritka gráfok és egyéb, korlátos arboricitású gráfokéra is.^[5]^[6]

Ezt a jellemzést tovább gondolva az $n$ csúcsú Laman-gráfok $O (n 2)$ időben felismerhetők egy „kavicsjáték” (pebble game) segítségével; a játék egy $n$ csúcsú élmentes gráffal kezdődik, ahol minden csúcsra két kavicsot helyezünk, majd a következő két lépéslehetőség alkotta sorozattal hozzuk létre a gráf éleit:

Húzzunk be egy irányított élt két olyan csúcs között, melyek mindegyikén két kavics van, és az él kiinduló csúcsából vegyünk el egy kavicsot.
Ha a legfeljebb egy kaviccsal rendelkező $u$ csúcsból él mutat a legalább egy kaviccsal rendelkező $v$ csúcsba, helyezzünk át egy kavicsot $v$ -ből $u$ -ba és fordítsuk meg az él irányát.

Ha ezekkel a műveletekkel létre lehet hozni adott gráfhoz egy irányítást, akkor a létrejövő gráf szükségképpen (2,3)-ritka, és vice versa. Ennél gyorsabb, $O(n^{3/2}{\sqrt {\log n}})$ idejű algoritmus is létezik, ami annak a tesztelésén alapul, hogy adott gráf egy élének megduplázása (2,2)-éles multigráfot hoz-e létre (vagy ezzel ekvivalens módon, felbontható-e két éldiszjunkt feszítőfára) és ezt a dekompozíciót használja fel annak vizsgálatára hogy adott gráf Laman-gráf-e.^[7]

A Henneberg-féle konstrukció

Évtizedekkel Laman munkássága előtt Lebrecht Henneberg német matematikus más megközelítésben jellemezte a kétdimenziós minimálisan merev gráfokat (azaz a Laman-gráfokat).^[8] Henneberg megmutatta, hogy a két vagy több csúcsú minimálisan merev gráfok pontosan azok a gráfok, melyek előállíthatók egyetlen élből kiindulva a következő műveletek alkalmazásával:

A gráfhoz új csúcs hozzáadása és két, korábban létező csúccsal való összekötése.
Egy él felosztása és az újonnan létrejött csúcs összekötése egy harmadik, korábban létező csúccsal.

Adott gráf esetében a gráfot létrehozó, fenti művetekből álló sorozatot a gráf Henneberg-konstrukciójának nevezik. Például a K_3,3 teljes páros gráf előállítható úgy, hogy az első művelettel létrehozunk egy háromszöget, majd a második művelettel a háromszög minden élét felosztjuk és összekötjük a háromszög szemben lévő csúcsával.

Fordítás

Ez a szócikk részben vagy egészben a Laman graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

↑ Laman, G. (1970), "On graphs and the rigidity of plane skeletal structures", J. Engineering Mathematics 4 (4): 331–340, DOI 10.1007/BF01534980.
↑ http://real.mtak.hu/249/1/37547_ZJ1.pdf
↑ Haas, Ruth; Orden, David & Rote, Günter et al. (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.
↑ az „éles” szó itt a matematikai zsargonban használt éles, tovább már nem javítható eredményre utal
↑ 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.
↑ 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.
↑ 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.
↑ Henneberg, L. (1911), Die graphische Statik der starren Systeme, Leipzig

[1] Laman, G. (1970), "On graphs and the rigidity of plane skeletal structures", J. Engineering Mathematics 4 (4): 331–340, DOI 10.1007/BF01534980.

[2] ttp://real.mtak.hu/249/1/37547_ZJ1.pdf

[3] Haas, Ruth; Orden, David & Rote, Günter et al. (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] z „éles” szó itt a matematikai zsargonban használt éles, tovább már nem javítható eredményre utal

[5] 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.

[6] 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.

[7] 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.

[8] Henneberg, L. (1911), Die graphische Statik der starren Systeme, Leipzig

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]