Számítástudomány epizód tartalma:
Itt mindent megtudhatsz arról, hogyan lehet egy gráfról eldönteni, hogy síkbarajzolható-e vagy sem. Kuratowski-tétel, Kuratowski-gráfok, a síkbarajzolhatóság szükséges feltételei. Feladatok Kuratowski-gráfokkal. Feladatok a síkbarajzolhatóság eldöntéséről.
Egyszerű gráfok síkbarajzolhatóságnak szükséges feltételei:
ha minden kör hossza legalább k:
Van itt ez a gráf. Döntsük el, hogy síkbarajzolható-e. Ha igen, rajzoljuk síkba.
Nézzük, hátha van benne K5.
K5-ben minden csúcs negyedfokú. Vagyis F nem illik a képbe.
Az eredeti gráf tartalmaz egy K5-tel topologikusan izomorf részgráfot.
Így aztán nem síkbarajzolható.
Van itt aztán ez a másik gráf. Döntsük el, hogy síkbarajzolható-e. Ha igen, rajzoljuk síkba.
Úgy tűnik hiába fáradoztunk…
Maradt bent egymást keresztező él.
És bármelyiket rakjuk is ki, akkor kint fog gondot okozni.
Így aztán jó lenne találnunk a gráfban K5-öt vagy K3,3-at.
K5-re azért ne nagyon számítsunk, mert nem sok negyedfokú csúcs van.
És egy dolgot nagyon jegyezzünk meg.
K3,3 valójában egy hatszög három átlóval.
Hát persze, hogy akkor ez a részgráf kell…
Ez topologikusan izomorf K3,3-mal, így aztán az eredeti gráf nem síkbarajzolható.
Most lássuk, mi a helyzet ezzel. Legalább hány élt kell törölnünk ebből a gráfból, hogy a megmaradt gráf síkbarajzolható legyen?
Ez egy páros gráf, így minden kör hossza legalább 4.
Lássuk, milyen kritérium lenne jó ide.
A jelek szerint két élt egészen biztosan törölnünk kell.
És valószínűleg nem ezeket az ártatlan kis éleket…
Hanem ezeket a brutális éleket, akik keresztülgázolnak mindenkin.
A megmaradt gráfra már teljesül ez a kritérium.
Nagy kár, hogy ez csak egy szükséges feltétel.
Vagyis hiába teljesül, az még nem bizonyítja a síkbarajzolhatóságot.
Ha be akarjuk bizonyítani, hogy a megmaradt gráf síkbarajzolható, akkor nincs mese, síkba kell rajzolni.
Bárcsak mindennel így lenne szerencsénk…