Síkbarajzolható gráf

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 egyenes vonalakkal is síkba rajzolható.

Kuratowski és Wagner tétele

$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 öt csú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

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

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

Tétel: Egy összefüggő, síkba rajzolt 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

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

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

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, aminek 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.