4 Eulerjevi in Hamiltonovi gra

(1)

1 Uvod 1

1 Uvod

Graf G = (V(G), E(G)) sestavlja mnoºica to£k V(G), imenovanih vozli²£, ter mnoºica povezav med temi vozli²£i, E(G). e med vozli²£ema u in v obstaja povezava pravimo, da sta vozli²£i uin v sosednji. Povezavi, ki imata skupno eno kraji²£e, imenujeno inciden£ni povezavi (na primer povezaviuv inuw). Stopnja vozli²£a u, deg(u), predstavlja ²tevilo vozli²£, ki so z u sosednji. Najmanj²o sto- pnjo med vsemi vozli²£i grafa imenujemo minimalna stopnja vozli²£ v grafu in ozna£imo δ(G), najve£jo pa maksimalna stonja vozli²£, ∆(G). e sta v grafu minimalna in maksimalna stopnja enaki re£emo, da je graf regularen. Za grafe velja naslednja opazka:

Lema o rokovanju.

X

v∈V(G)

degG(v) = 2|E(G)|

Graf H = (V(H), E(H)) je podgraf grafa G= (V(G), E(G)), £e velja: V(H)⊆ V(G) in E(H) ⊆ E(G). Podgraf H se imenuje vpeti, £e ima enaka vozli²£a kot graf G. e ima podgraf H na svojih vozli²£ih vse iste povezave kot graf G se imenuje inducirani podgraf grafa G. Graf je povezan, £e za vsak par vozli²£ v grafu obstaja pot med njima. e graf ni povezan, je nepovezan. Vsaka povezana enota grafa se v tem primeru imenuje povezana komponenta grafa. Vozli²£e v grafa G se imenuje prese£no vozli²£e, £e graf po odstranitvi tega vozli²£a postane nepovezan. Povezava e grafa G se imenuje most, £e graf po odstranitvi te povezave postane nepovezan.

(2)

1 Uvod 2

1. Nari²i grafG, £e jeV(G) = {x, y, z, u, v, w}inE(G) = {xz, xu, xv, yz, yv, yw, uv, vw}

ter dolo£iδ(G) in ∆(G). 2. Nari²i primer grafa na

(a) ²tirih vozli²£ih s stopnjami: 2,2,3,3;

(b) petih vozli²£ih s stopnjami: 1,2,2,3,3;

(c) ²estih vozli²£ih s stopnjami: 1,2,2,3,3,5.

3. Dokaºi ali ovrzi spodnje trditve:

(a) Obstaja 3regularen graf na 7 vozli²£ih.

(b) Vsak graf ima sodo vozli²£ lihe stopnje.

(c) Povezan r-regularen graf, kjer je r sodo ²tevilo, nima mosta.

4. Poi²£i in poimenuj komplemente grafov: C₅, K₄, K_3,3. 5. Na sliki je podan graf G.

u v

y w

x z

(a) Nari²i primer podgrafa H grafaG, za katerega je V(H) ={x, z, u, v}. (b) Nari²i primer podgrafa H grafa G, ki je induciran z vozli²£i iz mnoºice

{x, z, u, v}.

(c) Nari²i primer vpetega podgrafa H grafaG.

6. Dokaºi, da ima graf Gbrez trikotnikov na n vozli²£ih najve£

n² 4

povezav.

7. Konstruiraj graf s petimi vozli²£i in ²estimi povezavami, ki ne vsebuje 3- ciklov.

8. Dokaºi: £e sta u in v edini vozli²£i lihe stopnje v G, potem v G obstaja u, v-pot.

9. Za vsak k ≥1 konstruiraj (2k+ 1)-regularen graf, ki ima most.

(3)

1 Uvod 3

10. Naj bo G k-regularen graf, ki nima induciranih ciklov dolºine 3.

(a) Dokaºi, da je |V(G)| ≥2k.

(b) Poi²£i vse take grafe G, ki imajo natanko 2k vozli²£.

11. Ali je katero od spodnjih zaporedij grafovsko?

(a) 6,6,6,6,4,3,3,0;

