PEDAGOŠKA FAKULTETA
DIPLOMSKO DELO
MARUŠA SAKSIDA
PEDAGOŠKA FAKULTETA
Študijski program: MATEMATIKA IN RAČUNALNIŠTVO
HAMILTONSKOST GRAFOV
DIPLOMSKO DELO
Mentor: prof. dr. Aleksander Malnič Kandidatka: Maruša Saksida
Ljubljana, junij 2012
Zahvala
Zahvaljujem se prof. dr. Aleksandru Malniˇcu za mentorstvo pri pisanju diplomskega dela, Ivi Antonˇciˇc in Kaji Zupanc za vso pomoˇc tekom ˇstudija, ter svoji druˇzini za spodbudo in neizmerno podporo.
Program dela
Kandidatka naj pregledno predstavi problem hamiltonskosti v grafih ter nekaj primerov uporabe. Posebej naj obdela P´osev izrek in njegove posledice: Orejev izrek ter Diracov izrek. Pri ˇstudiju obravnavane tematike naj si pomaga z naslednjo primarno literaturo.
Harary, F. (1968). Graph Theory. Reading (Mass.), Addison-Wesley.
prof. dr. Aleksander Malniˇc
V Ljubljani, 12. decembra 2011
POVZETEK
Diplomsko delo obravnava lastnost grafov imenovano hamiltonskost grafov. Predstavljeni so nekateri pomembni potrebni in zadostni pogoji, ki nam povejo, kdaj graf je oziroma ni hamiltonski. Med zadostnimi pogoji spoznamo P´osev izrek in pomembni posledici tega izreka, Orejev in Diracov izrek. Ogledamo si tudi nekaj druˇzin grafov, ki so oziroma niso hamiltonski. Na koncu na kratko obravnavamo ˇse uporabno stran iskanja hamiltonskih ciklov v grafih.
KLJU ˇCNE BESEDE: Graf, hamiltonskost, hamiltonski cikel, P´osev izrek, Orejev izrek, Diracov izrek, problem trgovskega potnika, Kitajski obroˇci, fuleren.
TITLE: HAMILTONIAN GRAPHS
ABSTRACT
The diploma work discusses about graph characteristics called hamiltonicity. Some of the important necessary and sufficient conditions are presented which tell us when a graph is or is not Hamiltonian. Among sufficient conditions we recognize P´osa’s theorem and its corollaries are Ore’s theorem and Dirac’s theorem. We also take a look at some families of graphs that are Hamiltonian and some that are not. In the end, we briefly consider the practical aspect of searching Hamiltonian cycles in graphs.
KEYWORDS: Graph, hamiltonicity, Hamilton cycle, P´osa’s theorem, Ore’s theorem, Dirac’s theorem, traveling salesman problem, Chinese rings, fuleren.
0 UVOD 1
1 OSNOVNO O GRAFIH 3
1.1 GRAF IN PODGRAF . . . 3
1.2 STOPNJA VOZLIˇS ˇCA . . . 5
1.3 SPREHODI . . . 7
1.4 IZOMORFIZEM . . . 9
1.5 NEKATERE DRUˇZINE GRAFOV . . . 10
2 HAMILTONSKI GRAFI 17 2.1 HAMILTONSKI GRAFI . . . 17
2.2 WILLIAM ROWAN HAMILTON . . . 17
2.3 ZGODOVINA PROBLEMA . . . 19
2.4 ZGLEDI (NE)HAMILTONSKIH GRAFOV . . . 21
3 POGOJI ZA HAMILTONSKOST GRAFOV 27 3.1 POTREBNI POGOJI . . . 27
3.2 ZADOSTNI POGOJI . . . 30
3.2.1 P´osev izrek . . . 31
3.2.2 Orejev izrek in Diracov izrek . . . 35
3.3 DOMNEVE . . . 41
4 UPORABA 43 4.1 KITAJSKI OBRO ˇCI . . . 43
4.1.1 Grayeve kode . . . 44 v
4.1.2 Reˇsitev igre Kitajski obroˇci . . . 45 4.2 FULERENI . . . 47 4.3 PROBLEM TRGOVSKEGA POTNIKA . . . 49
5 ZAKLJU ˇCEK 51
UVOD
Diplomsko delo, ki je pred vami, sodi na podroˇcje teorije grafov. To je veja matematike, ki se ukvarja s preuˇcevanjem posebnih matematiˇcnih struktur, imenovanih grafi. Grafe si lahko predstavljamo kot mnoˇzico vozliˇsˇc in povezav med njimi. Te strukture je moˇc najti povsod, tako v kemiji, raˇcunalniˇstvu in gradbeniˇstvu kot tudi pri planiranju urnikov, trgovskih poti in analizi prijateljskih ter poslovnih odnosov.
Zaˇcetki teorije grafov segajo v leto 1735, ko se je ˇsvicarski matematik Leonhard Euler lotil problema K¨onigsbergˇskih mostov. Skozi mesto K¨onigsberg teˇce reka Pregel, ki mesto razdeli na ˇstiri dele, ki so med seboj povezani s sedmimi mostovi. Euler si je zastavil vpraˇsanje, ali je mogoˇce vsakega od mostov preˇckati le enkrat in se vrniti na zaˇcetno mesto. Reˇsitev tega problema je objavil leta 1736 v ˇclanku Sedem mostov K¨onigsberga in s tem priˇcel z novim, sploˇsno uporabnim podroˇcjem matematike, ki se v zadnjih dese- tletjih naglo razvija. Podobno vpraˇsanje, kot si ga je zastavil Euler, bi si lahko zastavili tudi sami, le da bi se vpraˇsali, ali je mogoˇce vsakega izmed ˇstirih delov mesta K¨onigsberg obiskati natanko enkrat in se vrniti na zaˇcetno mesto. Na videz podobno vpraˇsanje se je kasneje izkazalo za mnogo teˇzje. Lastnosti grafov, kjer vsako vozliˇsˇce obiˇsˇcemo natanko enkrat in se na koncu vrnemo v zaˇcetno vozliˇsˇce, pravimo hamiltonskost grafov. In prav ta lastnost je tema tega diplomskega dela.
Diplomsko delo je razdeljeno na veˇc poglavij. Na zaˇcetku so opredeljeni in na primerih 1
razloˇzeni osnovni pojmi teorije grafov, ki so bistveni za razumevanje nadaljnjega besedila.
Na koncu prvega poglavja so predstavljene tudi najpomembnejˇse druˇzine grafov, katerih hamiltonskost bomo obravnavali v naslednjih poglavjih. V drugem poglavju se natanˇcneje sreˇcamo s hamiltonskostjo grafov, zgodovino tega problema in grafi, ki so oziroma niso hamiltonski. Naslednje poglavje je namenjeno obravnavi nekaterih najpomembnejˇsih po- gojev, ki nam povejo, kdaj graf je oziroma ni hamiltonski. Nekoliko bolj se bomo posvetili P´osevemu izreku in njegovima dvema posledicama, Orejevemu in Diracovemu izreku. V zadnjem poglavju se sreˇcamo ˇse z uporabno platjo tega problema.
OSNOVNO O GRAFIH
V prvem poglavju si bomo ogledali osnovne definicije in trditve iz teorije grafov, ki jih bomo potrebovali v nadaljevanju. Na koncu poglavja so predstavljene tudi nekatere druˇzine grafov, s katerimi se kasneje veˇckrat sreˇcamo.
1.1 GRAF IN PODGRAF
Definicija. Naj bo V konˇcna neprazna mnoˇzica in E poljubna druˇzina dvoelementnih podmnoˇzic mnoˇziceV. ParuG= (V, E) pravimograf na mnoˇzici vozliˇsˇcV =V(G) in z mnoˇzico povezav E =E(G).
Grafe predstavimo z diagramom.
a
b
c d e
G
Slika 1.1: Primer grafa.
Na Sliki 1.1 je predstavljen grafG= (V, E) s petimi vozliˇsˇci (|V(G)|= 5), in sicerV(G) = {a, b, c, d, e}, ter sedmimi povezavami (|E(G)|= 7), ki soE(G) ={(a, b),(a, c),(a, e),(b, c), (b, d),(b, e),(c, d)}.
3
Definicija. Element {u, v} mnoˇzice E piˇsemo krajˇse kot uv. Kadar je par vozliˇsˇc uv element mnoˇzice E pravimo, da sta vozliˇsˇci u in v sosednji v grafu G in piˇsemo u ∼v.
Za povezavi pravimo, da sta sosednji, ˇce imata kakˇsno skupno krajiˇsˇce.
Opozorilo. Kot opozorilo omenimo, da definicija grafa ne dopuˇsˇca, da isti par vozliˇsˇc povezuje veˇc povezav (vzporedne povezave) ali moˇznosti, da je vozliˇsˇce povezano samo s seboj (zanka). Takim grafom, ki to dopuˇsˇcajo, pravimo multigrafi. Kadar ˇzelimo po- udariti, da govorimo o grafih brez zank in vzporednih povezav, takim grafom reˇcemo enostavni grafi.
Definicija. Graf H je podgraf grafa G, ˇce je vsako vozliˇsˇce grafa H tudi vozliˇsˇce grafa G, in ˇce je vsaka povezava grafa H tudi povezava grafa G, to je V(H) ⊆ V(G) in E(H)⊆E(G). Podgraf H grafaG oznaˇcimo zH ⊆G.
a b
c d
a b
c
G H
Slika 1.2: Graf Gin njegov podgraf H.
Definicija. Podgraf H grafa G je vpet grafu G, ˇce podgraf H vsebuje natanko vsa vozliˇsˇca grafa G, torej V(H) =V(G).
a b
c d
G H
a b
c d
Slika 1.3: Graf Gin njegov vpet podgraf H.
1.2 STOPNJA VOZLIˇ S ˇ CA
Definicija. Stopnja vozliˇsˇca u v grafu G je enaka ˇstevilu povezav grafa G, ki imajo vozliˇsˇce u za svoje krajiˇsˇce. Stopnjo vozliˇsˇca u oznaˇcimo z deg(u) ali d(u) in v znakih zapiˇsemo kot deg(u) =|{u | u∼v}|.
Vozliˇsˇcem stopnje 0 pravimo izolirana vozliˇsˇca, vozliˇsˇcem stopnje 1 pa listi.
Najmanjˇso stopnjo vozliˇsˇca grafa G oznaˇcimo z δ(G), najveˇcjo pa z ∆(G). Povpreˇcno stopnjo vozliˇsˇca grafa G oznaˇcimo zd(G) in je enaka:
d(G) = P
v∈V(G)deg(v)
|V(G)|
.
Zveza med minimalno, povpreˇcno in najveˇcjo stopnjo vozliˇsˇc grafa Gje torej:
δ(G)≤d(G)≤∆(G) .
e d
c b
a
f
Slika 1.4: Primer grafa za ponazoritev stopnje vozliˇsˇc.
Graf na Sliki 1.4 ima stopnjo posameznih vozliˇsˇc: deg(a) = 0, deg(b) = 2, deg(c) = 3, deg(d) = 2, deg(e) = 4 in deg(f) = 1. Vozliˇsˇce a je izolirano vozliˇsˇce. Najmanjˇsa stopnja vozliˇsˇc grafa G s Slike 1.4 je δ(G) = 0, najveˇcja ∆(G) = 4, povpreˇcna pad(G) = 2.
Definicija. Graf G je regularen, ˇce imajo vsa vozliˇsˇca grafa isto stopnjo. To pa je natanko takrat, ko velja δ(G) = ∆(G) = d(G). ˇCe imajo vsa vozliˇsˇca grafa stopnjo r, pravimo, da je graf regularen stopnje r ali r-regularen.
Grafom, ki so 3-regularni, pravimo tudikubiˇcni grafi.
r = 1 a b
a b
c
r = 2 r = 3
a b
d
c e
r = 4
a b
c
d
Slika 1.5: Nekaj primerov regularnih grafov.
Stopnjo vozliˇsˇc in ˇstevilo povezav grafa povezuje naslednja enakost:
Lema 1.1 (Lema o rokovanju) Za vsak graf Gvelja, da je vsota stopenj vozliˇsˇc enaka dvakratnemu ˇstevilu povezav:
X
v∈V(G)
deg(v) = 2· |E(G)|
.
Dokaz. Vsaka povezava ima dve krajiˇsˇci, torej vsaka povezava prispeva natanko 2 k
vsoti stopenj grafa.
Poimenovanje lema o rokovanju izvira iz dejstva, da lahko z grafom predstavimo rokovanje skupine ljudi na zabavi. Ljudi na zabavi vzamemo za vozliˇsˇca grafa, posamezne povezave med vozliˇsˇci pa dodamo, ˇce se ˇcloveka na zabavi rokujeta. ˇStevilo povezav je torej enako ˇstevilu vseh rokovanj, stopnja vozliˇsˇca je ˇstevilo rokovanj ene osebe, vsota stopenj vozliˇsˇc pa je vsota rokovanj vseh oseb. Torej lahko reˇcemo, da je vsota stopenj vozliˇsˇc ˇstevilo rok, ki so se rokovale. In ker sta za rokovanje potrebni dve roki, je ˇstevilo rok, ki so se rokovale, dvakrat veˇcje od ˇstevila rokovanj. Prav o tem govori lema o rokovanju.
Lema o rokovanju ima dve posledici:
Posledica 1.2 Vsota stopenj vozliˇsˇc v grafu G je soda in ˇstevilo vozliˇsˇc lihih stopenj je sodo.
Dokaz. Dokaˇzimo najprej prvi del posledice, da je vsota vozliˇsˇc v grafu G soda. Ta posledica je izpeljana neposredno iz leme o rokovanju, ki pravi, da je vsota stopenj vozliˇsˇc enaka dvakratnemu ˇstevilu povezav, torej je vsota stopenj vozliˇsˇc res soda. Dokaˇzimo ˇse drugi del posledice, ki pravi, da je ˇstevilo vozliˇsˇc lihih stopenj sodo. ˇCe to ne bi drˇzalo, bi bilo ˇstevilo vozliˇsˇc lihih stopenj liho, kar pomeni, da bi bila vsota stopenj vozliˇsˇc liho ˇstevilo, to pa po lemi o rokovanju ne drˇzi. Torej je ˇstevilo vozliˇsˇc lihih stopenj res sodo.
Posledica 1.3 Ce je grafˇ G r-regularen na n vozliˇsˇcih, potem ima G natanko 12 ·n ·r povezav: |E(G)|= 12 ·n·r.
Dokaz. Graf G ima po predpostavki n vozliˇsˇc stopnje r, kar pomeni, da je vsota vseh vozliˇsˇc r·n. Po lemi o rokovanju je ˇstevilo povezav natanko polovica vsote vseh vozliˇsˇc,
torej 12 ·r·n.
1.3 SPREHODI
Definicija. Sprehodv grafuGje zaporedje vozliˇsˇcS=v0v1v2...vk−1vk, kjer sta poljubni dve zaporedni vozliˇsˇci sosednji, to je vi−1vi ∈E(G). Dolˇzina sprehodaje enaka ˇstevilu povezav k.
a b
e f
c d
Slika 1.6: Graf za ponazoritev sprehodov in razdalje.
Na grafu na Sliki 1.6 jeaebf ebd sprehod dolˇzine 6 od vozliˇsˇca a do vozliˇsˇca d.
Definicija. Obhod je sklenjen sprehod, kar pomeni, da se sprehod zaˇcne in konˇca v istem vozliˇsˇcu, torej v0 =vk.
Definicija. Ce so v sprehodu med seboj razliˇˇ cna vsa vozliˇsˇca v0, v1, ..., vk, potem ta sprehod imenujemo pot.
Na grafu na Sliki 1.6 smo si pogledali primer sprehoda od vozliˇsˇcaa do vozliˇsˇca d. Ali je ta sprehod tudi pot? Odgovor je ne, saj se vozliˇsˇce eponovi dvakrat. Sprehod abedpa je tudi pot od vozliˇsˇcaa do vozliˇsˇcad.
Definicija. Sklenjeno pot (pot, ki se zaˇcne in konˇca v istem vozliˇsˇcuv0 =vk) imenujemo cikel v grafu.
Trditev 1.4 Ce v grafuˇ G obstaja sprehod od u do v, potem obstaja tudi pot od u do v.
Dokaz. Naj bov1v2v3· · ·vivi+1vi+2· · ·vj−1vjvj+1vj+2· · ·vksprehod v grafuGod vozliˇsˇca v1 do vozliˇsˇca vk in naj velja vi =vj. Potem lahko vmesni sklenjen sprehod zbriˇsemo in dobimo sprehod v1v2v3· · ·vivjvj+1vj+2· · ·vk, ki je krajˇse dolˇzine. Ko takih ponavljanj ni
veˇc, dobimo pot.
... ... ...
...
v1 v2 v3 vi = vj
vi+1 vi+2 vj-2
vj-1
vj+1 vj+2 vk
Slika 1.7: Ilustracija k dokazu Trditve 1.4.
Definicija. Graf Gjepovezan, ˇce med poljubnima vozliˇsˇcemau, v ∈V(G) obstaja pot.
Definicija. Ce v grafuˇ Gmed poljubnima vozliˇsˇcema u, v ∈V(G) obstaja pot, pravimo, da sta vozliˇsˇci u, v v istipovezani komponenti. ˇStevilo povezanih komponent grafaG oznaˇcimo z Ω(G).
Torej lahko drugaˇce tudi reˇcemo, da je grafG povezan, ˇce ima eno samo povezano kom- ponento, to je Ω(G) = 1.
a b c d
a b
c d
Slika 1.8: Levo primer nepovezanega grafa; desno primer povezanega grafa.
Definicija. Razdalja med dvema poljubnima vozliˇsˇcema u, v ∈ V(G) v grafu G je dolˇzina najkrajˇse poti od udo v. Oznaˇcimo jo zd(u, v).
Ce v grafuˇ G pot med vozliˇsˇcema u, v ∈ V(G) ne obstaja (kadar graf ni povezan), za
”razdaljo”med uin v vzamemo vrednost ∞.
Definicija. Diameter ali premer je najveˇcja razdalja v grafu (razdalja med najbolj oddaljenima vozliˇsˇcema v grafu).
Graf na Sliki 1.6 ima razdaljo med a in c enako d(a, c) = 2, konkretni najkrajˇsi poti sta aec aliabc. Prav tako je diameter 2.
1.4 IZOMORFIZEM
Definicija. Vzemimo grafaG inG0. Bijektivni preslikaviτ: V(G)→V(G0), za katero je uv ∈E(G) natanko tedaj, ko jeτ(u)τ(v)∈E(G0), pravimoizomorfizem grafov. Grafa G in G0 sta izomorfna, v znakih G ' G0, ˇce med njima obstaja kakˇsen izomorfizem.
V primeru, ko je graf G0 kar enak grafu G, izomorfizmu grafov pravimo avtomorfizem grafa.
Definicija. Graf G je tranzitiven na vozliˇsˇcih, ˇce za vsak par vozliˇsˇc u, v ∈ V(G) obstaja avtomorfizem τ grafaG, za katerega veljaτ(u) =v.
Grafi na Sliki 1.9 in 1.10 so vsi tranzitivni na vozliˇsˇcih, vendar grafa na Sliki 1.10 nista
1 2 3
5 4 6
a b
c
d e f
Slika 1.9: Primer izomorfnih grafov.
d c
b a
h g
f e
b
c d e f g h
a
Slika 1.10: Primer neizomorfnih grafov.
izomorfna, saj je izomorfizem stroˇzji pogoj in ohranja vse lastosti grafa, ne le tranzitiv- nosti. Za primer grafa, ki pa ni tranzitiven na vozliˇsˇcih se spomnimo grafa iz Slike 1.6.
Graf ni niti regularen, kar je potrebni pogoj za tranzitivnost na vozliˇsˇcih.
1.5 NEKATERE DRUˇ ZINE GRAFOV
Pogledali si bomo nekatere druˇzine grafov, ki jih bomo v prihodnosti veˇckrat omenjali.
Definicija. Cikelnan ≥3 vozliˇsˇcih je graf Cn, definiran z mnoˇzico vozliˇsˇcV(Cn) = Zn in mnoˇzico povezav E(Cn) = {u(u+ 1) | u ∈ Zn}. Graf Cn je 2-regularen in ima n povezav.
C3 C4 C5 C6
Slika 1.11: Cikli C3,C4, C5 in C6.
Definicija. Pot na n vozliˇsˇcih je graf Pn, definiran z mnoˇzico vozliˇsˇc V(Pn) = Zn in mnoˇzico povezav E(Pn) ={u(u+ 1) | u= 0,1, . . . n−1}. Graf Pn ima n−1 povezav in ga lahko dobimo iz ciklaCn z odstranitvijo katerekoli povezave. Graf Pn ni regularen, saj imata skrajni vozliˇsˇci stopnjo 1, ostala pa 2.
P1 P2 P3 P4 P5
Slika 1.12: Poti P1, P2, P3, P4 in P5.
Definicija. Polni graf na n vozliˇsˇcih je graf Kn, v katerem so vsa vozliˇsˇca paroma povezana, to je V(Kn) = Zn in E(Kn) = {uv | u, v ∈ Zn, u 6= v}. Polni graf Kn je (n−1)-regularen in ima po drugi posledici o rokovanju 12 ·n·(n−1) povezav.
K3 K4 K5
K2 K1
Slika 1.13: Polni grafi K1, K2, K3, K4 inK5.
Definicija. Diskretni graf je graf brez povezav. Diskretni graf nanvozliˇsˇcih oznaˇcimo z Nn in je 0-regularen.
N3 N4 N5
N2
N1
Slika 1.14: Diskretni grafi N1, N2, N3, N4 inN5.
Definicija. Graf je dvodelen, ˇce lahko mnoˇzico vozliˇsˇc V(G) zapiˇsemo kot disjunktno unijo dveh podmnoˇzic A, B ⊆ V(G), tako da za vsako povezavo uv ∈ E(G) velja, da je eno od vozliˇsˇc u, v vsebovano v mnoˇzici A, drugo pa v mnoˇzici B. Mnoˇzici A in B imenujemo mnoˇzici dvodelnega razbitja grafa G.
A
B
Slika 1.15: Ponazoritev dvodelnega grafa.
Definicija. Polni dvodelni graf je dvodelni graf, kjer je vsako vozliˇsˇce iz prve mnoˇzice dvodelnega razbitja povezano z vsemi vozliˇsˇci iz druge mnoˇzice dvodelnega razbitja. ˇCe je v prvi mnoˇzici dvodelnega razbitja m vozliˇsˇc, v drugi pa n, graf oznaˇcimo sKm,n. Polni dvodelni grafKm,n ima m+nvozliˇsˇc inm·n povezav. GrafomK1,n pravimo tudi zvezde.
K1,4 K3,3 K2,3
Slika 1.16: Polni dvodelni grafi K1,4,K2,3 in K2,3.
Med dvodelnimi grafi so posebej zanimivi grafi, imenovani hiperkocke.
Definicija. Hiperkocka je graf, katerega vozliˇsˇca si lahko predstavljamo kot binarne vektorje dolˇzine n, kjer sta dva vektorja povezana natanko tedaj, ko se razlikujeta le v eni koordinati. Formalno definiramo mnoˇzico vozliˇsˇc kot V(Qn) = {0,1}n in mnoˇzico povezav kot E(Qn) = {uv | |δ(u, v)| = 1}, kjer je δ(u, v) = {i ∈ {0,1, . . . , n} | ui 6= vi}.
Hiperkocka Qn je n-regularen graf na 2n vozliˇsˇcih in na n·2n−1 povezavah.
0 1 00 01 11
01 100 101
000 001 110 010
111 011
Q1 Q2 Q3
Slika 1.17: Hiperkocke Q1, Q2 inQ3.
Kot smo ˇze omenili, so vse hiperkocke dvodelni grafi. Za mnoˇzici dvodelnega razbitja vzamemo mnoˇzico vozliˇsˇc, ki ima sodo mnogo komponent enakih 0, in mnoˇzico vozliˇsˇc, ki ima liho mnogo komponent enakih 0.
Obiˇcajno med hiperkocke ˇstejemo tudi 0-razseˇzno kocko Q0 =K1.
Kot zanimivost lahko omenimo, da so hiperkocke v zadnjih letih deleˇzne velike pozornosti, saj je njihova uporaba tesno povezana s tehnologijo paralelenega raˇcunalniˇstva. Glavna ideja veˇcprocesorskih sistemov je deljenje danega problema na veˇc manjˇsih, samostojnih podproblemov, te pa se razdeli med procesorje. Komunikacija med procesorji naj bi po- tekala s ˇcim manjˇso ˇcasovno potrato in prav tu pride v poˇstev struktura hiperkocke, ki omogoˇca, da je ˇcas potreben za komunikacijo med procesorskimi enotami ˇcim manjˇsi.
Kasneje si bomo pogledali ˇse eno zanimivo lastnost hiperkock in sicer njihovo uporabo v teoriji kodiranja.
Definicija. Povezanim grafom brez ciklov pravimodrevesa.
Slika 1.18: Primer drevesa.
Definicija. Grafi pravilnih telesaliplatonski grafi, so grafi, ki jih dobimo iz platon- skih teles, tako da ogliˇsˇca teles vzamemo za vozliˇsˇca, robove pa za povezave grafa.
tetraeder kocka oktaeder dodekaeder ikozaeder
Slika 1.19: Platonska telesa in njim pripadajoˇci platonski grafi.
Platonska telesa so, kot lahko sklepamo ˇze po imenu, dobila ime po grˇskem filozofu Aristo- klu, ki je postal znan pod vzdevkom ’Platon’ ali ’ˇsirok’. ˇSe vedno ni znano ali je vzdevek dobil zaradi ˇsirokih ramen, ˇsirokega ˇcela ali ˇsirokega izbora svojih drugih sposobnosti.
Platon je ustanovil visoko ˇsolo, ki jo je po lastniku Academosu poimenoval Akademija. V njej so matematiko pouˇcevali kot vejo filozofije in vere. Tak primer je tudi pet platonskih teles. Verjeli so namreˇc, da so osnovni elementi (zemlja, ogenj, zrak in voda) sestavljeni iz geometrijskih atomov. Zemlja naj bi bila sestavljena iz kockastih atomov, ogenj iz tetraedrov, zrak iz oktaedrov, voda iz ikozaedrov, samo vesolje pa naj bi imelo obliko dodekaedra.
Definicija.: Posploˇseni Petersenov graf na n vozliˇsˇcih je graf Pn,k (n ≥ 3 in 0 <
k < n), definiran z mnoˇzico vozliˇsˇc V(Pn,k) = {ui, vi | i ∈ Zn} in mnoˇzico povezav E(Pn,k) = {uiui+1, uivi, vivi+k | i ∈ Zn}. Posploˇseni Petersenov kubiˇcen graf ima 2n vozliˇsˇc in 3n povezav.
Posploˇseni Petersenovi grafi so dobili ime po zelo znanem Petersonovem grafuP5,2, ki ima marsikatero zanimivo lastnost.
P3,1 P7,3 P5,2
Slika 1.20: Posploˇsena Petersonova grafaP3,1 in P7,3 ter Petersenov graf P5,2.
Definicija. Naj bo G konˇcna grupa in S ⊆ G\{e} poljubna podmnoˇzica grupe G, ki je zaprta za inverze. Cayleyjev graf G = Cay (G;S) je graf definiran z mnoˇzico vozliˇsˇc V(G) =Gin mnoˇzico povezavE(G) ={uv |u−1v ∈S}. Cayleyjevi grafi so|S|-regularni.
0 1
2
3 4 5
Slika 1.21: Primer Cayleyjevega grafa Cay(Z6; 2, 4, 3).
HAMILTONSKI GRAFI
2.1 HAMILTONSKI GRAFI
Definicija. Vpeti potiP v grafuG pravimo hamiltonska pot, torej V(P) =V(G).
Definicija. Vpetemu cikluCv grafuGpravimohamiltonski cikel, torejV(C) = V(G).
Definicija. Graf jehamiltonski, ˇce v grafu obstaja hamiltonski cikel.
Slika 2.1: Primer hamiltonskega grafa.
2.2 WILLIAM ROWAN HAMILTON
Hamiltonska pot in hamiltonski cikel sta dobila ime po irskem matematiku Siru Williamu Rowanu Hamiltonu. Rodil se je leta 1805 v Dublinu na Irskem. ˇZe zelo zgodaj je osirotel, a ˇse pred tem so ga starˇsi pri komaj letu dni starosti poslali ˇziveti k stricu, ki je bil med
17
drugim zadolˇzen za njegovo izobrazbo. Bil je zelo nadarjen otrok, pri treh letih je ˇze znal brati angleˇsˇcino, pri ˇstirih se je zaˇcel zanimati za geografijo in zaˇcel brati latinˇsˇcino, grˇsˇcino in hebrejˇsˇcino. ˇSe preden je dopolnil trinajst let je tekoˇce govoril kar trinajst jezikov.
Slika 2.2: William Rowan Hamilton [23].
Pri petnajstih letih, ko je spoznal Zeraha Colburna, se je Hamilton zaˇcel zanimati za ma- tematiko. Njegova kariera je bila bliskovita, pri komaj enaindvajsetih letih, ˇse preden je doˇstudiral na Trinity College v Dublinu, je postal kraljevi astronom Irske, direktor obser- vatorija v Dunsinku in profesor astronomije na univerzi. Pri tridesetih je bil povzdignjen v plemiˇski stan.
Hamilton je s svojimi izjemnimi deli prispeval pomembna odkritja v geometrijski optiki, dinamiki, teoriji grafov in algebri. Prelomnica v njegovem ˇzivljenju se je zgodila leta 1843, ko je med sprehodom odkril kvaternione in idejo zapisal kar na bliˇznji most.
Hamiltonovega ˇzivljenja niso zaznamovali le uspehi. Leta 1825 se je brezupno zaljubil v prijateljevo sestro Catherine Disney, ki ga je zavrnila. To ga je moˇcno potrlo. Kasneje se je poroˇcil s Helen Bayly, s katero sta imela tri otroke.
Umrl je 2. septembra leta 1865.
2.3 ZGODOVINA PROBLEMA
Kakor vrsta drugih problemov s podroˇcja teorije grafov in matematike nasploh, je tudi ta naloga pognala in ˇcrpala svoje osnovne zamisli iz kratkoˇcasne matematike.
Hamilton si je izmislil igro imenovano ikozaederska igra (kasneje Potovanje okoli sveta).
Bistvo igre je poiskati hamiltonski cikel na mreˇzi pravilnega dodekaedra (eden od petih platonskih teles), katerega ogliˇsˇca so oznaˇcena s ˇcrkami. Pri tem je prvih pet ˇcrk ˇze iz- branih.
R
S
T V
W
Q P
N
M
K L J
H X
Z
B C
D G F
Slika 2.3: Mreˇza pravilnega dodekaedra v igri Potovanje okoli sveta.
Dano zaporedje ˇcrk BCPNM lahko na primer igralec nadaljuje na natanko dva naˇcina:
BCPNMDFKLTSRQZXWVJHGM BCPNMDFGHXWVJKLTSRQZB
Hamilton je s pomoˇcjo ikozaederskega raˇcuna (algebre kvaternionov) dokazal, da ne glede na izbiro prvih petih zaporednih vozliˇsˇc, tak cikel vedno obstaja.
Idejo za igro je Hamilton prodal veletrgovcu z igrami za petindvajset funtov, a izkazalo se je, da je bila kupˇcija za trgovca slaba.
Zgodnejˇsi primer problema, ki ga lahko izrazimo s hamiltonskimi cikli, jeproblem skakaˇcevega
sprehoda: Ali lahko skakaˇc obiˇsˇce vsako polje ˇsahovnice z zaporedjem skokov in zakljuˇci sprehod na zaˇcetnem polju?
Problem je ravno iskanje hamiltonskega cikla. Polja so vozliˇsˇca, med katerimi obstajajo povezave, ˇce skakaˇc s prvega polja lahko skoˇci na drugega.
Poglejmo si poenostavljen problem na ˇsahovnici 4×4.
Slika 2.4: Levo ˇsahovnica 4×4; desno graf, ki ga izriˇse skakaˇc na ˇsahovnici 4×4.
Izkaˇze se, da ni nobenega skakaˇcevega sprehoda na ˇsahovnici 4×4 (da je to res bomo dokazali nekoliko kasneje). Na nekaterih ˇsahovnicah pa skakaˇcev sprehod obstaja. Prvi, ki je naˇsel sklenjeno reˇsitev za obiˇcajno ˇsahovnico velikosti 8×8, je bil Euler. Zasledimo jo v Eulerjevem pismu Goldbachu iz leta 1757. Kasneje, leta 1759, je Euler objavil tudi ˇ
clanek, v katerem podaja sistematiˇcen pristop za reˇsevanje tega problema na ˇsahovnicah razliˇcnih oblik.
Torej je odgovor na originalno vpraˇsanje, za obiˇcajno ˇsahovnico velikosti 8×8, pritrdilen.
A zaradi izredno velikega ˇstevila moˇznih skakanj je nesistematiˇcno iskanje reˇsitve pona- vadi obsojeno na neuspeh. Na Sliki 2.5 lahko vidimo nekaj moˇznih reˇsitev skakaˇcevega sprehoda na ˇsahovnicah velikosti 8×8.
ˇSe posebno lepa je prva reˇsitev; ˇce v polja zapiˇsemo zaporedje potez kot kaˇze Slika 2.6, dobimo magiˇcni kvadrat, v katerem je vsota v vsaki vrstici in v vsakem stolpcu enaka 260.
Slika 2.5: Nekaj moˇznih reˇsitev skakaˇcevega sprehoda na ˇsahovnicah 8×8.
50 11 24 63 14 37 26 35 23 62 51 12 25 34 15 38 10 49 64 21 40 13 36 27 61 22 9 52 33 28 39 16 48 7 60 1 20 41 54 29 59 4 45 8 53 32 17 42 6 47 2 57 44 19 30 55 3 58 5 46 31 56 43 18
Slika 2.6: Magiˇcni kvadrat.
2.4 ZGLEDI (NE)HAMILTONSKIH GRAFOV
Pogljemo si nekaj tipiˇcnih primerov hamiltonskih oziroma nehamiltonskih grafov.
Oˇcitno je, da so cikliCn hamiltonski grafi za vse vrednostin. Prav tako je oˇcitno, da poti Pnniso hamiltonski grafi za vse vrednostin, saj ti ne vsebujejo niti enega cikla. Vsebujejo pa hamiltonsko pot.
Polni grafi Kn so prav tako hamiltonski. ˇCe vozliˇsˇca oznaˇcimo z 1,2,3, . . . , n, je hamil- tonski cikel 123. . . n.
V sploˇsnem za hamiltonskost regularnih grafov velja naslednji izrek, glej [3].
K3 K4 K5 3
1
2
1 2
3 4
1
2
3 4 5
Slika 2.7: Hamiltonski cikli v polnih grafih.
Izrek 2.1 (Nash-Williams) Vsak r-regularen graf na 2r+ 1 toˇckah je hamiltonski.
Primer hamiltonskih grafov so tudi hiperkocke. ˇSe preden si pogledamo dokaz, da je hi- perkocka res hamiltonski graf, si poglejmo, kako lahko hiperkocko Qn+1 konstruiramo.
HiperkockoQn+1lahko konstruiramo tako, da vzamemo dve hiperkocki, imenovani ”leva”in
”desna”podhiperkocka,Q0n inQ1n, ter poveˇzemo istoleˇzna vozliˇsˇca. Primer si poglejmo na hiperkocki Q4 =Q3+1.
Slika 2.8: Konstrukcija hiperkocke Q4.
Sedaj, ko znamo skonstruirati hiperkocko Qn+1, lahko dokaˇzemo, da so hiperkocke Qn (n≥2) res hamiltonski grafi.
Trditev 2.2 Hiperkocka Qn (n ≥2) je hamiltonski graf.
Dokaz. Dokaz bomo izpeljali s pomoˇcjo indukcije po n.
Trditev za n= 2 velja, saj je oˇcitno, da je Q2 =C4 hamiltonski graf.
Predpostavimo sedaj, da trditev velja za n, in dokaˇzimo, da tedaj velja tudi za n+ 1, torej za hiperkocko Qn+1.
Naj bo Q0n ”leva”podhiperkocka (glej Sliko 2.9). Po indukcijski predpostavki Q0n vse- buje hamiltonski cikel, oznaˇcimo ga s C0. Podobno vzemimo hamiltonski cikelC1 v ”de-
sni”podhiperkockiQ1n, pri ˇcemer pazimo, da je hamiltonski cikelC1kar ˇzrcalna slika”hamiltonskega ciklaC0. Naj bostau, v ∈V(C0) sosednji vozliˇsˇci ciklaC0, vozliˇsˇciu0, v0 ∈V(C1) pa sose-
dnji vozliˇsˇci ciklaC1. Glede na konstrukcijo hiperkockeQn+1obstajata povezaviuu0, vv0 ∈ E(Qn+1), s tem pa obstaja hamiltonski cikel oblike: (C0−uv) +uu0+ (C1−u0v0) +vv0.
u
v u'
v'
C0 C1
Slika 2.9: Ilustracija k dokazu Trditve 2.2.
Prav tako so vsi platonski grafi hamiltonski.
tetraeder kocka oktaeder dodekaeder ikozaeder
Slika 2.10: Hamiltonski cikli v platonskih grafih.
Tipiˇcen primer nehamiltonskega grafa pa je Petersenov graf P5,2. Trditev 2.3 Petersenov graf P5,2 ni hamiltonski.
Dokaz. Recimo, da hamiltonski cikel v Petersonovem grafu obstaja, oznaˇcimo ga s H.
Z malo premisleka vidimo, da mora hamiltonski cikel vsebovati sodo mnogo povezav uivi
med zunanjimi ui in notranjimi vi vozliˇsˇci, saj je prihodov v zunanji cikel ravno toliko
kolikor je izhodov. Ker je med zunanjimi ui in notranjimi vi vozliˇsˇci skupno pet povezav, mora hamiltonski cikel vsebovati natanko dve ali natanko ˇstiri od povezav uivi.
u1
u2
u3 u4
u5
v1
v2
v3 v4
v5
u1
u2
u3 u4
u5
v1
v2
v3 v4
v5
u1
u2
u3 u4
u5
v1
v2
v3 v4
v5
Slika 2.11: Ilustracija k dokazu Trditve 2.3.
Poglejmo si najprej primer, glej Sliko 2.11, koHvsebuje natanko ˇstiri povezaveuivi. Brez ˇskode za sploˇsnost naj bodo povezave u1v1, u2v2, u3v3 inu4v4 v H. Iz tega sledi, da sta tudi u4u5 in u5u1 v H, torej u1u2, u3u4 in u5v5 niso v H. Sledi v3v5 in v5v2 v H. Do- bimo 5-cikelu2u3v3v5v2u2. V tem primeru Petersenov graf ne vsebuje hamiltonskega cikla.
u1
u2
u3
u4
u5
v1
v2 v3
v4
v5
u1
u2
u3
u4
u5
v1
v2 v3
v4
v5
u1
u3
u4
u5
v1
v2 v3
v4
v5
Slika 2.12: Ilustracija k dokazu Trditve 2.3.
Torej mora hamiltonski cikel vsebovati natanko dve povezavi uivi. Povazavi uivi morata biti zaporedni, saj bi v nasprotnem primeru hitro dobili primer kot v prvem delu dokaza.
Brez ˇskode za sploˇsnost privzemimo, glej Sliko 2.12, da sta v H povezavi u1v1 in u2v2. Sledi, da je pot u2u3u4u5u1 v H in da u1u2 ni v H (ˇce bi bila u1u2 v H bi spet priˇsli do primera kot v prvem delu dokaza). Torej tudi u3v3, u4v4 inu5v5 niso v H. Sledi, da so v H preostali dve povezavi, ki gredo iz vozliˇsˇc v3, v4 in v5. Torej H vsebuje tudi povezavi v2v4 inv4v1, s tem pa dobimo 8-cikelu1v1v4v2u2u3u4u5u1, ki zakljuˇci dokaz. Torej tudi v tem primeru Petersenov graf ne vsebuje hamiltonskega cikla.
Torej Petersonov graf res nima hamiltonskega cikla.
Petersenov graf pa ima veˇc hamiltonskih poti. Ena od njih je prikazana na sliki 2.13.
Slika 2.13: Primer hamiltonske poti v Petersenovem grafu.
Kljub nehamiltonskosti Petersenovega grafa P5,2 pa nehamiltonskost ne velja kar za vse posploˇsene Petersenove grafe. Precej oˇcitno je, da posploˇseni Petersenovi grafiPn,1,n ≥3, hamiltonski cikel imajo. V sploˇsnem je ta u1u2. . . unvnvn−1. . . v1u1.
u2 u3
u4
u5 u6
v1 v2 v3 v4 v5 v6 u7 u8
v7 v8
u1
Slika 2.14: Primer hamiltonskega cikla v posploˇsenem Petersenovem grafu P8,1.
B. Alspach v ˇclanku [1] dokaˇze pomembno trditev, ki nam pove, kdaj je posploˇseni Pe- tersenov graf hamiltonski.
Trditev 2.4 Posploˇseni Petersenov graf Pn,k (n ≥3 in 0< k < n) je hamiltonski, razen v naslednjih izjemnih primerih:
- Pn,2 'Pn,n−2 'Pn,(n−1)/2 'Pn,(n+1)/2 za n≡5 (mod 6), ter
- Pn,n/2 za n≡0 (mod 4) in n≥8.
POGOJI ZA HAMILTONSKOST GRAFOV
Iskanje potrebnih in zadostnih pogojev za hamiltonskost grafa je pomembno podroˇcje v danaˇsnji teoriji grafov. ˇZal pa ni znan noben ”preprost” postopek, ki bi bil uporaben za vse grafe, saj je ugotavljanje hamiltonskosti eden kljuˇcnih NP-polnih problemov (o njih bomo nekoliko veˇc spregovorili v zadnjem poglavju). V tem poglavju si bomo pogledali nekaj najpomembnejˇsih potrebnih in zadostnih pogojev. Nekoliko veˇc pozornosti bomo namenili P´osevemu izreku in njegovemu dokazu. Na koncu bomo omenili ˇse nekaj pomembnih domnev, s katerimi se matematiki ukvarjajo ˇze vrsto let.
3.1 POTREBNI POGOJI
Izrek 3.1 (Osnovni potrebni pogoj): ˇCe iz grafa G odstranimo k vozliˇsˇc in pri tem graf razpade na veˇc kot k komponent, tedaj graf G ni hamiltonski. ˇCe je komponent veˇc kot k+ 1, potem v grafu G ni niti hamiltonske poti.
Dokaz. Izrek dokaˇzimo s protislovjem. Recimo, da v grafu G obstaja hamiltonski cikel oz. pot. Graf z najmanj povezavami, ki vsebuje hamiltonski cikel oz. pot je kar graf, ki je sam cikel oziroma pot. ˇZe ˇce v takem grafu odstranimo k vozliˇsˇc, cikel razpade na najveˇc k delov (na k delov razpade, kadar odstranimo dve nesosednji vozliˇsˇci), pot pa na najveˇc k+ 1 delov (na k+ 1 delov razpade, ˇce odstranimo dve nesosednji nerobni vozliˇsˇci), torej
27
v vseh ostalih grafih z veˇc povezavami razpade kveˇcjemu na manj delov.
Slika 3.1: Razpad cikla po odstranitvi dveh vozliˇsˇc.
Slika 3.2: Razpad cikla z zgolj eno dodatno povezavo po odstranitvi istih dveh vozliˇsˇc kot na Sliki 3.1.
Vsak od teh delov cikla oziroma poti leˇzi v eni komponenti, na ketere razpade graf, in vsaka komponenta vsebuje vsaj en del cikla. Torej graf res ne more razpasti na veˇc kot k
oz. k+ 1 delov.
Zgled. Z uporabo Izreka 2.5 dokaˇzimo, da skakaˇcev sprehod na ˇsahovnici 4×4 res ne obstaja. Z drugimi besedami, radi bi dokazali, da hamiltonski cikel na grafu, ki ga izriˇse skakaˇc na ˇsahovnici 4×4 ne obstaja. ˇCe iz grafa odstranimo sredinska 4 vozliˇsˇca skupaj s povezavami, dobimo 6 komponent (Slika 3.3). Po Osnovnem potrebnem pogoju graf tako res nima hamiltonskega cikla oziroma ˇse veˇc, graf nima niti hamiltonske poti.
Slika 3.3: Slika k zgledu Izreka 3.1.
Posledica, ki sledi iz Osnovnega potrebnega pogoja, nam pomaga doloˇciti, kdaj dvodelni graf ni hamiltonski.
Posledica 3.2 Naj bo G dvodelni graf z razbitjem V(G) = X ∪Y. ˇCe je |X| 6= |Y|, potem graf G nima hamiltonskega cikla. ˇCe velja ˇse ||X| − |Y|| >1, potem G ne vsebuje niti hamiltonske poti.
Dokaz. Brez ˇskode za sploˇsnost najprej predpostavimo, da je |Y|>|X|.
Dokaˇzimo najprej prvi del posledice: ˇce velja|X| 6=|Y|, potem grafGnima hamiltonskega cikla. Ker je graf G dvodelen, vozliˇsˇca v posamezni mnoˇzici med seboj niso povezana.
Ce torej iz grafaˇ G odstranimo vsa vozliˇsˇca mnoˇzice X, ostanejo le nepovezana vozliˇsˇca mnoˇzice Y. Torej dobimo graf G−X, ki ima ravno |Y| komponent, to pa je veˇc kot je bilo odstranjenih vozliˇsˇc. Po Osnovnem potrebnem pogoju grafGres nima hamiltonskega cikla.
Podobno dokaˇzimo ˇse drugi del posledice: ˇce velja ||X| − |Y|| > 1, potem graf G ne vsebuje niti hamiltonske poti. Ker smo predpostavili |Y| > |X| velja |Y| − |X| > 1 oziroma |Y| > 1 +|X|. ˇCe iz grafa G odstranimo vsa vozliˇsˇca mnoˇzice X, ostanejo le nepovezana vozliˇsˇca mnoˇzice Y, teh pa je veˇc kot 1 +|X|. Po Osnovnem potrebnem pogoju graf G s to lastnostjo nima niti hamiltonske poti.
Na Sliki 3.4 je nekaj primerov dvodelnih grafov, ki nimajo hamiltonskega cikla, saj mnoˇzici dvodelnega razbitja nimata enake moˇci.
K1,4 K2,4
Slika 3.4: Primeri dvodelnih grafov brez hamiltonskega cikla.
Potrebni pogoji za Hamiltonskost grafov niˇc ne govorijo o tem, kdaj graf hamiltonski cikel oziroma pot ima (saj potrebni pogoji niso hkrati tudi zadostni). Na Sliki 3.5 je primer dvodelnega grafa, ki zadoˇsˇca pogoju, da imata mnoˇzici dvodelnega razbitja enako moˇc.
Napaˇcno bi torej lahko sklepali, da tak graf hamiltonski cikel ima, kar pa je oˇcitno, da ni res.
Slika 3.5: Primer dvodelnega grafa z razbitjem enake moˇci in brez hamiltonskega cikla.
Tu lahko omenimo ˇse dejstvo, da imajo vsi polni dvodelni grafi Km,n, kjer m = n, ha- miltonski cikel. Kar je seveda oˇcitno. Ce vozliˇsˇˇ ca prve mnoˇzice dvodelnega razbitja oznaˇcimo z 1n, vozliˇsˇca druge mnoˇzice pa z 2n, kjer n ∈ N, je hamiltonski cikel ravno:
11∼21∼12∼22· · ·1(n−1)∼2(n−1)∼1n∼2n∼11.
...
...
11 12 1(n-1) 1n
21 22 2(n-1) 2n
Km,n
Slika 3.6: Hamiltonski cikel v polnem dvodelnem grafu.
3.2 ZADOSTNI POGOJI
Dobrih zadostnih pogojev za hamiltonskost grafa ni enostavno najti. V tem podpoglavju si bomo pogledali nekaj pomembnih trditev, ki nam povejo, kdaj je graf hamiltonski.
3.2.1 P´ osev izrek
Prvi tak pomemben izrek je P´osev izrek [17] iz leta 1962. Preden povemo, kaj ta izrek trdi, omenimo ˇse dve oˇcitni lastnosti v zvezi s hamiltonskostjo:
• Ce hamiltonskemu grafu dodamo neko povezavo, je dobljeni graf ˇse vedno hamil-ˇ tonski.
• Ce hamiltonskemu ciklu odstranimo natanko eno povezavo, dobimo hamiltonskoˇ pot.
Ideje dokaza, ki sledi, so povzete po Hararyju [11].
Izrek 3.3 (P´osa, 1962) Naj bo G graf na n ≥ 3 vozliˇsˇcih in naj bo Vk mnoˇzica vseh tistih vozliˇsˇc, katerih stopnja ne presega k. ˇCe za vsak 1≤k ≤ bn−12 c velja
|Vk| ≤
( k−1, 1≤k < n−12
k, k = n−12 (n liho) potem G vsebuje hamiltonski cikel.
Dokaz.
Pa recimo, da izrek ne drˇzi, to pomeni, da obstaja tak graf nan≥3 vozliˇsˇcih, ki zadoˇsˇca pogoju izreka in ni hamiltonski. Ker je ˇstevilo grafov na n vozliˇsˇcih konˇcno, obstaja tak najveˇcji graf G, ki ni hamiltonski. Najveˇcji graf je tu miˇsljen kot graf, ki ima najveˇcje ˇstevilo povezav. Za zaˇcetek si poglejmo tri lepe lastnosti, ki jih ima tak graf G.
(1) Najprej pokaˇzimo, da ˇce grafu G dodamo poljubno povezavo uv ∈E(G), nastali graf G+uv ˇse vedno zadoˇsˇca pogoju izreka. Oˇcitno je, da za mnoˇzice Vk velja
V1 ⊆V2 ⊆... Vk ...⊆Vl, kjer je l =bn−12 c
Ceˇ u /∈ Vk se mnoˇzice V1, V2, ... Vl ne spremenijo. Zatorej naj bo u ∈ Vk. Dodatna povezava uv poveˇca stopnjo vozliˇsˇcau natanko za 1. V primeru, ko je k =l, je u∈Vn+1
2
v grafu G+uv, in ni kaj preverjati. Torej je k < l in u ∈ Vk+1 v grafu G+uv. Za graf G+uv velja
V1 ⊆V2 ⊆... Vk−1 ⊆ {Vk\{u}} ⊆ {Vk+1 ∪ {u}} ⊆Vk+2 ...⊆Vl. Oznaˇcimo {Vk\{u}}=Vk0 in {Vk+1 ∪ {u}}=Vk+10 . Od tod sledi, da je
|Vk0|=|Vk| −1, torej
|Vk+10 |=|Vk+1|.
Zato |Vk0| ter |Vk+10 |ˇse vedno zadoˇsˇcata pogoju. Podobno pokaˇzemo ˇse za drugo krajiˇsˇce v povezave uv. Sledi, da graf G+uv res ˇse vedno zadoˇsˇca pogoju izreka. Ker pa je G najveˇcji nehamiltonski graf, ki zadoˇsˇca pogoju, bi dodatna povezava pomenila, da je G+uv hamiltonski. Zato v grafuGmed vsakima dvema nesosednjima vozliˇsˇcema obstaja hamiltonska pot.
(2) Pokaˇzimo sedaj, da je vsako vozliˇsˇce stopnje vsaj (n−1)2 sosednje z vsakim vozliˇsˇcem stopnje vsaj n2. Brez ˇskode za sploˇsnost predpostavimo, da za nesosednji vozliˇsˇciv1, vn∈ V(G) velja deg(v1)≥ (n−1)2 in deg(vn)≥ n2. Ker je Gnajveˇcji nehamiltonski graf, po (1) obstaja hamiltonska pot v1v2. . . vn, ki povezujev1 in vn.
V grafu G bi obstajal hamiltonski cikel, ˇce obstajata taki zaporedni vozliˇsˇci vi−1 in vi na poti od v1 do vn, da je vozliˇsˇce vi−1 sosednje z vozliˇsˇcem vn in vozliˇsˇce vi sosednje z vozliˇsˇcem v1. Hamiltonski cikel bo v tem primeru ravno
v1P vi−1, vi−1vn, vnP vi, viv1 (kjer P predstavlja del hamiltonske poti).
v1 vi-1 vi vn
... ...
Slika 3.7: Ilustracija k dokazu P´osevega izreka.
Ker pa G po predpostavki ni hamiltonski, vozliˇsˇce vn ne sme biti sosednje nobenemu predhodniku sosedov vozliˇsˇcav1 na hamiltonski poti odv1 dov2, niti ne sme biti sosednje vozliˇsˇcuv1. Ker deg(v1)≥ (n−1)2 , dobimo
deg(vn)≤n−1−deg(v1)< n2.
To pa je v protislovju s predpostavko, da je deg(vn) ≥ n2. Torej morata biti v1 in vn res sosednji.
(3) Iz tega po (2) sledi, da v primeru, ko za vsako vozliˇsˇce v ∈ V(G) velja deg(v) ≥ n2, sta vsaki dve vozliˇsˇci grafa G sosednji, torej je G polni graf Kn. S tem pa pridemo v protislovje, saj je Kn hamiltonski za vsak n ≥3.
Dokazali smo nekatere lepe lastnosti grafa G, ki nas bodo v nadaljevanju pripeljale do protislovja pri dokazu izreka.
Po (3) sledi, da v grafuGobstaja vozliˇsˇce s stopnjo manjˇse od n2. Torej v grafuGobstaja vozliˇsˇce v s stopnjo deg(v) ≤ bn−12 c. Naj bo 1 ≤m ≤ bn−12 c najveˇcja stopnja med vsemi takimi vozliˇsˇci. Izberimo vozliˇsˇcev1 tako, da je deg(v1) =m.
Vozliˇsˇca stopnje 1 ≤ m ≤ bn−12 c tvorijo mnoˇzico Vm. Ker graf G zadoˇsˇca pogoju izreka sledi |Vm| ≤ m, kjer je enakost lahko doseˇzena, ko je n lih in m = n−12 . To pomeni, da ima graf G najveˇc n−12 vozliˇsˇc stopnje najveˇc n−12 . Od tod sledi, da mora imeti graf G veˇc kot n−12 vozliˇsˇc stopnje veˇc kot n−12 , torej vsaj n2 vozliˇsˇc stopnje vsaj n2. Zatorej mora obstajati neko vozliˇsˇce, recimovn, stopnje vsaj n2, ki ni sosednje zv1. Ker pav1 invnnista sosednji in imavn stopnjo vsaj n2, mora biti po (2) stopnjav1 manjˇsa od n−12 , kar pomeni, da je m < n−12 . Po predpostavki sledi, da je |Vm| ≤ m−1, to je graf G ima manj kot m vozliˇsˇc stopnje najveˇc m. Ker v1 in vn nista sosednji, po (1) obstaja hamiltonska pot v1v2. . . vn. Kot v (2) vozliˇsˇce vn ne sme biti sosednje nobenemu izmed m predhodnikov sosedov vozliˇsˇcav1. Predhodnikov sosedov vozliˇsˇca v1 je ravnom in ker je|Vm| ≤m−1, sledi, da je vsaj en od teh predhodnikov, oznaˇcimo ga z v0, stopnje vsaj n2. Po (3) sledi, da morata biti nesosednji vozliˇsˇci v0 invn povezani in po (2) mora obstajati hamiltonski cikel v grafuG, kar pa nas je pripeljalo do protislovja.
S tem smo dokazali, da najveˇcji graf, ki zadoˇsˇca pogoju izreka in ni hamiltonski, ne obstaja. Zato je vsak graf, ki zadoˇsˇca pogoju izreka, hamiltonski.
a b
c
d e
f
g
h
Slika 3.8: Primer grafa za ponazoritev P´osevega izreka.
Zgled. Graf na Sliki 3.8 ima 8 vozliˇsˇc. Preverimo, ˇce res za vsak 1 ≤ k ≤ b72c velja
|Vk| ≤k−1.
1. Za k = 1 je |V1| ≤0. Nobeno vozliˇsˇce ni stopnje najveˇc ena.
2. Za k = 2 je |V2| ≤ 1. Ker je natanko eno vozliˇsˇce stopnje dva, skupaj z 1. velja
|V2| ≤2.
3. Za k = 3 je |V3| ≤2. Ker nobeno vozliˇsˇce ni stopnje tri, skupaj z 2. velja |V3| ≤2.
Graf res izpolnjuje pogoj P´osejevega izreka, zato je hamiltonski.
a b
c
d e
f
g
h
Slika 3.9: Hamiltonski cikel na grafu iz slike 3.8.
Predvsem je tu potrebno poudariti, da je P´osev izrek zgolj zadosten in ne tudi potreben pogoj, kar pomeni, da graf lahko vsebuje hamiltonski cikel, tudi ˇce ne izpolnjuje pogoja P´osevega izreka. Primer takega grafa je prikazan na Sliki 3.10.
Slika 3.10: Primer grafa, ki ne izpolnjuje pogoja P´osevega izreka in vsebuje hamiltonski cikel.
3.2.2 Orejev izrek in Diracov izrek
Pomembni posledici P´osevega izreka sta Orejev izrek [15] in Diracov izrek [7]. ˇSe prej si poglejmo trditev, ki nam bo pomagala pri dokazu teh dveh izrekov.
Trditev 3.4 Naj bo G graf na n ≥ 3 vozliˇsˇcih in naj za vsaki dve nesosednji vozliˇsˇci u, v ∈ V(G) velja deg(u) + deg(v)≥n. Graf G+uv je hamiltonski natanko tedaj, ko je G hamiltonski.
Dokaz.
(⇐) Dokaz v to smer je oˇciten.
(⇒) Za laˇzjo predstavljivost le nekoliko spremenimo oznake vozliˇsˇc. Naj bosta v1 in vn taki nesosednji vozliˇsˇci grafa G, da velja deg(v1) + deg(vn) ≥ n. Predpostavimo sedaj, da je graf G+v1vn hamiltonski. Radi bi dokazali, da je tedaj tudi graf G hamiltonski.
S C oznaˇcimo hamiltonski cikel v grafu G+v1vn. ˇCe v C ni povezave v1vn, potem jeC tudi hamiltonski cikel v grafu G, in smo dokaz konˇcali. Zato privzemimo, da je povezava v1vn na ciklu C. ˇCe s cikla C odstranimo eno povezavo, dobimo hamiltonsko pot. Brez ˇskode za sploˇsnost odstranimo povezavo v1vn, torej je P = C−v1vn hamiltonska pot v grafu G+v1vn in tudi hamiltonska pot v grafu G. Kot pri dokazu P´osevega izreka, bo tudi tokrat v grafu Gobstajal hamiltonski cikel, ˇce obstajata taki zaporedni vozliˇsˇci vi−1
in vi na poti od v1 do vn, da je vozliˇsˇce vi−1 sosednje vozliˇsˇcu vn in vozliˇsˇce vi sosednje vozliˇsˇcuv1.
Torej ˇzelimo dokazati le, da taki vozliˇsˇci obstajata. Po predpostavki ima vozliˇsˇcev1 ravno deg(v1) sosedov. Ker vozliˇsˇce vn ni sosednje nobenemu predhodniku sosedov vozliˇsˇca v1, je stopnja vozliˇsˇcavn najveˇcn−1−deg(v1). Iz tega sledi deg(v1) + deg(v2)≤n−1, kar
pa je v protislovju s predpostavko, da velja deg(u) + deg(v)≥n.
S tem smo dokazali, da taki vozliˇsˇci obstajata, torej je graf Gres hamiltonski graf.
Izrek 3.5 (Orejev izrek, 1960) Naj bo G graf na n ≥ 3 vozliˇsˇcih in naj za poljubni nesosednji vozliˇsˇci u, v ∈V(G) velja deg(u) + deg(v)≥n. Potem je graf G hamiltonski.
Dokaz. Grafu Gdodajamo povezave toliko ˇcasa, da dobimo polni graf:
G0 =G, G1 =G0+u0v0, G2 =G1 +u1v1, . . ., Gp =Kn
Ker grafG0 zadoˇsˇca pogoju, sledi da zadoˇsˇcajo pogoju tudi vsi grafiG1, G2, ..., Gp. Ker je grafGp polni graf, je hamiltonski. Iz Trditve 3.2 sledi, da so tako vsi grafiGi hamiltonski.
Torej je G res hamiltonski graf.
Izrek 3.6 (Diracov izrek, 1952) Naj bo G graf na n ≥ 3 vozliˇsˇcih in naj za vsako vozliˇsˇce w velja deg(w)≥ n2, potem je G hamiltonski graf.
Dokaz. Po predpostavki za vsako vozliˇsˇce w velja deg(w) ≥ n2. Za poljubni nesosednji vozliˇsˇci u, v ∈V(G) torej velja deg(v) + deg(v)≥ n2 + n2 = n. Po Orejevem izreku sledi,
da jeG hamiltonski graf.
d a
e f
c b
Slika 3.11: Primer grafa za ponazoritev Diracovega izreka.
Zgled. Graf G na Sliki 3.11 je kubiˇcen graf in ima 6 vozliˇsˇc. Torej velja deg(w) = 3 za vsako vozliˇsˇce w ∈ V(G). Graf res zadoˇsˇca pogoju Diracovega izreka, saj za vsako vozliˇsˇce w∈V(G) velja deg(w)≥ |V(G)|2 , torej graf vsebuje hamiltonski cikel.
d a
e f
c b
Slika 3.12: Hamiltonski cikel na grafu iz Slike 3.11.
d c
a
b e
Slika 3.13: Primer grafa za ponazoritev Orejevega izreka.
Zgled. Za grafGna Sliki 3.13 ne moremo uporabiti Diracovega izreka, saj velja deg(a) = 2 < |V(G)|2 = 52. Zdi pa se, da bi Orejev izrek lahko veljal. Preverimo, ˇce res za vsaki nesosednji vozliˇsˇciu, v ∈V(G) velja deg(u)+deg(v)≥ |V(G)|. Nesosednji vozliˇsˇci vozliˇsˇca astacindin res velja deg(a) + deg(c) = 2 + 3 = 5 =|V(G)|in deg(a) + deg(d) = 2 + 3 = 5 =|V(G)|. Vozliˇsˇceb je sosednje z vsemi ostalimi vozliˇsˇci. Vozliˇsˇcic ind sta nesosednji z vozliˇsˇcem a in oba pogoja smo ˇze preverili. Vozliˇsˇce d pa je prav tako sosednje vsemi ostalim vozliˇsˇcem. Graf na Sliki 3.13 torej zadoˇsˇca Orejevemu pogoju, kar pomeni, da je hamiltonski.
d c
a
b e
Slika 3.14: Hamiltonski cikel na grafu iz Slike 3.13.
Pokaˇzimo sedaj, da sta Orejev in Diracov izrek res posledica P´osevega izreka, natanˇcneje, da iz P´osevega izreka sledi Orejev izrek, iz Orejevega izreka pa Diracov izrek. To pomeni,
da ˇce graf zadoˇsˇca pogoju Diracovega izreka, potem zadoˇsˇca tudi pogoju Orejevega in P´osevega izreka. ˇCe pa graf zadoˇsˇca pogoju P´osevega izreka, pa ni nujno, da tudi Oreje- vemu in Diracovemu.
Kar hitro najdemo primer grafa, ki zadoˇsˇca pogoju P´osevega izreka in ne zadoˇsˇca pogoju Orejevega izreka. Tak primer grafa je predstavljen na Sliki 3.8, za katerega smo ˇze do- kazali, da zadoˇsˇca pogoju P´osevega izreka. ˇCe bi graf iz Slike 3.8 zadoˇsˇcal tudi pogoju Orejevega izreka, bi moralo za vsaki dve nesosednji vozliˇsˇci u, v ∈ V(G) grafa G veljati deg(u) + deg(v) ≥ |V(G)|, vendar za nesosednji vozliˇsˇci h in a iz grafa na Sliki 3.8 velja deg(h) + deg(a) = 6, kar je manj kot ima graf iz Slike 3.8 vozliˇsˇc. Torej smo naˇsli graf, ki zadoˇsˇca pogoju P´osevega izreka in ne zadoˇsˇca pogoju Orejevega izreka. Ne obstaja pa graf, ki bi zadoˇsal pogoju Orejevega izreka in ne bi zadoˇsˇcal pogoju P´osevega izreka. S protislovjem dokaˇzimo, da tak graf res ne obstaja.
Trditev 3.7 Naj bo G povezan graf na n ≥ 3 vozliˇsˇcih, ki zadoˇsˇca pogoju Orejevega izreka. Potem G zadoˇsˇca tudi pogoju P´osevega izreka.
Dokaz. Recimo, da trditev ne drˇzi. Naj boG graf, ki zadoˇsˇca pogoju Orejevega izreka, ne zadoˇsˇca pa pogoju P´osevega izreka. V grafu G mora torej za poljubni nesosednji vozliˇsˇci u, v ∈V(G) veljati deg(u) + deg(v) ≥n, prav tako pa mora v grafu G obstajati 1≤k≤ bn−12 c, za katerega je
|Vk|>
( k−1, 1≤k < n−12
k, k = n−12 (n liho)
(1) ˇCe je n liho in je k = n−12 , mora biti |Vk| > k, torej |Vk| ≥ k + 1. Kar pomeni, da mora imeti grafG vsaj k+ 1 vozliˇsˇc stopnje najveˇc k.
Naj tvorijo vozliˇsˇca stopnje najveˇck mnoˇzico A, vozliˇsˇca stopnje veˇc odk pa mnoˇzicoB.
Po predpostavki je|A| ≥k+ 1, torej|B| ≤n−k−1. ˇCe bi mnoˇzica Avsebovala veˇc kot k+ 1 vozliˇsˇc, bi med temi vozliˇsˇci obstajali dve takˇsni, npr. a1 in a2, ki nista povezani med seboj. Sledi deg(a1) + deg(a2) ≤ 2k = n−12 + n−12 < n, kar pa je v protislovju s
pogojem Orejevega izreka.
A B
|A| >= k + 1 deg(a) <= k
|B| <= n - k - 1 deg(b) > k
Slika 3.15: Ilustracija k dokazu Trditve 3.7.
Iz tega sledi, da mora mnoˇzicaA vsebovati natankok+ 1 vozliˇsˇc in, da morajo biti vsa ta vozliˇsˇca med seboj povezana, saj bi sicer obstajali dve taki nepovezani vozliˇsˇci,a1, a2 ∈A, za kateri bi veljalo deg(a1) + deg(a2)≤ 2k = 2n−12 < n. Torej morajo imeti vsa vozliˇsˇca mnoˇzice A stopnjo natanko k. Ker pa je to najveˇcja stopnja, ki jo ta vozliˇsˇca po predpo- stavki lahko imajo, to pomeni, da vozliˇsˇca iz mnoˇzice A ne smejo biti povezana z vozliˇsˇci iz mnoˇzice B. S tem pa dobimo nepovezan graf.
A B
|A| = k + 1 deg(a) = k
|B| = n - k - 1 deg(b) > k
Slika 3.16: Ilustracija k dokazu Trditve 3.7.
(2) Naj bo 1≤k < n−12 . Potem je|Vk|> k−1, torej|Vk| ≥k. To pomeni, da mora imeti graf Gvsaj k vozliˇsˇc stopnje najveˇc k.
Naj kot v primeru (1) vozliˇsˇca stopnje najveˇcktvorijo mnoˇzicoA, vozliˇsˇca stopnje veˇc od k pa mnoˇzico B. ˇCe bi mnoˇzica A vsebovala veˇc kot k vozliˇsˇc, bi priˇsli v protislovje kot v (1). Torej mora mnoˇzica A vsebovati natanko k vozliˇsˇc in vsa morajo biti med seboj povezana, sicer bi priˇsli v protislovje kot v (1). Kar pomeni, da je stopnja teh vozliˇsˇc k−1 oziroma k.
