Síkbarajzolható gráf

A Wikipédiából, a szabad enciklopédiából

Egy gráfot akkor nevezünk síkbarajzolhatónak, ha lerajzolható úgy a síkban, hogy az élei nem metszik egymást (metszési száma 0). Sztereografikus projekcióval igazolható, hogy egy gráf akkor és csak akkor síkbarajzolható, ha gömbre rajzolható. A Fáry-Wagner-tétel szerint egy síkba rajzolható egyszerű gráf úgy is síkba rajzolható, hogy élei egyenes szakaszok.

Kuratowski és Wagner tétele[szerkesztés | forrásszöveg szerkesztése]

K_5
K_{3,3}

Kuratowski tétele szerint egy véges gráf akkor és csak akkor síkbarajzolható, ha nem tartalmaz olyan részgráfot, amely topologikusan izomorf K_5-tel (az ötcsúcsú teljes gráffal) vagy K_{3,3}-mal (az ún. három ház–három kút gráffal).

Az ehhez közelálló Wagner tétele szerint egy véges gráf akkor és csak akkor síkbarajzolható, ha sem K_5 sem K_{3,3} nem minora.


Négyszín-tétel[szerkesztés | forrásszöveg szerkesztése]

A négyszín-sejtés először akkor fogalmazódott meg, amikor egy diák, Francis Guthrie észrevette, hogy bármilyen térképet is néz, annak tartományait (országokat, megyéket (tengerekkel, tavakkal együtt)) mindig ki tudja színezni legfeljebb négy színnel úgy, hogy a szomszédos tartományok eltérő színt kapnak. Nem sokkal ezután Arthur Cayley hivatalosan is felvetette a problémát a Royal Society-nak.

A négyszín-tétel szerint minden síkbarajzolható gráf színezhető legfeljebb négy színnel.

Euler-formula[szerkesztés | forrásszöveg szerkesztése]

Síkbarajzolható gráfokra igaz az Euler-formula:

Tétel: Egy összefüggő, síkbarajzolt gráf csúcsainak és tartományainak száma (beleértve a külső, nem korlátos tartományt is) 2-vel nagyobb az éleinek számánál.

Bizonyítás:

Először vegyük észre, hogy minden belső, korlátos tartományt a gráf egy köre határol. Ebből adódik, hogy egy síkba rajzolt fának csak egy tartománya van, ez a külső, nem korlátos tartomány. Tudjuk, hogy minden fának 1-gyel kevesebb éle van, mint ahány csúcsa. Egyszerű számolással adódik, hogy a fákra teljesül az Euler-formula. Most bebizonyítjuk az állítást a kört tartalmazó, összefüggő gráfokra is. Tekintsük a gráf egyik körének egy m-mel jelölt élét. Ez az él határa egy a körön belüli és egy a körön kívüli tartománynak. Az m él elhagyásával a két tartomány egyesül. Tehát az élek és a tartományok száma egyaránt 1-gyel csökken, míg a csúcsok száma nem változik. Így ha az új gráfra teljesül az Euler-formula, akkor az eredetire is. Az eljárást (egy körbeli él elhagyása) folytassuk addig, ameddig a gráfban nem marad kör. Ekkor a gráf egy feszítőfájához jutunk, amelyre teljesül a formula, tehát az eredeti gráfra is.

Nem összefüggő gráfokra[szerkesztés | forrásszöveg szerkesztése]

Az Euler-formula síkbarajzolható, egyszerű, k összefüggő komponensből álló gráfokra a következőképpen módosul: c+t=e+k+1, ahol c a csúcsok, t a tartományok, e az élek számát jelöli.

Bizonyítás:

Rajzoljuk le síkba a gráfot. Ekkor külön-külön mind a k komponensre teljesül az Euler-formula. Mivel minden csúcs és minden él pontosan egy komponenshez tartozik, c=\sum c_i és e=\sum e_i, ahol c_i és e_i az i-edik komponens csúcsainak, illetve éleinek száma. A „külső” tartományok azonban mindegyik komponensnél azonosak, ezért t=\sum t_i - (k-1). A komponensekre felírt Euler-formulából adódik az állítás.

Szükséges feltételek a síkbarajzolhatóságra[szerkesztés | forrásszöveg szerkesztése]

Ha G egyszerű, síkbarajzolható gráf és pontjainak száma legalább 3, akkor az előbbi jelölésekkel e\leq 3c-6.

Bizonyítás:

Az állítást elég összefüggő gráfokra bizonyítani. Rajzoljuk le G-t síkba. Mivel a gráf egyszerű, minden tartományát legalább 3 él határolja, ugyanakkor egy él legfeljebb két tartományt határolhat. Összegezzük minden tartományra az őket határoló élek számát. Az előbbiek miatt ez az érték legalább 3t, legfeljebb 2e. Tehát 3t\leq 2e, felhasználva az Euler-formulát, 3(e-c+2)\leq 2e. Ezt az egyenlőtlenséget átrendezve adódik, hogy e\leq 3c-6.


Ha G egyszerű, síkbarajzolható gráf, melynek minden köre legalább 4 hosszú és csúcsainak száma legalább 4, akkor az előbbi jelölésekkel e\leq 2c-4.

Bizonyítás:

Az állítás igazolása hasonló gondolatmenettel történhet, mint az előzőé, figyelembe véve, hogy most minden tartományt legalább 4 él határol. Ebből adódik, hogy 4t\leq 2e és az Euler-formula alkalmazásával, hogy e\leq 2c-4.

Duális gráf[szerkesztés | forrásszöveg szerkesztése]

Síkba rajzolható gráf és duálisa

Egy síkba rajzolható gráf duális gráfja alatt azt a gráfot értjük, amelynek csúcsai az eredeti gráf tartományai, és azok a csúcsok vannak összekötve, amik megfelelői szomszédosak voltak (ha több él mentén voltak szomszédosak, akkor többszörösen is). Síkbarajzolható gráf duálisa is síkbarajzolható gráf.