(b) 6,5,4,3,2,2,2,2.

12. Za katera naravna ²tevila k je zaporedje 5,5, . . . ,5

| {z }

k

,4,3,2,1grafovsko?

13. Dokaºi, da za vsako naravno ²tevilon, obstaja graf G na2n vozli²£ih, katerega stopnje so: n, n, n−1, n−1, . . . ,2,2,1,1.

(4)

2 Izomorzmi grafov 4

2 Izomorzmi grafov

Bijektivna preslikavaf :V(G)−→V(H)je izomorzem grafov, £e jeuv ∈E(G) natanko tedaj, ko je f(u)f(v)∈E(H).

1. Grafe na sliki razdeli v skupine med seboj izomorfnih grafov. e sta dva grafa izomorfna poi²£i izomorzem, sicer poi²£i lastnost zaradi katere nista izomorfna.

G₁ G₂

G₃ G₄

G₅ G₆ G₇ G₈

2. Kateri od grafov na sliki so med seboj izomorfni?

G1 G2 G3

(5)

2 Izomorzmi grafov 5

3. Ugotovi ali sta grafa G_i inH_i na sliki izomorfna. e sta, poi²£i izomorzem med njima, sicer utemelji, zakaj nista izomorfna.

G₁

H₁

G₂

H₂

G₃

H3

4. Naj bo U poljubna kon£na mnoºica in D neka neprazna druºina njenih podmnoºic. Denirajmo graf G takole: V(G) = D in E(G) = {AB;A 6=

B, A∩B 6=∅}.GrafGimenujemo prese£ni graf druºineD. Katerim znanim grafom sta izomorfna prese£na grafa druºine D, kjer je

(a) D ={{i, i+ 1}; i= 1,2, . . . , n−1};

(b) D druºina vseh (n−1)-elementnih podmnoºic n-elementne mnoºice.

5. Dokaºi, da je vsak graf izomorfen nekemu prese£nemu grafu.

6. Petersenov graf lahko deniramo tudi takole. Vozli²£a grafa G so vse 2- podmnoºice 5-mnoºice. Dve vozli²£i sta sosednji natanko takrat, ko imata pripadajo£i mnoºici prazen presek. Dokaºi, da imata poljubni nesosednji vozli²£i v Gnatanko enega skupnega soseda.

7. Naj bo graf G izomorfen svojemu komplementu, to je G∼=G. Dokaºi, da je

²tevilo vozli²£ grafa G kongruentno 0 ali 1 po modulu 4.

(6)

3 Drevesa in dvodelni gra 6

3 Drevesa in dvodelni gra

Drevo je povezan graf brez ciklov. Za drevesa so naslenje trditve ekvivalentne:

1. G povezan in|E(G)|=|V(G)| −1;

2. G je graf brez ciklov in|E(G)|=|V(G)| −1; 3. G je povezan in vsaka povezava vG je most;

4. za vsak par vozli²£ v grafu obstaja natanko ena pot med njima.

Graf G je dvodelni graf, £e lahko mnoºico vozli²£ zapi²emo kot V(G) =A∪B, A∩B = ∅ tako, da znotraj mnoºice A ter znotraj mnoºiceB ni povezav. Izkaºe se, da je graf dvodelni natanko tedaj, ko nima lihih ciklov.

1. Nari²i vsa paroma neizomorfna drevesa na ²estih vozli²£ih.

2. Naj bo F = (V, E) gozd scpovezanimi komponentami. Dokaºi, da je |E|=

|V| −c.

3. Dokaºi, da je zaporedje naravnih ²tevil d₁ ≥ d₂ ≥ . . . ≥ d_n ≥ 1 (n ≥ 2) zaporedje stopenj vozli²£ nekega drevesa natanko tedaj, ko je Pn

i=1d_i = 2n−2.

4. Drevo T ima stopnje vozli²£ 1 in 4. Vemo, da ima natanko 10 vozli²£ stopnje 4, ostala vozli²£a pa so stopnje 1. Koliko povezav oziroma vozli²£ premore drevo.

