Diszkrét matematika 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.

A képsor tartalma

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…

 

Gráfok síkbarajzolhatóságának vizsgálata

07
hang
Hopsz, úgy tűnik nem vagy belépve, pedig itt olyan érdekes dolgokat találsz, mint például:

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.

Végül is miért ne néznél meg
még egy epizódot?
Ugrás az
összeshez