Kuratowski-tétel

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

A Kuratowski-tétel a gráfelméletben egy gráf részgráfjainak tulajdonságai alapján fogalmaz meg szükséges és elégséges kritériumot arra, hogy a gráf síkbarajzolható legyen.

A tétel állítása[szerkesztés | forrásszöveg szerkesztése]

K5
K3,3

Kazimierz Kuratowski lengyel matematikus 1930-ban bizonyította az alábbi tételt[1]

TételKuratowski síkbarajzolhatósági tétele – Egy gráf akkor és csak akkor síkbarajzolható, ha nem tartalmaz felosztott K3,3-at vagy felosztott K5-öt.

Itt K3,3 a (3,3) párhoz tartozó teljes páros gráf (a három ház–három kút-gráf), K5 az ötcsúcspontú teljes gráf (a „teljes ötös”).

Nonplanar.png

Egy gráfról akkor mondjuk, hogy felosztott H, ha a gráf a H gráf éleinek pontokkal való felosztásával jön létre. Ezt úgy kell érteni, hogy egy élen beiktatunk 0 vagy több újabb csúcsot (például •——• élhez hozzáveszünk még két csúcsot: •—•—•—•).

Ugyanezen tétel ekvivalens módon átfogalmazott kritériuma, ha nem tartalmaz a K3,3-mal vagy K5-tel homeomorf részgráfot.

Például az ábrán látható gráf nem tartalmaz ugyan K5-öt és K3,3-at, de van olyan részgráfja, mely izomorf K3,3-mal, így biztosan nem síkbarajzolható. (Ha a kék utat úgy képzeljük, mint a K3,3 egy élének felosztását, akkor világos, hogy maga a gráf homeomorf K3,3-mal)

Bizonyítás[szerkesztés | forrásszöveg szerkesztése]

Szükséges fogalmak és tételek[szerkesztés | forrásszöveg szerkesztése]

A tétel igazolásához fel kell használnunk az Euler–Descartes-féle poliédertételt, azaz a nevezetes c + l = e + 2 azonosságot, ahol c a csúcsok száma, l a lapoké, és e az éleké. Ezen kívül szükségünk lesz az alábbi tételre:

Tétel – A G gráf 3-összefüggő akkor és csak akkor, ha előáll a teljes négyesből a következő műveletekkel:

  1. egy már létező élnek bevesszük egy párhuzamos példányát;
  2. vegyünk egy legalább negyedfokú z pontot; a z-be menő éleket osszuk két, legalább kételemű csoportra; a z pont helyett vegyünk egy éllel összekötött pontpárt, z1-et és z2-t; a z-be menő élek első csoportját helyettesítsük a z1-be menő élekkel, a második csoportját a z2-be menő élekkel.

Megjegyzés. A párhuzamos élek bevétele azért kell, mert különben nem minden egyszerű 3-összefüggő gráfot lehetne ezen a módon létrehozni.

Végül a következő lemmára:

Lemma – Ha egy gráfban nincs felosztott K5 és K3,3, akkor élösszehúzás után sem lesz benne.

Lényegi rész[szerkesztés | forrásszöveg szerkesztése]

TételTutte – Ha a G = (V,E) gráf 3-összefüggő, egyszerű, nem tartalmaz felosztott K3,3-at és K5-öt, akkor síkba ágyazható úgy, hogy minden élt egyenes szakasz jelöl, az éleknek csak a végpontja lehet közös, és az összes tartomány konvex (a külső tartomány kivételével).

Bizonyítás – Ha a gráfnak 4 pontja van, akkor a gráf a teljes négyes, ami síkba ágyazható a kívánt módon. Feltehetjük, hogy V mérete legalább 5.

A lemma miatt van x1 és x2, hogy az x1x2, élt összehúzva egy G1 összefüggő gráfot kapunk. Ez nem tartalmaz felosztott K3,3-at és K5-öt, ezért indukció miatt síkba rajzolható a kívánt módon.

Jelölje az összehúzott pontot x. G1 \ {x} 2-összefüggő, ezért G1 \ {x} minden tartományát a gráf egy köre határolja. Jelölje K azt a kört, amely x-et belsejében tartalmazza.