5. Drevo T ima ²tiri vozli²£a stopnje 2, eno vozli²£e stopnje 3, dve vozli²£i stopnje 4 in eno vozli²£e stopnje 5. Vozli²£ vi²jih stopenj nima. Izra£unaj koliko vozli²£ stopnje 1 ima? Koliko vozli² in koliko povezav ima drevo T? 6. Naj bo T druºina dreves, ki imajo vsa notranja vozli²£a stopnje 3.

(a) Nari²i vsa neizomorfna drevesa druºine T na 12ih in 13ih vozli²£ih.

(b) Pokaºi, da imajo drevesa druºine T ²tevilo listov za 2 ve£je od ²tevila notranjih vozli²£.

7. Naj bo T drevo. Dokaºi, da so vsa vozli²£a drevesa T lihe stopnje natanko tedaj, ko imata, za vsako povezavoe ∈E(T), obe komponenti drevesaT −e liho ²tevilo vozli²£.

(7)

3 Drevesa in dvodelni gra 7

8. Naj bodo vsa vozli²£a nekega drevesa lihe stopnje. Pokaºi, da je ²tevilo povezav takega drevesa liho. Ali trditev velaj za dvodelne grafe?

9. Naj bo T drevo z vozli²£i stopnje 1 in k. Dolo£i vse moºne vrednosti za

|V(T)|.

10. Naj boG k-regularen dvodelen graf zk > 0in dvodelnim razbitjem V(G) = X+Y. Dokaºi, da velja: |X|=|Y|.

11. Iz standardne8×8²ahovnice odstranimo zgornji levi kvadrat in spodnji desni kvadrat. Dokaºi, da dobljene deske ne moremo pokriti z1×2dominami tako, da se domine med seboj ne prekrivajo.

(8)

4 Eulerjevi in Hamiltonovi gra 8

4 Eulerjevi in Hamiltonovi gra

Sprehod v grafu je zaporedje vozli²£ v₁, . . . , v_k, tako da velja v_iv_i+1 ∈ E(G) za vsak i. Sprehod, katerega vsa vozli²£a so razli£na, imenujemo pot v grafu. e se sprehod za£ne in kon£a v istem vozli²£u, govorimo o sklenjenem sprehodu.

Sklenjen sprehod v grafu, ki poteka skozi vse povezave in sicer skozi vsako natanko enkrat je Eulerjev obhod. e tak sprehod ni sklenjen, mu pravimo Eulerjev sprehod. Graf je Eulerjev £e vsebuje Eulerjev obhod.

Izrek. Povezan graf je Eulerjev natanko tedaj ko ima vsa vozli²£a sode stopnje.

Povezan graf premore Eulerjev sprehod natanko tedaj, ko ima najve£ dve vozli²£i lihe stopnje.

Vpet cikel grafa se imenuje Hamiltonov cikel (to je cikel, ki vsebuje vsa vozli²£a grafa). Vpeta pot grafa se imenuje Hamiltonova pot. Graf je Hamiltonov, £e premore Hamiltonov cikel. O hamiltonskosti vemo naslednje:

Trditev. Naj bo G graf in S neprazna podmnoºica vozli²£ grafa. e ima graf G\S ve£ komponent kot je vozli²£ v mnoºici S, potemG ni Hamiltonov.

Trditev. Naj bo G Hamiltonov graf. Tedaj za vsako mnoºico S vozli²£ velja, da ima graf G−S kve£jemu |S|povezanih komponent.

Trditev. Naj boG graf ter u inv njegovi nesosednji vozli²£i. e je deg(u) +deg(v)≥ |V(G)|,

potem je G Hamiltonov natanko tedaj, ko je Hamiltonov grafG+uv.

Izrek. (Ore) Naj boG graf na vsaj treh vozli²£ih in naj za vsak par nesosednjih vozli²£ uin v velja: deg(u) +deg(v)≥ |V(G)|. Potem je graf G Hamiltonov.

Izrek. (Dirac) Naj boG graf z vsaj 3 vozli²£i in naj boδ(G)≥ ^|V^(G)|₂ . Potem je graf GHamiltonov.

