Gráfok bejárása és gráfalgoritmusok
Feszítőfa
Egy gráf feszítőfája a gráf minden csúcsát tartalmazó fa részgráf. Feszítőfából általában több is van.
Minimális feszítőfa
A minimális feszítőfa egy gráfban a legkisebb élsúlyú feszítőfa.
Kruskal-algoritmus
A Kruskal algoritmus segítségével minimális feszítőfát lehet megtalálni.
Az első lépés, hogy keressük meg a gráfban a legkisebb súlyú élt. Ha több azonos súlyú él van, akkor válasszuk ki azt, amelyikhez kedvünk van.
Ezek után belépünk egy ciklusba, ahol minden lépésben az eddig még ki nem választott élekre alkalmazzuk az előző lépést úgy, hogy ne keletkezzen kör. Ha mégis kör keletkezne, akkor a legutolsó olyan élt, amelynek hozzávétele során a kört kapjuk, töröljük.
Ezt addig csináljuk, amíg kész nem vagyunk.
Gráfok szélességi keresése (BFS)
Gráfok egy adott pontjából való feltérképezésére alkalmas módszer a szélességi keresés (BFS = Breadth-first search).
Működése:
Elindulunk egy adott pontból, és megkeressük az összes szomszédos pontot. Ezek az 1 egység távolságra lévő szomszédok és mindegyikre ragasztunk egy 1-es címkét.
Most ezeknek keressük meg az 1 egység távoli szomszédjait. De csak azokat, akiken még nincsen címke.
Ők a kiinduló ponttól 2 egység távolságra vannak és 2-es címkét kapnak.
Ha valamelyik 2-es szomszédba több él is vezet, akkor csak az egyiket hagyjuk meg. Mindegy melyiket.
Az algoritmus aztán így folytatódik, és szép lassan végez.
Gráfok mélységi keresése (DFS)
A DFS (Depth-first search) algoritmus a gráf mélységi bejárása.
A DFS algoritmus lényege, hogy elindulunk egy úton, és megyünk, amíg csak tudunk.
Amikor elakadunk, mert már nem tudunk úgy továbbmenni, hogy olyan pontba jussunk, ahol még nem jártunk, akkor visszamegyünk egészen addig, ahonnan még lehet földerítetlen pontok felé haladni.
Amikor újra elakadunk, megint visszamegyünk, és ezt ismételjük, amíg az egész gráfot be nem jártuk.
BFS fa és DFS fa
A BFS és DFS algoritmusok végrehajtása során a gráfnak egy-egy feszítőfáját kapjuk. Ezeket nevezzük BFS és DFS fának.
Hamilton kör
Egy gráf csúcsainak bejárására van egy nagyon speciális módszer, amit Hamilton körnek nevezünk, és az a lényege, hogy egy olyan körön haladunk végig a gráfban, amely a gráf összes pontját tartalmazza.
Hamilton kör létezésének szükséges feltétele:
Ha egy gráfból $k$ darab csúcsot kitörlünk (a belőle kiinduló élekkel együtt), akkor a megmaradó gráfnak legfeljebb $k$ darab komponense lehet.
Hamilton út
A Hamilton út egy olyan út, amely a gráf minden csúcsát tartalmazza.
Hamilton út létezésének szükséges feltétele:
Ha egy gráfból $k$ darab csúcsot kitörlünk (a belőle kiinduló élekkel együtt), akkor a megmaradó gráfnak legfeljebb $k+1$ darab komponense lehet.
Dirac-tétel
A Dirac-tétel azt mondja ki, hogy ha egy $G$ egyszerű, $n \geq 3$ csúcsú gráfban minden csúcs foka legalább $\frac{n}{2}$, akkor a gráfban van Hamilton kör.
Ore-tétel
Az Ore-tétel azt mondja, hogy ha egy $G$ egyszerű, $n \geq 3$ csúcsú gráfban bármely $V_1$ és $V_j$ nem szomszédos csúcsra $d(V_i) + d(V_j) \geq n$ teljesül, akkor a gráfban van Hamilton kör.
Adjuk meg ennek a gráfnak a minimális súlyú feszítőfáját a Kruskal-algoritmus segítségével.
Térképezzük föl az alábbi gráfot a szélességi bejárás (BFS) segítségével.
Térképezzük föl az alábbi gráfot a mélységi bejárás (DFS) segítségével.
a) Íme, egy gráf két különböző kezdőpontjából készített BFS fája:
Adjuk meg az eredeti gráfot.
b) Egy gráfban minden csúcs fokszáma páros, és két különböző kezdőpont alapján készített BFS fája:
Adjuk meg az eredeti gráfot.
a) Létezik-e az alábbi gráfban Hamilton kör?
b) Létezik-e az alábbi gráfban Hamilton út?
a) 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 komplementerben is van Hamilton kör.
b) 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.
c) Mit mondhatunk arról a 101 pontú gráfról, amiben minden csúcs foka legalább 50. Van-e a gráfban Hamilton út?
a) Derítsük ki, hogy van-e az alábbi gráfban Hamilton kör. Ha nincs, akkor minimum hány újabb élt kell hozzávennünk ahhoz, hogy legyen?
b) Derítsük ki, hogy van-e az alábbi gráfban Hamilton kör. Ha nincs, akkor minimum hány újabb élt kell hozzávennünk ahhoz, hogy legyen?
c) Minimum hány élt kell behúznunk ebben a gráfban, hogy legyen benne Hamilton kör?
d) Adott egy 100 csúcsú egyszerű gráf, 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.
Térképezzük föl az alábbi gráfot a Dijkstra algoritmus segítségével.
a) A BFS algoritmus az alábbi ábra gráfjának csúcsait a következő sorrendben járta be: S, _ , _ , _ , H, _ , F, C, _ . Egészítsük ki a sorozatot a hiányzó csúcsok neveivel és adjuk meg a bejáráshoz tartozó BFS fát.
b) Az ábrán látható gráf egyik élét elhagytuk. Az él elhagyása előtt S-ből indított BFS algoritmus a gráf csúcsait az alábbi sorrendben járta be:
i) S, B, I, C, A, F, H, E, D
ii) S, I, B, E, D, H, C, A, F
Megállapítható-e egyértelműen, hogy melyik élt hagytuk el? Ha igen, akkor adjuk meg a bejáráshoz tartozó BFS-fát is.
a) Döntsük el, hogy az alábbi gráfnak van-e Hamilton köre, illetve Hamilton útja.
b) Van-e az alábbi gráfban olyan Hamilton kör...
i) ami nem tartalmazza az {A,B} élt?
ii) ami nem tartalmazza a {C,D} élt?
c) Döntsük el, hogy az alábbi gráfnak van-e Hamilton köre, illetve Hamilton útja.
d) 1001 pontú gráf minden csúcsa legalább 501 fokú, kivéve egyetlen csúcsot, aminek a fokszáma 500. Bizonyítsuk be, hogy a gráfban van Hamilton kör.
e) Döntsük el, hogy az alábbi gráfnak van-e Hamilton köre, illetve Hamilton útja.
a) A $G$ egyszerű gráf csúcshalmaza legyen $V(G)=\{1, 2, \dots, 10 \}$. Az $x,y \in V(G)$, $x \neq y$ csúcsok pontosan akkor legyenek szomszédosak $G$-ben, ha $ \mid x - y \mid \leq 2 $.
Van-e $G$-nek olyan feszítőfája, hogy összes éle olyan, amelyre $ \mid x-y \mid = 2$ teljesül?
b) A $G$ egyszerű gráf csúcshalmaza legyen $V(G)=\{1, 2, \dots, 10 \}$. Az $x,y \in V(G)$, $x \neq y$ csúcsok pontosan akkor legyenek szomszédosak $G$-ben, ha $ \mid x - y \mid =2 $ vagy $\mid x-y \mid = 3$.
Van-e $G$-ben Hamilton út, illetve Hamilton kör?
a) Egy 100 csúcsú $G$ összefüggő gráf éleit az 1 és 2 súlyokkal súlyoztuk úgy, hogy az 1 súlyú élek részgráfja (vagyis az a gráf, melynek csúcsai azonosak $G$ csúcsaival, de annak csak az 1 súlyú éleit tartalmazza) 7 komponensből áll.
Határozzuk meg $G$ egy minimális összsúlyú feszítőfájának súlyát.
b) Egy 100 csúcsú összefüggő, egyszerű gráfnak 101 éle van. Mutassuk meg, hogy ekkor van a gráfban 3 páronként különböző feszítőfa. (Két feszítőfa akkor különböző, ha nem pontosan ugyanazon élek alkotják.)
Itt röviden és szuper-érthetően elmeséljük, hogyan lehet egy gráfban megtalálni a minimális feszítőfát. Egy súlyozott gráfban a Kruskal-algoritmus segítségével találjuk meg a minimális élsúlyokkal rendelkező feszítőfát. Mi az a szélességi keresés? Hogyan kell szélességi keresést csinálni egy gráfban? A szélességi keresés (breadth-first search, röviden BFS) egy olyan bejárási algoritmus, amely igyekszik először egy adott csúcshoz legközelebbi csúcsokat átvizsgálni, és csak azután folytatja a keresést a mélyebb csúcsokon. Mi az a mélységi keresés? Hogyan kell végrehajtani? A mélységi keresés (depth-first search, röviden DFS) egy olyan algoritmus, amely egy pontból kiindulva bejárja a gráfot úgy, hogy először igyekszik a legtávolabbi csúcsig, a legmélyebb szintig eljutni. Majd megnézzük, mi az a BFS fa és DFS fa, hogyan kell legyártani. Rekonstruálunk egy gráfot a BFS fái alapján. Szélességi keresés, mélységi keresés, gráfalgoritmusok. Megmutatjuk, mi az a Hamilton kör és Hamilton út, hogyan lehet rájönni, hogy van-e egy gráfban Hamilton kör, mik a szükséges feltételei a Hamilton kör létezésének. Példák Hamilton körre, Hamilton körös feladatok. Könnyedén megtanulhatod, 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égezetül, gyorsan és egyszerűen megnézheted, mi az a Dijkstra algoritmus, hogyan működik és mire jó. Az élsúlyokkal ellátott gráfok minimális útjainak keresésére használjuk. Nézzük meg lépésről lépésre, hogyan működik a Dijkstra algoritmus.
A BFS és a DFS algoritmusok végrehajtása során a gráfnak egy-egy feszítőfáját kapjuk. Ezeket rendkívül frappáns módon BFS és DFS fának nevezzük. Mindketten az eredeti gráf feszítőfái. Csak hát az a baj, hogy a BFS és DFS fák megalkotása során nagy szerepe van a véletlennek. Ha például itt egy másik élt húzunk be… akkor egy egészen más BFS fát kapunk. Arról nem is beszélve, hogy az algoritmus elején a gráf bármelyik csúcsából indulhatunk. Mindezen gubancok ellenére megpróbálhatjuk rekonstruálni az eredeti gráfot annak BSF és DSF fái alapján. Íme, egy gráf két különböző kezdőpont alapján készített BFS fája: Adjuk meg az eredeti gráfot. Lássuk, hogyan tudnánk hasznosítani a BFS fákat. Készítünk egy ilyen kis szomszédsági táblázatot. Aztán pedig kezdjük is az első BFS fával. Eddig jó. Vannak még kétségek, de ezeket reméljük a másik BFS fa hamarosan eloszlatja. Az, hogy a C és D csúcsok között vezet él, immár biztosabb, mint a halál. Hát, ez kész. Már csak föl kell rajzolnunk. Csodás. Egy gráfban minden csúcs fokszáma páros, és két különböző kezdőpont alapján készített BFS fája: Hát, úgy tűnik eddig jutottunk. Nem baj, azért kezdjünk el rajzolgatni. Ezek itt a kérdőjeles élek. Viszont tudjuk még, hogy a gráf minden csúcsának a fokszáma páros. Ha mindkét élt elhagyjuk, az nem jó, mert akkor lesz páratlan fokszámú csúcs. És, ha mindkét élt behúzzuk, az se jó, mert akkor keletkezik harmadfokú csúcs. Ha csak az egyik élt húzzuk be… akkor így lesz egy elsőfokú csúcs. Így viszont minden csúcs páros fokszámú.
A gráfok bejárásának egyik lehetséges módját már láttuk.
Ez a BFS algoritmus, ami hullámszerűen fésüli át a gráfot.
Olyan, mint egy különleges alakulat, aminek a tagjai lépésről-lépésre teljes szélességben haladnak.
De nyomozni nem csak a különleges alakulatok tudnak, hanem a magányos detektívek is.
Ezt DFS algoritmusnak nevezzük.
A DFS algoritmus a gráf mélységi keresés.
A DFS algoritmus lényege, hogy elindulunk egy úton…
rendíthetetlenül.
És megyünk amíg csak tudunk.
Amikor elakadunk, mert már nem tudunk úgy továbbmenni, hogy olyan pontba jussunk, ahol még nem jártunk…
Akkor visszamegyünk egészen addig, ahonnan még lehet földerítetlen pontok felé haladni.
És megyünk a járatlan utakon tovább.
Amikor újra elakadunk, megint visszamegyünk.
Hopp.
Hát, ez ennyi.
Végül itt még vannak lehetőségek.
Így működik a mélységi bejárás.
A BFS és a DFS algoritmusok végrehajtása során a gráfnak egy-egy feszítőfáját kapjuk.
Ezeket rendkívül frappáns módon BFS és DFS fának nevezzük.
Mindketten az eredeti gráf feszítőfái.
Csak hát az a baj, hogy a BFS és DFS fák megalkotása során nagy szerepe van a véletlennek.
Ha például itt egy másik élt húzunk be…
akkor egy egészen más BFS fát kapunk.
Arról nem is beszélve, hogy az algoritmus elején a gráf bármelyik csúcsából indulhatunk.
Mindezen gubancok ellenére megpróbálhatjuk rekonstruálni az eredeti gráfot annak BSF és DSF fái alapján.
Íme, egy gráf két különböző kezdőpont alapján készített BFS fája:
Van itt ez a gráf.
És szeretnénk föltérképezni egy adott pontjából kiindulva.
Az egyik módszer a gráf földerítésére a szélességi keresés.
A BFS algoritmus működése nagyon egyszerű.
Elindulunk egy adott pontból, és megkeressük az összes szomszédos pontot.
Ezek az 1 egység távolságra lévő szomszédok és mindegyikre ragasztunk egy 1-es címkét.
Most ezeknek keressük meg az 1 egység távoli szomszédjait.
De csak azokat, akiken még nincsen címke.
Ők a kiinduló ponttól 2 egység távolságra vannak és 2-es címkét kapnak.
Ha valamelyik 2-es szomszédba több él is vezet, akkor csak az egyiket hagyjuk meg.
Mindegy melyiket.
Itt jönnek aztán a kiindulóponttól 3 egység távolságra lévő pontok.
És persze itt is elég egy él.
Az algoritmus folytatódik. Most a 3-as címkéjű pontoknak keressük meg a szomszédjait.
És szép lassan végzünk.
A BFS algoritmus úgy működik, mint egy hullám, ami a gráf élein szétterjed.
Olyan, mint egy különleges alakulat, aminek a tagjai lépésről-lépésre átfésülik a gráfot.
Nyomozni persze nem csak a különleges alakulatok tudnak…
hanem a magányos detektívek is.
Akik idejüket nem kímélve egyedül bejárják a gráf minden zegzugát.
Ez egy egészen más mentalitást igényel, amit mélységi keresésnek nevezünk.
Ez a vasúti hálózat egy gráf.
Megmutatja, hogy mely állomások között vezetnek vasútvonalak.
Ha ellátjuk az éleket súlyokkal…
Akkor az is kiderül, hogy milyen hosszúak az állomások közötti szakaszok.
Vagy hány percig tart a két állomás közötti út.
Vagy éppen mennyi pénzbe kerül a vasútvonal rekosntrukciója.
Ha például a rekonstrukció elvégzése során kezdetben elegendő az, hogy minden állomásról bármelyik másikra el lehessen jutni felújított vasútvonalon…
akkor a gráfnak egy feszítőfáját kapjuk.
Feszítőfából általában több is van.
És egészen biztosan van köztük egy olyan, ahol a költségek minimálisak…
Van itt ez a gráf, és rendeljünk hozzá az éleihez nem negatív valós számokat.
Ezeket a számokat súlyoknak nevezzük.
Képzeljük el, hogy ez a gráf egy úthálózat, vagy mondjuk egy elektromos hálózat, az élek súlyai pedig az áthaladás költsége.
Készítsük el ebben a gráfban a minimális súlyú feszítőfát.
Ez egy olyan hálózat lesz, amin keresztül bármely csúcsból bármely csúcsba el lehet jutni, de a benne szereplő élek súlyainak összege minimális.
Vagyis ez a legolcsóbban működtethető olyan hálózat, ami az összes csúcsot tartalmazza.
A minimális feszítőfát a Kruskal algoritmus segítségével lehet megtalálni.
Maga az algoritmus nagyon egyszerű.
Az első lépés, hogy keressük meg a gráfban a legkisebb súlyú élt.
Ha több azonos súlyú él van, akkor válasszuk ki azt, amelyikhez kedvünk van.
Ezek után belépünk egy ciklusba, ahol minden lépésben az eddig még ki nem választott élekre alkalmazzuk az előző lépést úgy, hogy ne keletkezzen kör.
Ha mégis kör keletkezik, akkor a legutolsó olyan élt, amelynek hozzávétele során a kört kapjuk, töröljük.
Most éppen van még egy 1-es él…
sőt még egy.
Aztán jönnek a 2-es élek.
Hopp, itt keletkezett egy kör.
Az nem jó, akkor ezt a legutóbbi élt töröljük.
A 2-esekbből kifogytunk, jönnek a 3-asok.
Elfogytak a 3-asok is, úgyhogy jöhetnek a 4-esek.
Ajaj, úgy tűnik mégse…
Hát akkor jöhet az 5-ös.
Aztán a 6-os.
Abból úgy tűnik csak ez az egy van.
Aztán itt jönnek a 7-esek.
A 8-asok…
Végül a 9-esek.
És voila, itt a minimális súlyú feszítőfa.
Az algoritmus röviden így írható le:
Legkisebb súlyú él kiválasztása
Kör keletkezik:
az élt töröljük
Nem keletkezik kör:
az élt megtartjuk
Vesszük a megmaradó
ki nem választott éleket
Egy gráfban lehet több minimális feszítőfa is.
Ez most is így van..
A gráfok csúcsainak bejárására van egy nagyon speciális módszer, amit Hamilton körnek hívunk.
A Hamilton kör lényege az, hogy egy olyan körön haladunk végig a gráfban, amely a gráf összes pontját pontosan egyszer tartalmazza.
Hamilton kör nem minden gráfban van.
Ebben a gráfban épp van.
Ha a gráfból ezt az élt elhagyjuk…
akkor a megmaradó gráfban már lehet, hogy nincs Hamilton kör.
De az is lehet, hogy van.
Olyan kritérium, ami egyértelműen meg tudja mondani, hogy egy gráfban van-e Hamilton kör,nem létezik.
Árulkodó jelek viszont vannak.
Ebben a gráfban egészen biztosan nincs Hamilton kör.
Ha a gráfban van legalább egy elsőfokú csúcs, akkor a Hamilton körnek annyi.
De Hamilton út még lehet.
A Hamilton út egy olyan út, amely a gráf minden csúcsát tartalmazza.
Lássuk, van-e ebben a gráfban Hamilton kör vagy Hamilton út.
Hamilton út biztosan van.
Viszont Hamilton kör…
Hát, az úgy ránézésre nincsen.
De ez a különbség a matematikusok és a csodadoktorok között.
Sajnos a ránézés itt kevés.
Van viszont egy remek kis tétel, ami segít.
Ehhez a tételhez azt kell megértenünk, hogy ha egy gráfnak bizonyos pontjait elhagyjuk…
akkor a gráf több komponensre esik szét.
Ebben a gráfban például most két csúcsot hagytunk el és három komponensre esett szét.
A Hamilton kör létezésének szükséges feltétele, hogy ha egy gráfból k darab csúcsot kitörlünk (a belőle kiinduló élekkel együtt), akkor a megmaradó gráfnak legfeljebb k darab komponense van.
Ez a feltétel most nem teljesül, mert 2 darab csúcsot töröltünk, a gráf mégis 3 komponensre esett szét.
Sajnos ehhez a tételhez azért kis szerencse is kell.
Ha például ezeket a csúcsokat töröljük ki…
Akkor 2 csúcsot töröltünk és a gráf 2 tartományra esik szét.
Vagyis teljesíti a feltételt, pedig nincs Hamilton köre.
Most lássuk, mit is kezdhetnénk az eredeti gráfunkkal.
Olyan csúcsokat érdemes elhagyni, amitől a gráf várhatóan tényleg szétesik.
Terrorista hajlamúak előnyben…
4 csúcs elhagyásával a gráf 5 komponensre esett szét.
Vagyis nem teljesül a szükséges feltétel, a gráfban biztosan nincs Hamilton kör.
Hamilton kör szükséges feltétele:
Ha egy gráfból k darab csúcsot kitörlünk (a belőle kiinduló élekkel együtt), akkor a megmaradó gráfnak legfeljebb k darab komponense lehet.
A Hamilton út szükséges feltétele hasonló:
Egy G gráfban akkor lehet Hamilton út, ha a gráfból k darab csúcsot kitörlünk (a belőle kiinduló élekkel együtt), akkor a megmaradó gráfnak legfeljebb k+1 darab komponense van.
Ennél a gráfnál például teljesül a feltétel.
1 csúcs elhagyásával a gráf 1+1=2 komponensre esett szét.
2 csúcs elhagyásával pedig 3 komponensre.
De minden hiába.
Vagyis a feltétel csak szükséges, de nem elégséges.
Attól, hogy teljesül, még nem biztos, hogy van Hamilton út.
És ezúttal például biztosan nincs.
A három darab első fokú csúcs miatt lehetetlen.
Vannak aztán elégséges feltételei is a Hamilton kör létezésének.
Ha egy gráfban minden csúcs foka elég nagy, akkor biztosan lesz benne Hamilton kör.
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.
Sőt, ebben is.
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.
Remek. Most pedig lássunk néhány gráfot.
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.
É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.
