Ha szívesen korrepetálnál, hozd létre magántanár profilodat itt.
Ha diák vagy és korrepetálásra van szükséged, akkor regisztrálj be és írd meg itt, hogy milyen tantárgyban!
Gráfelmélet - síkbarajzolhatóság?
thementalist-hungary2350
kérdése
476
Sziasztok!
Tudnátok segíteni, hogy az alábbi gráf síkbarajzolható-e? Sehol sem tudom "belelátni" sem a K3,3-at sem a K5-öt?
Jelenleg 1 felhasználó nézi ezt a kérdést.
gráf, síkbarajzolhatóság, gráfelmélet
0
Felsőoktatás / Matematika
Válaszok
4
bongolo{ }
megoldása
Ez a részgráf egy K₅:
1
Rantnad:
Ez nem K5.
6 éve0
bongolo:
Miért nem? Én annak látom...
6 éve0
bongolo:
Minden csúcs össze van kötve a többi 4-gyel.
6 éve0
bongolo:
Ami cúcsokat félig letöröltam, azokat kell az izomorfiában elhagyni.
6 éve0
Rantnad:
Először azt hittem, hogy a megmaradt csúcsokat kell nézni, azok nem alkotnak K5-öt. Így viszont nem tudom, hogy hogyan kell az ábrát értelmezni.
6 éve0
bongolo:
A megmaradt csúcsokat kell nézni. A félig törölt csúcsok nem maradtak meg.
6 éve0
bongolo:
Azok törölve vannak, csak bennhagytam egy részüket, hogy jobban össze lehessen hasonlítani az eredetivel.
6 éve0
bongolo:
De persze ha az összes csúcsot nézed, akkor is izomorf K₅-tel.
6 éve0
Rantnad:
Tehát, ha jól értem, akkor a megmaradt 5 csúcs alkot egy K5-öt. Ha viszont így gondolod, akkor alapjáraton egy síkbarajzolt gráfot kapunk, ami semmi szín alatt nem lehet K5. Nem kekeckedni akarok, csak szeretném megérteni, mert akkor (ezek szerint) valamit rosszul tudok/tudtam.
6 éve0
Rantnad:
A színezésnél pedig kikötöttem, hogy a 2-fokú csúcsokat vegyük ki, mert csak azok tudják elrontani a színezést (illetve ha a csúcs helyére egy komplett gráfot rakunk, akkor az is, de itt nincs olyan).
6 éve0
bongolo:
Ami fentebb van, az egy K5, és nem síkbarakzolt, mert keresztezik egymást az élei. Ezt nem én gondolom, hogy K5, hanem ez az. Ha gondolod, kicsit húzgáld odébb a csúcsait és egyenesítsd ki az éleit, megkapod az ötágú csillagot.
6 éve0
bongolo:
A színezés magyarázatához csinálok egy újabb választ lentebb, ahhoz lehet csak képet mellékelni...
6 éve0
Rantnad{ }
válasza
Első körben töröljük ki a 2 fokszámú csúcsot, mivel az nem befolyásolja a síkbarajzolhatóságot, de a részgráfokat "elrejtheti".
Belátni úgy tudod a legegyszerűbben, hogy kiszínezed a csúcsokat; ha ez a gráf kiszínezhető legfeljebb 4 színnel, akkor K₅ nem lehet benne, mivel a K₅ kromatikus száma 5 (megnéztem, és 3-mal színezhető).
A K3;3 már egy kicsit nehezebb, de lévén, hogy nincs benne túl sok csúcs, könnyen észrevehető, ha van benne.
1
bongolo:
Szerintem a bennmaradó csúcsok miatt tudod 3-mal szinezni. Van benne K₅-tel izomorf részgrág.
6 éve0
bongolo:
Pl. amit fentebb megadtam, az a részgráf izomorf K₅-tel, de szerintem van benne egy másik is még.
6 éve0
bongolo:
Ha visszaraksz a K₅ részgráf éleibe csúcsokat, akkor már kevesebb színnel is színezhető lesz, tehát a teljes gráf kromatikus száma nem jó detektor.
6 éve0
bongolo{ }
válasza
Színezéshez infó:
Az eredeti tényleg színezhető 3 színnel, pl. úgy, ahogy az első ábra mutatja.
Viszont nem csak 2-élű csúcsokat távolítunk el, amikor a részgráfot csináljuk, hanem éleket is, éz az élek eltávolítása után 2-élűek lesznek korábban többélű csúcsok, ami kétélűeket szintén eltávolítjuk.
(Valójában nem kell eltávolítani, mert akkor is topologikusan izomorf ha ott marad, de ez részletkérdés.)
Szóval eltávolítás után, hogy csak 5 csúcs maradjon, az eredeti színek úgy alakulnak, ahogy a második ábra mutatja. A két sárga egymás mellé kerül, tehát nem színezhető 3 színnel annak ellenére, hogy a bővebb gráf színezhető volt.
Az eredeti gráf kromatikus száma tehát nem mérvadó annak eldöntésénél, hogy van-e benne K₅ részgráf.
Módosítva: 6 éve
1
Még nem érkezett komment!
bongolo{ }
válasza
Csináltam még néhány rajzot, hogy jobban látszódjon a K₅.
Az első ugyanaz a durva rajz, amit az első válaszomban adtam. Ez a részgráf rajz úgy keletkezett, hogy letöröltem az eredeti gráfból néhány élet, aztán kidobtam néhány csúcsot is. A kidobott csúcsokat úgy jelöltem, hogy a csúcs-gombócoknak a felét letöröltem.
A második rajzban teljesen kihagytam a kidobott csúcsokat, és az oda menő éleket kicsit meggörbítettem, hogy látszódjon még rajtuk, mik voltak eredetileg, de az is jobban látszódjon, hogy honnan hová mennek. Ennél a rajznál könnyebb összeszámolni, hogy minden csúcs fokszáma 4 és két csúcs között nem megy 1-nél több él, vagyis ez tényleg K₅.
A harmadik rajznál a fenti középső csúcsot picit feljebb vittem, az eddigi görbe éleket pedig teljesen kiegyenesítettem. Ez már felismerhetően egy K₅ ábra.
-------
Hogyan találtam ezt a részgráfot? Leírom, közben figyeld az eredeti gráfot meg a mostani első képet is, ahogy olvasod:
A K₅-ben mind az 5 csúcs fokszáma 4. Vagyis amik kisebb fokszámúak, azok a csúcsok biztos nincsenek benne egy K₅ részgráfban. Ezzel 3 csúcs kiesett. Nem szabad azért kidobni őket, mert mit kezdesz akkor az éleikkel, az élekre szükség van még. (Az egy szem 2-es fokszámút ki lehet dobni és a két élet egyesíteni...)
Aztán kiválasztottam 5 csúcsot a maradék 8-ból. Az a gyanúm, ennél a gráfnál szinte mindegy, melyik 5-öt választjuk ki, valószínű mindegyik egy-egy K₅. Amiket választottam, azok úgy adták magukat, "látszott" rajtuk, hogy valószínű jók lesznek.
Aztán megnéztem, melyik csúcsból hány él megy közvetlenül egy másikba az 5 közül. Egyedül a fenti középsőből megy 4, azzal már nem kell foglalkozni. Az alsó kettőből 3-3 él megy, mindkettőhöz kell még 1-1-egy találni, amik a maradék csúcshoz mennek (nem ugyanahhoz...) A bal alsóból 1 köztes csúcson át megy élsorozat a jobb oldaliba, a jobb alsóból viszont már 3 közbelső csúcs is van, hogy eljussunk a bal oldali fentibe.
A fenti két szélsőből eredetileg 2-2 él ment az 5-be, most már 3-3, még egyet kell találni, ami őket kettejüket összeköti. Ez egyszerűen megvan, egyetlen egy köztes csúcs van csak az élsorozatban.
Kész.
1
thementalist-hungary2350:
Nagyon köszönöm mindkettőtöknek!
6 éve0