1. Ali lahko graf G na sliki nari²emo v eni potezi?

2. Ali obstaja Eulerjev sprehod po £rnih poljih 4×4 ²ahovnice, £e se lahko iz danega polja premaknemo le na sosednje £rno polje?

(9)

3. Dvoparametri£na druºina grafovG_n,k, kjer jen≥1in0≤k < n, je dolo£ena takole: V(G_n,k) ={A ⊆ {1, . . . , n};|A| ∈ {k, k+ 1}}, E(G_n,k) = {AB;A ⊂ B aliB ⊂A}.Kateri izmed grafov G_n,k so Eulerjevi?

4. Dokaºi, da je graf G Eulerjev natanko tedaj, ko je za vsako razbitje vozli²£

grafaGna mnoºici AinB, kjer veljaA∩B =∅, A, B 6=∅, V(G) = A∪B,

²tevilo povezav z enim kraji²£em v A in drugim v B sodo, vendar ne enako 0.

5. Povezavni graf L(G)grafaG je prese£ni graf povezav grafaG. (Vsaka povezava grafaGpredstavlja eno vozli²£e grafaL(G), dve vozli²£i grafa L(G)sta sosednji natanko tedaj, ko sta pripadajo£i povezavi v G sosednji). Dokaºi ali ovrzi:

(a) e je G Eulerjev, potem jeL(G)Eulerjev.

(b) e je L(G) Eulerjev, potem je GEulerjev.

6. Naj bo G dvodelen hamiltonov graf z dvodelnim razbitjem V(G) = A∪B.

Dokaºi, da je |A|=|B|.

7. Za katere n so graK_n in W_n Hamiltonovi?

8. Za katere n je kocka Q_n Hamoltonov graf?

9. Preveri hamiltonskost grafa na sliki.

10. Za grafe na sliki 1 preveri ali so Hamiltonovi.

(10)

G H K

Slika 1: Gar G,H, K.

11. Naj bo G graf na vsaj treh vozli²£ih in n=|V(G)|. Dokaºi, da iz

|E(G)| ≥

n−1 2

+ 2

sledi, da je graf Ghamiltonov.

12. Dokaºi, da Petersenov graf ni hamiltonov.

13. Dokaºi, da za poljuben r > 0, vsak r-regularen graf G, z 2r+ 1 vozli²£i premore hamiltonovo pot.

14. Dokaºi, da dvodelni graf na lihem ²tevilu vozli²£ ne more biti Hamiltonov.

15. Dokaºi, da je za vsako naravno ²tevilon grafK_n,2n,3n Hamiltonov in da graf Kn,2n,3n+1 ni Hamiltonov.

(11)

5 Ravninski gra 11

5 Ravninski gra

Graf je ravninski, £e ga lahko v ravnini nari²emo tako, da se njegove povezave ne sekajo. Za povezane ravninske grafe velja naslednja zveza:

n−m+f = 2.

kjer je n ²tevilo vozli²£, m ²tevilo povezav, f pa ²tevilo lic ravninskega grafa G. Izrek. (Kuratowski) GrafGje ravninski natanko tedaj ko ne vsebuje podgrafa, ki je subdivizija grafa K5 ali subdivizija grafa K3,3.

1. Kateri izmed grafov na sliki so ravninski? Ravninskim grafom dolo£i ²en, m inf.

G

H

2. Kateri izmed grafov K₅, K₆, K_3,3 in K_3,4 imajo lastnost, da je podgraf, ki je induciran z odstranitvijo poljubnega vozli²£a, ravninski graf?

3. Ali je kateri izmed grafov G, H na sliki 2 ravninski?

Slika 2: Grafa G, H.

4. Graf G ima 15, graf G¯ pa 13 povezav.

(a) Koliko vozli²£ ima graf G?

(12)

5 Ravninski gra 12

(b) Skiciraj 2 primera grafa G¯, od katerih naj bo eden ravninski, drugi pa ne.

5. Z uporabo Eulerjeve formule dokaºi, da Petersenov graf ni ravninski.

