Diszkrét matematika epizód tartalma:
Szuper-érthetően elmeséljük, hogy mi a Hamilton kör létezésének két legfontosabb elégséges feltétele, a Dirac-tétel és az Ore-tétel. Megnézzük, hogyan lehet rájönni, hogy van-e egy gráfban Hamilton kör, és hogyan tudjuk használni az elégséges feltételeket. Példák Hamilton körre, Hamilton körös feladatok.
Nézzük, milyen elégséges feltételek vannak a Hamilton kör létezésére.
Az egyik ilyen feltétel a Dirac-tétel.
Ez azt mondja ki, hogy ha egy G egyszerű, n≥3 csúcsú gráfban minden csúcs foka legalább n/2, akkor a gráfban van Hamilton kör.
Vagyis ebben a gráfban például egészen biztosan van Hamilton kör, mert minden csúcs foka legalább 8/2.
Sőt, ebben is.
És ebben is.
De attól, hogy épp nem teljesül a feltétel…
még simán lehet, hogy van Hamilton kör.
A Dirac tétel egy elégséges, de nem szükséges feltétel.
Viszont attól, hogy egy gráfban
Dirac-tétel:
Ha egy G egyszerű, n ≥ 3 csúcsú gráfban minden csúcs foka legalább n/2, akkor a gráfban van Hamilton kör.
Egy másik elégséges feltétel az Ore-tétel.
Az Ore-tétel azt mondja, hogy ha egy G egyszerű, n≥3 csúcsú gráfban bármely Vi és Vj nem szomszédos csúcsra d(Vi)+d(Vj) ≥n teljesül, akkor a gráfban van Hamilton kör.
Nézzük, mire használhatnánk ezeket a tételeket, jóra vagy rosszra...
Bizonyítsuk be, hogy minden 4-nél nagyobb n számra van olyan n csúcsú G gráf, hogy G-ben és a komplementerében is van Hamilton kör.
Egy gráf és a komplementere együttesen kiadja a teljes gráfot.
Ebből fogunk kiindulni.
Olyan n pontú gráfot nagyon könnyű mondani, amiben van Hamilton kör.
A komplementerében pedig a Dirac tétel miatt biztosan van.
Hiszen minden csúcs foka n-3, vagyis legalább n/2.
Persze, ha n legalább 5.
Egy 100 csúcsú egyszerű gráfban két nem szomszédos csúcs foka 49, az összes többi csúcs foka legalább 50. Bizonyítsuk be, hogy van a gráfban Hamilton út.
Ha minden csúcs foka legalább 50 lenne…
Az jó lenne, mert akkor a Dirac tétel miatt Hamilton kör is lenne a gráfban.
Legyen a két 49 fokú csúcs Vi és Vj.
Vegyünk hozzá a gráfhoz plusz egy élt Vi és Vj között.
Így most minden csúcs foka 50.
A Dirac tétel miatt pedig van Hamilton kör.
A plusz élt elhagyva, a Hamilton körnek legfeljebb egy élét hagyjuk el.
Tehát van Hamilton út.
Itt az ideje emelni a tétet. Lássuk mit mondhatnánk arról a 101 pontú gráfról, amiben minden csúcs foka legalább 50. Van-e a gráfban Hamilton út?
Most egy másik trükköt fogunk használni.
Ezt a trükköt érdemes megjegyezni.
Mindig adódhatnak az életünkben olyan krízishelyzetek, amikor ez a trükk jelenti majd a megoldást.
A trükk ezúttal az lesz, hogy vegyünk hozzá a gráfhoz egy 102-edik csúcsot.
Hívjuk mondjuk Bobnak.
És kössük össze a gráf minden csúcsával.
Az így keletkező gráfban minden csúcs foka legalább 51.
Mivel minden csúcs legalább 102/2 fokú, teljesül a Dirac tétel, tehát a gráfban van Hamilton kör.
Ha Bobot elhagyjuk, a Hamilton körből kiesik egy csúcs és két él.
Ami így marad, egy olyan Hamilton út, ami az eredeti gráf élein és összes csúcsán halad.
Diszkrét matematika epizód.