Diszkrét matematika epizód tartalma:

Szuper-érthetően megnézheted, hogyan lehet rájönni, hogy van-e egy gráfban Hamilton kör, és hogyan oldunk meg Hamilton körrel kapcsolatos feladatokat a szükséges feltétel és a két elégséges feltétel, a Dirac-tétel és az Ore-tétel segítségével. Példák Hamilton körre, Hamilton körös feladatok.

A képsor tartalma

És most pedig itt jön néhány gráf. Derítsük ki, hogy van-e bennük Hamilton kör. Ha nincs, akkor minimum hány újabb élt kell hozzávennünk ahhoz, hogy legyen?

Ezek a pontok eléggé gyanúsan viselkednek.

Nélkülük a gráf három részre esik szét.

A gráf nem teljesíti a szükséges feltételt, így aztán nincs benne Hamilton kör.

Húzzunk be egy új élt.

És aztán nézegessük egy kicsit a gráfot…

Így már van.

Egy új élt kell tehát hozzávenni az eredeti gráfhoz, hogy legyen benne Hamilton kör.

Nézzük, mi van ezzel:

Megint vannak gyanúsan viselkedő pontok.

Két pont elhagyásával a gráf három komponensre esett szét, így nincs benne Hamilton kör.

Nézzük, hány élt kell behúzni ahhoz, hogy legyen Hamilton kör.

Egyet…

Minimum hány élt kell behúznunk ebben a gráfban, hogy legyen benne Hamilton kör?

A gráf pillanatnyilag nem rendelkezik Hamilton körrel.

Nézzük, így már van-e…

Hát, ezzel a résszel még vannak gondok.

Mindez tudományosan is kimutatható.

Két pontot elhagyva a gráf négy komponensre esik szét, úgyhogy igencsak nem teljesül a szükséges feltétel.

Kénytelenek vagyunk behúzni még egy élt.

Valahol itt belül érdemes.

Na, most már csak jó lesz…

És most sem…

Persze az is lehet, hogy nem voltunk elég okosak…

Nézzük meg, mi van, ha ezt az élt…

inkább ide húzzuk be.

A megoldás tehát:

Sajnos nem voltunk elég okosak és 2 élt kell hozzávenni a gráfhoz.

Végül itt jön egy remek kis történet arról a 100 csúcsú egyszerű gráfról, amiben két szomszédos csúcs foka 49, az összes többi csúcs foka pedig legalább 50. Bizonyítsuk be, hogy van a gráfban Hamilton út.

Ha valahonnan ismerősnek tűnik a történet, az nem csak a véletlen műve.

Korábban már megoldottuk úgy, hogy Vi és Vj nem szomszédos csúcsok.

Most pedig megoldjuk úgy, hogy szomszédosak.

Így nehezebb…

Ha minden csúcs foka legalább 50 lenne, akkor a Dirac tétel miatt lenne Hamilton kör a gráfban.

Ennek érdekében vegyünk hozzá a gráfhoz egy Vi-ből és egy Vj-ből induló élt.

A Vi-ből induló extra él vezessen egy olyan X csúcsba, ami Vi-nek nem szomszédja, de Vj-nek igen.

A Vj-ből induló extra él pedig egy olyan Y csúcsba, ami eredetileg Vj-nek nem szomszédja, de Vi-nek igen.

Az extra élek behúzásával minden csúcs foka legalább 50, vagyis a Dirac tétel miatt van a gráfban Hamilton kör.

Hogyha a Hamilton kör legfeljebb egy extra élt tartalmaz, akkor nincsen semmi baj.

A két extra él elhagyásával ugyanis a Hamilton körnek legfeljebb egy élét hagyjuk el.

Tehát van Hamilton út.

De ha a Hamilton kör mindkét extra élt tartalmazza,

akkor nagy baj van.

A két extra él elhagyásával ugyanis a Hamilton kör két különálló darabra esik szét.

Az egyik darabja Vi és Vj között vezet, a másik darabja pedig X és Y között.

Ha ehhez a két különálló darabhoz hozzá vesszük a Vj-ből X-be vezető élt, akkor Hamilton utat kapunk.

De sajnos van itt még egy kis gubanc.

Előfordulhat, hogy nincsen a gráfban olyan X csúcs, ami Vi-nek nem szomszédja, de Vj-nek igen.

Ez úgy lehetséges, ha minden X csúcs vagy Vi-nek és Vj-nek egyszerre szomszédja… vagy pedig egyiknek sem.

És ha nincs ilyen X csúcs, akkor nem működik az a bizonyítás, amit az előbb csináltunk.

Ebben az esetben ki kell találni valami mást.

Válasszunk egy olyan X csúcsot, ami nem szomszédja sem Vi-nek, sem Vj-enk…

…és kössük össze velük.

Így most minden csúcs fokszáma legalább 50, vagyis a Dirac tétel miatt van Hamilton kör.

Ha a Hamilton kör legfeljebb egy extra élt tartalmaz, akkor az eredeti gráfban van Hamilton út.

De az is lehet, hogy mindkét extra él benne van a Hamilton körben.

Ebben az esetben viszont a Vi és Vj közti él biztosan nem.

Ez később még fontos lesz.

Az extra élek elhagyásával sajnos X kiesik a Hamilton körből.

És így a Hamilton útból is.

Úgy tudjuk visszaszerezni az elveszett X-et, hogy választunk egy tetszőleges Y csúcsot, ami X-nek szomszédja…

És itt megszakítjuk a Hamilton utat.

A Hamilton út Y-ba vezető egyik élét töröljük és helyette hozzávesszük az X-be vezető élt.

Végül a Vi és Vj közti élt bevesszük a Hamilton útba, és ezzel kész is.

 

Hamilton körrel kapcsolatos feladatok

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

Szuper-érthetően megnézheted, hogyan lehet rájönni, hogy van-e egy gráfban Hamilton kör, és hogyan oldunk meg Hamilton körrel kapcsolatos feladatokat a szükséges feltétel és a két elégséges feltétel, a Dirac-tétel és az Ore-tétel segítségével. Példák Hamilton körre, Hamilton körös feladatok.

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