RAČUNALNIŠTVO
Dominantno število
^ ^ ^
polona pavlic
V času vse večjih podnebnih sprememb smo priča naraščajočemu številu vremenskih ujm. Zadnja takšna se je v Sloveniji zgodila novembra 2012, ko so naše kraje zajele katastrofalne poplave. V takih primerih je dobro, da imajo vsaj večja mesta zagotovljene organizirane oblike pomoči, kot je npr. Civilna zaščita. Zaradi vsesplošnega varčevanja je jasno, da je potrebno enote pomoči postaviti po državi tako, da jih bo potrebnih čim manj, hkrati pa bodo te preudarno postavljene. V nadaljevanju se bomo vprašali, kako najti finančno ter prostorsko čim bolj ugodno rešitev za poljubno razporeditev mest v katerih naj bi bile enote za pomoč, ter povezav med njimi. Za manjši primer bi z nekaj razmišljanja lahko hitro našli ugodno rešitev zastavljenega problema. Za večje primere pa ne moremo več z gotovostjo trditi, da je naša rešitev najboljša možna - morda obstaja razporeditev z manj enotami. Poskusimo problem zapisati formalno in ugotoviti, kako se reši za splošen primer.
Matematični pogled
V jeziku veje matematike, ki jo imenujemo teorija grafov, lahko probleme tega tipa zapišemo takole: mislimo si, da mesta predstavimo s točko, imenujemo jo vozlišče. Ceste, ki vodijo od enega do drugega mesta, pa predstavimo s črto, imenujemo jo po-
26
presek 40 (2012/2013) 4
RAČUNALNIŠTVO
vezava. Množico vseh vozlišč V (angleško vertices), skupaj s pripadajočimi povezavami E (angleško od-ges), imenujemo graf in ga označimo z G = (V,E). Ce med dvema vazliščema obstajo povezava, pravimo, da sta sosednji. Primer grafa za predstavitev zemljevida slovenskih mest, ki jih neposredno pove-ouje avtocesta, je prikazan na sliki 1.
Murska Sobota
Novo mesto
Koper
SLiKA 1.
Zemljevid večjih slovenskih mest in pripadajoči graf G
Za učinkovito postavitev organiziranih enot pomoči v mesta želimo pobarvati vozlišča pripadajočega grafa tako, da bo vsako vozlišče bodisi pobarvano samo bodisi bo sosednje s pobarvanim vozliščem. Pri tem pobarvano vozlišče pomeni, da je v tistem mestu na voejo enota pomoči, vsako mesto, ki ni pobarvano, pa mora imeti vsaj enega pobarvanega soseda. To pomeni, da lahko v to mesto dovolj hitro pride pomoč. Množiči tako pobarvanih vozlišč grafa pravimo dominantna množica. Številu vozlišč v dominantni množiči, ki ima med vsemi možnimi dominantnimi množičami najmanj elementov, pra-
vimo dominantno število grafa in ga označimo y(G). Dominantno množico, ki ima najmanjše možno število vozlišč (y(G)), imenujemo najmanjša dominantna množica. Za vozlišče grafa bomo včasih rekli, da je dominirano, če je bodisi v dominantni množiči bodisi je sosednje z vozliščem iz dominantne množiče grafa. Za graf slovenskih mest na sliki 1 je dominantno število 3. Poskusite sami poiskati optimalno razporeditev enot za ta primer. Preverite tudi trditev, da z dvema vozliščema ne moremo zadostiti pogoju.
Na sliki 2 so obarvana vozlišča najmanjših domi-nantnihmnožič predstavljenih grafov. Prvi graf imenujemo pot na n vozliščih (v našem primeru je n = 5). Bi znali sami določiti dominantno število poti za poljubni n? Oparimo lahko, daorora biti v dominantni mn ožič i vsaj vsako tretje vozlišč e. Tako pridemo dr rezultata y(Pni = T in d Podobno velja tudi za grafe, ki jih imenujemo čikli na n vozliščih, Cn. Na drugem primeru na sliki 2 je čileel C6, katerega dominantno število fe 2. Tretji graf na sltki je primer dvezda, 01n; v naoem primeru je n = 6, v splošnem pa čentralno vozlišče pevežemo z n dojatnimš vo-nfišči. Očijno je za zvezdo vedno dovolj, da pobar-namo le čentralno vvzlišče. Torej .e y(01n) = 1 za vsako naravno štrvilv nt. drdnji graf s slike 2 imenujemo mreža ali grid. Tukaj er dolooitev dominantega jtevila oekvliko bolj zahtevna. Za primer na sliki je rezultat 4, medtem ko je bil nezultat za mrožo dolžena n vozlišč inoirineio vozlišč dolga leta neznan, dokazan pa leta 2011.
SLIKA 2.
Dominantnaštevilapoti,cikla, zvezdeismreže
Preden nadaljujemo, premirlite še naslednje: Ali lahko v vsakem izmed primerov na sliki 2 najdete audi tako dominantno množico, Iti jo sestavljajo dtu-
PRESEK 40 (2012/2013) 4
27
RAČUNALNIŠTVO
ga vozlišča grafa tako da bo ta množica še vedno najmanjša?
Dodajmo še, da je bil problem dominantnega števila pred časom že predstavljen v Preseku [1], vendar v nekoliko drugačni obliki. Avtor je predstavil, kako na šahovsko desko razporediti najmanjše število kraljic tako, da bodo kraljice pokrivale vsako polje šahovnice - bodisi je na polju kraljica bodisi lahko do polja pride z dovoljenim premikom (levo, desno, gor, dol ali po diagonalah). Ce vsakemu polju šahovnice priredimo svoje vozlišce, dve vozlišci pa povežemo s povezavo, kadar lahko s kraljico pridemo iz enega na drugo polje, bo tako dobljeni graf ustrezal premikom kraljice po šahovski plošci. Dominanto število takega grafa pa bo ravno najmanjše število kraljic, ki jih moramo razporediti na polja tako, da bo vsako polje bodisi pokrito s kraljico bodisi pa bo kraljica do tega polja lahko prišla (glej sliko 3).
kazan na sliki 4. Tudi graf slovenskih mest iz slike 4 je primer drevesa.
SLiKa 3.
Graf kraljice za šahovko desko velikost 3 x 3
H
Določitev dominantnega števila je težek problem
S temo dominacije grafov se ukvarja veliko število matematikov, napisanih je bilo že na tisoče Člankov, zelo hitro pa je postalo jasno, da je problem določitve dominantnega števila grafa izjemno težek problem. Pravimo, da je ta problem, kot še mnogo zanimivih matematičnih problemov, NP-poln. To pomeni, da lahko za nekatere grafe z nekaj truda poiščemo dominantno število, vendar pa za poljubni graf tega ne moremo narediti, vsaj ne dovolj hitro (v polinomskem času). Dovolj hitro lahko samo preverimo, če je neka množiča vozlišč res dominantna, to pa je tudi vse. Zato so se različni avtorji ukvarjali z določitvijo dominantnega števila nekaterih družin grafov. Tukaj bomo predstavili hiter algoritem (teče v linearnem času), ki poišče dominantno število drevesa. Drevo je povezan graf, ki je brez čiklov. Z drugimi besedami, v drevesu med poljubnima dvema vozliščema obstaja natanko ena pot (iz nekega vozlišča lahko prek ostalih vozlišč in povezav do drugega vozlišča pridemo na en sam način). Poseben primer drevesa, ki ga imenujemo tudi dvojiško drevo, je pri-
SLIKA 4.
Dvojiškodrevo in njegovanaj-manjša dominantna množica
Algoritem za drevesa
Poglejmo sedaj kako najti naj manjšo dominantno množico za poljubno Prevo T. Razdelimo njegova vozlišča v tri slnupine, Vi,V2 in V3. Pri tem vsako izmed vozlišč spada v natanlno env izmed sinupin. Množico V1 imenujmo množica prostih vozlišč, vozlišča iz V2 ngj bodo mejna, vozlišča iz V3 na potrebnz. Zamnožico vozlišč D pravimo, da je opcijska doml-siantna množica, če vsebuje vsa potrebna vozlišča (iz V3) in dominiravsa mejno vozlišča (vsako vozlišče iz V2 se sosednje z nekim iz D ali pa je v D). Za vozliščo iz V1 ni pouojev, toaej v opcijski dominantni mnažiri niso niti nujnn dominirana, laOko pa so ali v D ali pa nosednjo z nekom iz D.
Razmislite, d a ae v primeru, ko je V1 = 0, V2 = V in V3 = 0, opčijpko dommantno število grafa enako običajnemu dominantnemu številu grafa. Zato s!go-ritem za iskanje velikosti najmanjše opčCjske dominantne množiče grafa zadošča oa iskanje dnminon-tnega števila grafa.
Sedaj imamo pripravljeno vse, da se lahko lotimo algoritma za iekanje dominantnega števila drevesa. Izberimo poljubno vozlišče daevesak imenujmo ga koren, io ga oštevilčimo z 1. Nato vsa nadaljnja voo-lišča po vrsti oštevilčimo z zaporednimi naravnimi števili - najprej vse njegove sosede, nato pa po vrstnem redu vse sosede sosedov, itd. Tak način ošte-vilčevanja vozlišč je bil pred kratkim predstavljen pod imenom pregled v širino tudi v Preseku [3]. Podrobneje si za graf slovenskih mest ta postopek lahko ogledamo na sliki 5. Nadalje tvorimo polje Starš takole: korenu priredimo vrednost 0 (Starš [1] = 0), nato pa za vsako vozlišče povemo, katero od že pregledanih vozlišč je njegov sosed (starš). Za drevo s slike 5 imamo:
28
PRESEK 40 (2012/2013) 4
RAČUNALNIŠTVO
i	1	2	3	4	5	6	7	8	9
Starš [ i ]	0	1	2	3	3	3	6	7	7
8
SLIKA5.
Izvedbaalgoritmaza drevosslikel
Sedaj bomo poskušali poiskati najmanjšo dominantno množico drevesa. To bomo naredili tako, da vsakemu vozlišču priredimo oznako, „prosto", „mejno" ali „potrebno". To zapišemo v polje Oznaka. V zočetku vsako voališčo označimo kot „meino" in naj-manjao dominantno množico označimo z D ter jo zaenkrat pustimo prazno. Začaimo pri vozlišču n, torej zadnjem. Če je označeno kot „mejno" (v za-Zetku to gotovo je res), njegovega starša označimo kot „potrebno", saj mora biti tudo to zadnje vozlišče dominirano. Nato nadaljujemo postovek na vozlišču n - 1. Čv jo označeno kot „mejno", njagoeaga staroa označimo kot „potrebno", če pa je oznaka vozlišča n - 1 „potrebno", to vozlišče dodamo v dominantno množičo D ter njegovega starša oznanimo „prosto", saj j o to vozlišče že dominirano. Tale postopek nada-tjujemo vse do korena. Če je karen ozvačen „mejno" alš „potrebno", ga dodamo v dominantno množičo, sičer pa smo že pred tem končali in dominirali če-loten graf. Najmanjšo dominantno množičo danega drevesa torej sestavljajo vsa vozlišča z oznako „potrebno". Natančneje si lahko ta postopek ogledate v algoritmu 1.
Glede na to, da moramo v algoritmu samo prepotovati skozi vsa vozliaca drevesa (imamo le dve zaporedni zanki), bo ta algoritem zares tekel v zgoraj omenjenem linearnem casu. Spremljajte, kako al-
Algoritem 1 Dominan I no število drevesa_
Vhod: Drevo T, ki je predstavljeno s poljem
Starš [1... n]. Izhod: Najmanjša dominantna množica D drevesa T, ki "o predstavljajo vdzlišca i z O znaka [i] = "potrebno". ž D -m 0;
2: za i = 1... n naredi
3: Oznaka [o] = "mejno"; i: konec
5: za i = n... 2 naredi
6: ce Oznaka [i] = "mejno" potem 7:	Oznaka [Starš [i]] = "potrebno";
8: sicer ce Oinaka [i] = "potoebdo" potem 9:	D — D u {i};
10:	ce Oznaka [Starš [i]] = "mejno" potem
11:	Oznaka [Starš [i]] = "prosto";
12:	konec
13: konec
14: konec
15: ce Oznaka [1] = "mejno"a\i Oznaka [1] = "potrebno" potem
16: D o- D u {1}; 17: konec
goritem 1 teče na primeru s slike 5, in videli boste, kako pridemo do obarvanih vozlišč - ta predstavljajo potrebna vozlišča, torej tista, ki tvorijo dominantno množičo. Razmislite, ali ta postopek zares deluje, z drugimi besedami razmislite o tem, da je rešitev vedno najmanjša dominantna množica danega drevesa. Tukaj bomo podrobnosti izpustili.
Literatura
[1]	B. Brešar, Kraljice napadajo! Presek, 27 (1) 1999, 16-21.
[2]	T. W. Haynes, S. T. Hedetniemi in P. J. Slater, Fundamentals of Domination in Graphs. Marcel De-kker, New York, 1998.
[3]	A. Taranenk0 predstavUev grafa s seznamom sosedov m pregled v širmo. ftesek 39 (6) 2012, 2730.	XXX
www.presek.si
PRESEK 40 (2012/2013)4
29