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

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…

Egy lépésre vagy attól, hogy a matek melléd álljon és ne eléd.
  • Otthonról elérhető és olcsóbb, mint egy magántanár és akkor használom, amikor akarom.

    Milán, 19
  • Nem találsz külön tanárt? Ne is keress! Irány a mateking!!!!

    Bori, 19
  • Olyan weboldal, ami még egy vak lovat is megtanítana integrálni.

    Petra, 26
  • A mateking miatt sikerült az érettségi és az összes egyetemi matekos tárgyam.

    Míra, 21
BelépekvagyRegisztrálok Back arrow Ugrás az
összeshez