~ Io------- liL/ ctc,', -~> l(,6- 1q ~ ~ 9~~~ . ~~ ~~/f ~fYld' nAJnUJnEJŠE... o GRAFI11 DRUSTVO-MATEMATIKOV, FIZIKOV IN ASTRONOMOV SRS Ljubljana 1985 Math. Subj. Class. (1980) 50 - 01, 50C VSEBINA Stran 1. Uvod 2. Med ničeln im in polnim grafom 3. Pot, cikel in še kaj 4. Drevesa 5. Nekaj osnovnih l as t nost i gr afov 6. Dvodel ni grafi 7. Regularni grafi 8. Usmerjeni grafi in turnirji 9. Eulerjevi obhodi 10. Rešitve nalog Sklepna besed a Stvarno kazalo 2 3 5 9 14 18 22 28 33 44 49 62 63 1. poglavje UVOD Oglejmo si sliko 1.1! Kar dovolj je zapletena! Na njej so označene tOČke A, B, C, D, E, F, G in H. Od teh osmih točk so nekatere med sabo povezane s črtami - daljicami ali loki. Za te zveznice bomo uporabljali izraz povezave, ker se nam zdi, da še najmanj zavaja našo predstavo. Takoj povejmo, da nas njihova podrobna oblika sploh ne bo zanimala. za nas bo važno le to, ali sta dani točki povezani ali ne. L E F Slika 1.1 o H Poljubni točki nista nujno povezani . Lahko pa sta, in to tudi večkrat (govorimo o veČkratnih povezavah). Med povezavami na sliki 1.1 so nekatere · opremljene s puščico, rečemo jim usmerjene povezave, druge pa ne (neusmerjene povezave). Točka je lahko povezana sama s seboj z zanko (na primer točka C na sliki 1.1.). Manjka samo še izraz za celotno sliko. Recimo ji graf. Posebej opozorimo na tole: na sliki 1.1 se povezavi AC in BD sekata. Presečišču pravimo navidezna tOČka. Navidezna točka ni točka grafa. Nastane le zaradi risanja grafa. Če bi povezavo BD narisali v obliki loka, bi se lahko navidezni točki izognili! Malo domišljije je treba, pa nam točke grafa lahko predstavljajo mesta, povezave pa cestne odseke, enosmerne in dvosmerne, ki povezujejo mesta v cestno mrežo. Kaj vse lahko z bežnim pogledom razberemo iz cestnega 3 omrežja na sliki 1. 1! Iz točke Alahko dopotujemo v točko D po dveh cestnih odsekih. Iz D lahko pridemo v A neposredno po dvosmernem cestnem odseku . Lahko pa gremo naj pr e j po enosmer ni ul i ci do C, potem pa po dvosmerni do A. Iz točke AvE spl oh ne moremo priti (morda ležijo mesta E, F in G na otoku?) . Zanka v C predstavlja mor da sprehajališče , saj povezuje mesto C s samim seboj! Točka H je izolirana (osamljena). Iz nje i n vanjo ne vodi nobena povezava (H bi bi l lahko čisto majhen otok brez cest!). Navidezne točke niso cestna križišča, ampak nadvozi (alf podvozi) . Cestno omrežje pa ni edina predstava, ki jo lahko damo našemu grafu . Takoj omenimo dr ugo (in bralcu toplo priporočamo, da si sam poišče še tretjo!). Vsaka točka naj pomeni nogometni kl ub. Povezava med danima točkama pomeni, da sta se ustrezni ekipi pomerili med sebo j. Ce se j e to zgodi lo večkrat , je v grafu med njima več povezav . Neusmer jena povezava naj pomeni neodločen izid, usmerjena pa zmago. Povezava, usmerjena npr . od A proti B, pomeni, da j e ekipa A premagala ekipo B. V tej luči preberemo iz slike 1. 1, da j e moštvo D premagalo moštvo C, eki pi A in D st a se srečali dvakrat. Enkrat je zmagal o moštvo A, drugič pa j e bi l rezultat neodločen. Podobno st a se moštv i E in G srečali t r ikr at . Br al ec pa naj premisl i , kat ero moštvo j e imelo v teh t r eh srečanjih več špor t ne sreče ! Malo težje j e dati pomen zanki v točki C. Reci mo , da t o pomeni trening t ekmo med moštvom i n r ezervnimi i gralci ! Graf na sliki 1. 1 je precej splošen . V nj em nastopajo usmer jene i n neusmerjene povezave, zanke , večkratne povezave. Če se hočemo poceni dokopati do neka j osnovnih l astnosti gr afov, bo zat o priporočljivo , da pr ist anemo na kakšno omejitev. Naj pr e j pre povemo vse usmer jene povezave . Dobl j eni gr af se i menuj e neusmerjeni graf. Nato prepove mo vse zanke in večkratne povezave. Takemu gr af u pr avi mo enostavni neusmerjeni graf ' (kratkosti na l j ubo mu bomo re kli preprosto graf) . V kasne jših pogl avj i h se bomo l ot i l i spet dr ugega posebnega primera : gr afa, katerega vse povezave so usmerjene . To bo usmer jeni graf. Dogovorimo se še za neka j oznak. Če je G (neusmerjeni ) gr af , bomo z V(G) označil i množico njegov ih točk , z E(G) pa množico n j egovi h povezav . Povedati mor amo , da nekat er i prav ijo točkam vozlišča, poveza vam pa veje. Točki A i n B, ki jU veže kaka povezava e = AB = BA, st a sosednji . Rečemo , da st a A in B krajišči povezave e . Točke bomo označevali z veliki mi črkami , i z j emoma s š t evil kami. Povezave bomo oz načeva li z mali mi črkami . 4 2. poglavje MED NICELNIM IN POLNIM GRAFOM Cepr av j e enostavni neusmerjeni gr af le poseben primer splošnega grafa, irr~mo še vedno opravka z bogatim gradi vom, ki ga kaže sistematično obdel ati. Zato bomo gr af e , ki so tako ali drugače sorodni, obr avnaval i skupaj. Naj bo n števi l o točk grafa i n m število njegovih povezav. Ti š t evi l i sta precej neodvi sni . Hočemo reči: če poznamo n, s t em m še ni ka j pr ida določen, zanj ostane š e vedno prece j možnosti . Kar sama od sebe se vsiljujeta dva skrajna primera . Prvega ponazarja slika 2.1 i n ga ni t ežko opredeliti . To j e graf brez povezav (m O). Pravimo mu ničelni graf Nn na n točkah. Indeks n pomeni število točk. Slika 2.1 prikazuje N6 (n = 6, m = O). o o o o Slika 2.1 o o Slika 2. 2 Drugi skraj ni pr imer prikazuje slika 2. 2. Tu je n = 5 in m = 10. za ta gr af je značilno , da je v njem vsaka točka povezana z vsako drugo . Takemu grafu pravimo polni graf Kn na n točkah. Na sliki 2. 2 je prikazan K5• še enkrat poudarimo, da ima K5 na sliki 2.2 le pet točk. Na sliki vidimo š e pet navideznih točk, ki nastanejo pri sekanjU povezav. Ce si grafe spet zamišl jamo kot nogometna prvenstva, nam gr af na sliki 2. 2 pomeni 5 ekip ob koncu prvenstva, ko je vsako moštvo že i gralo z vsakim dr ugim moštvom natanko enkrat (rezultati posamezni h dvobojev pa nas ne zanimaj o) . 5 10 pol ni gr af na n točkah? Račun ni t ežak . vsemi dr ugi mi (n - 1) točkami . Skupa j j e srno vsako povezavo š t el i dvakrat , enkrat v treba t o š t evilo razpolov it i: Koliko povezav premore Kn, Vsako od n točk lahko povežemo z tor-ej n(n- 1) povezav. Pri t em pa eni smeri, drugič v drugi . zat o j e (2.1) m = n(n - 1) /2 Če vstavirno v obrazec (2. 1) n = 5, r es dobimo m 5' 4 / 2 povezav, kar srno videli že na sli.ki 2. 2. Če združimo oba skr a j na primera, že lahko postavimo meji , ~ed kater ima se mora gi bat i ~tevilo povezav m pol jub nega (enostavnega ) gra f a G z n točkami : (2. 2) ° < m < n(n - 1 )/2 2. 1. Zgl ed : Koliko j e različnih grafov s tremi točkami ? Če vstavirno v obrazec (2. 2) n = 3, dobimo (2.3) 0::m::3 Graf na treh točkah i ma lahko 0, 1, 2 ali 3 povezave. Slika 2.3 kaž e vse razl ične gr af e na treh točkah . Lii AB A B o A I o C (1) o B o C 0 >--- - .....0 A B (2 ) (3 ) (4) o A I \ B (5) I Slika 2.3 Slika 2. 4 Mogoče se bo komu zdelo , da srno pozabili gr-a f na sliki 2. 4 in mor da še katerega. To j e odvisno od tega , kako gledamo na stvar . Pa se kar dogovorimo, da kasneje ne bo nesporazumov. Če bi ločil i med točkami - npr. če bi bi l e A, B, G popolnoma določene osebe, povezave med njimi pa relacija ' poznat i se' , teda j bi se gr af (2) na sliki 2.3 in graf (5) na sl iki 2. 4 res r azlikovala . Nikakor ni isto, če se poznat a B i n G al i pa če se poznata A in B. Če pa i mamo vse točke za enakovredne (zamenl j i ve ) , tako da jih lahko po vol ji pr eimenujerno, t eda j pa nas oznake ne zanimajo in pr iznati moramo , da gre npr . pri grafih (2) in (5) pr-avzapr-av za en s am graf , le oznake so drugače razdeljene . Če na graf u (2) pr ei menuj emo točko A v točko G, točko G pa v točko A, do~imo ravno gr af (5) . Preimenovanj e : A - G, B - B, G - A nam iz gr afa (2) da graf (5) . 6 Učeno pravimo grafoma, ki ju lahko spreminjamo enega v drugega s preimenovan jem točk, izomorfna grafa. Izomorfizem je taka preslikava točk prvega grafa na točke drugega grafa (preimenovanje), ki ohranja sosednost : sosednji točki prvega grafa preslika v sosednji točki drugega in nesosednji točki prvega v nesosednji točki drugega. Včasih je precej težko ugotoviti, ali sta dva grafa izomorfna ali ne. Izomorfna grafa imata vse 'bistvene' lastnosti enake. Imata isto število točk, isto število povezav itd.°nCE~H D~ cc DUC A 8 F~G A~8 A 8 (1) Slika 2.5 (2) (1) Slika 2.6 (2) Grafa na sliki 2.5 sta izomorfna. Prvega preimenujemo v drugega takole: A - E, D - G, C - H, B - F. Grafa na sliki 2.6 pa nista izomorfna. V grafu (1) obstaja izolirana točka (to je točka Cl, ki nima nobenega soseda. V grafu (2) pa ni izolirane točke. Grafa torej nista izomorfna, čeprav se ujemata v številu točk in povezav. Vrnimo se spet k zgledu 2.1. Vprašanje bi se moralo glasiti : Koliko neizomorfnih grafov s tremi točkami obstaja? Če pa bi želeli ločiti med grafoma (2) in (5), bi morali vprašati: Koliko grafov na treh točkah obstaja? 2.2. Zgled: Ada, Beti in Cilka so tri dekleta iz istega mesta. Graf (2) na oC oC AI C \BAO 08 AO 08 °8 AO (1) (2) (3) (l.) AL8 A~B AI\8 ALB (5) (6) (7) (8) Slika 2.7 7 sliki 2. 3 prikazuje položaj, ko se Ada in Beti poznata, Cilka pa ni njuna znanka . Graf (3) na sl iki 2.3 prikazuje položaj, ko Ada pozna Beti in Cilko, Beti i n Cilka pa se ne poznata. Koliko je vseh možnost i ? Na sliki 2.7 je prikazanih vseh 8 možnosti. Na treh točkah obstaja 8 gr afov. 2.3. Zgled : Koliko gr afov je na pet ih točkah? Naj pre j poglejmo, koliko je sploh možnih povezav med petimi točkami. To je ravno število povezav polnega grafa KS' I z obrazca (2.1) dobimo za n = S: m 10. Vsako povezavo l ahko bodisi obdržimo, bodisi zbrišemo. Prva povezava daje 2 možnosti, druga ravno tako 2, in tako napr e j do desete. Ker so izbire neodvisne med seboj, dobimo skupno števi lo: 2· 2 '2 ' 2' 2.2.2 .2.2. 2= 210 = 1024 možnosti. 2. 4. Vaja : Koliko neizomorfnih grafov na štirih točkah obsta ja? 2.S. Va ja: Kol iko grafov na n točkah obsta ja? 2.6. Vaja : Grafe na sliki 2.8 razdeli v skupine med sebo j izornorfnih gr afov. Če sta dva grafa izomorfna, poišči pr i mer no preimenovanje, s icer pa poišči primerno lastnost, ki grafa razločuje! N (8 ) Cf--~P Q-_-JjR (3 )(2 )(1) Ji\ /f\ Lr7rK A~B E~F I~J lLV V~U lZI~ l~ M N S T A 8 O G HM (4) (5) ( 6) Slika 2.8 8 3. poglavje pal', CIKEL IN SE KAJ Vpeljimo nekaj novih pojmov. St evi l o sosedov točke A v grafu imenujemo stopnja točke A in j o označimo z d(A). (Nekateri stopnjo imenujejo valenca, . sa j res spominja na valenco atoma v molekuli.) Slika 3.1 Slika 3.2 3.1. Zgled: Kakšne so stopnje točk grafa na sliki 3.1? Stopnje točk so: d(A) =d (B) = d(C) d(D) = 2, d( E) 4. 3.2. Vaja: Kakšne so stopnje točk grafa na sliki 3.2? za stopnje gr afa vel ja nasl ednj i pomemben i zrek. 3.3. Izrek: Če ima graf G n točk in ima teh n točk stopnje dl' d2, graf pa i ma m povezav, vel ja enakost: dl + d2 + d3 + ... + dn = 2m • •• J Dokaz: Vsaka povezava i ma dva ' konca ' . Če se š tejemo vse stopnj e točk , seštejemo r avno vse 'konce' povezav - dobimo natanko dvojno š t evi l o povezav. 3.4. Posledica: ( 1) V poljubnem grafu je š t evi l o vseh l i hi h točk ( točk z liho stopnjo) sodo. (2 ) V poljubnem gr af u veljata za najmanjšo stopnjo dmi n i n za največjo stopnjo dmax neenakosti d. < 2m /n in dmax ~ 2m/n.ml n - 9 Dokaz: (1) Ce v enačbi (3.1) prenesemo vse sode člene z leve na desno. dobimo na desni še vedno sodo število. Na levi pa nam ostane vsota lihih števil (stopenj). Vsot a lihih števil pa bo soda le, če je število členov sodo . V grafu mora biti torej število točk lihe stopnje sodo. (2) Ce v enačbi (3.1) nadomestimo vsako stopnjo di z najmanjšo stopnjo dmi n dobimo neenakost n '~in ~ 2m. Podobno iz enačbe (3 .1) dobimo neenakost n.dmax ~ 2m. Ko delimo obe neenakosti z n, dobimo neenakost i , ki srno jU morali izpeljati. Ena najpomembnejših družin grafov je dr užina poti . Pot Pn je graf na n točkah. ki je izomorfen gr af u s točkami 1. 2, 3, ... , n. v katerem je točka 1 soseda točke 2. točka 2 soseda točke 3. • • •• točka n - 1 pa soseda točke n. Točke 2, 3, n - 1 imajo po dva soseda, točki 1 in n pa imata po enega soseda . Ti dve izjemni točki sta krajišči poti . Slika 3.3 prikazuje pot i P2, P3, P4 in P5 • / .. :>: P, P3 Slika 3.3 PS Poti so r es preprosti grafi. Pot Pn ima n točk in n- l povezav. Na poti Pn ima n - 2 točk stopnjo 2. dve točki - krajišči - pa imata stopnjo 1. Ce bi sklenili krajišči poti. bi dobili graf. ki mu pravimo cikel . Cikel Cn dobimo, če vzamemo za točke oglišča n-kotnika, za povezave pa stranice n- kotnika. Cikel Cn ima n povezav. Ciklu C3 pravimo pogosto kar t r ikotnik. Slika 3.4 pr ikazuje cikle C3, C4, C5, C6 i n C7. 60006 C3 C. Cs Slika 3.4 C. C, Mnogokrat j e pot ali cikel , ki ga obravnavamo, le del kakega večjega 10 grafa. Pravimo, da je podgraf drugega grafa. Na splošno dobimo iz grafa G podgraf H tako, da odstranimo iz G nekaj povezav in točk. (Razume se, da z vsako točko zbrišemo tudi vse povezave, ki imajo t o točko za krajišče.) 3. 5. Zgled: Koliko podgrafov, enakih P2 , ima graf na sliki 3. 1? Ker je P2 povezava, sprašu je naloga po številu povezav gr af a . Teh pa j e 6. 3. 6. Vaja : Kol iko podgr af ov, enakih P 3, P4 ali P5, ima graf na sliki 3. 1? 3. 7. Zgled : Poišči vse cikle, ki so podgrafi graf a na sliki 3. 1! Cikla sta samo dva : ACEA in BDEB. 3. 8 . Vaja: Poišči vse cikle v graf u na sliki 3.5! 1 I I I A B e O Slika 3.5 Sprehod v grafu je t ako zaporedj e točk T1, T2, T3 , ••• , Tn, da je T1 soseda T2, T2 soseda T3, ..• , Tn_1 soseda .Tn. T1 je začetek, Tn pa konec sprehoda. Če j e Tn = Tl' takemu s prehodu pravimo obhod. Če so v sprehodu same različne točke, nam sprehod določa podgraf, ki je pot. Podobno nam obhod s samimi ra zličnimi točkami (z iz jemo krajišč) določa cikel . zato takim sprehodom prav imo kar pot, takim obhodom pa cikel. Spr ehod, v kat er em se točke sicer lahko ponavljajo, povezave pa ne, Imenujemo enostavni sprehod. Podobno defini r amo enos t avni obhod. V prejšn j em poglavj u smo vi del i precej grafov . Nekateri med njimi so bili se st avljeni iz več ' kosov' . Med posameznimi kosi ni bi l o povezav. Če je graf iz enega samega kosa , je povezan , sicer pa je nepovezan. Vsakemu kosu nepovezanega grafa pravimo učeno povezana komponenta grafa. Natančneje: gr~f j e povezan, če za poljubni različni točki obstaja sprehod, ki ima ti točki za krajišči . Če za dve točki grafa tak sprehod ne obstaja, je graf nepovezan 11 in točki cikel Cn Velja tudi pr i padat a različnima njegovima komponent awa . Tako j e na primer povezan gr af na n točkah in vsa ka njegova točka ima stopnjo 2. obratno: če i ma povezani gr af n točk in ima vsa ka njegova točka stopnjo dva, tedaj j e to cikel Cn. 3. 9. ' Zgled: Graf na sliki 3.1 je povezan, graf na sliki 3.2 pa ne. Sest oj i i z t reh povezanih komponent. 3. 10. Vaja: Določi komponente gr afa na sliki 3. 2. Zani mivo j e , da vel ja t al e trditev. 3. 11. Trditev: Če s t a v gr af u točki povezani s sprehodom, sta v nj em povezani tudi s potjo . Dokaz: Naj bosta A in B kraji šči kakega sprehoda. Če so vse točke tega sprehoda različne, sprehod določa pot. Če pa se kaka točka, recimo C, na sprehodu ponovi, tedaj lahko spr ehod razdelimo na tri dele. Spr ehod od A do C, od C do C in od C do B. Srednji del lahko izpustimo in dobimo krajši sprehod od A do B. To lahko ponavljamo, dokler ne dobimo sprehoda s samimi različnimi točkami, kar smo že obravnaval i na začetku dokaza. Če j e v gr af u š t evilo povezav m dovolj majhno, gr af ne bo povezan, pa če še t ako gospodar no povezujemo točke. Seveda j e zanimi vo vpr ašanj e , koliko naj manj mora bi t i povezav, da je gr af lahko povezan. Na t o vprašanje odgovarja nasledn ja t r ditev . 3.12. Trditev: Če ima graf G z n (n > 1) točkami manj kot n-l povezav, graf ni povezan. Dokaz: Dokazujemo z matematično indukci jo. za n = 2 je trdi tev očitna. Recimo, da vel ja trditev za n = k. Dokazal i bomo , da vel ja tudi za n = k + 1. Vzemimo poljuben gr af z n = k + 1 točkami i n z m < k povezavami. Po posl edici 3. 4(2) obstaja v grafu točka s s topnjo d ~ 2m/n < 2k/ (k+1) < 2. Če je d =O, obstaja v grafu osamljena točka in indukcijska hipoteza j e dokazana br ez uporabe indukci jske predpostavke. Če pa je d = 1, obstaja v gr af u točka u s topnje 1 in ko j o iz gr af a odstranimo, dobimo gr af na k točkah z manj kot k-l povezavami. Ta gr af je po indukcijski hipoteZi 12 nepovezan, zat o je tudi večji gr af nepovezan (saj točka u ne more povezati več komponent). Po t rditvi 3.12 ima povezani graf na n točkah vsaj n-1 povezav. Ali bi se mor da dalo dokazati, da mora povezani graf na n točkah imeti vsa j n povezav? Ne, saj je že pot Pn povezani graf na n točkah, ima pa samo n-1 povezav. Kot bomo videli, pa ni Pn edini graf s to lastnost jo. 3.13. Vaja: Nariši vse povezane grafe s petimi točkami in s štirimi povezavami! ( Izomor f ni h gr af ov ne ločil) 3.14. Vaja: za n = 1, 2, 3 i n 4 nariši vse neizomorfne gr afe z n točkami in n-1 povezavami, ki so povezani. Kaj opaziš? Vaji 3.13 in 3.14 govorita o posebni družini gr afov, ki je tako pomembna, da zasluži posebno poglavje. 13 4. poglavje DREVESA V tem poglavju bomo s pregovor i li o dr evesih. za uvod začnimo z novima t rditvama. 4. 1. Trditev: Če v povezanem grafu G odstr ani mo povezavo e = AB i n je dobljeni gr af H povezan, tedaj v G obstaja cikel, ki vsebuje povezavo e. Dokaz: Na sl i ki 4.1 si oglejmo gr afa G in H. Če je H povezan, obstaja v H sprehod, ki veže A z B. Po trditvi 3.11 obsta ja v grafu tudi pot, ki veže A z B. To pomeni, da dobimo i z te poti cikel, brž ko vr nemo odstranjeno povezavo e . Trditev je dokazan a . Slika 4.1 4.2. Trditev: Če v povezanem grafu G odstranimo povezavo e, ki leži na kakem ci kl u, je dobl j eni graf še vedno povezan. Dokaz: Spet l ahko uporabimo kar sl iko 4.1 . Ker e = AB leži na ciklu v G, obstaja v H pot od A do B. Vzemimo poljubni točki C in D gr afa H. Ve~o, da j e mogoče po povezavah gr afa G priti od C do D. To pa lahko storimo tudi na gr af u H. Vsakič, ko bi v grafu G uporabili povezavo e , uporabimo namesto nje pot od A do B, ki poteka po grafu H i n ki po trditvi 3. 11 obstaja . Tr ditev smo dokazali . 14 Če združimo obe trditvi, pridemo do spoznanja . Vsak povezani graf ima tole lastnost: bodisi vsebuje cikel, bodisi mu ne moremo odstraniti nobene povezave, ne da bi pri tem dobili nepovezan graf. In že je vse pripravljeno za novo poimenovanje. Povezani graf brez ciklov se imenuje drevo. Naslednja trditev po svoje karakterizira drevesa. 4.3. Trditev: Drevo je vsak povezani graf z lastnost jo, da izgubi povezanost, brž ko mu odstranimo katerokoli povezavo. Dokaz: Če v drevesu odstranimo povezanost. PO drugi strani odstranimo povezavo , po trditvi poljubno povezavo, zaradi trditve 4.1 pa v grafu, ki zgubi povezanost, brž 4.2 ni ciklov. izgubi ko rru 4.4. Trditev: Povezani graf je drevo, če in samo če vodi od vsake točke do vsake druge ena in ena sama pot. Dokaz: Če bi obstajali dve poti s skupnim začetkom in skupnim koncem, bi v grafu obstajal tudi cikel. Če namreč vzamemo prvo pot veni smeri, drugo pa v nasprotni smeri, tedaj dobimo tak obhod, ki vsebuje cikel. Tudi to trditev bi morali dokazati. Graf bi ne bil drevo. V nasprotno smer je dokaz še lažji. Če povezani graf ni drevo, vsebUje cikel. ~ed poljubnima točkama na ciklu pa obstajata dve poti. 4.5. Trditev: V vsakem drevesu z vsaj dvema točkama obstaja točka stopnje 1. Dokaz: Dokazujemo sprotislovjem. Privzemirno, da trditev ne velja. Na j bo T drevo, ki nima točke stopnje 1. Ker j e gr af T povezan,nima osamljenih točk in je torej stopnja poljUbne točke vsaj 2. Vzemimo poljubno točko A1• Iz nje vodita vsaj dve povezavi. Izberimo poljubno povezavo e1 = A1A2• Ker Ak~ A, Slika 4.2 15 je tudi drugo krajišče A2 st opnj e vsaj 2, obstaja povezava e2 i el' t ako da je e2 =A2A3. Postopek ponovimo v točki A3. Tako dobivamo točke A1, A2, ••• , Ak · Ker i ma T končno mnogo točk, se morajo v zaporedju ponavljati (če prej ne, pa naj kasnej e po k = n, kjer je n število vse h točk drevesa) . Če se ustavimo pri ponovitvi kake točke v zaporedju, dobimo cikel, ki ga prikazuje slika 4. 2. Tako smo dobi li cikel v grafu T, ki pa je dr evo, t or e j graf brez ciklov. Ker nas j e zanikanje t rd itve privedlo do pro tislovja, moramo pač sprejeti trditev. 4.6. Posledica: Če imajo vse točke grafa G stopnjo vsaj 2, vsebuje G ci kel . Dokaz: Ker pogoji posledice veljajo za vsako komponento grafa, se lahko brez škode omejimo na primer, ko je graf G povezan. Po trditvi 4.5 povezani graf brez točk stopnje 1 ne more biti drevo. Povezani graf, ki ni drevo, pa vsebuje cikel . 4. 7 . Trditev: Vsak povezani graf z n točkami in n-l povez avami j e drevo . In obratno : vsako drevo z n točkami ima n-1 povezav. Dokaz prvega dela : Če iz grafa G odstranimo poljubno povezavo , dobimo graf z n točkami in n- 2 povezavami . Ta pa je po trditvi 3. 12 ~agotovo nepovezan . od t od pa že lahko sklepamo, da je G drevo . Dokaz drugega dela : Uporabili bomo metodo matematične indukcije. Indukcija bo po š t evi l u točk gr af a . za n = 1 trditev očitno velja . Osnova indukcije je t u. Dokazati moramo l e še i ndukcijski kor ak. Denimo, da trditev .velja za vsa drevesa z n = k točkami. Naj bo T drevo z n = k + točkaw~ . Po trditvi 4. 5 v njem obstaja vsa j ena točka stopnje 1. Imenujmo to točko A. Z U označimo gr af , ki ga dobimo i z T z odstranitvijo točke A. Glej sliko 4.3. A Q . . . . . · · · ···· · Slika 4. 3 u 16 Očitno smo s t em izgubili ravno eno povezavo. (Na sliki 4.3 je to povezava e = AB.) Jasno je, da je U spet drevo. Ker ima U n točk, zanj hipoteza indukcije velja. U ima torej n - 1 povezav. zato ima T eno več: skupaj n povezav. Tako je tudi indukcijski korak dokazan. Iz n sklepamo na n + 1. Ker je trditev veljavna za n = 1, velja tudi za vsak n. To pomeni, da pri povezanih gr af i h lastnost 'biti brez ciklov ' pomeni isto kot 'imeti za 1 manj povezav kot točk'. Spomnimo se, da ima pot Pn n točk in n - 1 povezav. Ker je Pn povezan graf, je torej le poseben primer drevesa. Zda j t udi r'azumemo, da sta vaji 3.13 in 3.14 spraševali po drevesih! 4. 8. Vaja: Nar iši najmanjših devet dreves, v katerih imajo točke lahko stopnjo samo 4 ali 1. 4.9 . Vaja: Drevo ima samo točke stopnje 1 in 4. Znano je, da ima 10 točk stopnje 4. Koliko povezav ima? Vaja 4.9. je kar težka, če se je lotimo nepripravljeni. Prav nobeni h težav pa ne bo delala, če se spomnimo izreka 3. 3. 17 5. poglavje NEKAJ OSNOVNIH LASTNOSTI GRAFUV o stopnjah točk v gr afu se da povedati mnogo zanimivi h reči . Na pr imer tol e: 5 . 1. Zgled : I zber imo si š t evi l a : dl = 1, d2 = 1, d3 = 2 , d4 = 3, d5 = 3, d6 =4, d7 =4, da =4. Ali obst a j a gr af , ki i ma osem točk in katerega s topnje so izbrana števi l a? Tak gra f obst a ja. Eno od možni h rešitev pr ikazuje slika 5. 1. Slika 5. 1 5. 2 . Zgled: I zber imo š t evi l a : dl = 1, d2 = 1, d3 = 2, d4 = 3, d5 =5, d6 = 6, d7 =6, da = 6. Tak gr af ne obsta ja . Tega ne borno dokazoval i . Br al ca vabimo, da si sam izmi sli še nekaj primerov i n poskuš a ugotoviti s pl oš no pr avi l o , ki mu mora zadoščati zapor ed je s t openj gra fa . Opozarjamo, da je pravi l o prece j zapl eteno i n ga v t ej knj i žici ne bo našel. 5.3 . Trditev: V poljubnem gr af u z vsaj dvema točkama i mat a vsaj dve točki i s to s top njo . Dokaz: Na j bo v gr afu n točk . Najmanjša mogoča s t opnja kake točke je O (če 18 je točka osamljena), največja pa n - 1. Zdi se, da je možnosti dovolj : ravno n, toliko) kolikor je točk v grafu. Toda ne! Stopnji O in n se izključujeta! Če je namreč v grafu kaka točka osamljena, nobena druga točka ne more imeti stopnje n - 1. Če bi imela stopnjo n - 1, bi bila povezana z vsemi točkami grafa , torej tudi z osamljeno točko, to pa je se veda nemogoče. Zato je nujno, da imata vsaj dve točki grafa isto stopnjo! zanimivo bi bilo raziskati grafe, ki 'skoraj' nasprotujejo trditvi 5.3. To bi bili gr af i , v katerih imata le dve točki isto stopnjo. 5.4. Vaja: Ali obstajajo gr af i , v katerih imata le dve točki isto stopnjo, ostale točke pa imajo same različne stopnje? Za hip se spet povrnimo k povezanosti grafov. V drugem poglavju smo izpeljali neenakost (2.2): O~ m~ n(n - 1)/2, ki omejuje število m povezav grafa na n točkah . Kasneje smo s trditvijo 3.12 dokazali, da je pa si zastavimo zagot ovo povezan. odgovarja naslednja nepovezan nasprotno Vprašanje trditev. vsak graf , vprašanje. je: Koliko ki ima m~ n - 2 povezav. Zdaj Če ima graf dovolj povezav, je je 'dovolj' ? Na to vprašanje 5.5 Trditev: Vsak graf z n točkami in več kot (n - 1)(n - 2) 12 povezavami je povezan. Dokaz: Vzemimo poljuben nepovezan gr af na n točkah . Poskusi mo mu povečati število povezav, le da pri tem ne sme pos tat i povezan. Znot r a j vsake povezane komponente lahko dodamo vse povezave . Pra v t ako lahko zvežemo dve Sl i ka 5.2 19 povezani komponenti, če ima graf več kot dve komponenti. Na koncu dobimo dve povezani komponenti, recimo prvo na n1 točkah in drugo na n2 točkah: n1 + n2 = n. Vsaka komponenta je poln graf (sicer bi povezave lahko še dodajali). Število povezav je m = n1(n1- 1) /2 +n2(n2- 1) /2 . Kako moramo izbrati n1 in n2 , da bomo dobili za m največjo vrednost? Naj bo recimo n1 ~ n2 . Če povečamo n1 za in zmanjšamo n2 za 1, se prvi sumand v vsoti poveča za n1, drugi pa zmanjša za n2 - 1. Vsota se poveča za n1 - n2 + lo Postopek se splača nadaljevati. za m bomo torej dobili največjo vrednost tedaj, ko bo n1 = n - 1 in n2 = 1. To je nepovezan graf z n točkami in največjim številom povezav. Ima točno (n - 1)(n - 2) /2 povezav. Vsak graf z več kot toliko povezavami je nUjno povezan. Trditev je dokazana. Preden končamo , vpeljimo še en pomemben pojem: to je komplement grafa. Naj bo G poljuben graf. Komplement grafa G označimo z G in je določen takole. Ima iste točke kot G: V(G)=V(G). VG sta dve točki sosednji, če in samo če nista sosednji v G. Takole si lahko predstavljamo: najprej narišemo graf G z modro barvo. Potem dopolnimo G do polnega grafa tako, da manjkajoče povezave potegnemo z rdečo barvo. Zbrišemo modre povezave in ostane komplement grafa G! 5.6. Zgled: POišči komplement grafa P4. Odgovor kaže slika 5.3. P. Slika 5.3 ~------o -, "- "--, -, -, "o-----~o P.=P. 5.7. Vaja: Nariši vse grafe na štirih točkah in poišči komplementarne pare. 5.8. Vaja: KakŠnemu pogoju mora zadoščati n, da bo kak grar na n točkah izomorfen svojemu komplementu? 5.9. Vaja: Poišči vse grafe, ki so izomorfni svojemu komplementu in nimajo več kot osem točk! 20 za konec pa še tale presenetljivi izrek. 5.10. Izrek: Kakorkoli izberemo graf G, je vsaj eden od grafov G in G povezan. Dokaz: Spet si mislimo, da so povezave grafa G pobarvane modro. povezave njegovega komplementa pa rdeče. Skupaj sestavljata polni graf Kn. Če je rdeči graf povezan, izrek velja. Privzemimo, da rdeči graf ni povezan. Pokazali bomo, da je tedaj modri graf povezan. Spomnimo se, da sta točki v grafu sosednji, če je med njima povezava, in sta povezani, če obstaja v grafu pot, ki ju veže. Vzemimo poljubni dve točki A in B v rdečem grafu. Če v rdečem grafu nista povezani, je med njima neposredna modra povezava. Če pa A in B ležita v isti povezani komponenti rdečega grafa, obstaja taka točka C, ki leži v drugi povezani komponenti rdečega grafa. Povezavi AC in EC sta modri. A in B sta v tem primeru povezani v modrem grafu. 21 6. poglavje DVODELNI GRAFI V tem poglav ju nas bodo zanimal i sodi in lihi ci kli . Cikel Cn je sod, če ima sodo mnogo točk (ali povezav) , torej če je n sodo š t evi l o . Lihi ci kel pa ima liho mnogo točk . Sodi ci kl i so C4' C6, CB, . . . lihi pa C3, CS' C7, 6.1. Vaja: za vsak graf na sl iki 6. 1 določi vse različne dolži ne ciklov, ki jih graf vsebu je. (1) KN41 ~ L G (2) J Slika 6. 1 (4 ) 6. 2. Vaja: za vsak gr af na sliki 6. 1 poišči najdal jš o pot , ki j o graf vsebu je. če graf vse buje pot Pn, tedaj vsebu je tudi Pn- 1, Pn- 2, , P2• Ali velja za cikle podoben skl ep? Cas je, da definiramo dvodelne grafe . Graf G j e dvodelen, če lahko množico njegovih točk VeG) razbi jemo na dve podmnožici V1 in V2 tako, da nobeni točki iz iste podmnožice nista sosednji (med njima ni povezave !) . Povezave (če j i h j e v grafu sploh ka j ) tedaj vežejo le točke i z V1 s točkami iz V2• Vsak ničelni graf Nn je dvodelen, saj nima nobene povezave. Paru V1, V2 pravimo dvodel no razbit je gr afa G. Ce točke i z V1 22 pobarvamo z belo barvo, točke iz V2 pa s črno barvo, nobena povezava ne veže dveh enako pobarvanih točk. Na kratko pravimo, da za dvodelne grafe obstaja belo-črno barvanje točk . Dvodelne grafe rišemo navadno tako, da rišemo točke iz V1 veni vrsti, točke i z V2 pa v drugi vrsti. Na sliki 6.2 so narisani nekateri dvodelni grafi . (5 ) 14 15 (4) 9C1--+----P12 80---013 100-----'011 19 17 'Z'1615 4 5 (2) 14 (3) 12 11 13 10~---?) 6 5 8 (1) 2 3 90------:;0 Slika 6. 2 6.3. Vaja: Dokaži, da sta grafa 6.1(2) in 6.2(1) izomorfna! 6.4. Vaja: Dokaži, da sta grafa 6.1(3) in 6. 2( 2) izomorfna! Ti dve vaji nas prepričata, da sta grafa (2) in (3) iz slike 6. 1 dvodelna . Seveda pa še ne vemo, ali sta gr afa (1) in (4) iz slike 6.1 dvodelna. Ce dvodelni graf 'lepo' nar1semo, se znamo prepričati , da je resnično dvodelen. Ne poznamo pa še mehanizma, ki bi nas prepričal , da kakšen graf ni dvodelen. 6.5 . Vaja: Dokaži , da t r i kotni k (graf C3) ni dvodelen! 6. 6. Vaja: Dokaži , da graf e., ni dvodelen! Kdor je resnično poskusil rešiti vaji zaslutil, da noben lih cikel ni dvodelni graf. 6.5 in 6.6, je verjetno Najprej bomo dokazali nekaj 23 preprostih trditev, ki jih bomo pot rebovali pri dokazu izreka o karakterizaciji dvodelnih gr afov. 6.7. Trditev: Vsak podgraf dvodelnega gr afa je dvodelen. Z drugimi besedami: če graf G vsebuje kak podgraf, ki ni dvodelen, tedaj tudi G ni uvodel en. Dokaz: Naj bo V1, V2 dvodelno razbitje grafa G in naj bo H podgr af v G. Množico VeH) razbijmo na podmnožici W1' W2 t akol e : W1 naj sestoji i z tistih točk gr afa H, ki so v V1, W2 pa iz tistih, ki so v V2• Med dvema točkama iz W1 ni povezave niti v G, kaj š el e v H. Prav tako ni v H povezave med nobenima točkama iz W2• 6.8 . .Zgled : Graf na sl i ki 3.5 je dvodelen. razbitje grafa . Množico V1 sestavljajo točke B, D, E i n G. o tem nas prepriča dvodelno A, C, F in H, množico V2 pa 6.9. Vaja : Dokaži, da grafa (1) i n (4 ) na sl iki 6.1 nista dvodelna. 6.10. Trditev: Graf G, ki sestoji iz povezanih komponent G1, G2, •.• Gk, je dvodelen, če i n samo če j e vsaka komponenta dvodelni gr af . Dokaz: Izraz 'če in samo če ' zahteva, da dokažemo ekvi valenco trditev. To bomo dokazali tako, da bomo najprej dokazali trditev (implikacijo) veni smeri, pot em pa še v naspr ot ni smeri . Po t rditvi 6.7 je vsak podgraf dvodelnega grafa dvodelen. Zato je tudi vsaka komponenta dvodelnega gr afa dvodelna . V nasprotno smer pa dokaz ni nič težji. Če so vse komponente Gi (i = 1, 2, • • • , k) dvodelne , lahko najdemo za vsako od njih raZbitje množi ce točk V(G .) na V1(i) in V2( i) Združimo V1(1), V1(2), • •• , V1{k) v V1, preostale množice pa v V2• Dobljeni množici V1 in V2 sta r avno iskano ra Zbitje množice točk grafa G. Že prej smo zaslutili, da nam lihi ci kl i nagajajo pr i dvodelnosti. Naslednji i zrek pa bo okarakteriziral dvodelne grafe ravno z lihirni cikli. 6.1 1. I zrek: Graf je dvodelen, če in samo če ne vsebuje l i hi h ciklov . Dokaz: Najprej pokažirno, 24 da lih cikel C2n+ 1 ni dvodelen. Točke na ciklu oštevilčimo vzdolž cikla: " 2, 2n+'. Ce bi bil cikel C2n+' dvodelen, bi lahko množico točk razbili na dve podmnožici V, in V2. Recimo, da točka' pripada množici V,. Tedaj točka 2 pripada množici V2' saj je točka 2 soseda točke'. Podobno ugotovimo, da 3 pripada spet V, itd. Točke', 3, 5, pripadajo množici V" točke 2, 4, 6, ••• pa množici V2• Težava nastopi pri zadnji točki 2n+'. Pripadati mora množici V,. Pa smo v protislovju. Ker je 2n+' soseda točke " mora.ležati v drugi množici - to pa ni mogoče. Prvi del izreka je dokazan: če graf vsebuje lih cikel, po trditvi 6.7 ni dvodelen. Preostane še obrat: če graf ne vsebuje lihega cikla, je dvodelen. Naj bo G povezan graf in A njegova točka. Naj bo Vo : {A} mnozlca, ki vsebuje eno samo točko A. V, naj bo množica, ki vsebuje vse sosede točke A. V2 naj vsebuje vse sosede točk iz V" ki jih ni v Vo ali v V" tako gremo naprej: Vk+' vsebuje vse sosede točk iz Vk' ki jih ni v Vk_, ali v Vk• Sestavimo: U, : V, u V3 u V5 u U2 : Vo U V2 U V4 U Naslednji razmislek pokaže, da nobeni dve točki znotraj U, (ali U2) ne moreta biti povezani s povezavo, če v.grafu ni lihega cikla. Recimo, da bi taki točki X in Y obstajali. Denimo, da X pripada množici Vm' Ker so sosede točke X nujno veni od množic Vm_" Vm ali Vm+', lahko sklepamo, da Y pripada isti mnoŽici Vm' Ce je m oblike 2j+', pripadata X in Y množici Ul' sicer pripadata množici U2. Lahko bi se prepričali, da za vsako točko S iz Vk obstaja pot A : SO' S" ••. , ~: S, tako da vsaka točka Sm pripada množici Vm' zato obstajata tudi poti A: XO' X" , .. , Xm: X in A : YO' Y" •.. , Ym: Y. Poti imata skupen začetek in različna konca. zato obstaja na njiju zadnja skupna točka, recimo Z Xi Yi' tako da točke Xi : Yi' yi+" Ym' Xm, Xm_" ..• , Xi oblikujejo cikel lihe dolžine. To je nemogoče, zato takih točk X in Y v grafu ni. To pa dokazuje, da je graf brez lihih ciklov res dvodelen. Iz dokaza razberemo, da je graf dvodelen, če in samo če obstaja zanj belo-črno barvanje točk. Ta izrek je ugoden za ugotavljanje, ali je izbrani graf dvodelen. Ce za graf G najdemo dvodelno razbitje množice točk, ugotovimo, da je dvodelen, če pa v njem poiščemo lih cikel, vemo, da ni dvodelen. 25 6.12 . Posledica: Vsako drevo j e dvodelni graf . Dokaz: Ker dr evo nima ciklov, nima lihih ci kl ov in j e po izreku 6.11 dvodelni gr af. 6. 13. Vaja: Kateri med gr af i na sliki 6.3 so dvodel ni in kateri niso? ( 1) ( 2) ( 3) (4) (6) Slika 6.3 (7) 6.14 . Vaja : Poišči vse Pn, en in Kn, ki so dvodelni ! Če dvodel nernu grafu dodamo povezavo, se kaj r ado zgodi , da zgubi l as tnos t dvodelnosti . Zanimajo nas grafi, ki so dvodel ni, i zgubi j o pa t o l as t nost, če jim dodamo katerokoli povezavo. Očitno mora biti vsaka točka i z V1 soseda vsake točke iz V2• Če ima V1 m točk, V2 pa n tOČk , dobi mo na ta način Krn , n' polni dvodelni graf'. 26 6.15. Zgled: Nari ši gr afe K1, l' K1, 2' K1, 3' K1, 4' K2,2' KZ 3' KZ 4' K3 3' K3 4' K4 4 ' , Rešitev je ~a sliki 6.4. Seveda je Km,n enak grafu Kn ,m. K". K,,> K,, 3 K". K> ,> K> ,3 Slika 6.4 6.16. Zgled: Koliko točk ima graf K ?m, n Pol ni dvodelni graf K ima na enem bregu m točk, na drugem pa n-1IJ , n točk. Skupa j ima m+ n točk. 6.17. Zgled: Koliko povezav ima pol ni dvodelni graf K ?m,n Polni dvodel ni gra f Km,n ima mn povezav: vsaka od n točk pr vega brega je povezana z vsako od m točk drugega brega. 6. 18. Vaja: Koliko največ povezav ima lahko dvodelni gr af na n točkah? 27 druži no gr af ov. da je stopnja 7. poglavje REGULARNI GRAFI V tem poglavju pa s i bomo pobli že ogledali zani mi vo Grafi v njej se odlikujejo po svoji pravilnosti. Spomnimo se, točke š t evi l o nj enih sosedov. 7. 1. Zgled: Določi stopnje točk grafov na sliki 7 . 1! (1) Slika 7 .1 Točke i majo naslednje stopnje: deA) = 1, d( B) = 2, dfC) = 2, deD) = 3, deM) = 3, deN) = 3, d( P) = 3, deR) = 3, deS) = 3, deT) = 3. Na sl iki 7.1 ima graf (2) lastnost, da imajo vse njegove točke isto s t opnjo. Gr afu s to lastnos t jo rečemo regularni graf. Graf G j e regularen stopnje d ali d-val enten, če imajo vse nj egove točke stopnjo d. 7.2 . Zgled: Določi vse regularne grafe stopnje in 2! I II III Iiii 28 (1) (2) (3) Slika 7. 2 ( 4) Edini povezani regularni graf stopnje 1 j e K2. Vs i dr ugi regularni gr af i stopnje 1 sestojijo iz komponent, ki so vse enake K2, Slika 7.2 pr i kazuje štiri regularne gr afe stopnj e 1. Edini povezani r egularni gr afi s t opnje 2 so cikl i en' Vsak r egul arni graf stopnj e 2 sest oj i torej i z komponent , ki so ci kl i - v spl ošnem različnih dol žin , 7. 3. Vaja: Določi vse r egul ar ne grafe s t opnje 2 na 12 točkah. Kol i ko je regularn i h grafov stopnje 2 na 20 točkah? Situacija postane prece j bol j zapl etena pri r egul arnih graf i h višjih stopenj. Že pr i s topnji 3 ni več preprosto popisat i vseh povezanih regularnih grafov. ~timogrede, regu l ar nim graf om stopn j e 3 pr avimo tudi kubični grafi , saj spomi nja jo na mrežo kocke . 7.4. Vaja: Poišči vsa j dva neizomorfna povezana kubična grafa z istim š t evilom točk. 7.5. Vaja : Pokaži , da ne obsta ja kubični gr af, ki bi imel 11 točk. Kdor ni znal r eš i t i te va j e , naj si ogleda trditev 7.6 i n posledico 7.7 . 7. 6. Trditev: za r egul arni graf G s top nje d z n točkami i n m povezavami velja zveza (7 . 1) nd =2m pa dobi moDokaz: V obrazec (3.1 ) vstavimo za vse stopn j e isto vr ednost d , zvezo (7. 1) . I z t e t rdit ve i Zhaja , da j e n = 2m/d. Če j e d l i ho števi lo je n nUjno sodo š tevi l o. To pa l ahko POVeffiO t udi drugače . 7.7 . Posledica: Vsak r egular ni graf l i he s topn je ima sodo mnogo točk. 7.8 . Vaja: Poišči vse pol ne dvodel ne grafe Km n' ki so regularni., 7. 9. Vaja: Al i obs t a ja kak regularni dvodelni graf z l iho mnogo točkami? 7.10. Vaja: Poišči vsa drevesa , ki so r egularni grafi! 29 7. 11. Vaja: Al i j e polni graf Kn regularen? Ogl ejmo si še neka j posebni h druži n gr afov, ki j i h matemati ki i z takš ni h ali drugačnih r azl ogov pogosto omenjajo. Kolo Wn (ali piramida) j e graf , ki ga dobimo s t em , da ci kl u Cn dodamo točko, ki j i pravi mo vrh, in jo zvežemo z vsemi točkam i ci kl a . Sl i ka 7.3 prikazu je kol esa W 3 , W4, W5 in W6• W, W. Slika 7. 3 W, W. 7. 12. Vaja: Poišči vsa kolesa Wn, ki so (a) regularni grafi, (b) dvodelni gr af i ! 7.13. Vaja: Koliko točk i n kol iko povezav ima kol o Wn? Kakš ne so stopnj e točk v grafu Wn? Prizma Tn je gr af , ki je ogr odje n-strane prizme . Dobi mo ga tako, da v dveh koncentričnih pravi lni h n- kot ni ki h paroma zvežemo ustrezna oglišča . Sl ika 7. 4 kaže pr i zme T3, T4, T5 i n T6• T, T. Slika 7.4 T, T. 7.1 4. Vaja : Reši naloge i z 7. 12 in 7.1 3 za gr af e Tn! Antiprizma An je graf , ki j e ogrodje n- strane ant ipri zme. Dobimo ga tako, da vzamemo dva koncentrična pr avi l na n- kotni ka. Zasukamo ju tako , da ima eden oglišča na sredini strani c dr ugega . Potem zvež emo vsako točko 30 notran jega ci kla z dvema najbljižjima točkama zunanjega cikla. Na jbol j e , da pogledamo sl iko 7.5, ki kaže antiprizme A3, A4, A5 in A6• Sl i ka 7. 5 7. 15. Vaja: Reš i nal oge i z 7. 12 i n 7. 13 za grafe An ! 7. 16. Vaja: Kol i ka je dolžina najkra j šega in kolika dolžina najdaljšega cikl a v grafih Wn, Tn in An? Hoebiusova lestvica Mn je gr af, ki ga dobimo iz cikla C2n t ako , da zvežemo vsak par diametralno nasprotnih točk. Sl i ka 7. 6 prikazuje M2, M3, M4, i n Ms · M, Slika 7.6 7.17. Vaja: Ponovi naloge 7.12, 7.13 in 7.16 za grafe Mn ' 7. 18. Vaja: Nariši grafe W7, T7, A7 in ~! Kdor je rešil nalogi 7. 8 in 7.10, je verjetno začuti l, da je poj em regularnosti za nekat er e dr uži ne grafov. prav po mačehovsko pr estr og. Na primer polni dvodel ni grafi Km so tako lepi , da so skoraj regularni . Pa. ,n poskusimo ta pojem strožje zajeti. Graf K i ma n točk stopnje m in m točk stopnje n. To bo naše m,n 31 izhOdišče. V splošnem bomo rekli, da je graf G (m,n)-polregularen, če i ma samo točke stopnje m in točke st opnj e n. (m, m)-polregularni gr af je regularni gr af stopnje m. Ko bomo govor i l i o (m,n)-polregularnih gr af i h , bomo vedno privzeli, da j e m~ n. 7.1 9. Zgled: Ali j e l ahko dr evo polregularen gr af? Lahko ! Vsako dr evo vse buje toČko stopnje 1. Zato j e nujno pol regu l arni graf oblike (m, 1). Pri mer (m,1)-polregularnega drevesa je kar K 1.m, 7.20. Vaja: Ali je kolo Wn pol regularni gr af? 7. 21. Vaja: za katera števi l a m in nobstaja jo (m,n)-polregularna drevesa z 1985 točkami? 7.22 . Vaja: Denimo, Koliko točk stopnje da i ma (4, 1)-polregularno drevo n točk s t opnje 4. ima? (Gl e j vajo 4. 8) 7.23. Vaja: Pokaži, da je kompl ement r egularnega grafa r egul arni gr af . Al i j e t udi komplement polregul ar nega grafa polr egul aren? 32 8. poglavje USMERJENI GRAFI IN TURNIRJI V prejšnji h poglavjih smo se posvečali enostavnim neusmerjenim grafom. V tem poglavju pa bomo govor i l i o usmerjenih gr af i h. To so taki gr af i , ki imajo vse povezave usmerj ene. (Glej sliko 8. 1. ) Slika 8.1 Slika 8.2 Ne bomo se ukvarjali z najbolj splošnimi (usmerjenimi) gr af i. Omej i l i se bomo na enostavne usmerjene grafe. To so usmerjeni grafi z največ eno zanko v vsaki točki in brez večkratnih povezav, ki potekajo v isti smeri; lahko pa sta dve točki povezani dvakrat, vendar v nasprotnih smereh. Glej sliko 8. 2. Usmerjeni graf na sliki 8.1 ni enostaven, ker sta v točki A dve zanki, ker vodita od D do B vzporedni povezavi in ker sta med A in B od treh povezav dve istosmerni. Graf na sliki 8.2 je enostaven usmerjeni graf , sa j po ena zanka v B in C ne moti, niti ne motita povezavi med A in D, saj sta nasprotno usmerjeni. Ce v usmerj enem grafu nadomestimo vse povezave z neusmerjenimi, dobi mo njegov temeljni graf. Temel j ni graf je seveda neusmerjen. Če j e t emeljni gr af enostaven, j e tudi pr vot ni usmerjeni gr af enostaven. Obr at no pa ni res. Če je usmerjeni gr af enostaven, ima njegov temeljni graf največ po eno zanko v vsaki točki in med dvema točkama največ po dve povezavi . 33 Odslej bomo enostavnim usmerjenim grafom rekli pr epr os t o usmerjeni grafi. Podobno kot za neusmerjene lahko tudi pri usmerjenih gr af i h vpeljemo pojem izomorfizma. 8. 1. Zgled: Koliko neizomorfnih usmerjenih gr afov na dveh točkah obst aja? Na dveh točkah obstaja 10 neizomorfnih usmer jenih gr afov, ki j i h kaž e slika 8. 3. o O O O ~ ~ (1) (2) (3) ( 4) ~ <> O O~ (5) (6) (7) (8 ) o<> 0<>0 (9) (10 ) Slika 8 .3 Usmerjeni gr a f je poln, če ima vse možne povezave; to je t eda j , ko ima vsaka točka zanko in med poljubnima različnima točkama obsta jata obe nasprotno usmerjeni povezavi . Sl ika 8 . 4 prikazuje pol ne usmer jene grafe na eni, dveh in treh točkah. o (1) (2) Slika 8 . 4 8.2. Vaja : Koli ko povez av i ma polni usmer j eni graf na n točkah? Podobno kot smo pr i neusmer j enih grafih govor ili o komplementu , lahko t a pojem pre nesemo na usmer j ene gr af e . 34 8.3. Zgled: Poišči komplement usmerjenega gr af a na sliki 8. 2 ! Reš itev pr i kazuj e slika 8.5. Nasprotni graf G~ usmerjenega grafa G ima isti temeljni graf, tod a nasprotno usmerjene povezave. Slika 8 . 5 Slika 8.6 8 .4 . Zgled: Poišči nasprotni gr af usmer jenega gr afa na sliki 8. 2 ! Reš i t ev pr-i kazuje slika 8.6 . 8 . 5. Vaja: Ali obstaja kakšen usmerjeni graf, ki j e izomorfen svojemu komplementu? Al i obsta ja kakšen usmerjeni graf, ki j e nasproten samemu sebi? Ali obstaja kakšen usmerjeni gr af , ki je hkrati komplementaren in nas proten samemu sebi? Gr a f, ki je nas proten samemu sebi, i menujemo simetrični graf. Odlikuje ga last nost , da med pol jubnima njegovima točkama bodisi ni povezave ali pa da sta dve nasprotno usmerjeni povezavi. Vsakemu neusmer jenemu graf u l ahko na en sam način priredimo simetrični usmer jeni gra f brez zank tako, da vsako neusmer jeno povezavo nadomestimo s parom nas protno usmerjenih povezav. Obra t no lahko vsakemu simetri čnemu usmerjenemu gr afu brez zank priredimo neusmerjeni graf tako, da par nasprotnih povezav nadomestimo z neusmerjeno povezavo. Zato so v nekem smislu neusmerjeni grafi isto kot simetrični gr af i brez zank . Pr i neusmerj enih gr a f ih smo govor i li o stopnji posameznih točk. Če je graf usmer jen, ni vseeno, če se povezava v točki začne ali če se v njej konča . Zat o se tu vsil juje drugačna definici ja. Št evi l o vseh povezav z začetkom v točki A imenujemo izhodna s topnja (cdstopnja) d" (A). š t evilo vseh povezav s koncern v točki A i menujemo vhodna s topnja (dos topnja) d-(A) . Domenirno se še, da zanka v A prispeva 1 k d+(A) in prav tako 1 k d- (A). 35 ti.b. Zgled: Koli ke so stopn je točk na gr afu na sliki 8. 2? d+(A ) = 1, d+(B) = 3, d+(C) = 2, d+(D) = 1, d-( A) = 2, d-(B ) = 2, d- (C) = 1, d-(D ) = 2. Če poznamo vhodne in izhodne stopnje točk kakega grafa , jih lahko na pr epr os t način izračunamo tudi za točke nasp rotnega grafa . Ker v nasprotnem gr afu dosledno obrnemo smeri povezav , se za vsako točko števi l i d+ in d- zamenj at a . 8. 7. Trditev: Če v usmerjenem gr afu seštejemo vhodne stopnj e vseh točk , dobimo isto število, kot če seštejemo izhodne stopnje vseh točk, to pa je ravno š t evi l o povezav . Dokaz: Ko preštejemo začetke vseh povezav, dobimo ravno vsoto vseh i zhodnih stopenj. Ko pre štejemo konce vseh povezav, dobimo vsoto vseh vhodnih stopenj. Odtod neposredno sledi trditev. Pojma poti in cikla se zelo enostavno preneseta od neusmer jenih na usmerjene gr af e . Usmer jeno pot P dobimo tako, da usmerimo povezaven na pot i Pn vzdolž poti od enega krajišča proti drugemu. Podobno dobimo usmerjeni cikel Cn i z Cn• Slika 8. 7 pr i kazuj e P4 i n CS• Usmer j eni graf j e šibko Usmerjeni gr af je krepko usmer j ena pot , ki ima X za Sl ika 8.7 Več možnos t i i mamo za poj em povezanosti. povezan, ko j e njegov temeljni gr af povezan. povezan, če za poljubni točki X in Y obstaja začetek in Y za konec. Jasno j e , da je vsak kr epko povezani graf tudi š i bko povezan. Zlahka se dokaže, da je simetrični gr af krepko povezan natanko t akrat, ko je š i bko povezan. Ni pa poljuben š i bko povezani graf t udi krepko povezan. Na s l i ki 8.8 . usmerjeni gr af (1) ni š i bko povezan, graf (2) j e šibko povezan, ne pa kr epko in gr af (3 ) je krepko povezan . 36 Če za kako točko A usmerjenega gr afa velja d+(A) tedaj gr af got ovo ni krepko povezan. 1 (l) o {2} Slika 8.8 D> (3) 8. 8. Vaja: Poišči šibko povezani graf, ki ni krepko povezan in za vsako njegovo točko X velja d+(X) > ° in d-(X) > O. 8. 9. Trditev: Če za vsako točko X usmerjenega grafa velja d+(X) > O, t edaj graf vsebuje usmerjeni cikel. Dokaz: Naj bo A, poljubna točka grafa. Ker je d+(A,) > O, obsta ja povezava z začetkom v A,. Naj bo A2 konec te povezave. Ker je tudi d+(A2) > O, lahko postopek ponovi mo v A2• Tako dobimo A3 in tako dal j e . Ker je v grafu točk končno mnogo, se v zaporedju A" A2, A3, ••• začnejo točke ponavljati. Tako dobimo usmerjen cikel. Poseben primer, ko je A8 A3, prikazuje slika 8.9. A, Slika 8. 9 Svojo pozornost izkažimo turnirjem. Dobimo jih iz neusmerjenih pol ni h grafov, tako da vse povezave usmerimo. Ime j e posrečeno - spomni mo se teniških turnirjev, na kat er i h vsak udeleženec i gra z vsakim do zmage enega ali drugega. Običajnih šahovskih turnirjev pa graf turnir ne predstavlja, saj so na šahovskih turnirjih možni tudi remiji. Podobnost nam omogoča, da si od pravih turnirjev izposodimo še drugo 37 izr azje. Tako bomo točkam lahko rekli kar udeleženci i n names t o ' od A do B je usmerjena povezava' dejali 'udeleženec A je premagal udeleženca B' . Tudi izhodno stopnjo d+(A) lahko progl as imo za število zmag udeleženca A. Prav t ako se bo števi l o d- CA ) l ahko glasilo število porazov udel eženca A. In končno bomo razvrstitvi točk po padajočih i zhodni h s t opnjah preprosto r ekl i lestvica. 8 .10. Vaja: Nariši vse t ur ni r j e z dvema in t r emi udeleženci! 8.1 1. Vaja: Koliko je t ur ni rjev s š t i r imi udeleženci? Koliko j ih j e z n udeleženci ? 8.12 . Vaja: Na tu rn ir jih na sli ki 8. 10 poišči vse i zhodne i n vse vhodne stopnj e! Sest avi l estvico ! tremi in štirimi Slika 8. 10 8.13 . Vaja: . Koli kšna j e vsota vseh števil na lestvici t urnirja z n udeleženci? Kater o je l ahko največje š t evi l o na taki lestvici ? Sta na lestvici lahko dve ničli ? 8. 14. Vaja: Koliko je neizomorfnih turnir jev z dvema, udeleženci ? Les t vi ca je razvr stitev udeležence v. Lahko se zgodi, da je udeleženec X v tej razvrstitvi neposr edno pred udeležencem Y, čeprav je v njunem srečanju zmagal Y. Zato j e razvrst i t ev, ki j o prinaša lestvica , le do neke mere zanimi va . Bol j zanimivo bi bilo v turnir ju poi skati take lestvice, da je vsak udeleženec premagal tistega , ki mu v tej lestvici neposredno sledi . Drugače povedano: zanima nas, ali je mogoče vse točke turnirja povezati z usmer j eno potjo? V usmerjenem grafu pravimo t aki usmerjeni poti , ki vsebuje 38 vse točke grafa, usmerjena Hamiltonova pot. 8 . 15. Vaja: Poišči Nič čudnega , nasl ednj i i zrek . nekaj Hamiltonovih poti na graf i h na sliki 8. 10. da nam j e pr i teh zgl edi h vedno uspelo, sa j velja 8. 16. Izrek: Vsak turni r premor e Harniltonovo pot . Dokaz: za najenostavnejši turni r , t ur ni r z dvema udeležencema, izrek vel j a . Iskana r azvr s t i t ev sovpada z ono, ki jo prinaša lestvica. Vzemimo, da je i zrek dokazan za vse turnir je z n udel eženci . Ali se da od t od dokazat i, da i zrek drži t udi za turnir je z (n + 1) udeleženci? 1 2 3 n -l n 0-----0-----0- . . - --0------0 IlJ ~" '7 (3) ~ 1 2 3 n- l n ~,~ Slika 8. 11 Vzemimo tu rn ir z n+l udeleženci . Prvih n udeležencev sest avlja man jši turnir , v katerem obstaja po induktivni predpostavki Hami ltonova pot . Na sl i ki 8 .1 1( 1) srno to pot narisa li. Pri t em srno i zpustili vse druge povezave turnir ja in smo i zbr ali oznake točk . Udeleženec n+l je i gral z vsemi dr ugi mi udeleženci. Pri tem je izpolnjena ena od nasledn jih treh možnosti: 1. Udeleženec n+l j e premagal udeleženca 1 (slika 8. 11(2 » . V tem pr imeru vključimo udel eže nca n+l na pr vo mes t o in dobi mo Hamil tonovo pot ri- t , 1, 2, • • • , n- l, n. 2. Udeleženec n+l j e izgubi l z udeležencem n (sli ka 8. 11(3». Raztegnjena razvrst itev j e seda j : 1, 2, 3, • •• n- l, n, n+l. 3. Če ne velja nobena od prvih dveh možnosti (slika 8. 11(4» , je udeleženec n+l pr emagal udeleženca n in izgubil z udeležencem 1. To pa 39 pre magal premagal je torej r , n+1, r+1, • •• n. obstaja na poti od 1 do n udeleženec r , ki je zadnj i že nasl ednji udeleženec r+1 pa je z njim i zgubil . I z udeležencev črtamo povezavo (r , r+1) in jo nadomestimo s n+1) in (n+1, r+1) . Tako dobimo zažel eno razvr sti t ev : n-}, dapomeni , premagal razvr stitve n povezavama (r , 1, 2, 3, Izr ek je dokazan. Da se dokazati , da je prvouvrščeni vse nasprotnike neposredno ali pa, če tega ni storil i n je n. pr. z B i zgubil , je zagotovo nekega C, ki je premagal B. Če ne v enem koraku , neposredno, posredno samo v dveh korakih premagal vse ostale udeležence . Če smo se z izrekom 8.16 nekako vživeli v pr vouvrscenega, nam bo v naslednjem i zreku bolj pri srcu problematika zadnjeuvrščenega. Zgodi se , da se na pravem turnirju zadnjeuvrščeni lahko t ako potolaži : ' zadnji sem res, toda premagal sem A, ta je premagal B • • • i n t a je premagal samega prvaka.' Kdaj se to zgodi ? Prav got ovo je to takrat, ko j e vse točke tur ni rja mogoče povezati z usmerjenim ciklom, ki mu pr avimo usmerjeni Hamiltonov cikel . Pred izrekom še definicija: tepena skupina S turnirja T j e podmnožica Udeležencev, ki so i zgubili vsa srečanja z udeleženci , ki ni so iz S. Naj nam bo dovol j en pr imer: avtorja te knjige in bral ec , ki jo trenutno bere, bi na svetovnem teniškem prvenstvu hočeš nočeš se s tavljali tepeno skupino. Turnir bi pravzaprav r azpadel na dva : turnir pravih, močnih udeležencev in t ur ni r nas treh š i bki h udeležencev. Zato se turnirju s t epeno skupino tudi praVi razcepni turnir, turnir, ki take tepene skupine ne premore , pa j e nerazcepni. Slika 8. 12 shematično pr ikazuj e razcepen turnir • • •---• Slika 8.1 2 Razume se, da tepena skupina lahko sestoji iz enega samega udeleženca , če je ta prav z vsemi izgubil , iz dveh ali i z n - 1 udeleženca. Ta zadnj i posebni primer nastopi takrat, ko je prvouvrščeni premagal prav vse nasprotni ke. 40 8.17. Izrek: Vsak nerazcepni turnir premore Hamiltonov cikel. Dokaz: PO prejšnjem izreku obstaja Harniltonova pot: 1, 2 , 3, ... n-l , n. Zadnji udeleženec v tej razvrstitvi (n) je seveda izgubil z (n- l), ni pa mogel izgubi ti z vsemi ostalimi udeleženci, sa j bi t eda j sam ses t avl jal tepeno skupino. Torej obstaja vsaj en udeleženec, imenujmo ga k, s katerim je n zmagal (glej sliko 8.13). k123 0------0-----<> ... --Q-_-O--- Slika 8. 13 n- 1 n To pa pomeni , da v turnirju obsta ja usmerjeni cikel e = k , k+l, • • • n- 1, n, k. Dokaz bo v tem, da bomo ta cikel postopoma razširili na vse udeležence in tako dobili iskani Hamiltonov cikel. Pri tem bomo izkoristili samo predpostavko, da v našem turnirju ni tepenih skupin . Udel ežence , ki so ostali zunaj e bomo razdelili v t r i skupine : 1) v Udeležence, ki so z nekater i mi udel eženci ci kl a e zmagal i , z nekaterimi pa izgubili, 2) v udeležence, ki so premagali prav vse udeležence cikla e, 3) v udeležence, ki so izgubili prav z vsemi udeleženci cikla e. Začnimo pr i prvi skupini! Naj bo r udeleženec te skupine. Teda j morata biti v ci kl u e taka sosedna udeleženca s in s + 1, da je s premagal r , s + 1 pa je izgubil z r- (glej sliko 8 . 14) . Slika 8. 14 2-:-,'. Gc .: "', : ", .o' n Oo Slika 8. 15 41 Če iz C črtamo povezavo s , s + 1 in na njeno mest o postavimo pot s, r , s + l,smo ci kel C razširili na ci kel C', ki vsebuje novega udeleženca r. S podobnimi zapor edni mi razširitvami izčrpamo vso pr vo skupino, kat er e udeleženci se t ako znajdejo v razšir jenem ciklu C~ . Preostanet a nam dr uga in t r et ja skupi na . Udeleženci druge in tretje skupine niso i grali samo z udel eženci cikl a C, i gr al i so tudi med sabo. Je mogoče , da bi vsi udeleženci dr uge skupine pr emagal i vse udel ežence t r et je skupine? Ne , ko bi bilo tako , bi t r e t ja skupi na bi l a tepena skupina,to pa ne srne biti. Sledi, da obstaja v tretji s~Jpini t ak udel eženec p, ki je premagal vsa j enega udel eženca t d~uge skupi ne (gl e j sliko 8. 15) . Toda t ako se da cikel C* razširi ti : črtamo i z nj ega povezavo n, n+l, namesto nje vr inemo n, p, t, n+l in ci kel se obogati za dva udel eženca . S postopnimi r azš i r i t vami se še drug i udeleženci druge in tret je skupine znajdejo v ci klu , ki je, ker pač obsega pr av vse udeležence t urni rja, njegov Hamiltonov ci kel . Dokaz je končan. Včasih je težko ugotoviti, ali v danem turnir ju, posebno če ima ta dosti udeležencev , tepena skupina obstaja ali ne in ali zat o t urnir premore Hami l t onov cikel ali ne . Zato nam marsikdaj pride pr av naslednji i zrek , ki ga tu poda jamo brez dokaza. sicer zadosten, ni kakor pa ni da premore t ur nir Hami l t onov cikel , 8 . 18. Izrek: Če je razlika med točkami (na l estvici) točkami zadnjeuvrščenega manjša od polovice udeležencev turnir Hamiltonov cikel. Posebe j poudarimo, da j e pogoj potreben. Prav lahko se namreč zgodi, zgorn ji neenakosti pa ni zadoščeno. prvouvrščenega in turnirja, pr emor e 8 . 19. Zgled: za preizkus izreka uporabimo podatke turnirja na sliki 8.1 0(1) . Ker velja 3 - 1 <5/2, mora ta turnir imeti Hamiltonov cikel. In res : tak je ci kel ADEBCA. 42 8.20. Zgled: Na sliki 8.16 je prikazan drug 4- 1:6 /2:3 , pogoju i zreka ni zadoščeno . To ne Hami l t onovega cikl a . Pa saj ga i ma: tak cikel je turnir. Ker je sedaj pomeni , da turnir nima PBCDEFA . D C Slika 8. 16 A 43 9. poglavje EULERJEVI OBHODI V tem poglavju se bomo posvetili posebnim sprehodom in obhodom v grafu, ki so v tesni zvezi z risanjem grafa. 9.1. Zgled: Graf na sliki 9.1 ima med drugimi sprehod AEBCDEB, ki ima začetek v točki A, konec v točki B, ki ni enostaven, saj se povezava EB v njem ponovi. Sprehod ABDEBC je enostaven sprehod, ki pa ni pot, saj se točka B ponovi. Sprehod AEBDC je pot. Sprehod ABEDBEA je obhod, saj se začne in konča v točki A. Obhod BAEBDCB je enostaven, ni pa cikel . Obhod ABCDEA pa je cikel. Obhod ABEABEA ni ni ti enostaven, kaj šele cikel . Slika 9.1 E O ~ ABe Obhod ABCDBEDEA izčrpa vse povezave gr afa na sliki 9. 1, ni pa enostaven. V njem se povezava ED ponovi. Če s svinčnikom na papirju sledimo temu obhodu, lahko sicer narišemo graf, vendar pri tem narišemo povezavo ED dvakrat. Vprašanje pa j e, ali lahko graf na sliki 9. 1 narišemo z eno potezo. To pomeni, da ga narišemo tako, da svinčnika med risanjem ne dvignemo od papirja in nobene povezave ne rišemo dvakr at. Z drugimi besedami : ali iu;a ta graf kakšen enostaven sprehod, ki izčrpa vse povezave? S poskušan jem lahko najdemo sprehod EABEDBCD, s katerim lahko graf narišemo veni potezi. Zaman pa bi iskali obhod s to lastnost je. Na tem mestu bomo to lastnost posebej poimenovali. Eulerjev obhod grafa G je enostaven obhod, ki vsebuje vse povezave grafa G. Eulerjev sprehod gr afa G je enostaven sprehod, ki vsebuje vse povezave gr af a G. 44 Graf, ki premore Eulerjev obhod, je mogoče začenši pri poljubni toČki prerisati tako, da gremo enkrat in samo enkrat po vsaki povezavi, ne da bi morali kdaj vzdigniti pero, in se na koncu znajdemo v začetni točki. Kdaj graf G premore Eulerjev obhod? Preden si potešimo radovednost, rešimo naslednje vaje. 9.2. Vaja: Nariši vse povezane grafe z na~več osmimi povezavami, ki imajo same sode točke! 9.3. Vaja: Nariši vse povezane grafe z največ petimi povezavami, ki nimajo samih sodih točk! 9.4. Vaja: Poišči morebitne Eulerjeve obhode na grafih vaje 9.2! 9.5. Vaja: Napravi isto za grafe vaje 9.3! Če smo vestno rešili zadnje vaje, morda že slutimo naslednji izrek. 9.6. Izrek: Neusmerjeni povezani graf premore Eulerjev obhod natanko takrat, ko so vse stopnje njegovih točk sode. Dokaz'· Izrek bomo dokazali v obeh smereh. Začnimo s prvo smerjo. Če povezani graf G premore Eulerjev obhod, tedaj so vse točke grafa sode. Začnimo obhod pri točki T. Vsakokrat, ko gremo skozi kakšno točko, porabimo dve povezavi: eno, ko vanjo pridemo, in drugo, ko jo zapustimo. Ker po predpostavki Eulerjev obhod obstaja, se nam ne sme nikjer zatakniti. Zato ne sme nobena toČka imeti stopnje 1: že ko bi jo prvič dosegli, bi ne mogli naprej. Prav tako ne bi mogli naprej, če bi točka imela stopnjo 3: prv~c bi nam šlo gladko, ko pa bi toČko drugič dosegli, bi se ustavili. Podoben sklep velja za vsako točko lihe stopnje. IZjema je točka T. Ko smo jo prvič zapustili, je prispevala eno povezavo, ko smo jo drugič, tri, itd. Toda ko obhod zaključimo v točki T, vanjo samo pridemo in je ne zapustimo več. To povezavo prištejemo dosedanjemu lihemu številu in dobimo tudi za točko T sodo stopnjo. V nasprotno smer pa dokažemo izrek z matematično indukcijo po številu povezav m. V vaji 9.4 smo se prepričali, da za najnižje vrednosti števila mizrek 45 velja. Vzemimo sedaj, da izrek velja za vse grafe z m ali manj povezavami. Vzemimo graf D z m+1 povezavami, ki zadošča pogojem izreka! Ker je povezan in so stopnje vseh njegovih točk sode, imajo vse njegove točke vsaj stopnjo 2. Iz posledice 4.6 sledi, da G vsebuje cikel, na primer C. Zbrišimo povezave cikla C! Dobimo podgraf H prvotnega grafa G. H ima manj povezav kot G, lahko pa je nepovezan. Naj bodo H1, H2, .•. , Hk njegove komponente. Vsaka njegova komponenta Hi mora imeti vsaj eno točko na C. Taka točka je pri brisanju povezav cikla izgubila dve povezavi. Vsaka komponenta Hi zadošča pogoju, da je povezana in da imajo vse njene točke sodo stopnjo. Ker je število povezav vsake komponente Hi gotovo manjše od m, premore po hipotezi indukcije vsak graf Hi Eulerjev obhod. Slika 9.2 Pomikajmo se po povezavah cikla C, dokler ne naletimo na točko kakšne izmed komponent Hi grafa H. To točko imenujemo po komponenti Ti' Zavijmo v komponento Hi! Opišimo njen Eulerjev obhod in se vrnimo v Ti' Nato nadaljujmo po ciklu C, dokler spet ne naletimo na točko Tj kakŠne komponente Rj• Postopek ponavljajmo, vse dokler se ne vrnemo v začetno točko cikla C. Ko smo to storili, smo opisali Eulerjev obhod po celem grafu G. Dokaz j e končan. 9.7. Vaja: Kateri polni grafi premorejo Eulerjev obhod? 9.8. Zgled: Primer za Eulerjev obhod je partija domine, ki se izide. Graf ima 7 točk: števila O, 1, 2, • • • , 6. Njegove povezave so posamezne domine. Ker obstajajo vse domine (t , j), kjer je i =O, 1, .•• , 6 in j =O, 1, • • • , 6, je ta graf polni graf~, ki ima povrh v vsaki točki zanko. Stopnja vsake točke (če zanko izvzamemo) je 6. Zato po pravkar dokazanem izreku 46 prerrore graf Eul erjev obhod. Tak Euler jev obhod je par t i ja domine, pri kateri se ni zat aknilo. 9. 9. Vaja: Odstrani i z i gr e vse dvojne domi ne (O , O), ( 1, 1) ••• (6, 6) in vse domine , ki vsebujejo ničlo. Kaj misliš , se part ija t ako skrčene domine mor-a vedno i zteči ali se pr-r njej včasih ali celo vedno zat akne? 9. 10. Vaja: Kateri od nasledr.jih graf ov pr emor e j o Euler jev obhod: Wn, Tn, An In Mn? Ko igramo domino, nas v resni ci ne zani ma , če se . zadnj a domina v vrsti lahko poveže s prv o. Podobno nas t udi pr i r i san j u gr afa z eno potezo ne zamrna, če r isbo končamo v točki , kjer smo pero postavi li na papir. To pomeni, da nas ne zanima Euler j ev obhod, ampak spr ehod. O t em pa govor i naslednja posplošitev izreka 9.6 . 9.1 'I . Izrek: Neusmer jeni povezani graf pr -emore Euler jev sprehod natanko takr-at , ko ima kvečjemu dve lihi točki. ~lZ: Če ima graf same sode točke , velja izrek 9.6 . Ene l i he točke gr af ne mor-e imeti zaradi posl edi ce 3. 4. Če ima gr af dve lihi točki , r ecimo A in B, dodamo povezavo AB in dobimo gr af s samimi sodimi točkami . Po izreku 9.6 obs taja v njem Eulerjev obhod. Tega pa lahko spremeni mo v sprehod od A do B, če dodatn o povezavo AB spet zbrišemo. Če pa i ma osnovni gr af več kot dve lihi točki, zanj ne obstaja Eulerjev sprehod. O t em se lahko prepričamo s podobnim r azmislekom kot v dokazu i zreka 9. 6. Graf, ki ga v dokazu konstruiramo, ni nUjno enostaven. Kljub temu pa izrek vel j a , saj velja izrek 9.6 t udi za splošne grafe . Pr ed koncem pa še neka j besed o Euler jevi h obhodih na usmerjeni h grafih . Usmerjene sprehode , obhode, pot i in ci kle definiramo na usrnerjenih gr afih na podoben način kot na neusmerjenih. Usnerjeni sprehod je zaporedje E o Slika 9.3 47 točk T1, T2, ••• , Tn usmerjenega grafa in usmerjene povezave vodijo od točke T1 do točke T2, od točke T2 do točke T3, ••• , od točke Tn_1 do točke Tn• 9.12. Zgled: Na sliki 9.3 sta AEBC in BCDE usmerjeni poti, EBCDE je usmerjen cikel, CBAEB je enostaven sprehod, BAEBCDCB pa je enostaven obhod. Graf gotovo nima Eulerjevega sprehoda, saj ima na primer točka D izhodno stopnjo 3, vhodno pa 1. Brez dokaza povejmo, kateri usmerjeni grafi premorejo Eulerjev obhod. 9.13. Izrek: Usmerjeni graf vsebuje EUlerjev obhod, če in samo če je povezan in je za vsako njegovo točko izhodna stopnja enaka vhodni stopnji. Slika 9.4 Drs] A B 9.14. Zgled: Graf na sliki 9.4 premore Eulerjev obhod, Pogoju izreka 9.13 je zadoščeno, saj je d+(A) = d-(A) = 1, =2, d+(C) =d-(C) = 2, d+(D) =d-(D) =2 48 n.pr. ABCDCBDA. d+(B) = d-(B) 10. poglavje RESI1VE NALOG 2.4. Na štirih točkah obstaja 11 neizornorfnih grafov. To so grafi na sliki 10.1 O O 1 O L 1 1O O O (1) (2) (3) (4) n~VD (5) (6) (7) (B) rx: (9) IX1~ (10) (11) Slika 10.1 2.5. Najpre j v mislih narišimo vse možne povezave med n točkami! Po formuli (2.1) je teh n(n-l)/2. za vsako od teh povezav imamo dve možnosti: d a jo obd r ž i mo al i d a jo zbrišemo, in to neodvisno od o s tal ih. Vsaka izbira nam da različen graf, zato je iskano število enako: 2·2·2 ·2· •.• · 2,2 , kjer je š t evi l o dvojk enako n(n-l)/2 . Zato na n točkah obstaja 2n(n- 1) / 2 gr afov. 2.6. Grafa (1) in (3) sta izomorfna. Eno izmed možnih preimenovanj je 49 A - 1 , B - J , C - K , D - L. Grafi (2), (4) in (5) so izomorfni. To uvidimo že od tod, ker je vsak izmed njih polni graf K4• Ker so pri polnem grafu vse točke enakovredne, je vsako preimenovanje sprejemljivo. Grafi (6), (7) in (8) niso izomorfni z nobenim od prejšnjih, ker imajo različno število točk. Tudi med sabo niso izomorfni, saj ima na grafu (6) točka C 5 sosedov (D,E,F,A in B), nobene take točke pa ne premoreta graf (7) in (8). Po drugi strani ima graf (7) točko L s štirimi sosedi, graf (8) pa take točke nima. od osmih grafov na sliki 2.8 je tako 5 neizomorfnih . 2.7. Rešitev prikazuje slika 10.2. o K, Slika 10.2 3.2. Točke A, D, E in G imajo stopnjo dva, ostale točke pa imajo stopnjo ena. 3.6. V grafu na sliki 3.1 je deset podgrafov enakih P 3• To so ACE , AEC, AEB, AED, BED, BDE, BEC, CAE, CED, DBE. Osem podgrafov je enakih P4• To so AEDB, AEBD, ACEB, ACED, CEBD, CEDB, CAEB, CAED. Štirje podgrafi so enaki P5• To so ACEBD, ACEDB, CAEBD, CAEDB. 3.8. V grafu na sliki 3.5 obstajajo naslednji cikli: AEFBA, BFGCB, CGHDC , AEFGCBA , BFGHDCB , AEFGHDCBA • 3.10. Točke A, Din E določajo prvo komponento, točki Bin F drugo, točke C, G in H pa tretjo komponento. 3.13. Slika 10.3 kaže vse povezane grafe s petimi točkami in štirimi povezavami. 50 Slika 10.3 3.14 . Na sliki 10.4 so vsi zahtevani grafi. Opazimo, da nobeden med njimi ne vsebuje cikla. o 0---0 Slika 10. 4 4.8. Slika 10.5 prikazuje najmanjših 9 dreves, v katerih imaj o točke stopnjo 1 ali 4. vodik metan et a n propan butan 1 butan, ) n 3 . ~ ~ pentapenton ,pentan 1 Slika 10.5 V kemiji podkovan bralec je v vseh teh grafih (razen prvega, ki je molekula vodika) prav gotovo prepoznal ogljikovodike. Točke stopnje 1 so atomi vodika, točke stopnje 4 pa atomi ogljika. Iz risb lepo razberemo, da obstaja ena sama vrsta metana CH4, etana C2H6 in propana C3H8 ' da pa obstajata dve vrsti butana C4H lO (Lzoner-t ) in tri vrste pentana C5H12 . Zato ni čudno, da je prav kemija spodbudila - pred dobrimi sto leti - prve raziskave dr eves . Bralca opozar'jamo, da smo pri butanu i n pentanu zapisali 51 indekse čisto poljubno, ker želimo izomere zgolj razločevati, medtem ko je ustaljeno kemijsko poimenovanje teh izomer drugačno, bolj natančno in zamotano. Ime spojine mora namreč vsebovati vso informacijo, ki kemiku omogoča zapisati .strukturno formulo (graf) molekule. 4.9. Naj bo x število točk stopnje 1. Vseh točk je zato x+10. Ker imamo opravka z drevesom , mora biti povezav x+9. To število pa lahko izračunamo tudi drugače. Iz vsake od x točk štrli po ena povezava, iz vsake od 10 točk po štiri. Skupno bi dobili x+40 povezav. Ker pa smo vsako povezavo šteli dvakrat, je to število treba deliti z 2 in dobimo (x+40)12. Izenačimo oba izraza in rešimo enačbo x+9=(40+x)/2j rešitev je 22. Toliko je točk stopnje 1 v našem drevesu. Drevo ima 31 povezav. 5.4. Ti grafi imajo naslednje stopnje točk. če je število točk grafa sodo (2r): A) 1 2 3 .•• r r ••• (2r-2) (2r-1) B) O 1 2 ••• (r-1) (r-1) ••• (2r-2) Če je število točk grafa liho (2r+1): C) 1 2 3 r r (2r-1) (2r) D) O 1 2 ••• rr... (2r-1) Izkaže se, da je za vsak r le en graf tipa A, B, C in D. Pri tem je B komplement A, D pa komplement C. To je mogoče dokazati z matematično indukcijo. Slika 10.6 prikazuje najmanjših osem grafov (r = 1 in r =2). r = 1 Slika 10.6 r = 2 52 1 A A o o B o B c c o L o o 5.7. Na sliki 10.7 pomeni puščica ~ med dvema grafoma , da sta grafa kompl ement arna . O O rgr 1 1 X~ ~O O 0----0 ~ n L~ ~O O r ~ ~ ~ ~ Lj Slika 10.7 Na š t i rih točkah je 11 neizomorfnih grafov. Eden med njimi j e i zomorfen svojemu kompl effientu ( je sebi komplementaren). 5. 8. Gin G imata skupaj n(n-1)/2 povezav. Če sta izomor f na , morat a imeti enako š t evi l o povezav , torej vsak po n(n-l )/4. To š t evi l o mora bi t i naravno š t evi l o. Zato mora biti bodisi n = 4, 8, 12 •.• bodisi n = 1, 5, 9, 13 Matematiki so za vsak n, ki zadošča temu pogoju, uspeli t udi konstruirati samemu sebi komplementaren graf na n točkah. 5. 9. PO prejšnji nalogi prihajajo v poštev le nas lednje vred nost i za število točk n: n = 1, 4, 5, 8. S preizkuŠanjem najdemo gr afe na s l i ki 10. 8 O~ n=5 n=5 O n =1 U n=4 Slika 10.8 n = 8 n = B 53 Bodi V1 množica, biti v množici V2• ležita 4 in 6 v V2, 6.1. Graf (1) vsebuje cikle dolžine 3, 4, 5 in 6, graf (2) vsebuje cikle dolžine 4, 6 in 8, graf (3) ne vsebuje nobenega cikla, graf (4) pa vsebuje cikle dolžine 5, 6, 8 in 9. 6.2. (1): P6 (2): P8 (3): P7 (4): P10• Kot vidimo iz prejšnje naloge, ne velja, da graf vsebuje manjše cikle Cn_1, Cn_2, ••• C3, brž ko vsebuje Cn' 6.3. Eno od preimenovanj je: 1 - G, 2 - 1, 3 - K, 4 - E, 5 - L, 6-H, 7-F, 8-J. 6.4. Eno od preimenovanj je: 9-1, 10-G, 11-J, 12-E, 13-M, 14-A, 15-B, 16-C, 17-D, 18-L, 19-F, 20-K, 21-H. 6.5. Množico treh točk grafa C3 poskusimo razbiti v dve podmnožici, tako da noben par točk v isti podmnožici ni povezan. V vsakem primeru sta v eni podmnOŽici vsaj dve točki. Ker je v C3 vsaka točka soseda vsake druge, ne moreta biti v isti podmnožici niti dve točki. Razbitje ni mogoče: C 3 ni dvodelen. 6.6. Imenujmo točke cikla C7 kar po vrsti: 1,2,3,4,5,6,7, tako da ga določa obhod 123.45671. v katero smo dali točko 1. Ker je 2 sos eda 1, mora Ker je 3 soseda 2, mora biti v V1• Po isti logi ki 5 in 7 pa v V1• zato je V1 = { 1,3,5,7 i , V2 ={2,4 ,6 l. To pa je že protislovje, ker sta 1 in 7 v isti množici, čeprav sta sosednji. Cikel C7 tore j ni dvodelen. Na podoben način bi lahko dokazali., da noben lih cikel ni dvodelen. 6.9. Seveda nista! Graf (1) na sliki 6.1 vsebuje trikotnik, ki ni dvodelen. Graf (4) pa vsebuje cikel C5' ki prav tako ni dvodelen. 6.13. Dvodelni so: (1) (vsebuje samo cikle C4' C6, C8, C12), (3) (njegovi edini cikli so C4 in C6) in (6) (ima le cikle: C6 in C8). Prav tako je dvodelen graf (5), saj lahko razbijemo njegovih točk v podmnožici: V1 = { A,C,J,P,G,L,N,E 1 in V2 ={ B,H,I,K,D,O,M,F } tako, da sta povezani kvečjemu dve točki iz različnih podmnožic. Niso dvodelni: (2) (vsebuje trikotnike C3), (4) (vsebuje C5) in (7) (vsebuje C 3). 6.14. Vse poti Pn so dvodelne: nimajo. Cikli Cn so dvodelni le, 54 ker nimajo ciklov, tudi lihih ciklov če je n =2k (sodo število). od polnih grafov Kn sta dvodelna le K1 in K2, vsi drugi vsebujejo trikotnik . 6.18. Seveda prihajajo v poštev le polni dvodelni grafi Ka~' kjer je a + b =n. Iz neenačbe O:5. (a - b)2 oziroma 4ab ~ a2 + 2ab + b dobimo ab < (a + b)2 /4 =n2 / 4. Produkt ab torej ne more biti večji od n2 / 4 . če Je n sodo število: n = 2k, je torej ab:5. k2 in vidimo, da j e ~ k graf z največ povezavami. Če pa je število n liho: n = 2k .. 1, število ~2/4 = (4k2 + 4k + 1)/4= k2 + k + (1/4) ni celo, zato produkt ab ne more biti večji od (n2 - 1)/4 =k2 + k kek + 1); vidimo da je zdaj ~+l,k graf z največ povezavami. 7. 3. Regularni grafi stopnje dva na dvanajstih točkah so: (Gg , G~) , (G8, G4) , (~, Gs) , (G6, G6) , (G6, G3, G3) , (G5, G4, (G4, G4, G4) , (G3, G3 , G 3 , G 3 ) · TU pomeni na pr i mer (G9, G3) graf, ki sestoji i z dveh komponent , od katerih j e prva cikel G9, druga pa cikel G3• Regularnih gr af ov stopnje 2 na 20 točkah j e kar 49. Na toliko načinov namreč lahko zapišemo š t evi l o 20 kot vsoto cel i h š t evi l , večjih od 2. 7.4. Na sliki 10.9 sta najmanjša -neizomorf na kubična grafa z istim š t evilom točk. (1) Slika 10.9 (2) Grafa nista izomorfna, ker (1) vsebuje trikotnike , (2) pa ne. 7.5. Kubični graf na 11 točkah bi imel liho število lihih točk. To pa je v nasprotju s posledico 7.7. 7.8. Števili m in n morata biti enaki. V K j e m točk stopnje n inm,n n točk stopnje m. Graf K je torej regularen natanko t eda j, ko je m = n.m,n 7.9. Naj bo G poljuben regularen, dvodelen graf stopnje d z dvodelnim razbitjem V1, V2• Naj V1 vsebuje m tOČk, V2 pa n točk. Tedaj iz množice V1 izhaja md povezav, i z mnOŽice V2 pa nd povezav. Obakrat dobimo vse 55 povezave grafa. Zato je md = nd in m= n, Tako srno dokazali, da ima poljuben regularen, dvodelen graf sodo mnogo točk. 7.10. Edino drevo stopnje O je K1• Edino drevo stopnje 1 je K2• Zaradi trditve 4.5 ne more obstajati nobeno regularno drevo stopnje d > 1. 7.11. Seveda je, saj je stopnja katerekoli njegove točke n-l. 7.12. (a) Kol o Wn srno dobil iz cikla Cn in vrha. Ko smo vse točke cikla Cn spojili z vrhom, je stopnja vsake točke cikla poskočila od 2 na 3. Isto stopnjo mora imeti vrh, če naj bo graf regularen. To pa je mogoče samo, če je Cn = C3• Torej je W3 = K4 edino kolo, ki je regularen graf. (b) Nobeno kolo ni dvodelen graf, saj očitno vsebuje trikotnike. 7.1 3. Wn ima n+l točk (n točk cikla in vrh) in 2n povezav (n povezav cikla Cn in še n povezav, ki točke cikla povezujejo z vrhom). Vse točke , ki so se prvotno nahajale v ciklu Cn ' imajo v Wn stopnjo 3, vrh pa ima stopnjo n. 7.14. Vse prizme Tn so regularni grafi stopnje 3. če je n lih, Tn vsebuje lih cikel Cn in zato ni dvodelni graf. Ce je n sod, je Tn dvodelni graf , o čemer se lahko bralec prepriča sam. Tn ima 2n točk in 3n povezav. 7.15. Vse antiprizme An so regularni grafi stopnje 4. Nobena antiprizma ni dvodelni graf, saj vsaka vsebuje trikotnike. An i ma 2n točk (točke dveh ciklov Cn) in 4n povezav (po n povezav na vsakem od obeh ciklov in 2n povezav, ki točke prvega cikla povezujejo s točkami drugega). 7.16. Dolžina najkrajšega cikla v Wn je 3. Dolžina najkrajšega cikl a v Tn je 4 (edina izjema je T3, kjer je ta dolžina enaka 3). V An je dol žina najkrajšega cikla 3. Dolžina najdaljšega cikla v Wn je n+l. Sl i ka 10.10 nam pokaže, kako v W6 poiščemo CT C, v W. Slika 10.10 C,2 V T. Slika 10.11 C,2 V A. Slika 10.12 Grafu, ki vsebuje cikel enake dol žine, kot je š t evi l o njegovih točk, 56 pravimo Hamiltonov graf. Slika 10.11 prikazuje, da T6 vsebuje cikel C12• Na splošno Tn vsebuje C2n• Tudi An vsebuje najdaljši cikel C2n' Poseben primer C12 v A6 prikazuje slika 10.12. Vsi grafi Wn, Tn in An so torej Hamiltonovi. 7.17. Vsi grafi Mn so regularni stopnje 3. Če je n sod, dobimo iz polovice cikla C2n in iz enega 'premera', cikel lihe dolžine n+l in zato M n ne more biti dvodelen. Dvodelen pa je vsak ~ zlihim n. Graf ~ ima 2n točk in 3n povezav. Na splošno je dolžina najkrajšega cikla v ~ enaka 4. Izjema je~, kjer je najkrajši cikel trikotnik. · Dolžina najdaljšega cikla v Mn je 2n, zato je ~ Hamiltonov graf. 7.18. Iskane grafe prikazuje slika 10.13. Slika 10.13 7.20. Kolo Wn je (n,3)-polregularni graf. 7.21. Ker imajo vsa drevesa točko stopnje 1 (glej trditev 4.5), se moramo omejiti na n =1 in iskati polregularna drevesa oblike (m,l). Naj bo v drevesu x točk stopnje m in y točk stopnje 1. Število vseh točk bo zato x+y. Število povezav lahko izrazimo takole: (mx + y)/2. Tako smo dobili enačbi mx + y = 2'1984 x + y = 1985 Če drugo enačbo odštejemo od prve, dobimo mx - x = 1983, od tod pa m = 1 + 1983/x Ker je x naravno število in m prav tako , bomo dobili vse rešitve, če bomo v izraz za m vstavili namesto x zapored vse delitelje števila 1983. Ker je 1983 =3-661, so vsi možni njegovi delttelji le tile: 1, 3, 661, 1983. 57 Vse rešitve so zbrane v razpredelni ci x m y 1 1984 1984 3 66 2 1982 66 1 4 132 4 1983 2 2 po f ormuli (3.1 ); (4n + x )/2. (4n + x ) /2, katere re šitev je Iz nje med drugim razberemo, da obs t a ja pol r egular no (662, l)-dr evo s tremi točkami s t opnj e 662 in s 1982 točkami stopnje 1. 7. 22. Označimo iskano število z x. St evi l o vseh točk dr evesa je zato n+x, števi l o vseh povezav pa n+x-l . Izračunajmo š t evi l o povezav še drugače, Oboje izenačimo in dobimo enačbo n + x - 1 = x = 2n + 2. 7.23. Najprej bomo pokazali, da je komplerrent polregularnega gr afa pol regularen. Bodi N število točk (m,n)-polregularnega gr af a . Če i ma neka točka stopnjo d, ima v komplementu st opnj o N - d - 1. Od tod sledi, da ima kompl ement (m,n)-polregularnega gr afa le točke s stopnj ami N-l-m i n N-l-n . Kompl ement (m,n) -polregularnega graf a je tako (N-l -n,N-l-m)-polregularen . Ker je vsak m-regularni gr af (m,m)-polregularen, je tudi komplement m- regularnega grafa (N-l-m,N-l-m)-polregularen oziroma (N-l -m)- r egul aren. 8.2. Polni usmerjeni graf na n točkah i ma n2 povezav. 8. 5. Graf na sliki 10.14 je hkrati komplementaren i n nasprot en samemu sebi. Sl i ka 10.14 Sl ika 10.15 8. 8. Iskani graf prikazuje slika 10.15. 8.10. Slika 10.16(1) prikaZUje oba turnirja z dvema udeležencema, slika 10.16(2) pa vseh 8 turnirjev s tremi udeleženci . 58 'li0----_---.0 A B 0---1_---.;0 A B(1) 666~ ABA BAB A B ")~.~ ~ ~ ABA BAB A B Slika 10.16 8; 11. za vsako od šestih povezav imamo dve možni smeri. Skupno je zato 26 = 64 turnirjev s štirimi udeleženci. V splošnem je pri n udeležencih n(n-l)/2 partij in 2n(n-l)/2 turnirjev. 8.12. Stopnje točk so: d+(A) =d+(C) = 3, d+(B) =2, d+(D) = =d+(E) = 1, d-(A) =d-(C) = 1, d-(B) =2, d-(D) =d-(E) =3, d+(~) 3, d+(G) =d+(H) =d+(J) =2, d+(I) = 1, d-(~) = 1, d-(G) =d-(H) = d-(J) = 2, d-(I) = 3 in lestvici (3, 3,2,1 ,1), (3, 2,2,2,1). 8.13. Vsota vseh števil je enaka š tevilu povezav, teh pa je n(n -1 )/2. Na lestvici je lahko največje število n-l; dose ženo je le takrat, ko prvouvrščeni premaga vse ostale udeležence. Na lestvi ci ne moreta biti dve ničli, ker sta tudi zadnjeuvrščena i grala med sebo j in eden med njima je moral zmagati. 8. 14. Z dvema udeležencema je turnir en sam: v njem je eden zmagovalec, drugi premaganec. Obstajata dva neizomorfna turnirja s tremi udeleženci. Prvi j e usmerjeni cikel C3• Predstavlja nam položaj, ko en udeleženec premaga drugega, drugi tretjega in tretji prvega. Drugi turnir s tremi udeleženci, imamo takrat, ko je en udeleženec premagal drugega in tretjega, drugi pa premagal tretjega. za n =4 je možnosti več . Da ne prezremo katere, si pomagamo z lestvico. Edine možne lestvice so (3, 1, 1, 1)\ (3,2,1,0)1 (2,2,2,0) in 59 (2,2,1,1). Vsaki ustreza en sam turnir, zato so štirje neizomorfni turnirji štirih udeležencev. (Glej sliko 10.17.) Številke ob točkah pomenijo število zmag. '~ O~~l o~~r '[gJ' 3 13 22 22 2 Slika 10.17 8.15. Turnirja na sliki 8.10 imata več Hamiltonovih poti. N,pr.: AEBCD, ADEBC, FHGJI, HIGFJ, JIGFH. 9. 2. Slika 10.18 prikazuje vse povezane grafe z največ osmi mi povezavami in samimi sodimi stopnjami. o rn e O ~DOOX m=3 m=4 rn e S rn e f m=6 m=7 m =7 m =7 m =8 m= 8 m =8 m =8 60 Slika 10.18 9.3. Slika 10.19 prikazuje vse povezane graf e z največ petimi povezavami, katerih točke nimajo samih sodih stopenj. 0--0 rn e l 0----0--0 m=2 m=3 ~ m =3 m =4 m =4 m =4 rn e S ~ m =5 >-< m =5 m =5 IZJ m =5 Slika 10.1 9 "