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.

A képsor tartalma

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.

 

Dirac-tétel és Ore-tétel, a Hamilton kör elégséges feltételei

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

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.

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