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 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:
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.