ISSN 0351-6652 Letnik 17 (1989/1990) Številka 1 Strani 17-21, 48
Janez Žerovnik:
PROBLEM BARVANJA TOČK GRAFA
Ključne besede: matematika, računalništvo, teorija grafov, barvanje grafa, časovna zahtevnost, algoritem.
Elektronska verzija: http://www.presek.si/17/966-Zerovnik.pdf
© 1989 Društvo matematikov, fizikov in astronomov Slovenije © 2010 DMFA - založništvo
PROBLEM BARVANJA TOČK GRAFA
Nekateri problemi v matematiki imajo lepo lastnost: zeio enostavno jih je zastaviti (za razumevanje problema ni potrebno veliko znanja), toda rešitev je vse prej kot enostavna.
Verjetno ste že slišali za Fermatov problem. Poglejmo ceioštevilsko enačbo
xn +yn = zn
Pri izbranem n iščemo cela števila x, y in z, ki ustrezajo enačbi. Pri n = 2 lahko hitro najdemo iskana Števila. To so ravno pitagorejske trojice, na primer* = 3, y = 4, z - 5! Kaj pa lahko rečemo za />jer ki so večji od 2? Znameniti francoski matematik Fermat (1601—1665) je domneval, da obstajajo cele netrivialne rešitve samo pri n = 2, pri n > 2 pa po njegovi domnevi ni nobene netrivialne rešitve, (Trivialne rešitve so tiste, pri katerih je ena od spremenljivk enaka nič, take pa seveda obstajajo pri vsakem n.) Poiskati dokaz ali protidokaz te domneve je slavni Fermatov problem. Od Fermatovih časov do danes je mnogo matematikov poskusilo dokazati ali ovreči domnevo, toda brez popolnega uspeha. Problem očitno ni enostaven! Zanimivo je, da je Fermat zapisal, da je našel dokaz za svojo trditev, ki pa ga ni nikjer objavil. Več o Fermatovem problemu si lahko preberete v knjižici prof. Ivana Vidava Rešeni in nerešeni problemi matematike (Knjižnica Sigma; 1).
Problem barvanja točk grafa je mlajši, pa ima vendar kar zanimivo zgodovino. Za razliko od Fermatovega problema tu ni težav z obstojem rešitev; zajec tiči v drugem grmu. Ko namreč želimo poiskati hiter algoritem, ki bo našel barvanje za poljuben graf, se izkaže, da to nikakor ni enostavno.
Preden zastavimo problem, navedimo in ponovimo nekaj pojmov iz teorije grafov, ki jih najdemo na primer v presekovi knjižici Najnujnejše o grafih, ki sta jo napisala Drago Baje in Tomaž Pisanski, Graf G = (V, E) je matematični objekt, ki ga podamo z množico točk V in množico povezav (torej parov točk)
E. Točki sta sosednji, če med njima poteka povezava. Barvanje grafa je preslikava, ki vsaki točki grafa priredi neko barvo. Za imena barv običajno zaradi enostavnosti vzamemo kar naravna števila. Dobro barvanje je tako, ki sosednje točke pobarva z različnimi barvami. Na primer barvanje na sliki t je dobro barvanje, barvanje na sliki 2 pa ne.
Graf je k~pobarvljiv, če obstaja dobro barvanje s k ali manj barvami. Graf iz prejšnjega primera (stika 1 in 2) ni 2-pobarvljiv, je pa 3-pobarvtjiv in seveda 4—, 5—, ... —pobarvljiv, torej Ar—pobarvljiv za vse k > 3. Minimalno število barv, potrebnih za dobro barvanje, imenujemo kromatično Število grafa in ga označimo z xlG). Graf iz prejšnjega primera ima torej kromatično število 3.
Zdaj pa naloga: Imamo graf G = (U, E) in naravno število k. Ali je graf G k—pobarvljiv? To je odločitveni problem barvanja točk grafa.
Problem ni nerešen, tako kot Fermatov, je pa "težak" na drug način, ki ga bomo poskusili pojasniti v nadaljevanju. V kratki zgodovini teorije zahtevnosti računskih postopkov se je izoblikovala tudi domneva, da obstajajo problemi, za katere obstajajo učinkoviti postopki in taki, za katere učinkovitih postopkov ni mogoče konstruirati. Zvesti bralci Preseka se bodo verjetno spomnili članka Sandija Ktavžarja o časovni kompleksnosti algoritmov v 2. številki letnika 86/87. Natančna definicija učinkovitih postopkov presega okvir tega sestavka, tukaj povejmo le, kaj bi za problem barvanja točk grafa pomenilo, da je algoritem učinkovit. Ko določimo Število k in imamo dan graf G, lahko definiramo obsežnost problema barvanja točk grafa: to naj bo kar število točk grafa, torej n = moč(V). Hitrost algoritma lahko merimo s številom potrebnih korakov. Lahko privzamemo, da smo algoritem zapisali v enem od programskih jezikov {na primer v pascalu, FORTRANu ali BASICu). Korak algoritma je izvedba enega enostavnega ukaza. Na primer vrstica
x := y + z * 3 je en (pascalski) korak, del programa
for i := 1 to n do
for j := 1 to n do begin
x[l] s-y[i];
z [ i ] := 2 * y [ i ]
end;
pa je 2 * n2 korakov. Pogosto nas zanima samo velkostni red, konstantni faktor takrat ni pomemben. Del programa v prejšnjem primeru ima število korakov, ki je kvadratna funkcija n—ja, to pa zapišemo krajše 0(n2) in preberemo veliki o od n kvadrat. Po definiciji je funkcija gin) reda 0(f(n)), če obstaja
konstanta C > 0, tako da je g(n) < Cf(n) za vse dovolj velike n. Pri tem fraza "trditev velja za vse dovolj velike n" pomeni, da obstaja naravno Število n', da je za vsak n ^n' trditev veljavna.
Pravimo, da je algoritem polinomski, če je njegovo število korakov enako 0(p(n}) za neki polinom p. Polinomski postopki so v teoriji Časovne zahtevnosti ravno učinkoviti postopki.
Problem je polinomski, če zanj obstaja polinomski algoritem. Za problem barvanja točk grafa na primer ne poznamo nobenega polinomskega algoritma. Prav tako doslej ni nihče dokazal, da takega algoritma ni mogoče konstruirati. Vsi doslej znani postopki za reševanje problema barvanja točk grafa imajo vsaj eksponentni red potrebnega Števila korakov. (Število korakov je na primer 10*2" ali 10", torej ne obstaja polinom p(n), da bi bilo Število korakov reda 0<p</i)) ).
Poglejmo si primerjavo rasti neke polinomske in neke eksponentne funkcije, Recimo, da imamo polinomski algoritem s časovno zahtevnostjo lOOOOrj2 in eksponentni algoritem s časovno zahtevnostjo 2 ". Predpostavimo, da osnovna operacija traja eno milisekundo in preračunajmo potrebne čase za nekaj različnih n—jev (tabela 1).
Tabela 1
n	10000 n1	2"
10	106 = 16 min	2l0^1s
20	4.106 =1 h 6 min	220==17min
30	9.106 s 2 h 30 min	230 =i12d
40	1,6.107 = 4 h 26 min 2*°s36let
50	2,5.107 2= 7 h	2S0 ==45000 let
100	ID8 si d 3 h
1000	1010 s 115 dni
Vidimo, da eksponentna funkcija zelo hitro prehiti polinomsko. Ker število korakov tako hitro narašča, so postopki z eksponentno časovno zahtevnostjo praktično neuporabni že pri malo večjih n. Toda, računalniki so vedno vsak dan hitrejši, porečete. Na žalost to ne pomaga kaj prida. Če na primer računalnike pohitrimo za faktor 1000, se to bore malo pozna, ko želimo ugnati problem pri velikih n—jih z eksponentnim algoritmom. Poglejmo, kako bi se spremenila tabela 1, če bi imeli 1000 krat hitrejši računalnik. V tabeli 2 je osnovna enota mikrosekunda.
n
T 0000/)
2
2 n
1000
10 20 30 40 50 100
106 = 1 s 4.106 = 4 s 9.106 ^ 9 s 1,6.107 = 16 s 2,5.107 = 25 s 108 ss100s 1010 =*2h46rnin
2 = 17 min
210 s 1 ms 220 = 2 s
240 se 12 d 2S 0 =36 let
30
Tabela 2
Danes poznamo veliko praktičnih problemov, ki so prav tako "težki" kot problem barvanja točk grafa. Vprašanje, alt resnično ni mogoče najti poli-nomskega algoritma za te probleme, je eno od najbolj znanih odprtih vprašanj teoretičnega računalništva.
Za tiste, ki jih zanima zgodovina matematike, pa za konec še povejmo, kako je problem barvanja točk grafa povezan s slavnim problemom štirih barv. Problem štirih barv je bil skoraj sto let velika uganka, ob kateri se je razvijala teorija grafov. Problem si je prvi zastavil leta 1852 londonski študent Francis Guthrie, ko je barva! zemljevid angleških grofij. Domneval je, da je mogoče vsak zemljevid pobarvati s štirimi barvami, seveda tako, da ozemlja, ki mejijo, niso pobarvana z enako barvo. Pri tem ozemlja, ki se dotikajo samo v končno mnogo točkah, ne štejemo za sosednja. Problem običajno zastavimo v nekoliko drugačni obliki. Namesto ozemelj barvamo točke (lahko si mislimo, da so to glavna mesta), povezani pa sta točki, ki sta v sosednjih državah. Problem se potem glasi: ali je mogoče točke vsakega planarnega grafa pobarvati s štirimi barvami (tako da pobarvamo poljubni povezani točki z različnima barvama)? Planaren je graf, ki ga lahko narišemo v ravnini tako, da se noben par povezav ne seka. Francisov brat Frederic je problem predstavil profesorju Augustu de Morganu, Širše znan je problem posta! leta 1878, ko je Arthur Caytey na srečanju Londonske matematične družbe (London Math. Society) vprašal, ali je problem že rešen. Prvi se je reševanja problema resno lotil A.B. Kempe, ki je leta 1879 objavi! dokaz, da štiri barve zadoščajo. Oeset let kasneje je P.J. Heawood odkril napako v Kempejevem dokazu, ki pa so jo mnogi imeli bolj za tehnično pomanjkljivost kot pa za resno napako. Ko pa so leta minevala in nikomur ni uspelo popraviti dokaza, je postalo jasno, da problem ni od muh. Leta 1976 sta Kenneth Appel in Wolfgang Haken objavila, da sta
dokazala izrek o štirih barvah. Ideja dokaza je v bistvu eriaka Kempejevei, le število posebnih primerov, ki jih je bilo potrebno pregledati, je precej večje (okoli 1500 namesto 51). Obsežnost je tudi glavna pomanjkljivost dokaza, saj je za pregled (okoli 600 strani dolgega) dokaza potrebno ogromno Časa, tudi če za nekatera rutinska opravila uporabimo računalnik, kot sta to storila avtorja dokaza.
Za konec pa še nekaj nalog: 1. Poišči optimalno barvanje za graf na stiki 3!
O
Slika 3
2. Premisli, koliko barv potrebuješ za optimalno barvanje cikla lihe dolžine c2k+\
3. Dokazi izrek: 2— pobarvtjivi grafi so natanko tisti grafi, ki ne vsebujejo (kot podgraf) nobenega lihega cikla, (To so ravno dvodelni grafi.)
2,	3 barve
3,	H ¡e podgraf grafa G, če ga dobimo iz G tako, da odstranimo nekaj točk in povezav. Skupaj s točko grafa moramo seveda izbrisati tudi vse povezave, ki imajo to točko za krajišče, Očitno dobro barvanje grafa G, zoženo na podgraf Ht določa dobro barvanje grafa H, Zato število barv, potrebnih za dobro barvanje grafa G, gotovo zadošča za dobro barvanje grafa H. Torej x(S)>xW).
Zdaj pa do kazimo izrek:
a.	Recimo, da je graf 2—pobarljiv in vsebuje kot podgraf kak lihi cikel H. Potem bi bil tudi H kot podgraf G 2-pobarljiv* To pa je v nasprotju s premislekom v nalogi 2,
b.	Naj bo zdaj G graf, ki vsebuje kakšen lihi cike! H. Iz naloge 2 vemo, da je x(W = 3, Ker je H podgraf grafa G, pa mora biti x(G) > = 3.