UNIVERZA V LJUBLJANI PEDAGOˇ SKA FAKULTETA
NUˇ SA BUTALA
HAMILTONSKA RAZ ˇ CLENITEV GRAFA IN OTROˇ SKI PLESI
DIPLOMSKO DELO
UNIVERZA V LJUBLJANI PEDAGOˇ SKA FAKULTETA
ˇSTUDIJSKI PROGRAM: DVOPREDMETNI U ˇCITELJ SMER: MATEMATIKA IN RA ˇCUNALNIˇSTVO
NUˇ SA BUTALA
Mentor: doc. dr. BOˇ STJAN KUZMAN
HAMILTONSKA RAZ ˇ CLENITEV GRAFA IN OTROˇ SKI PLESI
DIPLOMSKO DELO
Kazalo
1 Uvod 1
2 Osnovni pojmi in definicije 2
2.1 Osnovni pojmi . . . 2
2.2 Hamiltonske poti in cikli . . . 4
2.3 Prirejanja . . . 5
2.4 Faktorji in faktorizacija grafa . . . 9
3 Lucasove uganke in faktorizacija 13 3.1 Hamiltonska faktorizacija grafa K2n+1 . . . 13
3.2 Hamiltonska faktorizacija grafa Kn,n . . . 17
3.3 Hamiltonska faktorizacija grafa K2n−nK2 . . . 19
3.4 1-faktorizacija grafa K2n . . . 21
3.5 1-faktorizacija grafa Kn,n . . . 23
4 Sorodni rezultati in odprti problemi 25
Slike
1 Graf in trije podgrafi . . . 2
2 Poln graf K5, poln dvodelni grafK3,3, cikel C5 in pot P5 . . . 3
3 Primer nehamiltonskega in hamiltonskega grafa . . . 4
4 Graf G premore hamiltonski cikel . . . 5
5 Prirejanja v grafih . . . 6
6 Vozliˇsˇce v ∈H je povezano z vozliˇsˇcem w∈S . . . 7
7 Grafa Gin G0 . . . 7
8 e1 in e2 pripadata istemu ciklu. Vir: [3] . . . 8
9 P3 ne premore popolnega prirejanja . . . 8
10 Zgledi n-faktorjev grafa K6 zan = 0,1,2,3 . . . 9
11 6 razliˇcnih hamiltonskih faktorizacij grafa K5. Vir: [10] . . . 10
12 Zgled nehamiltonske 2-faktorizacije . . . 10
13 1-faktorizacija Desarguesovega grafa. Vir: [11] . . . 10
14 Razˇclenitev Petersenovega grafa . . . 12
15 Kvazi-hamiltonska razˇclenitev grafa K6 . . . 12
16 Postavitev otrok pri plesih . . . 13
17 Pomoˇzna shema . . . 14
18 Konstrukcija s tabelo za prvi ples . . . 14
19 Hamiltonska cikla grafa K2n+1 za i= 1 in i= 2 . . . 15
20 Hamiltonski cikli grafa K11 . . . 16
21 Razporeditev plesalcev . . . 18
22 Razˇclenitev grafa K4,4 na hamiltonska cikla . . . 18
23 Pomoˇzna shema in razporeditev plesalcev za drugi ples . . . 20
24 Razˇclenitev grafa K6 na tri cikle in 1-faktor . . . 21
25 Razpored deklet za prvi sprehod . . . 22
26 1-faktorizacija grafa K6 . . . 23
27 1-faktorizacija grafa K3,3 . . . 24
Povzetek
Hamiltonska faktorizacija grafa je 2-faktorizacija grafa na hamiltonske cikle. V di- plomskem delu se osredotoˇcimo na iskanje hamiltonske razˇclenitve ali faktorizacije grafov K2n+1,Kn,n inK2n−nK2 ter iskanja 1-faktorizacije grafov K2n inKn,n. Pred tem na zaˇcetku definiramo sploˇsne definicije in grafovske lastnosti, ki jih po- trebujemo za nadaljnje razumevanje dela. To so hamiltonske poti, prirejanja ter faktorji. V razdelku o prirejanjih dokaˇzemo Tutteov izrek, v razdelku o faktorjih in faktorizaciji pa, kdaj je graf 1-faktorabilen oziroma 2-faktorabilen. Iskanje faktori- zacije v tretjem poglavju prikaˇzemo na primeru otroˇskih plesov, kot jih je predstavil Edouard Lucas. Vse ponazorimo s preprostimi primeri. Za nekatere primere izde-´ lamo programsko kodo, ki problem faktorizacije reˇsi za konkretenn.
Kljuˇcne besede: faktor, 1-faktorizacija, 2-faktorizacija, hamiltonska faktorizacija
Abstract
Hamiltonian factorization of a graph is a 2-factorization of the graph into Hamilto- nian cycles. In this thesis we focus on finding Hamiltonian factorization or decom- position of graphsK2n+1,Kn,n,K2n−nK2 and finding 1-factorization of graphs K2n
and Kn,n.
On start some general definitions and properties of a graph are needed to further understand the work. Among these are Hamiltonian paths, matchings and factors.
In subsection on Matchings we prove Tutte’s theorem, in subsection of factors and factorization we define when the graph is 1-factorable or 2-factorable. In section three we present finding factorization on the example of children’s dances, as they were presented by ´Edouard Lucas. We illustrate these results with simple examples.
For some examples we create a program code that solves the problem of factorization for concrete n.
Keywords: factor, 1-factorization, 2-factorization, Hamiltonian factorization
1 Uvod
Naloge iz podroˇcja razvedrilne matematike lahko obiˇcajno reˇsujemo brez globljega znanja matematike, kljub temu pa se ob njih lahko razvijejo nove matematiˇcne teo- rije. Eden od takih ˇstevilnih primerov je problem enakomernega razporejanja otrok pri plesu v krogu katerega je francoski matematikEdouard Lucas´ predstavil v enem izmed svojih del.
Liho ˇstevilo otrok pleˇse v krogu, po vsakem plesu pa se malo premeˇsajo. Ali lahko sestavimo tako zaporedje razporeditev pri plesih, da se bosta poljubna dva plesalca natanko enkrat drˇzala za roko?
To je naloga, ki jo lahko reˇsimo s poskuˇsanjem na majhnem ˇstevilu otrok in za reˇsitev s konkretnimi ˇstevilkami ne potrebujemo znanja iz teorije grafov. Lahko pa jo posploˇsimo na problem iskanja hamiltonske faktorizacije grafa K2n+1 in reˇsimo za poljuben n. Lucas v svoji knjigi reˇsitev naloge pripisuje Felixu Waleckemu, pro- fesorju matematike na pariˇskem liceju Condorcet ([12]), o katerem ni dosti znanega, od tod se ustrezni izrek o hamiltonski razˇclenitvi polnih grafov lihega reda obiˇcajno imenuje Waleckijev izrek. V diplomskem delu se bom ukvarjala z neusmerjenimi grafi, lahko pa bi nalogo posploˇsili tudi na usmerjene grafe. Takrat bi govorili o Waleckijevih turnirjih. Pri tem je turnir usmerjeni graf, ki ga dobimo tako, da povezavam neusmerjenega polnega grafa doloˇcimo orientacijo. Walecki je poiskal konstrukcijo, kako graf Kn razˇclenimo na hamiltonske cikle, Lucas pa jo je kasneje predstavil in zapisal.
V diplomskem delu bom najprej predstavila lastnosti grafov, izreke in definicije, ki so potrebni za razumevanje dela. V osrednjem delu bom predstavila ˇstiri Luca- sove uganke, ki jih bom naprej prikazala na naˇcin, kakrˇsnega je predstavil ´Edouard Lucas v svojem delu, nato pa jih bom opisala v jeziku teorije grafov ter za vsako poiskala ustrezno hamiltonsko faktorizacijo ali pa 1-faktorizacijo. Dodala bom tudi peto uganko, pri kateri bom pokazala, da obstaja 1-faktorizacija polnega dvodel- nega grafaKn,n. Nekaterim ugankam bom priloˇzila tudi programsko kodo, izdelano v programskem jeziku Python, s pomoˇcjo katere lahko izpiˇsemo ˇzeleno faktorizacijo izbranega grafa.
2 Osnovni pojmi in definicije
V tem poglavju bom ponovila osnovne pojme in lastnosti grafov, ki jih bo bra- lec potreboval za laˇzje razumevanje diplomskega dela. Definicije bom ponazorila z enostavnimi primeri. Poglavje je povzeto po virih [2], [3], [5], [7] in [9].
2.1 Osnovni pojmi
V diplomski nalogi bom obravnavala predvsem neusmerjene grafe, torej take, kjer povezave nimajo podane usmeritve. Prav tako ne bomo dopuˇsˇcali veˇckratnih pove- zav med istim parom vozliˇsˇc.
Definicija. Graf G = (V(G), E(G)) je urejeni par mnoˇzic, kjer je V(G) nepra- zna mnoˇzica vozliˇsˇc grafa G, E(G) pa mnoˇzica povezav grafa G. Pri tem je vsaka povezava e ∈ E(G) neurejen par vozliˇsˇc, torej e = {u, v} ⊂ V(G), kar krajˇse piˇsemo kar z e = uv. Povezavo oblike {v,v} imenujemo zanka. Graf brez zank in veˇckratnih povezav med istim parom vozliˇsˇc imenujemo enostaven graf. Kar- dinalnost mnoˇziceV(G) imenujemoredgrafaG. Graf jekonˇcen, ˇce ima konˇcen red.
V nadaljevanju naloge bo izraz graf vselej pomenil konˇcen enostaven graf, more- bitne izjeme bodo posebej poudarjene.
Definicija. Naj bosta u in v vozliˇsˇci v grafu G. Ce medˇ u in v obstaja pove- zava e, potem sta u in v sosednji. Reˇcemo tudi, da sta u in v krajiˇsˇci povezave e = uv. ˇStevilo povezav, ki vsebujejo vozliˇsˇce u, imenujemo stopnja vozliˇsˇca u.
Oznaˇcimo jo z deg(u). V primeru, da imajo vsa vozliˇsˇca grafa enako stopnjo, je graf regularen, tedaj govorimo tudi o stopnji grafa. ˇCe je stopnja vseh vozliˇsˇc v regularnem grafu enaka r, je to r-regularen graf.
Definicija. Graf H je podgraf grafa G, ˇce velja V(H)⊆ V(G) inE(H)⊆ E(G).
Ce veljaˇ V(H) =V(G), potem jeH vpeti podgraf grafaG. PodgrafH jeinduci- rani podgraf grafaG, ˇce njegova mnoˇzica povezav vsebuje natanko tiste povezave iz grafaG, ki imajo obe krajiˇsˇci vH, torej, ˇce jeE(H) = {{u, v} ∈E(G)|u, v ∈V(H)}.
Ce jeˇ S ⊆V(G) neka podmnoˇzica vozliˇsˇc grafa G, potem inducirani podgrafH ⊆G z mnoˇzico vozliˇsˇcV(H) = S oznaˇcimo z G[S].
Primer. Poglejmo si zgled grafa in podgrafov.
Slika 1: Graf in trije podgrafi
2
Na Sliki 1 so prikazani graf G reda 5 z mnoˇzico vozliˇsˇc V(G) = {a, b, c, d, e} in mnoˇzico povezav E(G) ={ab, ac, ad, ae, bc, cd, de} ter trije njegovi podgrafi H1, H2 in H3. Pri tem je podgraf H1 vpeti podgraf grafa G, saj velja V(H1) ⊆ V(G) in E(H1) ⊆ E(G). Podgraf H2 je inducirani podgraf v G, velja H2 = G[S], kjer je S={a, b, c, d}. Graf H3 pa ni podgraf grafa G, saj ne veljaE(H3)⊆E(G).
V nadaljevanju bomo namesto graf G= (V(G), E(G)) zapisali zgolj G= (V, E), ˇce bo iz konteksta razvidno, za katere mnoˇzice gre.
Poznamo razliˇcne vrste grafov. V diplomskem delu bom potrebovala predvsem eno- stavne, dvodelne in polne grafe, polne dvodelne grafe, cikle, poti ter regularne grafe, zato jih definirajmo.
Definicija.Potredanje graf z mnoˇzico vozliˇsˇcV ={v1, ..., vn}in mnoˇzico povezav E = {vivi+1 | i = 1, ..., n−1}. Pot reda n ima n−1 povezav, oznaˇcimo jo s Pn. Cikel reda n, n ≥ 3, pa je graf z isto mnoˇzico vozliˇsˇc in dodatno povezavo, torej E ={vivi+1 | i= 1, ..., n−1} ∪ {vnv1}. Cikel redan oznaˇcimo sCn.
Definicija. Graf G = (V, E) je dvodelen, ˇce lahko njegovo mnoˇzico vozliˇsˇc raz- bijemo na dve disjunktni neprazni podmnoˇziciAinB tako, da vsaka povezava grafa Gpovezuje po eno vozliˇsˇce iz podmnoˇzice A z enim izmed vozliˇsˇc podmnoˇzice B.
Definicija. Graf G reda n imenujemo poln graf, ˇce sta njegovi poljubni razliˇcni vozliˇsˇci povezani, torej, ˇce je E(G) = {uv|u, v ∈ V(G), u 6= v}. Poln graf reda n oznaˇcimo s Kn. Dvodelni graf G z razbitjem vozliˇsˇc V = A∪B, A∩B = ∅, ime- nujemopoln dvodelni graf, ˇce velja, da je vsako vozliˇsˇce iz A povezano z vsakim vozliˇsˇcem iz B z natanko eno povezavo. Poln dvodelni graf oznaˇcimo s Km,n, kjer stam=|A| inn =|B| moˇci ustreznih podmnoˇzic vozliˇsˇc.
Primer. Na Sliki 2 so predstavljeni poln graf K5, poln dvodelni graf K3,3, cikel C5 in pot P5.
Slika 2: Poln graf K5, poln dvodelni grafK3,3, cikel C5 in pot P5
Graf K5 je poln graf reda 5 in je regularen, saj so vsa njegova vozliˇsˇca stopnje 4.
GrafK3,3 je poln dvodelni graf reda 6 in je prav tako regularen, saj so vsa njegova vozliˇsˇca stopnje 3. Prav tako je regularen grafC5, ki ima 5 vozliˇsˇc stopnje 2. Graf P5, ki je pot, pa ni regularen, saj ima dve vozliˇsˇci, ki sta stopnje 1, vsa ostala pa so stopnje 2.
2.2 Hamiltonske poti in cikli
V nadaljevanju bom definirala hamiltonske poti in cikle, ki jih bo bralec potreboval za nadaljnje razumevanje diplomske naloge. Brez dokazov bom podala tudi nekaj kriterijev za hamiltonskost grafa ter jih podkrepila z nekaj zgledi.
Definicija. Pot grafa G, ki obiˇsˇce vsa vozliˇsˇca grafa G se imenuje Hamiltonova oziroma hamiltonska pot. Cikel grafa G, ki vsebuje vsa vozliˇsˇca grafa G pa je Hamiltonov oziroma hamiltonski cikel.
Definicija. Graf G je hamiltonski, ˇce vsebuje hamiltonski cikel, torej, ˇce obstaja zaporedje razliˇcnih paroma sosednjih vozliˇsˇc, ki vsebuje vsa vozliˇsˇca grafa.
Primer. Poglejmo si zgled nehamiltonskega in hamiltonskega grafa.
Slika 3: Primer nehamiltonskega in hamiltonskega grafa
GrafK1,3ni hamiltonski, saj na njem ne moremo poiskati nobenega cikla, poslediˇcno tudi hamiltonskega ne. V grafu K4 pa lahko poiˇsˇcemo hamiltonski cikel, na primer (ef ghe), zato je ta graf hamiltonski.
Problem iskanja hamiltonskega cikla je v sploˇsnem algoritmiˇcno izredno zahteven, pravimo tudi, da je NP poln. Poznamo razliˇcne kriterije, ki dajejo zadostni pogoj za hamiltonskost. Tri izmed njih bom podala kot izreke brez dokazov, podkrepljene s preprostim zgledom. Dokaz izrekov je naveden denimo v [2] in [3].
Izrek (Diracov kriterij za hamiltonskost). Naj bo G graf reda n ≥ 3. ˇCe za po- ljubno vozliˇsˇcev velja deg(v)≥ n2, potem je G hamiltonski.
Izrek (Orejev kriterij za hamiltonskost). Ce jeˇ G graf reda n ≥ 3 tak, da za po- ljuben par nesosednih vozliˇsˇcu, vveljadeg(u)+deg(v)≥n, potem jeGhamiltonski.
Izrek (P´osev kriterij za hamiltonskost). Naj bo G graf reda n ≥ 3. Ce za vsakˇ k, 1 ≤k < n−12 , velja, da ima G manj kot k vozliˇsˇc stopnje najveˇc k in v primeru, da jen lih, velja ˇse, da ˇstevilo vozliˇsˇc stopnje najveˇc n−12 ne presega n−12 , potem G premore hamiltonski cikel.
Znano je, da je P´osev kriterij najmoˇcnejˇsi od treh naˇstetih, saj lahko iz njega izpe- ljemo Orejev in Diracov kriterij kot posebna primera.
4
Primer. Poglejmo si grafGnaSliki 4, ki premore hamiltonski cikel. Preverimo, ali zadoˇsˇca kateremu od prej omenjenih kriterijev za hamiltonskost.
Slika 4: GrafG premore hamiltonski cikel
Iz Slike 4 je razvidno, da graf G premore hamiltonski cikel ABCDEA. Poglejmo, kako je s kriteriji za hamiltonskost grafa. Za Diracov izrek velja, da mora biti sto- pnja poljubnega vozliˇsˇca veˇcja ali enaka n2. Stopnja vozliˇsˇcaB je v tem grafu enaka 2, torej z Diracovim kriterijem za ta graf ne moremo potrditi, da je hamiltonski.
Da bi pokazali hamiltonskost grafa po Orejevem kriteriju, mora veljati, da za po- ljubni dve nesosednji vozliˇsˇci velja, da je vsota njunih stopenj veˇcja ali enaka redu grafa. Nesosednja vozliˇsˇca v grafu G so A in C, B in D ter B in E. Velja deg(A) +deg(C) = 6 > 5, deg(B) + deg(D) = 5 in deg(B) +deg(E) = 5. Po Orejevem izreku torej velja, da je graf G hamiltonski.
Pri P´osevem kriteriju mora veljati, da ima grafGmanj kot 1 vozliˇsˇce stopnje najveˇc 1 in manj kot 2 vozliˇsˇci stopnje najveˇc 2. Vidimo, da to velja. Ker je graf lihega reda, pa mora veljati ˇse, da ima graf G najveˇc 2 vozliˇsˇci stopnje najveˇc 2. Tudi to velja, torej je po P´osevem izreku G hamiltonski.
Bralec lahko sam preveri, da graf K4 iz prejˇsnjega primera zadoˇsˇca Diracovemu kriteriju za hamiltonskost.
2.3 Prirejanja
V razdelku o prirejanjih v grafih si bomo najprej pogledali definicijo prirejanja, ne- kaj primerov, potem pa ˇse Tutteov izrek, ki nam pove, kdaj graf premore popolno prirejanje. Razdelek je povzet po [3] in [8].
Definicija.Mnoˇzica povezavM ⊆E(G) jeprirejanjegrafaG, ˇce nobeni dve pove- zavi v M nimata skupnega krajiˇsˇca, torej, ˇce nista incidenˇcni. Pri tem jeM najveˇcje prirejanje, ˇce ne obstaja tako prirejanje M0, za katerega velja |M0| > |M|. M je maksimalno prirejanje, ˇce ne obstaja prirejanje M0, za katerega velja M ⊂ M0. Vozliˇsˇce grafa, ki je krajiˇsˇce povezave v M, je z M nasiˇceno, v nasprotnem pri- meru je z M nenasiˇceno. V primeru, ko so z M nasiˇcena vsa vozliˇsˇca grafa G, je M popolno prirejanje, oziroma tudi 1-faktorgrafa G.
Primer. Oglejmo si prirejanja na grafu G, ki je prikazan na Sliki 5.
Slika 5: Prirejanja v grafih
Pri prvem primeru so z rdeˇco barvo oznaˇcene tri povezave, in sicer te povezave ne predstavljajo prirejanja v grafu G, saj sta povezavi na diagonali incidenˇcni. Pri drugem primeru povezave, oznaˇcene z rdeˇco barvo, predstavljajo prirejanje, saj no- beni dve povezavi nista incidenˇcni. To prirejanje, oznaˇcimo ga zM, je maksimalno, saj ne obstaja prirejanje M0, za katero bi veljalo M ⊂ M0. To prirejanje pa ni najveˇcje, saj je iz tretjega primera razvidno, da obstaja prirejanje N, za katerega velja |N| > |M|. Prirejanje N v tretjem grafu je najveˇcje, maksimalno in pa tudi popolno, saj so z njim nasiˇcena vsa vozliˇsˇca grafaG.
S prirejanji v grafih se je veliko ukvarjal britanski kriptolog in matematik Wil- liam Thomas Tutte, ki je pustil velik peˇcat v matematiki, posebno v teoriji grafov.
Med drugim je veliko prispeval k obstoju k-faktorjev v hamiltonskih in nehamilton- skih grafih, podal pa je tudi potreben in zadosten pogoj, kdaj nek graf G premore popolno prirejanje. V nadaljevanju bom predstavila Tutteov izrek in enega izmed njegovih dokazov. Dokaz, ki ga bom predstavila, je naˇsel britanski matematikL´aszl´o Lov´asz, eden najpomembnejˇsih ˇziveˇcih matematikov ([13]).
Izrek (Tutteov izrek). Graf G = (V, E) premore popolno prirejanje natanko te- daj, ko ˇstevilo lihih komponent grafa (G−S) ne presega |S| za vsako podmnoˇzico vozliˇsˇcS ⊂V.
Dokaz. Predpostavimo, da graf G premore popolno prirejanje M. Od tod sledi, da je red grafa G sod, torej ima sodo ˇstevilo vozliˇsˇc. Z o(G) oznaˇcimo ˇstevilo lihih komponent grafa G, torej, ˇstevilo tistih komponent grafa glede na povezanost ki imajo liho ˇstevilo vozliˇsˇc. MnoˇzicaS naj bo neka poljubna mnoˇzica vozliˇsˇc izG. ˇCe je S prazna mnoˇzica, potem je o(G−S) = o(G) = 0 = |S|. Predpostavimo, da S ni prazna. ˇCe (G−S) nima lihih komponent, potem o(G−S) = 0 <|S|. Denimo sedaj, da jeH liha komponenta v (G−S). Potem obstaja vsaj eno vozliˇsˇcev ∈H, ki v prirejanjuM ni povezano s drugim vozliˇsˇcem iz H. Ker smo predpostavili, da Gpremore popolno prirejanje, obstaja povezava e, ki v prirejanju povezuje vozliˇsˇci v ∈H inw∈S (Slika 6). Torej za vsako liho komponento obstaja ustrezno vozliˇsˇce v S. Isto vozliˇsˇce v S ne more ustrezati dvema razliˇcnima lihima komponentama, ker je v popolnem prirejanju lahko eno vozliˇsˇce krajiˇsˇce le ene povezave. Sledi, ˇce je o(G−S) = k, potem je |S| ≥k.
Pokazali smo, da je to potreben pogoj za obstoj popolnega prirejanja. Da bi dokazali, da je to tudi zadosten pogoj, moramo pokazati, da G premore popolno prirejanje, ˇce velja o(G −S) ≤ |S| za vsako mnoˇzico vozliˇsˇc S. Iz neenakosti sledi, da G
6
Slika 6: Vozliˇsˇcev ∈H je povezano z vozliˇsˇcem w∈S
nima lihih komponent, vzamemo na primer S = ∅, zato je red n grafa G sod. ˇCe je graf sodega reda poln, potem premore popolno prirejanje. Predpostavimo, da G ni poln. Denimo, da je G0 graf, ki ga iz grafa G dobimo tako, da poveˇzemo poljubni dve nesosednji vozliˇsˇci, da Gpostane vpeti podgraf grafaG0, kot kaˇzeSlika 7. Potem je o(G0 −S) ≤ o(G−S), saj ˇstevilo lihih komponent grafa (G0 −S) ne more biti veˇcje od ˇstevila lihih komponent grafa (G−S). Bralec lahko to pokaˇze sam tako, da vzame dve nesosednji vozliˇsˇci iz grafa G, graf G0 pa dobi tako, da v G poveˇze ti dve vozliˇsˇci. Zatem pogleda ˇstevilo lihih komponent o(G −S) in o(G0 −S) v primeru, ˇce obe vozliˇsˇci pripadata mnoˇzici S, isti komponenti ali pa pripadata dvema razliˇcnima lihima komponentama. Iz neenakosti o(G−S) ≤ |S|
sledi, da je o(G0 − S) ≤ o(G− S) ≤ |S|. Tako lahko brez izgube za sploˇsnost predpostavimo, da je grafGmaksimalen v tem smislu, da obstaja popolno prirejanje v vsakem razˇsirjenjem grafu, kjer sta neki dve nesosednji vozliˇsˇci izGpovezani z novo povezavo. Dovolj je pokazati, da obstaja popolno prirejanje v takˇsnem maksimalnem grafuG, ki zadoˇsˇca neenakosti o(G−S) ≤ |S| za vsako mnoˇzico vozliˇsˇc S v grafu G.
Slika 7: Grafa G inG0
Naj boW mnoˇzica vozliˇsˇc stopnjen−1 vG. ˇCe je vsaka komponenta grafa (G−W) polna, potem vG obstaja popolno prirejanje. Namreˇc, vsaka soda komponenta ima popolno prirejanje. ˇCe pa iz vsake lihe komponente odstranimo po eno vozliˇsˇce, lahko preostala vozliˇsˇca poveˇzemo v pare. Ker je vsaka komponenta grafa (G−W) polna, so odstranjena vozliˇsˇca sosednja z vsemi ostalimi vozliˇsˇci v grafu, torej so sosednja tudi med seboj in tudi njih lahko poveˇzemo v pare. Torej v G obstaja popolno prirejanje. Denimo, da ima (G −W) komponento H, ki ni polna. To pomeni, da obstajajo tri vozliˇsˇca x, y, z ∈ H tako, da x in z nista sosednji in je y sosednja z obema. Ker y /∈W, je njena stopnja manj kot n−1, od koder sledi, da obstaja vozliˇsˇce w, ki ni sosednje y. Vozliˇsˇce w ne more biti v W, ker je stopnja vsakega vozliˇsˇca v W enaka n−1. Torej je w vozliˇsˇce ene izmed komponent grafa (G−W). Zaradi predpostavke maksimalnosti na Gobstaja popolno prirejanje M1 v grafuG1, ki ga dobimo tako, da x inz poveˇzemo s povezavoe1. Podobno dobimo
popolno prirejanjeM2 v grafuG2, ki ga dobimo tako, dayinwpoveˇzemo s povezavo e2. Oˇcitno je, da jee1 ∈M1 ine2 ∈M2, prav tako pae1 ∈/ M2, saj na primer vozliˇsˇci xin z v G2 nista sosednji.
Naj bo F vpeti podgraf grafa G, katerega povezave so ali v M1 ali M2, vendar ne v obeh. Tak podgraf obstaja, saj sta M1 in M2 popolni prirejanji, torej vsebujeta vsa vozliˇsˇca grafa G. ˇCe je povezava, ki povezuje p inq, v M1, ne pa v M2, potem obstaja vozliˇsˇce r, ki je sosednje p tako, da je povezava, ki povezuje p in r v M2. Torej je stopnjap(in podobno za r) v F enaka 2. Torej je stopnja vsakega vozliˇsˇca vF enaka 2, torej jeF disjunktna unija ciklov. Od tod sledi, da ima vsak cikel sodo ˇstevilo povezav. ˇCe povezava e1 pripada ciklu C1 in povezava e2 pripada drugemu ciklu C2, dobimo prirejanje M ∈ G. M je sestavljeno iz vseh povezav cikla C1, ki so vsebovane vM2 in vseh povezav, ki so vsebovane v prirejanju M1.
Na koncu predpostavimo, da e1 in e2 obe pripadata istemu ciklu, kot to prikazuje Slika 8.
Slika 8: e1 in e2 pripadata istemu ciklu. Vir: [3]
Vsaka druga poljubna povezava ciklaC, ki nie1 alie2, je povezava grafaG. Povezava a∈G, ki povezujexiny, ne more biti povezava v prirejanjuM. Torejani povezava cikla C. Podobno b ∈ G povezuje y in z ter zato ne more biti povezava v C. Ena izmed teh dveh povezav (denimoa) bo razdelilaCv dva soda cikla, kjer boaskupna povezava teh dveh ciklov. Potem lahko dobimo prirejanje vozliˇsˇc vC, ki vsebuje a, povezave prirejanjaM1 na enem od dveh ciklov in povezave prirejanjaM2 v drugem ciklu. Prirejanja grafaC, skupaj s prirejanji pod M1 ali M2 predstavljajo popolno prirejanje grafaG. S tem smo dokaz zakljuˇcili.
Primer. Primer grafa G=P3, ki ne premore popolnega prirejanja.
Slika 9: P3 ne premore popolnega prirejanja
Ce grafuˇ P3 odstranimo srediˇsˇcev ostaneta dve lihi komponenti, torejo(P3− {v}) = 2>|{v}|, zato po Tutteovem izreku P3 ne premore popolnega prirejanja.
8
2.4 Faktorji in faktorizacija grafa
V tem razdelku se bomo spomnili pojmov faktor in faktorizacija grafa ter spoznali, kdaj je faktorizacija hamiltonska. V nadaljevanju se bomo namreˇc ukvarjali z iska- njem hamiltonske faktorizacije.
Primer. Oglejmo si nekaj primerov n-faktorjev grafa K6.
Slika 10: Zgledi n-faktorjev grafa K6 zan= 0,1,2,3
NaSliki 10 so grafiˇcno predstavljeni primeri n-faktorjev grafaK6 zan={0,1,2,3}.
Bralec lahko sam poiˇsˇce ˇse primer zan = 4 inn = 5. V tem primeru n-faktorjev ni bilo teˇzko poiskati, v sploˇsnem pa je to teˇzak problem.
Kaj je faktor grafa smo videli na primeru, sedaj pa ga ˇse formalno definirajmo.
Definicija. Faktor grafa G je poljuben vpeti podgraf grafa G (torej vsebuje vsa vozliˇsˇca iz G). ˇCe je H faktor grafa G in je stopnja vsakega vozliˇsˇca v H enaka n, je H n-faktor grafa G. Tako je 1-faktor unija loˇcenih povezav, torej popolno prirejanje, kot smo videli ˇze v razdelku o prirejanjih. 2-faktorgrafaGje 2-regularni vpeti podgraf grafaG, torej unija loˇcenih ciklov, povezan 2-faktorpa je enak ha- miltonovemu ciklu.
Definicija.GrafGjen-faktorabilenoziroma iman-faktorizacijo (razˇclenitev), ˇce in samo ˇce obstaja druˇzina n-faktorjev H1, ..., Hm ∈G, katerih mnoˇzice povezav E(Hi) so paroma disjunktne, njihova unija pa je enaka E(G).
Definicija. Hamiltonska faktorizacija grafa je 2-faktorizacija grafa na hamil- tonske cikle.
Hamiltonska faktorizacija je ime dobila po irskem matematiku, fiziku in astronomu Williamu Rowanu Hamiltonu. Hamilton je veliko prispeval k znanju iz optike, al- gebre in dinamike, najbolj znana pa je njegova formulacija Newtonove mehanike, ki se danes imenujeHamiltonova mehanika. Po njem pa se imenujejo tudi hamiltonski grafi ter nekaj drugih lastnosti grafov, ki so predstavljeni v tem delu.
Primer. Oglejmo si razliˇcne hamiltonske faktorizacije polnega grafa K5.
Izkaˇze se, da je vsaka 2-faktorizacija polnega grafaK5 kar hamiltonska faktorizacija.
Ta graf ima ˇsest razliˇcnih hamiltonskih faktorizacij, ki so predstavljene na Sliki 11.
Slika 11: 6 razliˇcnih hamiltonskih faktorizacij grafaK5. Vir: [10]
Primer. Oglejmo si ˇse zgled 2-faktorizacije, ki ni hamiltonska.
Slika 12: Zgled nehamiltonske 2-faktorizacije
Na Sliki 12 desno je prikazana 2-faktorizacija levega grafa. Graf je razdeljen na dva 2-faktorja, katerih mnoˇzice povezav so paroma disjunktne, njihova unija pa je enaka mnoˇzici povezav prvega grafa. Prvi 2-faktor (rdeˇca barva) je sestavljen iz dveh ciklov, drugi 2-faktor (ˇcrna barva) pa je hamiltonski cikel. Ta faktorizacija ni hamiltonska, saj to ni razˇclenitev grafa na same hamiltonske cikle.
Trditev. Ce je grafˇ G1-faktorabilen, potem je regularen.
Dokaz. Naj bo G 1-faktorabilen graf. Torej obstaja druˇzina 1-faktorjev, katerih mnoˇzice povezav s paroma disjunktne. Z 1-faktorjem so nasiˇcena vsa vozliˇsˇca, po dve vozliˇsˇci skupaj imata eno povezavo. Torej morajo imeti vsa vozliˇsˇca enako ˇstevilo povezav in je graf regularen.
Primer. Oglejmo si 1-faktorizacijo Desarguesovega grafa.
Slika 13: 1-faktorizacija Desarguesovega grafa. Vir: [11]
10
Na Sliki 13 je grafiˇcno prikazana 1-faktorizacija Desarguesovega grafa. Ker 1- faktorizacija obstaja, mora biti graf regularen. Iz slike je razvidno, da je graf 3- regularen.
Povedali smo, da je 1-faktorabilen graf regularen. Regularen graf pa ni nujno 1- faktorabilen. Tak primer je na primer Petersenov graf, ki je regularen, vendar ne premore 1-faktorizacije, kar bomo pokazali v nadaljevanju. Najprej pa si poglejmo ˇse lastnost 2-faktorabilnega grafa.
Trditev. Ce je grafˇ G2-faktorabilen, potem je sode stopnje.
Dokaz. 2-faktorabilen graf lahko razbijemo na druˇzino loˇcenih ciklov, katerih mnoˇzice povezav so paroma disjunktne. To pomeni, da ima vsako vozliˇsˇce za vsak pripadajoˇci cikel po dve povezavi. Torej nobeno vozliˇsˇce ne more imeti lihega ˇstevila povezav, zato je graf sode stopnje.
V nasprotju s prejˇsnjim izrekom v tem primeru velja tudi obratno. Zapiˇsimo trditev in jo dokaˇzimo.
Trditev. Vsak graf sode stopnje ima 2-faktorizacijo.
Dokaz. Na zaˇcetku dela smo povedali, da o stopnji grafa lahko govorimo takrat, ko so vsa vozliˇsˇca enake stopnje. V tem primeru so torej vsa vozliˇsˇca stopnje 2r, r ≥1.
Ker je graf povezan in sode stopnje, lahko v njem najdemo Eulerjev obhod, to je obhod, ki gre skozi vse povezave grafa ter se zaˇcne in konˇca v istem vozliˇsˇcu. Da ta obhod obstaja ne bomo dokazovali, lahko pa si bralec dokaz ogleda v [2]. Vozliˇsˇca grafa oznaˇcimo zV ={v1, v2, ..., vn}. Konstruirajmo dvodelni grafG0 =X∪Y tako, da jeX ={x1, x2, ..., xn} inY ={y1, y2, ..., yn}. Povezave tvorimo tako, da vozliˇsˇci xi in yj poveˇzemo, ˇce v Eulerjevem obhodu obstaja povezava med vi in vj. ˇCe je vozliˇsˇcevi povezano z r drugimi vozliˇsˇci, bo enako veljalo zaxi ter yj. Od tod sledi, da je dobljeni dvodelni graf r-regularen in ima 1-faktorizacijo (da to velja bomo dokazali v razdelku 1-faktorizacija grafaKn,n). Vsak 1-faktor v faktorizaciji definira mnoˇzico paroma disjunktnih ciklov v G, saj je vozliˇsˇce xi povezano z vozliˇsˇcem vj in vozliˇsˇce xj povezano z vozliˇsˇcem vi za vsak i, j. Torej je graf 2-faktorabilen.
Primer. Poiˇsˇcimo faktorizacijo Petersenovega grafa.
Hitro vidimo, da Petersenov graf ni 2-faktorabilen. Vemo namreˇc, da je graf 2- faktorabilen samo v primeru, ˇce je r-regularen in je r sodo ˇstevilo. Petersenov graf pa je 3-regularen. Poglejmo ali je 1-faktorabilen.
Petersenov graf ima 15 povezav. ˇCe je 1-faktorabilen, potem ima tri 1-faktorje s po petimi povezavami. Ker je povezav med notranjimi in zunanjimi vozliˇsˇci 5, bi po Di- richletovem principu vsaj eden od 1-faktorjev moral vsebovati vsaj dve taki povezavi.
Recimo, da neki 1-faktor vsebujeAF inBG. Potem vsebuje ˇse tri povezave, ki niso
incidenˇcne vozliˇsˇcem A, B, F, G, torej tri izmed povezavEJ, J H, HC, CD, ED, ID.
Edina moˇznost jeCH, DI, EJ, v primeru da izberemo drugo povezavo, dve vozliˇsˇci ostaneta nenasiˇceni. Torej dobimo 1-faktorM1 : (A, F),(B, G),(C, H),(D, I),(E, J).
Ker preostale povezave tvorijo dva petcikla, iz tega ne moremo dobiti ˇse dveh 1- faktorjev. Torej Petersenov graf ni 1-faktorabilen.
Lahko pa Petersenov graf razˇclenimo na dva 2-faktorja in 1-faktor, kot prikazuje Slika 14.
Slika 14: Razˇclenitev Petersenovega grafa
Definicija. Graf lihe stopnje ima kvazi-hamiltonsko razˇclenitev, ˇce ga lahko zapiˇsemo kot povezavno-disjunktno unijo 2-faktorjev in enega 1-faktorja.
Petersenov graf ima torej kvazi-hamiltonsko razˇclenitev. Podobno velja za grafK6. Primer. Graf K6 ima kvazi-hamiltonsko razˇclenitev.
Vozliˇsˇca grafa oznaˇcimo z 1,2, ...,6. Vozliˇsˇce 1 ohranimo kot zaˇcetno toˇcko veˇckotnika, ostala vozliˇsˇca pa naraˇsˇcajo v smeri urinega kazalca. S tem postopkom dobimo tri 1-faktorje:
M1 : (1,2),(3,6),(4,5) M2 : (1,3),(4,2),(5,6) M3 : (1,4),(5,3),(6,2)
Iz prvih dveh prirejanj dobimo naslednja hamiltonska cikla:
C1 : 1→2→3→6→4→5→1 C2 : 1→3→4→2→5→6→1
Cikla C1, C2 in 1-faktor M3 predstavljajo razˇclenitev grafa K6 na dva hamiltonska cikla in 1-faktor, torej kvazi-hamiltonsko razˇclenitev.
Slika 15: Kvazi-hamiltonska razˇclenitev grafa K6
12
3 Lucasove uganke in faktorizacija
Fran¸cois ´Edouard Anatole Lucas je bil francoski matematik, ki je najbolj znan po njegovi ˇstudiji o Fibonaccijevem zaporedju, po njem pa so poimenovana Lucasova ˇstevila. Razvil je metodo za testiranje, ˇce je neko ˇstevilo praˇstevilo. Veliko se je ukvarjal z razvedrilno matematiko, leta 1883 je predstavil danes vsem dobro znano igro Hanojski stolp. V eni izmed svojih knjig, R´ecr´eations math´ematiques, je predstavil problem enakomernega razporejanja otrok pri plesu v krogu. Na to temo je zastavil in tudi reˇsil razliˇcne uganke. Gre za naloge, ki jih lahko posploˇsimo in sistematiˇcno reˇsimo s pomoˇcjo pojmov in izrekov sodobne teorije grafov, ki so bili predstavljeni v prejˇsnjih poglavjih. Poglavje je povzeto po virih [1], [3], [4] in [6].
3.1 Hamiltonska faktorizacija grafa K
2n+1Uganka: Liho ˇstevilo otrok pleˇse v krogu, po vsakem plesu pa se malo premeˇsajo.
Ali lahko sestavimo tako zaporedje razporedite pri plesih, da se bosta poljubna dva plesalca natanko enkrat drˇzala za roko?
Najprej si poglejmo, kako je reˇsitev uganke predstavil ´Edouard Lucas. Opazimo, da ima v vsaki razporeditvi vsak otrok dva soseda; enega na desni in drugega na levi strani. Ker noben otrok ne sme biti dvakrat poleg istega, bo ˇstevilo sosedov za vsakega otroka vedno sodo, od koder sledi, da mora biti skupno ˇstevilo otrok v krogu nujno liho. Lucas je idejo reˇsitve predstavil na konkretnem primeru, ko je ˇstevilo otrok 11.
Otroke predstavimo s ˇcrkami abecede, in sicer A, B, C, D, E, F, G, H, I, J in K.
Predstavimo jih na pomoˇzni shemi (Slika 17), in sicer tako, da 10 otrok enakomerno razporedimo na kroˇznici, enajstega pa postavimo na premer kroga. Kot razpored za prvi ples vzamemo ABCDEFGHIJKA. Da dobimo razpored za drugi ples, vse povezave premaknemo za eno mesto naprej, v smeri urinega kazalca. Tako dobimo razporeditev ACEBGDIFKHJA. Nato nadaljujemo po istem postopku in dobimo ˇse tri razporeditve; AEGCIBKDJFHA, AGIEKCJBHDFA in AIKGJEHCFBDA.Slika 16 predstavlja skico plesalcev, Slika 17 pa pomoˇzno shemo, s pomoˇcjo katere do- bimo razporede za vse plese.
Slika 16: Postavitev otrok pri plesih
Lucas je idejo za konstrukcijo predstavil ˇse na drug naˇcin, in sicer kot tabelo z dvema
Slika 17: Pomoˇzna shema
vrsticama. Otroke razporedimo v tabelo, kot kaˇze Slika 18. Razpored za prvi ples dobimo tako, da vzamemo prvega otroka iz prve vrstice in nato prvega otroka iz druge vrstice, nato drugega iz prve vrstice in tako naprej do konca sledimo cik cak vzorcu. Razpored za naslednji ples dobimo tako, da tabelo preuredimo, in sicer tako, da najprej odstranimo obe vrednosti, nato pa kvadratke, ki ˇse vsebujejo ˇcrke, zaro- tiramo v nasprotni smeri urinega kazalca ter A vrnemo v prazne kvadratke. Tako kot prej za drugi ples dobimo razpored ACEBGDIFKHJA. Nadaljujemo in dobimo enake razporede za plese kot v naˇcinu s pomoˇzno shemo s kroˇznico.
Slika 18: Konstrukcija s tabelo za prvi ples
Sedaj ˇzelimo uganko reˇsiti ˇse v sploˇsnem s pomoˇcjo terminologije iz teorije grafov.
Otroke si predstavljajmo kot vozliˇsˇca grafa. Povezave v grafu predstavljajo pare otrok, ki se pri katerem od plesov drˇzijo za roke. Vsak posamezni ples torej pred- stavlja nek hamiltonski cikel v grafu. Kot smo ˇze prej privzeli, imamo liho ˇstevilo otrok, torej 2n+ 1. Zanima nas, ˇce obstaja hamiltonska faktorizacija grafa K2n+1. Obstoj take hamiltonske faktorizacije nam zagotavlja naslednji izrek.
Izrek(Walecki, 1890). Poln graf reda 2n+ 1 lahko faktoriziramo nanhamiltonskih ciklov.
Dokaz. Imamo mnoˇzico vozliˇsˇc V = {vi|i ∈ {1,2, ...,2n+ 1}}. Definirajmo pot Pi med vozliˇsˇcema vi in vi+n tako, da gremo skozi vsa vozliˇsˇca, razen skozi vozliˇsˇce v2n+1, pri tem pa za indekse vzamemo ˇstevila 1,2, ...,2n (mod 2n). To naredimo tako, da poveˇzemo vozliˇsˇca v naslednjem zaporedju: vi → vi−1 → vi+1 → vi−2 → ...→ vi+n−1 → vi+n. Prva pot bo torej 1 → 2n → 2 → 2n−1→ ... Druga pot se bo zaˇcela z vozliˇsˇcem 2, torej 2 → 1→ 3 →2n → .... V vsaki poti Pi, i= 1, ..., n, nastopajo sama razliˇcna vozliˇsˇca. Zato so tudi povezave v Pi med seboj razliˇcne.
Lahko pa bi se zgodilo, da se katera od povezav v Pi ujema s katero od povezav v Pj. Pokaˇzimo, da to ni mogoˇce. V vsaki poti Pi nastopata dva tipa povezav; prvi tip jevi−k ∼vi+k,k ={1, ..., n−1}, drug tip pa je vi+k∼vi−k−1,k ={0, ..., n−1}.
14
Za ujemanje povezav iz razliˇcnih poti Pi inPj so zato tri moˇznosti:
1) Ista povezava je prvega tipa v obeh poteh, torej je oblikevi−k ∼vi+kinvj−l ∼vj+l za neke i, j, k, l. To pomeni, da je i−k =j−l (mod2n) ini+k =j+l (mod2n).
Sledi 2i = 2j (mod 2n) in zato i =j (mod n). Ker je 0< i, j < n+ 1, to pomeni i=j, protislovje.
2) Ista povezava je drugega tipa v obeh poteh, pokaˇzemo podobno kot pri 1).
3) Ista povezava je prvega tipa v Pi in drugega tipa v Pj. Potem je i − k = j −l (mod 2n) in i− k − 1 = j + l (mod 2n). Sledi 2i − 1 = 2j (mod 2n), kar nima reˇsitve, saj je na levi liho, na desni pa sodo ˇstevilo.
Hamiltonove cikle iz potiPidobimo tako, da zaˇcetno in konˇcno vozliˇsˇce poti poveˇzemo z vozliˇsˇcem v2n+1, kot prikazuje Slika 19.
Slika 19: Hamiltonska cikla grafa K2n+1 zai= 1 in i= 2
Pokazali smo ne le, da hamiltonska faktorizacija grafaK2n+1 vselej obstaja, temveˇc smo v dokazu opisali tudi algoritem za konstrukcijo faktorizacije.
Primer. Razˇclenimo graf K11 na Hamiltonove cikle.
K11 je poln graf reda 2 ·5 + 1 = 11, torej n = 2. Po izreku Waleckega ga torej lahko razˇclenimo na n hamiltonskih ciklov. Tako kot prej definiramo poti P1, P2, P3, P4 inP5, tokrat za indekse vzamemo ˇstevila 1,2, ...,10 (mod 10).
P1 :v1 →v0 →v2 →v9 →v3 →v8 →v4 →v7 →v5 →v6 P2 :v2 →v1 →v3 →v0 →v4 →v9 →v5 →v8 →v6 →v7 P3 :v3 →v2 →v4 →v1 →v5 →v0 →v6 →v9 →v7 →v8
P4 :v4 →v3 →v5 →v2 →v6 →v1 →v7 →v0 →v8 →v9 P5 :v5 →v4 →v6 →v3 →v7 →v2 →v8 →v1 →v9 →v0
Pripadajoˇce hamiltonske cikle dobimo tako, da zaˇcetno in konˇcno vozliˇsˇce vsake poti poveˇzemo ˇse z vozliˇsˇcem v11 (Slika 20).
Slika 20: Hamiltonski cikli grafa K11
S pomoˇcjo programskega jezika Python sem izdelala tudi kodo, ki izpiˇse vse hamil- tonske cikle v grafu K2n+1. Koda deluje tako, da uporabnik vpiˇse ˇzeleni n, potem pa se izpiˇsejo vsi hamiltonski cikli. Vozliˇsˇca grafa so predstavljena s ˇstevilkami od 0 do 2n.
Programska koda v Pythonu:
p r i n t ( " P r o g r a m i z p i s e r a z c l e n i t e v p o l n e g a g r a f a z 2 n +1 v o z l i s c i na n h a m i l t o n s k i h c i k l o v . " )
z e l e n i _ n = int ( i n p u t ( " V p i s i p o z i t i v n o n a r a v n o s t e v i l o n , za k a t e r e g a z e l i s i z p i s a t i f a k t o r i z a c i j o : " ) )
w h i l e z e l e n i _ n <= 0:
z e l e n i _ n = int ( i n p u t ( " V p i s i p o z i t i v n o n a r a v n o s t e v i l o n , za k a t e r e g a z e l i s i z p i s a t i f a k t o r i z a c i j o : " ) )
p r i n t ( " V o z l i s c a so o z n a c e n a s s t e v i l k a m i od 0 do n -1. " )
# F u n k c i j a , ki s e s t a v i s e z n a m v o z l i s c ( v b i s t v u je to kar p r v o z a p o r e d j e )
def s e z n a m ( n ) :
n = 2*( z e l e n i _ n ) + 1 s = l i s t ( r a n g e (0 , n ) ) s . a p p e n d (0)
r e t u r n s
s = s e z n a m ( z e l e n i _ n ) # p r v o z a p o r e d j e p = ( len ( s ) - 2) // 2
p r i n t ( ’ H a m i l t o n s k i c i k l i : ’ ) p r i n t ( s )
for j in r a n g e ( p - 1) : # n a s l e d n j i h n -1 z a p o r e d i j for i in r a n g e ( len ( s ) ) :
if s [ i ] == 1:
s [ i ] += 1
16
e l i f s [ i ] == len ( s ) -2:
s [ i ] -= 1
e l i f s [ i ] % 2 == 0 and s [ i ] >= 2 and s [ i ] < len ( s ) -2:
s [ i ] += 2
e l i f s [ i ] % 2 == 1 and s [ i ] >= 3 and s [ i ] < len ( s ) -2:
s [ i ] -= 2 p r i n t ( s )
Pri prvi uganki smo ugotovili, da problem ni reˇsljiv, ˇce je ˇstevilo otrok sodo. Problem pa lahko preoblikujemo tako, da bomo iskali reˇsitev pri sodem ˇstevilu otrok. Taka je naslednja Lucasova uganka.
3.2 Hamiltonska faktorizacija grafa K
n,nUganka: Dekleta in fantje pleˇsejo v krogu, drˇzeˇc se za roke. Ali lahko sestavimo tako zaporedje razporeditev pri plesih, da bo poljuben deˇcek poleg poljubnega de- kleta natanko enkrat in prav tako poljubno dekle poleg poljubnega fanta natanko enkrat?
Edouard Lucas je deˇ´ cke oznaˇcil s ˇcrkami abecede A, B, C, ..., dekleta pa s ˇcrkami grˇske abecede α, β, γ, ... Njegove oznake so za majhne primere sicer primerne, za velike pa niso preveˇc praktiˇcne, saj je ˇstevilo ˇcrk v abecedi premahjno za velike grafe.
Ker pa se bom ukvarjala z grafi, pri katerih takˇsno oznaˇcevanje ni problematiˇcno, le-tega ne bom spreminjala.
Najprej opazimo, da mora biti vsak deˇcek poleg vsakega dekleta natanko enkrat, nikoli pa ne stoji poleg drugega deˇcka. Od tod sledi, da moramo imeti sodo ˇstevilo deˇckov in prav tako sodo ˇstevilo deklet. Lucas je reˇsitev podal za 6 deˇckov in 6 deklet. Deˇcke je postavil kot toˇcke na kroˇznici, znotraj kroˇznice pa je med dva deˇcka postavil eno izmed deklet. Razpored za prvi ples dobimo tako, da izmeniˇcno poveˇzemo toˇcke na kroˇznici s toˇckami znotraj kroˇznice, kot prikazuje Slika 21 in dobimoAαBβCγDδEF ϕA.
Da dobimo razpored za drugi ples, deˇcki ostanejo na svojih mestih, dekleta pa se premaknejo za dve mesti naprej. Torej bo dekleα, ki je bilo prej med deˇckoma A in B, sedaj med deˇckoma C in D. ˇCe bi naredili premik le za eno mesto, bi bilo dekle α zopet poleg deˇcka B, tega pa ne ˇzelimo. S tem postopkom dobimo tri razliˇcna zaporedja za postavitev otrok.
V sploˇsnem imamo n deklet in n deˇckov. Kroˇznico razdelimo na n enakih delov in nanjo postavimo deˇcke. Dekleta pa postavimo med deˇcke tako kot prej ter jih izmeniˇcno poveˇzemo. Za vsak naslednji razpored plesov dekleta pomaknemo za dve mesti naprej. Tako dobimo n2 rotacij.
Uganko lahko predstavimo tudi kot nalogo iz podroˇcja teorije grafov. Graf, s ka- terim smo predstavili deˇcke in dekleta si ogledamo kot dvodelni graf Kn,n, kjer je n sod. Podobno kot pri prvi uganki iˇsˇcemo hamiltonsko faktorizacijo, tokrat grafa Kn,n.
Slika 21: Razporeditev plesalcev
Izrek. Polni dvodelni graf Kn,n, kjer je n ≥ 2, lahko razˇclenimo na n2 hamilton- skih ciklov, ki so med seboj disjunktni.
Dokaz. Imamo polni dvodelni graf z mnoˇzico vozliˇsˇc V = {ui | i ∈ {1,2, ..., n}} ∪ {vj | j ∈ {1,2, ..., n}}. Vozliˇsˇca ui in vi enakomerno izmeniˇcno razporedimo po kroˇznici, torej u1, v1, u2, v2, ...S tem dobimo prvi hamiltonski cikelu1, v1, u2, v2.... V naslednjem koraku vozliˇsˇcaui ostanejo na svojih mestih, vozliˇsˇcavi pa pomaknemo za dve mesti naprej. Torej, v1 se premakne na mesto, kjer je bilo v3 in tako naprej.
S tem dobimo drugi hamiltonski cikel u1, v3, u2, v5, .... Postopek nadaljujemo. Ker je vozliˇsˇc vi enako n in se pomikajo za dva koraka naprej, bomo potrebovali n2 ponovitev. DefinirajmoCi =u1, v1, u2, vi+1, ..., un, vi+nzai= 1, ...n(mod n). Potem so Ci gotovo hamiltonski cikli, saj vsebujejo vsa vozliˇsˇca natanko enkrat. Da so razliˇcne tudi povezave Ci in Cj pa lahko bralec premisli sam podobno, kot smo naredili v primeru za K2n+1.
Primer. Razˇclenimo graf K4,4 na hamiltonske cikle.
Vemo, da lahko vozliˇsˇca polnega dvodelnega grafa razbijemo na dve podmnoˇzici, na primerV =U ∪Z. Graf na kroˇznici predstavimo tako, da so vozliˇsˇcaA, B, C, D ∈U inα, β, γ, δ ∈Z. Prvi hamiltonski cikel dobimo tako, da po vrsti poveˇzemo vozliˇsˇca, torejC1 :A →α →B → β → C → γ → D→ δ →A. Drugi hamiltonski cikel pa dobimo tako, da vozliˇsˇca iz podmnoˇzice U ostanejo na istih mestih, vozliˇsˇca iz pod- mnoˇzice Z pa pomaknemo za dve mesti naprej. Tako dobimo ˇse drugi hamiltonski cikel, torej C2 :A →γ →B →δ→C →α→D→β →A.
Slika 22: Razˇclenitev grafa K4,4 na hamiltonska cikla
18
Tudi za iskanje hamiltonske faktorizacije v grafu Kn,n sem izdelala kodo v pro- gramskem jeziku Python, ki deluje na enak naˇcin, kot prejˇsnja. Uporabnik vpiˇse n, za katerega ˇzeli izpisati razˇclenitev grafa na hamiltonske cikle.
Programska koda v Pythonu:
p r i n t ( " P r o g r a m i z p i s e r a z c l e n i t e v p o l n e g a d v o d e l n e g a g r a f a z 2 n v o z l i s c i na n h a m i l t o n s k i h c i k l o v . " )
z e l e n i _ n = int ( i n p u t ( " V p i s i z e l e n i s o d i n , za k a t e r e g a z e l i s i z p i s a t i f a k t o r i z a c i j o : " ) )
w h i l e z e l e n i _ n % 2 == 1:
z e l e n i _ n = int ( i n p u t ( ’ To ni b i l o s o d o s t e v i l o . ’
’ I z b e r i s o d i n : ’ ) )
# F u n k c i j a , ki s e s t a v i s e z n a m v o z l i s c def s e z n a m ( n ) :
n = 2*( z e l e n i _ n ) + 1 s = l i s t ( r a n g e (0 , n ) ) for i in r a n g e (0 , n ) :
if i % 2 == 0 and i < n -1:
s [ i ] = chr (65 + i / / 2 ) if i % 2 == 1:
s [ i ] = i //2 if i == n -1:
s [ i ] = ’ A ’ r e t u r n s
s = s e z n a m ( z e l e n i _ n ) n = 2*( z e l e n i _ n ) +1 p = int ( z e l e n i _ n )
p r i n t ( ’ H a m i l t o n s k i c i k l i pri p o l n e m d v o d e l n e m g r a f u z ’ , n -1 , ’ v o z l i s c i : ’ )
for j in r a n g e ( z e l e n i _ n / / 2 ) : for i in r a n g e ( len ( s ) ) :
if i % 2 == 1:
s [ i ] -= 2
if s [ i ] > z e l e n i _ n -1:
s [ i ] = s [ i ] % ( z e l e n i _ n ) if s [ i ] < 0:
s [ i ] += ( z e l e n i _ n ) p r i n t ( s )
3.3 Hamiltonska faktorizacija grafa K
2n− nK
2Uganka: Otroci pleˇsejo v krogu, drˇzeˇc se za roke, okrog dveh, ki sta v sredini kroga.
Ali lahko sestavimo tako zaporedje razporeditev pri plesih, da bo vsak izmed otrok enkrat znotraj kroga in bo poleg poljubnega otroka natanko enkrat?
Najprej opazimo, da mora biti ˇstevilo otrok sodo. V tem primeru je ´Edouard Lucas podal reˇsitev za 14 otrok, in sicer tako, da jih je tako kot pri prejˇsnjih ugankah razporedil kot toˇcke na kroˇznici. Na kroˇznici najprej doloˇcimo 12 toˇck, ki predsta- vljajo otroke v krogu, nato pa ˇse dve toˇcki znotraj kroˇznice, ki predstavljata par
znotraj kroga. Toˇcke tako kot prej poimenujemo s ˇcrkami abecede, od A do N. Toˇcki znotraj kroˇznice poimenujemo z A in B, toˇcke na kroˇznici pa s ˇcrkami od C do N.
Za zaporedje pri prvem plesu tako dobimo CDEFGHIJKLMNC na kroˇznici ter AB v sredini. Do drugega zaporedja pridemo tako, da sledimo ciklu. Prva toˇcka, ki je bila pri prvem zaporedju na kroˇznici, bo sedaj v centru. Sledimo ciklu in dobimo zaporedje ADNEMFBLGKHJA ter na sredini CI, kot prikazujeSlika 23.
Slika 23: Pomoˇzna shema in razporeditev plesalcev za drugi ples
Da pridemo do razporeda za tretji ples, povezave obrnemo v smeri CD, pri tem pa izoliramo toˇcki D in J. Tako dobimo zaporedje AECFNGBMHLIKA ter DJ v sredini. Analogno nadaljujemo in dobimo sedem razliˇcnih razporedov. Opazimo, da so v srediˇsˇcu zaporedoma toˇcke, ki so diametralne, torej je vsaka eno krajiˇsˇce ustreznega premera kroˇznice. Poleg tega dve zaporedni ˇcrki, ki sta v prvem krogu sosednji, v nobenem naslednjem ne bosta veˇc.
V sploˇsnem to nalogo predstavimo kot iskanje faktorizacije grafa K2n−nK2 v n ciklov z 2n − 2 vozliˇsˇci, saj je ˇstevilo otrok sodo, pri vsakem plesu pa sta dva razliˇcna otroka v centru kroga. Tako faktorizacijo lahko poiˇsˇcemo z uporabo izreka, ki ga bomo dokazali v nadaljevanju.
Izrek. Poln graf reda 2n lahko faktoriziramo na n hamiltonskih ciklov in 1-faktor.
Dokaz. Vozliˇsˇca grafa oznaˇcimo z 1,2,3, ...,2n. Konstruirajmo cikel z 2n−1 vozliˇsˇci, ki jih oznaˇcimo z 2,3, ...,2nv smeri urinega kazalca tako, da je srediˇsˇcno vozliˇsˇce ci- kla enako vozliˇsˇcu 1 polnega grafa. 1-faktorM1 je sestavljen iz povezave, ki povezuje vozliˇsˇci 1 in 2 skupaj z n −1 povezavami, ki jih konstruiramo po naslednjem po- stopku. n−1 vozliˇsˇc leˇzi v smeri urinega kazalca vozliˇsˇca 2 v ciklu,n−1 vozliˇsˇc pa v nasprotni smeri urinega kazalca tega vozliˇsˇca, razen toˇcke 2 polnega grafa. Poveˇzimo vozliˇsˇca, ki so od vozliˇsˇca 2 oddaljena za i v smeri urinega kazalca in vozliˇsˇca, ki so od vozliˇsˇca 2 oddaljena za i v nasprotni smeri urinega kazalca, pri tem pa je i= 1,2, ..., n−1. Po tej metodi zajamemon−1 povezav. Povezava, ki povezuje vo- zliˇsˇce 1 in vozliˇsˇce 2, skupaj s temin−1 povezavami tvori 1-faktor. Sedaj poiˇsˇcemo vozliˇsˇca, ki so od vozliˇsˇca 3 na ciklu enako oddaljena. S tem dobimo 1-faktor, ki vsebuje povezavo vozliˇsˇc 1 in 3, skupaj zn−1 novih povezav. Tako nadaljujemo do konca. Hamiltonov cikel C1 konstruiramo tako, da zaˇcnemo z vozliˇsˇcem 2n in nato izmeniˇcno povezujemo vozliˇsˇca v smeri urinega kazalca in nasprotni smeri prirejanja M1. Prvih n −1 1-faktorjev bomo porabili, da konstruiramo n−1 Hamiltonovih ciklov. Naslednji 1-faktor in teh n−1 ciklov nam bo dalo ˇzeleno faktorizacijo.
20
Posledica. K2n ima kvazi-hamiltonsko razˇclenitev.
Pokazali smo, da lahko graf K2n razˇclenimo na n hamiltonskih ciklov z 2n − 2 vozliˇsˇci, 2 vozliˇsˇci pa sta del 1-faktorja. Sledi, da lahko problem otroˇskega plesa ˇstirinajstih otrok predstavimo kot sedem razliˇcnih zaporedij teh plesov.
Primer. V razdelku o faktorjih in faktorizaciji grafa smo pokazali, da graf K6 pre- more kvazi-hamiltonsko razˇclenitev na dva hamiltonska cikla in 1-faktor (Slika 15).
Izrek tukaj pa pravi, da ga lahko razˇclenimo na 3 hamiltonske cikle in 1-faktor.
Naloge se lotimo po zgornjem postopku in res dobimo tri razliˇcne cikle s 4 vozliˇsˇci in pa 1-faktor, kot to prikazujeSlika 24.
C1 :C →D→E →F →C C2 :D→B →F →A→D C3 :A→E →D→C →A M : (A, B), (A, E), (D, F)
Slika 24: Razˇclenitev grafa K6 na tri cikle in 1-faktor
3.4 1-faktorizacija grafa K
2nNaslednjo uganko je Lucas predstavil kot sprehode v parih, vendar bi jo lahko pred- stavili tudi tako, da bi vzeli plese v parih, kjer bi vsaka izmed deklet plesala z vsemi drugimi natanko enkrat.
Uganka: V dijaˇskem domu je sodo ˇstevilo deklet, ki vsak dan v parih hodijo na sprehod v parih. Ali lahko sestavimo tako zaporedje razporeditev sprehodov, da bo vsaka izmed deklet imela za partnerico vsak dan drugo dekle, vsako natanko enkrat?
Edouard Lucas je reˇsitev te uganke predstavil za 12 deklet, ki jih je predstavil´ kot toˇcke na kroˇznici, poimenovane s ˇcrkami abecede od A do L. Na kroˇznico je najprej razporedil 11 toˇck, dvanajsto je postavil v sredino. Nato je toˇcke povezal v pare. Za prvo razporeditev je tako dobil pare AL, BL, CJ, DI, EH in FG, kot si lahko ogledamo na Sliki 25.
Da dobimo drugi razpored, tako kot pri prejˇsnji uganki rotiramo povezave, in sicer
Slika 25: Razpored deklet za prvi sprehod
v smeri urinega kazalca, medtem ko toˇcke ostanejo na svojih mestih. Tako dobimo drugo zaporedje BL, CA, DK, EJ, FI, GH. Nadaljujemo do konca in dobimo enajst razliˇcnih zaporedij sprehodov, ki vkljuˇcujejo vsa dekleta.
Da bi nalogo reˇsili za poljuben n moramo poiskati 1-faktorizacijo grafa K2n. Izrek. Poln graf sodega reda je 1-faktorabilen.
Dokaz. Vozliˇsˇca grafa znaˇcimo z 1,2, ...,2n. Konstruirajmo cikel z 2n−1 vozliˇsˇci in oznaˇcimo ta vozliˇsˇca z 2,3, ...,2n v smeri urinega kazalca. Srediˇsˇcno vozliˇsˇce cikla je enako vozliˇsˇcu 1 polnega grafa. 1-faktorM1 je sestavljen iz povezave, ki povezuje vozliˇsˇci 1 in 2, skupaj z n−1 povezavami, ki jih dobimo po naslednjem postopku.
Od vozliˇsˇca 2 je v vsaki smerin−1 vozliˇsˇc. Med seboj poveˇzemo vozliˇsˇca, ki so od vozliˇsˇca 2 oddaljena i enot v vsaki smeri, i = 1,2, ..., n. Po tej metodi zajamemo n−1 povezav. Povezava, ki povezuje srediˇsˇcno vozliˇsˇce 1 in vozliˇsˇce 2, skupaj s temin−1 povezavami tvori 1-faktor. Naslednji 1-faktor dobimo tako, da poveˇzemo vozliˇsˇca, ki so v vsaki smeri od vozliˇsˇca 3 oddaljena za ienot. Tako nadaljujemo do konca. Zadnji 1-faktor je sestavljen iz povezave, ki povezuje vozliˇsˇci 1 in 2n, skupaj zn−1 novimi povezavami. S to konstrukcijo definiramo 2n−1 popolnih prirejanj.
Ker ima vsak 1-faktorn povezav, je skupno ˇstevilo povezav v teh 2n−1 prirejanjih enako n(2n−1), kar pa je skupno ˇstevilo povezav v polnem grafu. Torej je graf 1-faktorabilen.
Primer. Poiˇsˇcimo 1-faktorizacijo grafa K6.
Iskanja 1-faktorizacije grafaK6 se lahko lotimo tako, da sledimo konstrukciji v do- kazu, lahko pa si pomagamo z Lucasovim postopkom. Po tem postopku dobimo pet razliˇcnih 1-faktorjev, s katerimi pokrijemo vse povezave grafa, kot prikazuje Slika 26.
M1 : (A, F),(B, E),(C, D) M2 : (B, F),(A, C),(D, E) M3 : (C, F),(A, E),(B, D) M4 : (D, F),(C, E),(A, B) M5 : (E, F),(A, D),(B, C)
22
Slika 26: 1-faktorizacija grafaK6
Za iskanje 1-faktorizacije grafaK2nsem v programskem jeziku Python izdelala kodo, ki izpiˇse iskano faktorizacijo. Koda deluje tako, da uporabnik vpiˇse ˇzeleni sodin, za katerega ˇzelimo izpisati faktorizacijo. Ko program zaˇzenemo, se izpiˇsejo seznami, ki predstavljajo 1-faktorje iskanega grafa.
Programska koda v Pythonu:
z e l e n i _ n = int ( i n p u t (" V p i s i s o d i n : ") ) w h i l e z e l e n i _ n % 2 == 1:
z e l e n i _ n = int ( i n p u t ( ’ To ni b i l o s o d o s t e v i l o . I z b e r i s o d i n :
’) )
# F u n k c i j a , ki s e s t a v i s e z n a m v o z l i s c ( v b i s t v u je to kar p r v o z a p o r e d j e )
def s e z n a m ( n ) :
s = l i s t ( r a n g e (0 , n ) ) r e t u r n s
s = s e z n a m ( z e l e n i _ n ) p = len ( s ) - 1
for k in r a n g e ( p ) : n o v i = []
for i in r a n g e ( len ( s ) / / 2 ) : # t v o r i m o p a r e n o v i . a p p e n d ([ s [ i ] , s [ - i - 1 ] ] )
for j in r a n g e ( p ) : # t v o r i m o d r u g i s e z n a m s [ j ]+= 1
if s [ j ] >= len ( s ) -1:
s [ j ] = s [ j ] % ( z e l e n i _ n - 1) p r i n t ( n o v i )
3.5 1-faktorizacija grafa K
n,nKot zadnjo izmed nalog si bomo ogledali uganko, ki je sicer ni v Lucasovi knjigi, jo pa lahko prav tako reˇsimo z uporabo izreka iz teorije grafov.
Uganka: Dekleta in enako ˇstevilo deˇckov pleˇsejo v parih tako, da nikoli skupaj ne pleˇseta dve dekleti ali dva deˇcka. Ali lahko sestavimo tako zaporedje razpore- ditev pri plesih, da bo poljuben deˇcek poleg poljubnega dekleta natanko enkrat in
poljubno dekle poleg poljubnega deˇcka natanko enkrat?
Predstavljajmo si, da imamon deklet in n deˇckov. Ker vsako dekle pleˇse z vsakim deˇckom in obratno, jih lahko predstavimo kot vozliˇsˇca polnega dvodelnega grafa Kn,n. Pokazati moramo, da je graf Kn,n 1-faktorabilen. To storimo z uporabo Hal- lovega izreka, ki ga ne bomo dokazovali, se pa dokaz nahaja v [3].
Izrek(Hallov izrek). V dvodelnem grafu (X, Y, E) obstaja popolno prirejanje med X inY ˇce in samo ˇce za vsako podmnoˇzico AmnoˇziceX velja|f(A)| ≥ |A|, pri tem pa jef(A) mnoˇzica tistih vozliˇsˇc v Y, ki so sosednje vsaj enemu vozliˇsˇcu vA.
Izrek. Vsak r-regularen dvodelni graf je 1-faktorabilen.
Dokaz. Dokaza se lotimo z indukcijo nar. ˇCe jer = 1, je graf oˇcitno 1-faktorabilen.
Predpostavimo sedaj, da velja za r−1, kjer je r ≥ 2. Ker je graf regularen, po Hallovem izreku graf Kn, premore 1-faktor F ∈ G. ˇCe F odstranimo iz grafa G, dobimo graf G0 = G−F. Ta graf je regularen graf stopnje r −1, saj po dvema vozliˇsˇcema odstranimo po eno povezavo. Po indukcijski predpostavki je graf G0 1- faktorabilen. Katerakoli 1-faktorizacija grafa G0, skupaj z 1-faktorjem F nam da torej 1-faktorizacijo grafaG. Torej je r-regularen dvodelni graf 1-faktorabilen.
Primer. Poiˇsˇcimo 1-faktorizacijo grafa K3,3.
Imamo 3 dekleta in 3 deˇcke. Dekleta oznaˇcimo z A, B, C, deˇcke pa E, D, F. Naj- demo lahko tri 1-faktorje, s katerimi pokrijemo vse povezave grafa K3,3 tako, da se nobeni dve ne prekrivata, (Slika 27).
M1 : ((A, D),(B, F),(C, E)) M2 : ((A, E),(B, D),(C, F)) M3 : ((A, F),(B, E),(C, D)
Slika 27: 1-faktorizacija grafaK3,3
24
4 Sorodni rezultati in odprti problemi
V tem poglavju bom brez dokazov predstavila ˇse nekaj ˇze znanih rezultatov in pa hipotez o hamiltonski razˇclenitvi, povzeto po viru [10].
Leta 1964 je Kotzig pokazal, da je kubiˇcni graf hamiltonski, ˇce in samo ˇce ima njegov graf povezav hamiltonsko razˇclenitev. Pri tem se spomnimo, da je graf kubiˇcni, ˇce so vsa njegova vozliˇsˇca stopnje 3, torej je 3-regularen.
Regularni hamiltonski nevozliˇsˇcno tranzitivni grafi ne premorejo hamiltonske fakto- rizacije. Bralec lahko to sam preveri na primerih, na primer potP2, Petersenov graf ali pa povezavni graf Petersenovega grafa.
S. Wagon je leta 2013 podal domnevo, da imajo vsi povezani vozliˇsˇcno tranzitivni grafi hamiltonsko razˇclenitev, z izjemo Petersenovega, Coxeterjevega, povezavnega grafa in grafa, ki ga dobimo tako, da vsako vozliˇsˇce nadomestimo s ciklom C3. Po- zneje so seznam izjem ˇse dopolnili, leta 2014 pa sta domnevo zavrnila Bryant in Dean, ki sta s protiprimeri pokazala, da je neskonˇcno mnogo povezanih vozliˇsˇcno tranzitivnih grafov, ki nimajo hamiltonske razˇclenitve.
Leta 1954 je Ringel pokazal, da ima hiperkocka Qn hamiltonsko razˇclenitev v pri- meru, ko jenpotenca ˇstevila 2. Leta 1990 pa je Alspach pokazal, da to velja za vsak n >2. Leta 2012 je Alpach s sodelavci pokazal ˇse, da imajo hamiltonsko razˇclenitev tudi Paleyevi grafi.
Vidimo, da je na temo hamiltonske razˇclenitve grafa ˇse veliko neraziskanega, ve- liko je podanih domnev, ki ˇse niso dokazane, ostajajo odprti problemi. Vsekakor gre za podroˇcje, ki bi ga bilo zanimivo raziskovati tudi vnaprej in ga pribliˇzati bralcu s posploˇsitvijo na vsakodnevne primere.
5 Literatura
(1) Haggard, G. (1980). Excursions in graph theory. Orono: University of Maine at Orono.
(2) Benjamin, A., Chartrand, G. in Zhang, P. (2015). The fascinating world of graph theory. Oxford: Princeton University.
(3) Balakrishnan, V. K. (1997). Schaum’s outline of theoy and problems of graph theory. New York: McGraw-Hill.
(4) Lucas, ´E. (1979). R´ecr´eations math´ematiques. Paris: Librairie scientifique et technique.
(5) Wilson, R. J., Watkins J. J. (1997). Uvod v teorijo grafov. Ljubljana: Druˇstvo matematikov, fizikov in astronomov Slovenije.
(6) Wikipedia. (2017). E. Lucas. Dostopno na:´ https://en.wikipedia.org/
wiki/%C3%89douard_Lucas.
(7) Wikipedia. (2017). W. T. Tutte. Dostopno na: https://en.wikipedia.org/
wiki/W._T._Tutte.
(8) Wikipedia. (2017). W. R. Hamilton. Dostopno na: https://en.wikipedia.
org/wiki/William_Rowan_Hamilton.
(9) Weisstein, Eric W. (2017). P´osa’s Theorem. Dostopno na: http://mathworld.
wolfram.com/PosasTheorem.html.
(10) Weisstein, Eric W. (2017). Hamilton Decomposition. Dostopno na: http:
//mathworld.wolfram.com/HamiltonDecomposition.html.
(11) Wikipedia. (2017). Graph factorization. Dostopno na: https://en.m.wikipedia.
org/wiki/Graph_factorization#1-factorization.
(12) Persee. (2017). F´elix Louis Walecki. Dostopno na: http://www.persee.fr/
doc/inrp_0298-5632_1986_ant_11_1_6604.
(13) Wikipedia. (2017). L´aszl´o Lov´asz. Dostopno na: https://en.wikipedia.
org/wiki/L%C3%A1szl%C3%B3_Lov%C3%A1sz.
26