6. Ali je graf na sliki 3 ravninski?

Slika 3: GrafG.

7. Nari²i 5-regularen ravninski graf.

8. Dokaºi: £e jeGravninski graf na vsaj 11 vozli²£ih, potem njegov komplement ni ravninski.

(13)

6 Barvanje vozli²£ in povezav 13

6 Barvanje vozli²£ in povezav

1. Barvanje vozli²£

Barvanje vozli²£ grafa je preslikava c : V(G) −→ {1,2, . . . , k}, ki vsakemu vozli²£u priredi neko barvo. Barvanje vozli²£ grafa je dobro, £e sosednjima vozli²£ema priredimo razli£ni barvi. Kromati£no ²tevilo grafa, χ(G), je najmanj²e ²tevilo barv, ki jih potrebujemo, da graf po vozli²£ih dobro pobarvamo. Velja naslednje:

• Naj bo G dvodelni. Potem je χ(G)≤2.

• Za vsak graf Gvelja: χ(G)≤∆(G) + 1.

• (Brooks) e G ni poln graf ali lihi cikel, potem je χ(G)≤∆(G). 2. Barvanje povezav

Barvanje povezav grafa je preslikavac:E(G)−→ {1,2, . . . , k}, ki vsaki povezavi priredi neko barvo. Barvanje povezav grafa je dobro, £e inciden£nima povezavama priredimo razli£ni barvi. Kromati£ni indeks grafa, χ⁰(G), je najmanj²e ²tevilo barv, ki jih potrebujemo, da graf po povezavah dobro pobarvamo. Velja naslednje:

∆(G)≤χ⁰(G)≤∆(G) + 1.

Za graf re£emo, da je tipa 1, £e je χ⁰(G) = ∆(G) in da je tipa 2, £e je χ⁰(G) = ∆(G) + 1.Dvodelni gra so tipa 1.

1. Dolo£i kromati£no ²tevilo grafov: K_n, C_n, W_n. 2. Dolo£i kromati£no ²tevilo grafov G inH na sliki.

G

H

(14)

3. V tovarni so naredili skladi²£e kemikalij a, b, c, d, e, f, g. Pari kemikalij, ki ne smejo stati skupaj so: ab, ac, ad, ag, bc, bd, be, bg, cd, cf, df, f g. Najmanj koliko prostorov potrebujemo?

4. Dolo£i kromati£no ²tevilo grafaG= (V, E)zV(G) = {1,2, . . . , n}inE(G) = {uv; u+v je pra²tevilo}.

5. Dolo£i kromati£ni indeks grafov C_n, W_n, K_n.

6. Dolo£i kromati£ni indeks grafov G, H inK na sliki.

G H

K

7. Na O bo 7 svetovalnih delavcev 34 u£encem svetovalo glede ²olanja. Razgo- vori bodo potekali individualno. Vsak od u£encev mora na vsaj en in najve£

3 razgovore. Najmanj koliko razli£nih terminov za razgovore moramo dolo-

£iti, £e mora prvi svetovalni delavec opravit 3, drugi in tretji 10, £etrti 7, peti in ²esti 14 ter sedmi 9 razgovorov.

8. Na tekmovanju sodeluje n mo²tev. Vsako mo²tvo mora odigrati tekmo z vsakim od preostalih n −1 mo²tev. Najmanj koliko kol je potrebnih, £e lahko hkrati odigrajo poljubno ²tevilo tekem, v katerih tekmujejo razli£na mo²tva? Za n= 5 zapi²i tudi primer moºnega razporeda.

9. Dolo£i kromati£ni indeks grafa na sliki 4.

a

b

c

d e f

g h

i

Slika 4: Grafa G.

(15)

10. Naj bo n ≥ k(k+ 1) in naj bodo vozli²£a grafa G_n,k postavljena tako, da tvorijo vozli²£a enakostrani£nega n-kotnika. Vsako vozli²£e je sosednje s k najbliºjimi sosedi v vsako smer. Dokaºi, da je

χ(G_n,k) =

k+ 1; k+ 1 deli n, k+ 2; sicer.