Állításx1 és x2 egyikének van olyan, a másiktól különböző szomszédja, amely nem szomszédja a másiknak.

Tegyük fel indirekt, hogy nem ez a helyzet. A 3-összefüggőség miatt van x1 és x2-nek három közös szomszédja: u,v,z. Ekkor az x1,x2,u,v,z pontok a K körrel együtt egy felosztott K5-öt adnak, ez ellentmondás.

Tehát az állítás szerint van például x1 -nek olyan szomszédja, ami nem szomszédos x2-vel. Nevezzük ezt a szomszédot u-nak. Innen elindulva K mentén mindkét irányban lesz egy első pont, ami szomszédjax2-nek. x2 legalább harmadfokú, ezért ez a két pont, s és t különböző.

Állításx1 minden szomszédja K-nak az st ívén van, mint u.

Különben, ha például a v pont a másik íven lenne, akkor x1,x2,u,v,s,t a K körrel együtt egy felosztott K3,3-at határozna meg.

Ezek szerint az x pont szétnyitható úgy, hogy a G gráfot a kívánt módon síkba ágyazzuk.

A bizonyítás befejezése[szerkesztés | forrásszöveg szerkesztése]

Tétel - Egy gráf síkbarajzolható akkor és csak akkor, ha nem tartalmaz felosztott K3,3-at és K5-öt.

Az Euler-formulával belátható, hogy K3,3 és K5 nem síkba rajzolható, mert a formulából sehogy sem jön ki az élek száma. Tehát ezek a gráfok nem síkba rajzolhatók, így az ilyeneket felosztva tartalmazó gráfok sem.

A másik irányt indirekt módon bizonyítjuk. Feltesszük, hogy van egy minimális ellenpélda, ami nem tartalmaz felosztott K3,3-at és K5-öt, mégsem rajzolható síkba. Belátjuk, hogy nincs ilyen ellenpélda.

Jelöljük ezt az ellenpéldát G-vel. Könnyen látható, hogy összefüggő és egyszerű.

Állítás - G 2-összefüggő. Ha t elvágó pont lenne, akkor lenne V-nek X és Y részhalmaza, amelyekre igazak a következők: metszetük t, egyesítésük V, mindkét halmaz legalább 2 pontú, t-t kivéve nincs él közöttük, és az X,Y halmazok által feszített részgráfok összefüggők. Mivel G minimális ellenpélda volt, azért ezek a részgráfok síkba rajzolhatók. Ha összeillesztjük őket t-nél, akkor G egy síkba rajzolását kapjuk, ami ellentmondás. Tehát G 2-összefüggő.

Állítás - G 3-összefüggő. Feltehető, hogy G-nek legalább 5 csúcsa van, mert a teljes 4-es síkba rajzolható, így a legfeljebb 4 pontú gráfok is.

Tegyük fel indirekt, hogy x,y elvágó pontpár.

Ekkor van V-nek X és Y részhalmaza, amelyekre igazak a következők: metszetük x,y, egyesítésük V, mindkét halmaz legalább 3 pontú, x,y-t kivéve nincs él közöttük, és az X,Y halmazok által feszített részgráfok összefüggők. Legyen GX az X által feszített gráf az e=xy éllel, és hasonlóan a GY az Y által feszített gráf az e=xy éllel.

G_X nem tartalmaz felosztott K3,3-at és K5-öt.

Különben az használná az új e élt, hiszen G-ben nincs felosztott K3,3 és K5. GY-ban azonban van út x és y között. Erre az útra cserélve az e élt az eredeti G gráfban is kapunk felosztott K3,3-at vagy K5-öt, ellentmondás.

Hasonlóan GY sem tartalmaz felosztott K3,3-at és K5-öt. Indukcióval GX és GY is síkbarajzolható. Ezeket összetéve az e él mentén a G síkba rajzolását kapjuk az e él esetleges hozzávételével.

3-összefüggő gráfokra a tétel következik Tutte fent említett tételéből.

Külső hivatkozások[szerkesztés | forrásszöveg szerkesztése]

Jegyzetek[szerkesztés | forrásszöveg szerkesztése]