UNIVERZA V LJUBLJANI PEDAGOŠKA FAKULTETA
FAKULTETA ZA MATEMATIKO IN FIZIKO
DIPLOMSKO DELO
SABINA PINTAR
UNIVERZA V LJUBLJANI PEDAGOŠKA FAKULTETA
FAKULTETA ZA MATEMATIKO IN FIZIKO Študijski program: Matematika in fizika
JOHNSONOVI IN KNESERJEVI GRAFI
DIPLOMSKO DELO
Mentor:
doc. dr. Primož Šparl
Kandidatka:
Sabina Pintar
Ljubljana, april, 2014
Zahvala
Iskreno se zahvaljujem svojemu mentorju, doc. dr. Primožu Šparlu, najprej za kvalitetna in zanimiva predavanja, zaradi katerih sem se odločila izbrati to temo diplomskega dela, pozneje pa za strokovno vodenje v kombinaciji z dopuščanjem velike mere samostojnosti. Izredno cenim tudi njegovo dosto- pnost in čas, ki mi ga je v tem obdobju namenil.
Rada bi se zahvalila tudi prijateljem, ki so mi v času študija stali ob strani, sošolkam, ki so mi študij naredile prijeten, partnerju, ki me je podpiral, spodbujal in priskrbel dovolj časa, ter družini, ki mi je poleg vsega naštetega študij sploh omogočila.
Program dela
V diplomskem delu obravnavajte Johnsonove in Kneserjeve grafe. Raziščite nekatere njihove najbolj znane lastnosti.
Ljubljana, julij 2013 Mentor: doc. dr. Primož Šparl
Povzetek
To diplomsko delo obravnava družino tako imenovanih J-grafov in dve njeni poddružini, Johnsonove in Kneserjeve grafe. Gre za zelo znane družine gra- fov, ki imajo nekaj pomembnih lastnosti. So, na primer, zelo simetrični - Johnsonovi grafi so tako celo razdaljno tranzitivni in jih kot takšne zelo radi študiramo.
V diplomskem delu najprej raziščemo najosnovnejše lastnosti teh družin gra- fov, na primer red grafa, povezanost, regularnost ter točkovno, povezavno in ločno tranzitivnost, nato pa se posvetimo tudi nekaterim bolj zahtevnim.
Tako določimo premer Johnsonovih grafov in pokažemo, da so razdaljno tran- zitivni in hamiltonsko povezani. Določimo tudi ožino Kneserjevih grafov in njihovo kromatično število.
Čeprav so vse te družine že nekaj časa pod drobnogledom matematikov, še kar nekaj vprašanj ostaja odprtih. Na koncu diplomskega dela predstavimo eno izmed bolj zanimivih.
Ključne besede: Johnsonov graf, Kneserjev graf, J-graf, premer grafa, ožina grafa, kromatično število, hamiltonska povezanost, regularen graf.
Abstract
This graduation paper deals with the so-called J-graph family and two of its subfamilies, the Johnson graphs and the Kneser graphs. These graph fami- lies are well known and their members have some important properties. For instance, they are very symmetric: the Johnsons graphs are even distance- transitive and therefore very interesting for researches.
In this graduation paper we first present some basic properties of these graph families, their degree, connectedness, regularity and vertex-, edge- and arc- transitivity. Later we focus on some of the more complex properties. We determine the diameter of Johnson graphs and show that they are distance- transitive and hamilton connected. We determine the girth of the Kneser graphs and their chromatic number.
Even though matematicians have been studying these graph families for quite a while now, a lot of questions remain unanswered. At the end of this gra- duation paper we present one of the more interesting ones.
Key words: Johnson graph, Kneser graph, J-graph, diameter, girth of graph, chromatic number, hamilton connectedness, regular graph.
MSC(2010): 05C15, 05C38, 05C45, 05E99
Kazalo
1
UVOD 1
2
OSNOVNI POJMI 4
3
J GRAFI - POSPLOŠENI JOHN-
SONOVI GRAFI 16
3.1 NEKAJ PRIMEROV J-GRAFOV . . . 18 3.2 OSNOVNE LASTNOSTI J-GRAFOV . . . 21
4
JOHNSONOVI GRAFI 25
4.1 PRIMERI JOHNSONOVIH GRAFOV . . . 26 4.2 RAZDALJNA TRANZITIVNOST IN PREMER JOHNSO-
NOVIH GRAFOV . . . 28 4.3 HAMILTONSKOST JOHNSONOVIH GRAFOV . . . 31
5
KNESERJEVI GRAFI 35
5.1 PRIMERI KNESERJEVIH GRAFOV . . . 36 5.2 OSNOVNE LASTNOSTI KNESERJEVIH GRAFOV . . . 37 5.3 PREMER KNESERJEVIH GRAFOV . . . 41
5.4 KROMATIČNO ŠTEVILO KNESERJEVIH GRAFOV . . . . 44 5.5 HAMILTONSKOST KNESERJEVIH GRAFOV . . . 52
6
ZAKLJUČEK 54
Slike
1.1 Graf poznanstva . . . 2
2.1 Enostaven graf . . . 5
2.2 Graf Γin njegov komplement . . . 5
2.3 Enostaven graf, njegov podgraf in graf induciran na V1 . . . . 6
2.4 Dva izomorfna grafa . . . 6
2.5 Regularen graf . . . 7
2.6 Sprehod na grafu . . . 8
2.7 Pot na grafu . . . 8
2.8 Graf z ožino tri . . . 9
2.9 Nepovezan graf . . . 9
2.10 Obhod na grafu . . . 10
2.11 Eulerjev obhod na grafu . . . 10
2.12 Poti od u dov . . . 10
2.13 Premer grafa . . . 11
2.14 Hamiltonova pot . . . 11
2.15 Hamiltonov cikel . . . 12
2.16 Dve dobri barvanji istega grafa . . . 13
2.17 Kromatično število . . . 13
2.18 Točkovno, povezavno in ločno tranzitiven graf . . . 14
3.1 1. korak konstrukcije grafa . . . 17
3.2 2. korak konstrukcije grafa . . . 17
3.3 3. korak konstrukcije grafa . . . 18
3.4 Dokončno skonstruiran graf . . . 18
3.5 J(5; 1; 0) . . . 19
3.6 J(2; 1; 1) . . . 19
3.7 J(6; 3; 1) . . . 20
3.8 J(7; 3; 1) . . . 20
3.9 Sosednji vozlišči . . . 21
3.10 Preslikava . . . 24
4.1 J(4; 2) . . . 26
4.2 J(5; 2) . . . 26
4.3 J(6; 2) . . . 26
4.4 J(6; 3) . . . 26
4.5 J(7; 1) in J(9; 1) . . . 27
4.6 Delovanje presikaveϕ. . . 30
4.7 Iskanje Hamiltonove poti . . . 33
5.1 J(2; 1; 0) inJ(4; 1; 0) . . . 36
5.2 J(5; 2; 0) . . . 36
5.3 J(6; 3; 0) . . . 37
5.4 Tricikel . . . 38
5.5 5 cikel v Petersenovem grafu . . . 40
5.6 Razdaljna particija . . . 41
Poglavje 1
UVOD
To diplomsko delo spada na področje teorije grafov, ki je v primerjavi z dru- gimi vejami matematike dokaj mlada veda. Za začetek te teorije se šteje Eulerjeva objava rešitve problema Konigsberških mostov¨ leta 1736, vendar se je ta veja matematike zares začela razvijati šele v 20. stoletju. Od druge polovice 20. stoletja pa se je začel bliskovit razvoj, ki je med drugim omo- gočil, da se danes rezultati te teorije uporabljajo na mnogih področjih od naravoslovnih do družboslovnih [10].
Osnovni gradniki teorije grafov so grafi, ki sestojijo iz objektov, imenovanih vozlišča, in morebitnih povezav med njimi. Za lažjo predstavo grafe veli- kokrat upodobimo s sliko, na kateri vozlišča grafa predstavimo s točkami, povezave pa so krivulje, ki povezujejo določene točke med seboj. Pri posa- meznem grafu je bistveno le, katere točke so med seboj povezane. Veliko življenjskih situacij lahko predstavimo s pomočjo grafa. Za preprost primer lahko vzamemo "Graf poznanstva". Graf sestavlja pet oseb (Nika, Ajda, Pe- ter, Maja in Rok), povezava med dvema osebama pa pomeni, da se poznata.
Nika
Rok
Maja Peter
Ajda
Γp
Slika 1.1: Graf Poznanstva.
Dobro znan je tudi problem, poznan pod imenom Problem trgovskega po- tnika, ki se ukvarja s tem, v katerem zaporedju mora trgovec obiskati kraje prodaje in se nato vrniti domov, da bo njegova pot najcenejša. V tem pri- meru kraji predstavljajo naše točke grafa (vozlišča), povezave pa so vse ceste, ki peljejo iz enega mesta v druga. S podobnimi preprostimi situacijami se tudi sami srečujemo vsak dan. In ravno zato ker se toliko problemov da prepisati v jezik teorije grafov in jih tam tudi dokaj uspešno rešiti, ta veda doživlja takšen vzpon.
Seveda pa vse tudi ni tako enostavno. Nekateri tovrstni problemi so lahko praktično nerešljivi. Velikokrat moramo stvari najprej do dobra raziskati, da bi lahko v prihodnosti dobljeno teorijo uporabili na konkretnih problemih.
Zato se znanstveniki lotevajo raziskovanja grafov in njihovih lastnosti, ki so že na prvi pogled zanimive in bi se jih kasneje dalo uporabiti. Tudi družine tako imenovanih J-grafov, Johnsonovih grafov in Kneserjevih grafov, ki so osrednja tema našega diplomskega dela, imajo nekaj zelo zanimivih lastnosti.
Predvsem so zelo simetrične in so kot take k študiju pritegnile že marsikoga.
V današnjem času, ko prevladuje moderna tehnologija lahko marsikateri iz- račun opravimo z računalnikom. Vendar pa prej omenjene naštete družine grafov premorejo številne tako velike grafe, da tudi računalnikom predsta-
vljajo prevelik zalogaj. Zato se je potrebno obravnave lastnosti teh grafov lotiti teoretično. Take vrste pristop bo prikazan tudi v našem diplomskem delu.
V vsakem od naslednjih poglavij bomo najprej predstavili osnovne lastno- sti ene od omenjenih družin grafov, nato pa pri vsaki poizkusili izpostaviti še eno ali dve zahtevnejši značilnosti in jih tudi dokazali. Tako v drugem poglavju začnemo z J-grafi, ki jih seveda najprej definiramo in navedemo nji- hove zančilnosti kot so število vozlišč, red grafa, ali so povezani ali ne. Proti koncu poglavja pokažemo, da so ločno in povezavno tranzitivni. V tretjem poglavju se posvetimo Johnsonovim grafom in njihovim lastnostim. Poka- žemo tudi, da so razdaljno tranzitivni in hamiltonsko povezani. V zadnjem poglavju spoznamo še Kneserjeve grafe, katerim določimo ožino in premer.
Poglavje 2
OSNOVNI POJMI
Preden se lotimo preučevanja katere koli vede, se je potrebno seznaniti z nje- nimi osnovnimi pojmi. Poenostavljeno razlago, kaj grafi sploh so, smo podali že v uvodu, sedaj pa pojem grafa vpeljimo še formalno. V tem poglavju so predstavljeni pojmi in rezultati, ki so potrebni za razumevanje nadaljevanja diplomskega dela. Snov je povzeta po [6], [10], [17].
Definicija 1. (Enostaven) grafΓje urejen par(V(Γ), E(Γ)), kjer jeV(Γ) neprazna množica, E(Γ)pa podmnožica množice neurejenih parov {u, v}raz- ličnih elementov iz V(Γ). Če je graf Γ razviden iz konteksta, pišemo krajše kar Γ = (V, E). Elemente množice V(Γ) imenujemo vozlišča, elemente množice E(Γ) povezave grafa Γ, medtem ko urejenim parom (u, v), kjer je {u, v} ∈ E(Γ), pravimo loki grafa Γ. Vozlišči u in v grafa Γ sta sosednji, če je {u, v} ∈ E(Γ). To označimo z u∼Γ v (oziroma z u ∼v, kadar je graf Γ razviden iz konteksta). Povezavo {u, v} krajše označimo tudi z uv. Številu vozlišč grafa Γ, torej kardinalnosti |V(Γ)|, rečemo tudi red grafa Γ.
b
d e
c Γ a
Slika 2.1: Enostaven graf.
Graf Γna sliki 2.1 je (enostaven) graf z množico vozlišč V(Γ) ={a, b, c, d, e}
in množico povezavE(Γ) = {ae, ad, de, dc, eb, ce}. Vozliščea ima dva soseda, namreč d ine. Red grafa ΓP na sliki 1.1 je enak številu oseb, torej pet. Ker se bomo v tem diplomskem delu ukvarjali le z enostavnimi grafi, bo za nas beseda graf vedno pomenila enostaven graf.
Definicija 2. Komplement grafaΓ je grafΓ, ki ga dobimo iz grafa¯ Γ tako, da ohranimo vozlišča (V(¯Γ) = V(Γ)), povezave E(¯Γ) pa so ravno tisti pari različnih vozlišč, ki v grafu Γ niso sosednji.
Γ a b
d c
Γ a b
d c
Slika 2.2: Graf Γin njegov komplement Γ.¯
Graf Γ na sliki 2.2 ima povezave ab, ac, bd in cd, medtem ko ima njegov komplement Γ¯ povezavi bc in ad (ravno nepovezavi grafa Γ).
Definicija 3. Naj bosta Γ = (V, E) in Γ1 = (V1, E1) grafa. Tedaj je Γ1 podgraf grafa Γ, če velja V1 ⊆ V in E1 ⊆ E. Če velja, da je E1 = {uv ∈ E :u, v ∈V1}, je graf Γ1 podgraf, induciran na množici V1.
1 2
3
4 5
6 7
8
Γ: 1
8
5 6 7
1 2
3
4 5
8
Γ1: Γ2:
Slika 2.3: Enostaven graf Γ, podgraf Γ1 grafaΓ in podgraf Γ2 grafaΓ indu- ciran na množici {1,5,6,7,8}.
Sicer je pri obravnavi nekaterih konkretnih situacij lahko pomembno, kako se imenujejo posamezna vozlišča, za lastnosti grafa kot celote, pa to ni po- membno. Kdaj sta dva grafa v teoriji grafov enaka do poimenovanja vozlišč natančno, pove naslednja definicija.
Definicija 4. Naj bosta Γ1 = (V1, E1) inΓ2 = (V2, E2) dva grafa. Preslikava ϕ : V1 → V2 je izomorfizem grafov, če je bijekcija in ohranja sosednost, kar pomeni, da za poljubna u, v ∈V1 velja:
u∼Γ1 v ⇔ϕ(u)∼Γ2 ϕ(v).
V tem primeru pravimo, da sta Γ1 in Γ2 izomorfna grafa, kar označimo z Γ1 ∼= Γ2.
Γ1:
i1 i2
i3 i4
i5 i6
i7
i8
i'1
Γ2: i'
6
i'2
i'4
i'5 i'3
i'8
i'7
Slika 2.4: Γ1 ∼= Γ2.
Grafe običajno študiramo le do izomorfizma natančno. Tako je graf natanko podan že s tem, da narišemo njegovo upodobitev (brez poimenovanja voz- lišč). To storimo tako, da vozlišča upodobimo s točkami v ravnini in tista, ki so med seboj povezana, povežemo z daljico (ali ustrezno ukrivljeno črto).
Grafa na sliki 2.4 sta izomorfna. Lahko je namreč preveriti, da je presli- kava ϕ:(Γ1)→(Γ2), podana s predpisomi7→i0, izomorfizem grafov.
Definicija 5. Naj boΓ = (V, E) graf, v ∈V in naj bo N(v) ={u∈V :v ∼ u}. Množici N(v) pravimo soseščina vozlišča v, njeni kardinalnosti |N(v)|
pa stopnja vozlišča v in jo označimo z degΓ(v). Minimalno stopnjo vozlišč/a v grafu Γ označimo z δ(Γ), maksimalno stopnjo vozlišč/a v Γ pa z ∆(Γ). Če so vsa vozlišča grafa Γ iste stopnje rečemo, da je graf Γ regularen. V tem primeru govorimo kar o stopnji grafa.
Slika 2.5: Regularen graf stopnje 4.
Soseščina posamezne osebe v grafu s slike 1.1 je množica oseb, s katerimi se ta oseba pozna. Nika se pozna z Rokom, Majo in Petrom. Te osebe torej tvorijo Nikino soseščino. Število oseb v tej soseščini pa predstavlja Nikino stopnjo, degΓP(N ika) = 3. Osebi, ki se poznata z najmanj ljudmi, sta Ajda in Maja, vsaka se pozna z dvema, zato je minimalna stopnja vozlišč grafa ΓP enaka δ(ΓP) = 2. Rok se pozna z vsemi štirimi osebami, iz česar sledi, da je maksimalna stopnja vozlišč v grafu ΓP enaka ∆(ΓP) = 4. Naš graf ΓP ni regularen, saj bi bili v tem primeru maksimalna in minimalna stopnja vozlišč enaki.
Definicija 6. Naj boΓ = (V, E)graf inu, v ∈V poljubni vozlišči. Zaporedje (v0, v1, . . . , vn) vozlišč grafa Γ, kjer je v0 =u in vn =v, je sprehod grafa Γ od u do v, če za vsak i ∈ {0,1, . . . , n−1} velja vivi+1 ∈ E. V tem primeru pravimo, da je ta sprehod dolžine n. Če so vozlišča vi paroma različna, govorimo o poti od u do v.
Z drugimi besedami: če po obstoječih povezavah grafa pridemo od nekega vozlišča do nekega drugega vozlišča, zapisano zaporedje vozlišč, ki smo jih pri tem obiskali, imenujemo sprehod. Število povezav, po katerih smo prišli do določenega vozlišča, določa dolžino sprehoda. Pot pa je enostavneje povedano sprehod, kjer nobene povezave, niti vozlišča, nismo obiskali dvakrat.
v6
v=v7 v4
v5
v2 v3 v1
u=v0
Γ
Slika 2.6: Sprehod.
Rdeče obarvan del grafa Γ na sliki 2.6 predstavlja sprehod (v0, v1, v4, v3, v5, v4, v3, v1, v7) dolžine 8 od u dov.
v6
v=v7 v4
v5
v2 v3 v1
u=v0
Γ
Slika 2.7: Pot.
Rdeče obarvan del grafaΓna sliki 2.7 predstavlja pot(v0, v1, v3, v4, v7)dolžine 4 od u dov.
Definicija 7. Graf Γ je povezan, če v njem za poljubni vozlišči u, v ∈ V obstaja pot od u do v. Obhod ali sklenjen sprehod v grafu Γ je tak sprehod (v0, v1, . . . , vn), kjer je vi ∈ V(Γ), da velja vn =v0. Cikel je obhod dolžine vsaj tri, na katerem se razen prvega in zadnjega vozlišča ne ponovi nobeno vozlišče. Dolžini najmanjšega cikla v grafu Γ pravimo ožinagrafa Γ.
Če obhod vsebuje vse povezave grafa Γ in se nobena povezava ne ponovi, ga imenujemo Eulerjev obhod.
a
b c
d f e
Slika 2.8: Graf z ožino 3.
Na sliki 2.8 je primer grafa z ožino 3. Tudi graf Γp s slike 1.1 ima ožino tri.
Cikel dolžine tri sestavljajo npr. Ajda, Peter in Rok.
V povezanem grafu torej lahko iz vsakega vozlišča po obstoječih povezavah grafa pridemo v vsako drugo vozlišče.
v1
v2
v3 v4
v5
Γ
Slika 2.9: Nepovezan graf.
GrafΓna sliki 2.9 ni povezan, ker npr. iz vozliščav2po obstoječih povezavah ne moremo priti v vozlišče v4.
v0
v1 v2
v3 v4
Γ
Slika 2.10: Primer obhoda.
Rdeče obarvan del grafaΓ (v0, v1, v2, v3, v1, v0)na sliki 2.10 je primer obhoda.
v5
v4 v3
v2 v0 v1
Γ
Slika 2.11: Eulerjev obhod.
Obhod (v0, v1, v2, v3, v1, v4, v5, v0, v3, v4, v0) grafa Γ na sliki 2.11 je Eulerjev obhod tega grafa.
Definicija 8. Če med vozliščemau in v v grafu Γ obstaja kakšna pot, potem dolžini najkrajše poti odudov pravimorazdaljamed uinv in jo označimo z dΓ(u, v)(oziroma zd(u, v), kadar je grafΓrazviden iz konteksta). V primeru, da je grafΓ povezan, maksimalni možni razdalji med vozlišči grafaΓpravimo premer grafa Γ.
u
v
Γ
Slika 2.12: Tri možne poti od udo v.
V grafuΓna sliki 2.12 obstajajo iz vozliščautri poti do vozliščav z dolžinami 1, 2 in 3. Razdalja od u dov v grafu Γ je torejdΓ(u, v) = 1.
u
v
Γ
Slika 2.13: Premer grafa.
Najdaljša razdalja med dvema vozliščema v grafuΓ s slike 2.13 (pripadajoča pot je označena z rdečo) je 3. Do vseh ostalih vozlišč lahko iz vozlišča u pridemo v enem ali dveh korakih. Premer tega grafa je 3.
Za nas bosta v nadaljevanju diplomskega dela pomembni posebni obliki poti in cikla imenovani Hamiltonova pot in Hamiltonov cikel.
Definicija 9. Naj boΓ = (V, E) graf reda n. Pot dolžine n−1 v grafu Γ se imenuje Hamiltonova pot grafa Γ.
Gre torej za pot, ki obišče vsa vozlišča grafa.
v1 v2
v3 v4
v5 v6
v7 v8
v9
v10
Slika 2.14: Petersenov graf.
Graf na sliki 2.14, ki je znan pod imenom Petersenov graf, premore Hamil- tonovo pot (v1, v2, v3, v4, v5, v6, v7, v8, v9, v10).
Definicija 10. Naj bo Γ = (V, E) graf reda n. Sklenjen sprehod dolžine n, ki obišče vsa vozlišča grafa Γ natanko enkrat (torej vsakega, razen prvega in zadnjega), se imenuje Hamiltonov cikel grafa Γ.
v1 v2
v3 v4 v5 v6
v7
Γ v8
Slika 2.15: Hamiltonov cikel.
Hamiltonov cikel grafa Γ na sliki 2.15 predstavlja zaporedje (v1, v2, v3, v4, v5, v6, v7, v8, v1).
Ukvarjali se bomo tudi s tematiko barvanja grafa, zato si poglejmo, kaj točno to pomeni.
Definicija 11. Naj boΓ = (V, E)graf. Preslikava c:V →N je dobro bar- vanje vozlišč grafa Γ, če za poljubna u, v ∈V velja: u ∼ v ⇒c(u)6=c(v).
Najmanjšemu takemu naravnemu številu χ(Γ), da obstaja dobro barvanje c : V → N grafa Γ, za katerega je c(v) ≤ χ(Γ) za vse v ∈ V, rečemo kromatično število grafa Γ.
Kromatično število grafa torej predstavlja minimalno število barv, s katerimi lahko obarvamo vozlišča danega grafa, da nobeni dve sosednji vozlišči nimata iste barve.
Slika 2.16: Dva primera dobrega barvanja istega grafa.
Γ
Slika 2.17: Dobro barvanje grafa z dvema barvama.
Kromatično število grafa Γ na sliki 2.17 je χ(Γ) = 2, saj smo graf uspeli pobarvati s samo dvema barvama tako, da nobeni dve sosednji vozlišči nista iste barve, očitno pa je, da se grafa z eno barvo ne da dobro obarvati.
Za konec tega poglavja se posvetimo še simetrijam grafov, saj so družine grafov, ki jih bomo obravnavali v nadaljevanju, znane tudi po številnih sime- trijah.
Definicija 12. Naj boΓ = (V, E)graf. Permutacija vozliščϕ∈SV (množica vseh bijekcij iz V v V) je avtomorfizem grafa Γ, če ohranja sosednost, to je, če za poljubni dve vozlišči u, v ∈V velja:
u∼v ⇔ϕ(u)∼ϕ(v).
Pri študiju simetrij grafov nas običajno zanimajo taki, ki premorejo prav posebej veliko mero simetrije.
Definicija 13. Naj bo Γ = (V, E) graf. Če za vsak par vozlišč u, v ∈ V obstaja ϕ∈AutΓ, da velja v =ϕ(u), potem je grafΓtočkovno tranzitiven
oziroma po vozliščih tranzitiven. Če za vsaki dve povezavi uv, xy ∈ E obstaja ϕ ∈ AutΓ, da je ϕ(u)ϕ(v) = xy (torej ϕ(u) = x in ϕ(v) = y ali pa ϕ(u) = y in ϕ(v) = x), je graf Γ povezavno tranzitiven. Če za vsaki povezavi uv in xy ∈E obstaja ϕ∈AutΓ, da je ϕ(u) = x in ϕ(v) = y, hkrati pa tudi τ ∈AutΓ, da je τ(u) = y in τ(v) =x, je graf Γ ločno tranzitiven.
1 2
3 4
C
4Slika 2.18: Točkovno, povezavno in ločno tranzitiven graf.
Graf C4 na sliki 2.18 je točkovno tranzitiven, saj očitno velja ϕ = (1234) ∈ AutC4. Isti automorfizem dokaže, da je C4 povezavno trazitiven. Ker je tudi β = (12)(34)∈AutC4, je ta graf tudi ločno tranzitiven.
Trditev 1. Če je graf Γ ločno tranzitiven, je tudi povezavno tranzitiven.
Dokaz: Ločna tranzitivnost zahteva, da lahko vsak urejen par sosednih vozlišč preslikamo v vsak drug urejen par sosednih vozlišč. Zato lahko tudi neurejene pare sosednih vozlišč preslikamo v neurejene pare sosednih vozlišč.
Definicija 14. Graf Γ je razdaljno tranzitiven, če za poljubna vozlišča u, v, x, y∈V(Γ), za katera velja d(u, v) =d(x, y), obstaja avtomorfizem ϕ, za katerega je ϕ(u) = x in ϕ(v) =y.
Definicija 15. Povezan regularen graf Γ je razdaljno regularen, če je za vsako naravno število i in za vsak par vozlišč u in v grafa Γ na razdalji i številoci (oziromaai, oziromabi) sosedov vozliščav na razdaljii−1(oziroma i, oziroma i+ 1) od vozlišča u odvisno samo od števila i.
Iz definicij 14 in 15 je jasno razvidno, da velja naslednje:
Trditev 2. Vsak razdaljno tranzitiven graf je razdaljno regularen.
Sedaj smo spoznali vse za nas pomembne pojme, s katerimi se bomo večkrat srečevali tekom tega diplomskega dela. Nekaj pojmov, ki nastopijo samo v določenih delih poglavij, bomo omenili kar na tistih mestih samih.
Poglavje 3
J GRAFI - POSPLOŠENI JOHNSONOVI GRAFI
Kot smo omenili že v uvodu, bomo v diplomskem delu raziskali lastnosti nekatereih družin zelo simetričnih grafov. Johnsonovi in Kneserjevi grafi sta dve podružini tako imenovane družine J-grafov (imenovanih tudi Posplošeni Johnsonovi grafi), ki jih študirajo predvsem zaradi njihovih številnih simetrij.
Oglejmo si kar definicijo J-grafov, ki je povzeta po [7].
Definicija 16. Naj bodo n, k in i fiksna nenegativna cela števila, za ka- tera velja n ≥ k ≥ i in naj bo Ω fiksna množica števil velikosti n (običajno vzamemo kar Ω = {1,2, ..., n}). J-graf J(n;k;i) definiramo takole: vozli- šča grafa J(n;k;i) so podmnožice množice Ω, velikosti k, pri tem pa sta dve vozlišči sosednji, če je njun presek velikosti natanko i.
Za boljšo predstavo si najprej poglejmo, kako skonstruiramo primer takšnega grafa. Bralca opozorimo, da je konkretna konstrukcija in prikaz večjih grafov, ki bodo obravnavani v tem diplomskem delu, skoraj nemogoča, oziroma si z njo ne moremo veliko pomagati.
Konstrukcija grafa J(5; 4; 3):
1. Naša fiksna naravna števila so : n = 5, k = 4 in i = 3. Naša fiksna množica števil Ω ={1,2,3,4,5}.
2. V množici Ω poiščemo vse podmnožice velikosti k = 4. Te bodo pred- stavljale vozlišča našega grafa. To so: {1,2,3,4}, {1,2,3,5},
{1,2,4,5}, {1,3,4,5}, {2,3,4,5}.
3. Narišemo vseh 5 vozlišč in jih označimo.
{1, 2, 3, 4}
{1, 2, 3, 5}
{1, 2, 4, 5}
{1, 3, 4, 5}
{2, 3, 4, 5}
Slika 3.1: Vozlišča grafa J(5; 4; 3) z oznakami.
4. Izberemo si eno vozlišče (na primer{1,2,3,4}) in med preostalimi voz- lišči poiščemo taka, ki imajo natanko tri skupne elemente s tem prvim vozliščem.
{1, 2, 3, 4}
{1, 2, 3, 5}
{1, 2, 4, 5}
{1, 3, 4, 5}
{2, 3, 4, 5}
Slika 3.2: Prvo vozlišče in vse njegove povezave.
V našem primeru so kar vsa ostala vozlišča sosedi izbranega vozlišča.
5. Enako storimo za vsa ostala vozlišča.
{1, 2, 3, 4}
{1, 2, 3, 5}
{1, 2, 4, 5}
{1, 3, 4, 5}
{2, 3, 4, 5}
Slika 3.3: Prvo in drugo vozlišče z vsemi njunimi povezavami.
6. Dobljena konstrukcija je naš graf J(5; 4; 3).
{1, 2, 3, 4}
{1, 2, 3, 5}
{1, 2, 4, 5}
{1, 3, 4, 5}
{2, 3, 4, 5}
Slika 3.4: Dokončno skonstruiran graf J(5; 4; 3).
3.1 NEKAJ PRIMEROV J-GRAFOV
Preden se posvetimo lastnostim J-grafov, si oglejmo nekaj primerov.
V zgornjem primeru (graf J(5; 4; 3)) smo opazili, da je bilo vsako vozlišče povezano z vsemi drugimi vozlišči. Takim grafom damo posebno ime.
Definicija 17. Graf Γ reda n je poln graf Kn, če sta poljubni dve različni vozlišči sosednji.
Kot pokaže naslednja trditev, vse polne grafe najdemo med J-grafi. Na sliki 3.5 tako vidimo grafe K2, K3, K4 in K5.
{1}
{2} {3}
{1} {2}
{3} {4}
{1} {2}
Γ1: Γ2: Γ3:
{2}
{3}
{4}
{5}
Γ4: {1}
Slika 3.5: GrafiΓ1 =J(2; 1; 0)∼=K2 ,Γ2 =J(3; 1; 0)∼=K3,Γ3 =J(4; 1; 0)∼= K4 in Γ4 =J(5; 1; 0)∼=K5 .
Prejšnji primeri nakazujejo, da velja naslednja trditev:
Trditev 3. Naj bo n ≥ 1 naravno število. Tedaj je poln graf Kn izomorfen J-grafu J(n; 1; 0).
Dokaz: J(n,1,0)je graf reda n, ki ima za vozlišča 1-elementne podmnožice množice{1,2, ..., n}, dve vozlišči pa sta med seboj povezani, če sta disjunktni.
Ker vsako vozlišče premore le 1 element, sta si poljubni dve različni vozlišči med seboj disjunktni in posledično med seboj povezani.
Sledi še nekaj primerov J-grafov.
{1} {2}
Slika 3.6: Graf J(2; 1; 1)ni povezan.
{1, 2, 3} {1, 2, 4}
{1, 2, 6}
{1, 3, 4}
{1, 3, 5}
{1, 3, 6}
{1, 4, 5}
{1, 5, 6}
{2, 3, 4}
{2, 3, 5}
{1, 4, 6}
{2, 3, 6}
{2, 4, 5}
{2, 4, 6}
{2, 5, 6}
{3, 4, 5}
{3, 4, 6}
{3, 5, 6}
{4, 5, 6}
{1, 2, 5}
h
Slika 3.7: Graf J(6; 3; 1).
{1, 2, 4}
{1, 2, 5}
{1, 2, 6}
{1, 2, 7}
{1, 3, 4}
{1, 3, 5}
{1, 3, 6}
{1, 3, 7}
{1, 4, 5}
{1, 4, 6}
{1, 4, 7}
{1, 5, 6}
{1, 5, 7}
{1, 6, 7}
{2, 3, 4}
{2, 3, 5}
{2, 3, 6}
{2, 3, 7}
{2, 4, 5}
{2, 4, 6}
{2, 4, 7}
{2, 5, 6}
{2, 5, 7}
{2, 6, 7}
{3, 4, 5}
{3, 4, 6}
{3, 5, 6}
{3, 6, 7}
{4, 5, 6}
{4, 5, 7}
{4, 6, 7} {5, 6, 7} {1, 2, 3}
{3, 4, 7}
{3, 5, 7}
Slika 3.8: Graf J(7; 3; 1).
3.2 OSNOVNE LASTNOSTI J-GRAFOV
Oglejmo si nekaj osnovnih lastnosti te družine grafov.
Najprej opazimo naslednje:
I. Če je i=k, graf J(n;i;i)očitno nima nobenih povezav.
II. Če želimo, da ima graf sploh kakšno povezavo, mora veljati tudi2k−i≤ n. Če namreč želimo, da sta dve vozlišči v J-grafu J(n;k;i) sosednji, morata imeti v preseku ielementov. Vozlišča so k-elementne podmno- žice Ω, zato v vsakem vozlišču "ostane" še k−i elementov (slika 3.9).
Zanima nas minimalno število elementov množice Ω, da se to sploh lahko zgodi. Torej mora veljati:
n ≥k−i+k−i+i= 2k−i
Zato je smiselno obravnavati le grafe J(n;k;i), za katere je n ≥ 2k−i in i < k.
k-i i k-i
Ω
Slika 3.9: Dve sosednji vozlišči v J-grafih.
Trditev 4. Naj bodo n ≥ k > i taka nenegativna cela števila, da velja n ≥2k−i. Tedaj je J-grafJ(n;k;i)regularen graf z nk vozlišči, (nk)(ki)(n−kk−i)
2
povezavmi in stopnjo grafa kin−kk−i.
Dokaz: Na grafu Γ si izberemo poljubno vozlišče x (k-elementna podmno- žica n-elementne množice Ω). Določimo število njegovih sosedov. Vsako
vozlišče, ki je povezano zx, ima z njim iskupnih elementov in k−ivozlišču xtujih elementov. Skupne elemente izberemo iz k-elementne množicex. Ta- kih kombinacij jeki. Preostalihk−ielementov izberemo iz množiceΩbrez k elementov, ki jih vsebuje že vozlišče x (skupno n−k). Takih kombinacij je n−kk−i. Skupno ima vozliše x kin−kk−i sosedov. Ker smo vozlišče xizbrali poljubno, ima vsako vozlišče v grafu Γ ravno toliko sosedov. To pomeni, da je graf regularen. Če število povezav iz enega vozlišča pomnožimo s števi- lom vozlišč, dobimo dvakratnik števila vseh povezav v grafu, saj je povezava omejena z dvema vozliščema in smo tako eno in isto povezavo šteli dvakrat.
Število povezav J-grafa J(n;k;i) je torej (nk)(ki)(n−kk−i)
2 .
Potrdimo navedbe trditve 4 še na konkretnem primeru. Oglejmo si graf J(6; 3; 1)na sliki 3.7. Vidimo, da ima graf 20 vozlišč, kar se ujema s številom
6
3
. Prav tako so vsa vozlišča v grafu stopnje 9, kar je ravno 3132.
Že v zgornjih primerih smo videli, da velja J(5; 4; 3) ∼= K5 ∼= J(5; 1; 0).
Da je temu res tako, kaže naslednja trditev.
Trditev 5. Za poljubne n ≥ k ≥ i, za katere je n−2k+i ≥ 0, sta grafa J(n;k;i) in J(n;n−k;n−2k+i) izomorfna.
Dokaz: Označimo Γ1 = J(n;k;i) = (V1, E1) in Γ2 = J(n;n − k;n − 2k +i) = (V2, E2). Vozlišča grafa Γ1 so k-elementne podmnožice množice Ω = {1,2, ..., n}, vozlišča grafaΓ2 pa (n−k)-elementne podmnožice množice Ω. Da dokažemo, da sta grafa izomorfna, moramo najti bijekcijoϕ:V1 →V2, ki ohranja sosednost. Pokažimo, da je ustrezna kar preslikava ϕ:A7→(A)c. Pokažimo najprej, da je ϕ bijekcija. V ta namen se najprej prepričajmo, da imata oba grafa isto število vozlišč. Po trditvi 4 ima grafΓ1 nk= k!(n−k)!n!
vozlišč, graf Γ2 pa n−kn = (n−k)!(n−(n−k))!n! = (n−k)!k!n! vozlišč. Grafa imata torej res isto število vozlišč. Torej je za bijektivnost dovolj dokazati injektiv- nost funkcije ϕ. Le-ta je očitna. Če namreč zak-elementni podmnožici Ain
B ⊆Ω veljaAC =ϕ(A) = ϕ(B) = BC, mora seveda veljatiA=B. Torej je preslikava ϕinjektivna in zato tudi bijektivna.
Pokažimo še, da jeϕhomomorfizem grafov, to je, da ohranja sosednost. Naj bosta A inB poljubni sosednji vozlišči v Γ1. Tedaj je |A∩B|= i. Vozlišči A in B s ϕ preslikamo v njuna komplementa AC in BC. Oglejmo si kardi- nalnost |Ac∩Bc|. Po de Morganovem zakonu je |AC ∩BC|=|(A∪B)C|= n− |A∪B| = n −(|A|+|B| − |A∩B|) = n−2k+i. Po definiciji grafa Γ2 sta torej vozlišči ϕ(A) inϕ(B)v Γ2 povezani. Preslikavaϕ torej ohranja sosednost, in zato sta grafa Γ1 inΓ2 res izomorfna.
Pokažimo sedaj, da J-grafi res premorejo precejšnjo mero simetrije, o čemer že tako dolgo govorimo.
Trditev 6. Naj bodo n ≥ k > i nenegativna cela števila, kjer je n ≥ 2k− i. Tedaj grupa avtomorfizmov grafa J(n;k;i) vsebuje podgrupo, izomorfno simetrični grupi Sn. Posledično je graf J(n;k;i) vozliščno, povezavno in ločno tranzitiven.
Dokaz: Naj bo α ∈ Sn. Za poljubno k-elementno podmnožico A množice {1, 2, ..., n} tedaj definiramo α(A) ={α(a) : a ∈A}. Pokažimo, da je tako definirana preslikava α
1. bijekcija na J(n;k;i) in da 2. ohranja sosednost.
Naj bo α(A) = α(B). Potem je {α(a) : a ∈ A} = {α(b) : b ∈ B}, iz česar sledi, da za vsak a ∈ A obstaja b ∈ B, tako da velja α(a) = α(b). Ker je α ∈ Sn, je α injektivna preslikava, torej sledi a = b. Torej za vsak a ∈ A obstaja b ∈ B, da velja a = b. Ker velja |A| = |B| = k, sledi A = B.
Preslikava α je torej injektivna in zato tudi res bijektivna na J(n;k;i).
Pokažimo še, daαohranja sosednost v grafuJ(n;k;i). Vzemimo v ta namen
sosednji vozlišči A inB, to je |A∩B|=i. Ker jeα bijekcija na{1,2, ..., n}, seveda velja |α(A)∩α(B)|=|{α(a) :a∈A∩B}|=i.
Da dokažemo vozliščno tranzitivnost, si izberimo dve poljubni vozlišči A in B, recimoA={a1, a2, ..., ak}inB ={b1, b2, ..., bk}. Preslikavoα si izberemo tako, da veljaα(a1) = b1,α(a2) = b2,..., α(ak) =bk. ElementeΩ\Apoljubno na bijektiven način preslikamo na elemente Ω\B, kjer je Ω = {1,2, ..., n}.
To lahko storimo, ker je |Ω\A|=|Ω\B|=n−k.
Pokažimo še, da je J(n;k;i)ločno tranzitiven, iz česar po trditvi 1 sledi, da je tudi povezavno tranzitiven. Na grafu vzamemo dva poljubna loka (A, B) in(C, D), torej so A, B, C inDtake množice, da velja|A∩B|=|C∩D|=i.
Ker velja tudi |A|=|C|, lahko elemente A\B poljubno na bijektiven način preslikamo na C\D, enako B\A na D\C, A∩B na C∩D, Ω\(A∪B) pa na Ω\(C∪D), kot kaže slika 3.10. Torej je graf J(n;k;i)res tudi ločno tranzitiven.
A B
C D
i i
Slika 3.10: Delovanje preslikave.
Poglavje 4
JOHNSONOVI GRAFI
V tem poglavju bomo obravnavali posebno družino J-grafov, t. i. Johnsonove grafe, ki se imenujejo po Selmerju Martinu Johnsonu (1916 - 1996). Doktor matematike je najbolj znan po pionirskem delu z G. Dantzigom in D. R. Ful- kersonom pri uporabi t.i. »cutting plane« metode za reševanje celoštevilkih linearnih programov ter po Johnsonovih grafih in shemah (bralec lahko več o S. M. Johnsonu izve v [9], [20]). Glavni deli snovi tega tega poglavja so povzeti po [7].
Definicija 18. Naj bo n naravno število in naj bo 1 ≤k ≤n. Johnsonov graf J(n;k) je tedaj J-graf J(n;k;k−1).
Z drugimi besedami: Johnsonov graf sestavljajo vozlišča, ki so vsek-elementne podmnožice izbrane n-elementne množice, dve vozlišči pa sta povezani na- tanko tedaj, ko imata skupnih natanko k −1 elementov. Že v prejšnjem poglavju smo ugotovili, da je za J(n;k;i) grafe smiselno privzeti n≥2k−i.
Za Johnsonove grafe to pomenin≥2k−(k−1) =k+ 1, kar je seveda vedno res, razen v primeru n=k, ki pa da grafJ(n;n)z enim samim vozliščem. V primeru, ko velja n≥k+ 1, torej velja n−2k+k−1 = n−k−1≥0, zato nam trditev 5 pove, da veljaJ(n;k) =J(n;k;k−1)∼=J(n;n−k;n−k−1) = J(n;n−k). Zato je pri obravnavi Johnsonovih grafov smiselno privzetik ≤ n2.
Ker so Johnsonovi grafi le poseben primer J-grafov, tudi zanje velja rezultat iz trditve 4.
Posledica 7. Naj bodo 1≤k < nnenegativna cela števila. Tedaj je Johnso- nov graf J(n;k) regularen graf z nk vozlišči, stopnjo k(n−k) in k(n−k)2 nk povezavami.
Dokaz: Dokaz sledi neposredno iz trditve 4.
4.1 PRIMERI JOHNSONOVIH GRAFOV
Oglejmo si najprej nekaj primerov, ki nam bodo kasneje v pomoč pri pred- stavitvi nekaterih lastnosti te družine grafov.
{1, 2} {1, 3}
{2, 3}
{3, 4}
{2, 4}
{1, 4}
Slika 4.1: Graf J(4; 2).
{1, 2} {1, 3}
{1, 4}
{1, 5}
{2, 3}
{2, 4}
{2, 5}
{3, 4}
{3, 5}
{4, 5}
Slika 4.2: Graf J(5; 2).
{1, 2}
{1, 3}
{1, 4}
{1, 5}
{1, 6}
{2, 3}
{2, 4}
{2, 5}
{2, 6}
{3, 4}
{3, 5}
{3, 6}
{4, 5}
{4, 6}
{5, 6}
Slika 4.3: Graf J(6; 2).
{1, 2, 3} {1, 2, 4}
{1, 2, 5}
{1, 2, 6}
{1, 3, 4}
{1, 3, 5}
{1, 3, 6}
{1, 4, 5}
{1, 4, 6}
{1, 5, 6}
{2, 3, 4}
{2, 3, 5}
{2, 3, 6}
{4, 5, 6}
{2, 4, 5}
{2, 4, 6}
{2, 5, 6}
{3, 4, 5}
{3, 4, 6}
{3, 5, 6}
Slika 4.4: Graf J(6; 3).
Nekateri Johnsonovi grafi so prav posebej zanimivi, zato jih uvrščamo v posebne podskupine z lastnim imenom in jih kot take tudi individualno štu-
diramo. Po trditvi 3 so na primer Johnsonovi grafi J(n; 1) ravno polni grafi Kn (slika 4.5). Tudi grafiJ(n; 2) so zelo zanimivi.
{3}
{1}
{2}
{4}
{6} {5}
{7}
{8}
{9}
{1}
{2}
{3}
{5} {4}
{6}
{7}
Slika 4.5: Na levi polni graf J(7; 1), na desni polni graf J(9; 1).
Definicija 19. Naj bo n ≥ 3 naravno število. Trikotniški graf T(n) je tedaj Johnsonov graf J(n; 2).
Trikotniški grafi imajo nekaj zanimivih lastnosti. Ena izmed njih je predsta- vljena v naslednji trditvi.
Trditev 8. Naj bo n≥3 naravno število. Tedaj je trikotniški graf T(n)izo- morfen grafu povezav polnega grafa Kn, njegov komplement pa je izomorfen J-grafu J(n; 2; 0).
Dokaz: Graf povezav polnega grafa Kn je graf, katerega vozlišča so pove- zave grafa Kn, dve vozlišči pa sta sosednji, če sta pripadajoči povezavi iz Kn incidenčni (imata skupno krajišče). Ker sta v polnem grafu poljubni dve različni vozlišči sosednji, so torej vozlišča grafa povezav polnega grafa Kn ravno vse 2-elementne podmnožice množice{1,2, ..., n}, dve taki podmnožici pa sta sosednji, če sta pripadajoči povezavi incidenčni, to je, če je v preseku teh dveh 2-elementnih podmnožic ravno en element. Očitno gre torej ravno za Johnsonov graf J(n; 2).
Sledi še drugi del dokaza. Trikotniški graf T(n) ima za vozlišča 2-elementne podmnožice dane n-elementne množice, ki so med seboj povezana, če imajo v preseku en element. Komplement grafa T(n)je torej graf, ki ima ista voz-
trikotniških grafih ima namreč vozlišče s poljubnim vozliščem bodisi en sku- pen element bodisi nobenega. Komplement grafa T(n) tako lahko drugače
zapišemo kot J(n; 2; 0).
Pomen drugega dela trditve 8 je v tem, da so tudi grafi oblike J(n;k; 0) zelo zanimivi. Gre za tako imenovane Kneserjeve grafe, ki jih bomo spoznali v poglavju 5.
4.2 RAZDALJNA TRANZITIVNOST IN PRE- MER JOHNSONOVIH GRAFOV
Poglejmo si nekatere lastnosti te družine grafov. Prva izmed njih pove, da je razdalja med dvema vozliščema Johnsonovega grafa odvisna le od kardinal- nosti preseka pripadajočih množic.
Trditev 9. Naj bo n naravno število in naj bo 1≤k ≤n. Tedaj za poljubni vozlišči A in B Johnsonovega grafa J(n;k) velja
d(A, B) = k− |A∩B|.
Posledično je premer grafa J(n;k) enak min{k, n−k}.
Dokaz: Dokaz prvega dela izpeljemo s pomočjo indukcije in sicer z indukcijo na d≥0pokažemo, da za poljubni vozlišči A inB velja, da je
d(A, B) = d⇔ |A∩B|=k−d.
1. d= 0, potem d(A, B) = 0⇔ |A∩B|=k,
Jasno je, da je d(A, B) = 0 natanko tedaj, ko je A = B, kar je ek- vivalentno pogoju A∩B =A, to je |A∩B|=|A|=k=k−0.
2. d= 1, potem d(A, B) = 1⇔ |A∩B|=k−1,
Po definiciji sosednosti v grafu J(n;k) je d(A, B) = 1 natanko tedaj, ko je A∼B, kar se zgodi natanko v primeru |A∩B|=k−1.
3. d ⇒ d+ 1, kjer je d ≥ 1. Naj bosta najprej A, B taki vozlišči, da je d(A, B) = d+1. Potem zagotovo obstaja vozliščeC, da veljad(A, C) = d inC ∼B. Po indukcijski predpostavki je |A∩C|=k−d, hkrati pa velja tudi|C∩B|=k−1. Tedaj je|A∩B| ∈ {k−d−1, k−d, k−d+1}.
Po indukcijski predpostavki bi v primeru|A∩B| ∈ {k−d, k−(d−1)}
veljalo d(A, B)≤d, kar je v protislovju z d(A, B) = d+ 1. Torej velja
|A∩B|=k−d−1 = k−(d+ 1).
Naj bosta sedaj A, B taki vozlišči, da je |A∩B|=k−(d+ 1).
Ker obstajaa∈A\B inb ∈B\A, lahko vzamemoC = (B\{b})∪{a}, ki je seveda zoped vozlišče grafa J(n;k). Zato je |A∩C| = k−(d+ 1) + 1 = k −d in tako po indukcijski predpostavki velja d(A, C) = d.
Ker je|B∩C|=k−1, sledi tudi B ∼C. Iz vsega tega lahko sklepamo, da je d(A, B) ≤ d+ 1. Vendar, če d(A, B) < d+ 1, potem mora po indkcijski predpostavki veljati|A∩B|> k−(d+ 1), kar je v protislovju z |A∩B|=k−(d+ 1).
Torej res velja d(A, B) = d+ 1.
S tem je prvi del trditve dokazan.
Za določitev premera Johnsonovega grafa izberemo poljubno k-elementno množico A. Iščemo k elementno množico B, da bo od A na maximalni razdalji, torej da bo |A∩B| minimalen. To zagotovimo po naslednjem po- stopku. Najprej izbiramo elemente iz Ω\A (kjer jih je n−k), po potrebi pa dodamo še nekatere iz A. Slednjih (torej elementov iz A ∩ B) potre- bujemo max{0, k −(n −k)} = max{0,2k −n}. Tako je k − |A∩ B| =
min{k, k−(2k−n)}=min{k, n−k}.
Trditev 10. Johnsonovi grafi so razdaljno tranzitivni in razdaljno regularni grafi.
Dokaz: Po trditvi 9 za poljubna vozlišča A, B, C, D grafa J(n;k) velja d(A, B) =d(C, D) = d⇔ |A∩B|=k−d=|C∩D|.
Naj bo torej d ≥ 0 tako poljubno celo število, da obstajajo vozlišča A, B, C in D, za katera velja |A∩B| =i = |C∩D|. Kot v dokazu trditve 6 lahko A∩B bijektivno preslikamo naC∩D. Podobno je|A\B|=k−i=|C\D|, zato lahko tudi A\B bijektivno preslikamo na C \ D. Ravno tako velja
|B\A|=k−i=|D\C|, iz česar sledi, da lahkoB\Abijektivno preslikamo naD\C. In nazadnje|Ω\(A∪B)|=n−k−d=|Ω\(C∪D)|, zaradi česar spet Ω\(A∪B)bijektivno preslikamo na Ω\(C∪D).
A B
C D
k-d
k-d
φ φ φ
Slika 4.6: Delovanje preslikaveϕ.
S tem smo dokazali razdaljno tranzitivnost grafa J(n;k). Hkrati to pomeni, da so Johnsonovi grafi tudi razdaljno regularni.
4.3 HAMILTONSKOST JOHNSONOVIH GRA- FOV
Leta 1969 je matematik László Lovász zastavil naslednje vprašanje: ali je res, da imajo vsi povezani točkovno tranzitivni grafi Hamiltonovo pot [12]?
Vse do danes še nihče ni odkril povezanega točkovno tranzitivnega grafa, ki ne bi vseboval Hamiltonove poti, po drugi strani pa tudi pozitivnega od- govora še nikomur ni uspelo dokazati. Omeniti velja, da je Babai leta 1996 postavil domnevo, ki močno nasprotuje Lovászovemu vprašanju [12].
Za Johnsonove grafe po trditvi 6 vemo, da so točkovno tranzitivni. Če je odgovor na Lovászovo vprašanje pritrdilen, naj bi torej vsebovali Hamilto- novo pot. V naslednjem rezultatu Briana Alspacha, povzetem po [1], bomo videli, da za Johnsonove grafe to res drži. V resnici velja še veliko več. V teh grafih namreč obstajajo Hamiltonove poti s poljubno predpisanima kra- jiščema.
Vpeljimo pojem hamiltonske povezanosti še formalno.
Definicija 20. Graf jehamiltonsko povezan, če za poljuben par različnih vozlišč u,v obstaja Hamiltonova pot tega grafa, katere končni vozlišči sta u in v. Graf z enim samim vozliščem je trivialno hamiltonsko povezan.
Izrek 11. Naj bon naravno število in naj bo 1≤k ≤n. Tedaj je Johnsonov graf J(n;k) hamiltonsko povezan.
Dokaz: Če je k < nsta grafa J(n;k)in J(n;n−k)po trditvi 5 izomorfna.
Če torej uspemo dokazati, da je prvi od teh dveh grafov hamiltonsko pove- zan, smo s tem avtomatsko dokazali, da je tak tudi drugi, ali obratno.
Trditev dokažemo z neke vrste dvojno indukcijo, in sicer najprej z indukcijo
na k, pri vsakem k pa še z indukcijo na n. Za graf J(n;k) predpostavimo naslednji indukcijski hipotezi:
1. J(m, k0)je hamiltonsko povezan za k0 < k (in m≥k0) in 2. J(m, k) je hamiltonsko povezan zam < n (in m≥k).
Drugače povedano, ko dokazujemo hamiltonsko povezanost grafa J(n;k), predpostavljamo, da so hamiltonsko povezani vsiJ(m;k0)zak0 < kink0 ≤m ter vsi J(m;k)za m < n.
Začnimo s k = 1. Graf J(n; 1), kjer je n ≥ 1, je poln graf Kn, ki je se- veda hamiltonsko povezan.
Naj bo sedaj k > 1. Pokažimo, da je graf J(n;k) hamiltonsko povezan za vse n ≥k. Začnemo pri J(k;k), ki je graf z enim samim vozliščem in kot tak trivilano hamiltonsko povezan. Recimo sedaj, da je n > k. Po trditvi 5 je J(n;k) ∼= J(n;n−k). Če je torej n−k < k, to je, če je n < 2k, je graf J(n;n−k) (in zato tudi J(n;k)) hamiltonsko povezan po indukcijski predpostavki. Zato lahko v nadaljevanju privzamemo, da velja n ≥ 2k. V tem primeru moramo dejansko pokazati, kako najti ustrezno Hamiltonovo pot. Po trditvi 6 je graf J(n;k) točkovno tranzitiven, zato je dovolj po- kazati obstoj Hamiltonove poti od vozlišča u={1,2, . . . , k}do kateregakoli drugega vozlišča. Naj bov ={a1, a2, . . . , ak}poljubno vozlišče, različno odu.
Če obstaja element x izΩ ={1,2, . . . , n}, ki ne pripada nobeni od teh dveh množic, lahko elementeΩ preimenujemo tako, da nobena izmed množicuin v ne bo vsebovala elementa n. Tako sta obe množici podmnožici množice {1,2, . . . , n−1}. Po indukcijski predpostavki obstaja Hamiltonova pot odu dov v grafu J(n−1;k). Vozlišča, ki so sosedna vzdolž te poti v J(n−1;k), so sosedna tudi v J(n;k). Naj boP0 ustrezna pot odudov v grafu J(n, k).
Pot P0 torej vsebuje vsa vozlišča, ki ustrezajo k-elementnim podmnožicam množice Ω, ki ne vsebujejo elementa n.
Naj bosta sedaj w1 = {y1, y2, . . . , yk−1, yk} in w2 = {y1, y2, . . . , yk−1, zk} dve sosedni vozlišči na P0 (ker je k ≥ 2 in n ≥ 2k, ima P0 vsaj tri vozlišča).
Vozlišče w1 je sosedno z vozliščem w3 ={y2, y3, . . . , yk−1, yk, n}, vozlišče w2 pa z vozliščem w4 ={y2, y3, . . . , yk−1, zk, n}.
Podgraf X grafaJ(n;k), induciran na množici vseh vozlišč, katerih pripada- joče podmnožice vsebujejo elementn, je očitno izomorfen grafuJ(n−1;k−1).
Po indukcijski predpostavki tako v X obstaja Hamiltonova potP00 odw3 do w4. Sedaj naP0 odstranimo povezavo med w1 inw2, dodamo povezavi w1w3 in w2w4 in nato dodamo še pot P00 od w3 do w4 v X. Dobljena pot je Ha- miltonova pot v J(n;k)s končnima vozliščema uin v. Postopek je prikazan na spodnji sliki 4.7.
{1, 2}=u {1, 3}
{1, 4}=v
{1, 5}
{2, 3}
{2, 4}=w1
{2, 5}=w3
{3, 4}=w2
{3, 5}=w4 {4, 5}
P' P''
Slika 4.7: Poti P’ in P” skupaj predstavljata celotno Hamiltonovo pot na grafu J(5; 2).
Če jen >2k, potem seveda vedno obstaja elementx, ki ni vsebovan v nobeni izmed množic u in v in tako prejšnji argument dokaže, da je v tem primeru J(n;k)hamiltonsko povezan.
Ostane nam le še primer n = 2k. V tem primeru obstaja natanko ena podmnožica, ki ne ustreza zgornjemu kriteriju, to je komplement podmno- žice {1,2, . . . , k}. Da zaključimo dokaz indukcijskega koraka, je torej treba le še pokazati obstoj Hamiltonove poti odu={1,2, ..., k} dov ={k+ 1, k+ 2, ...,2k} v J(2k;k).
Oglejmo si k-elementne podmnožice iz {1,2, . . . ,2k}, ki ne vsebujejo ele- menta 2k. Podgraf X0 grafa J(2k;k), induciran na tem naboru vozlišč, je izomorfen grafu J(2k − 1;k) in je hamiltonsko povezan po indukcijski predpostavki. Zato v grafu X0 obstaja Hamiltonova pot od u do w = {1,2, . . . , k−1,2k−1}. Naj bo P kopija te poti v J(2k;k). Sedaj preučimo vse k-elementne podmnožice iz {1,2, . . . ,2k}, ki vsebujejo element 2k. Pod- grafY0, induciran na tem naboru vozlišč, je izomorfen grafuJ(2k−1;k−1).
Graf J(2k −1;k −1) je po indukcijski predpostavki hamiltonsko povezan, torej v grafu Y0 obstaja Hamiltonova pot, ki poteka od {1,2, . . . , k−1,2k}
do v. Ker je končno vozlišče prve poti na grafu X0 v grafu J(n;k) sosedno z začetnim vozliščem druge poti na grafu Y0, obstaja Hamiltonova pot v J(2k;k)odu dov. S tem je indukcijski korak, z njim pa tudi celoten dokaz,
zaključen.
Poglavje 5
KNESERJEVI GRAFI
Kot je nemalokrat v praksi, se tudi Kneserjevi grafi imenujejo po znanstve- niku. Gre za Martina Kneserja (1928 - 2004), ki je najbolj poznan ravno po grafih, ki nosijo njegovo ime, sicer pa se večina njegovih objav ukvarja s kvadratnimi formami in algebrskimi grupami [23].
Definicija 21. Naj bo n naravno število in 1 ≤ k ≤ n. Kneserjev graf K(n;k) je tedaj J-graf J(n;k; 0).
V primeru n < 2k graf nima nobenih povezav. V primeru n = 2k je graf stopnje 1, iz česar sledi da je graf nepovezan (razen v trivilanem primeru, ko je k = 1 in n = 2). To bomo formalno dokazali nekoliko pozneje. Zato je Kneserjeve grafe smiselno preučevati le za n≥2k+ 1.
5.1 PRIMERI KNESERJEVIH GRAFOV
Za začetek si oglejmo nekaj primerov Kneserjevih grafov.
{1} {2}
Γ1:
{1} {2}
{3} {4}
Γ2:
Slika 5.1: Polna grafaΓ1 =K(2; 1)∼=K2 in Γ2 =K(4; 1)∼=K4. Seveda je J(n; 1) = K(n; 1), iz česar sledi, da je vsak poln graf hkrati tudi Kneserjev graf. Malce bolj zanimiva sta grafa K(5; 2) in K(6; 2), ki sta predstavljena na sliki 5.2. Petersenov graf K(5; 2) je eden izmed najbolj znanih grafov v teoriji grafov nasploh.
{1, 2}
{3, 4}
{4, 5}
{3, 5}
{2, 3} {1, 5}
{1, 4}
{2, 4}
{1,3} {2, 5}
{1, 2}
{1, 3}
{1, 4}
{1, 5}
{1, 6}
{2, 3}
{2, 4}
{2, 5}
{2, 6}
{3, 4}
{3, 5}
{3, 6}
{4, 5}
{4, 6}
{5, 6}
Slika 5.2: Levo Petersenov graf K(5; 2) in graf K(6; 2) na desni.
Tudi tako imenovane letvene prečke dobimo kot Kneserjeve grafe, gre namreč za grafe K(2k;k).
