Opis programa GraphColoring

Program GraphColoring poisce minimalno barvanje danega grafa. Najde optimalno resitev in jo prikaze. Ce je vec resitev, najde eno izmed njih. Uporablja metodo razveji in omeji.

PODATKOVNE STRUKTURE IN SPREMENLJIVKE

Graf je predstavljen s petimi vektorji (glej sliko 1):

vektorji xtocke, ytocke in barve vsebujejo koordinate in barve tock,
vektorja crta1 in crta2 vsebujeta pare tock, med katerimi obstaja povezava.

Med delovanjem program uporablja sklad (glej sliko 2). Na sklad shranjuje mozna nadaljevanja v obliki trojk (tocka, barva, Tmin):

tocka - katero tocko naj pobarvam
barva - kako naj tocko pobarvam
Tmin - koliko barv bo uporabljenih, ko tocko pobarvam

V spremenljivki minbarv je zapisano trenutno najmanjse stevilo potrebnih barv. Na zacetku je minbarv enaka stevilu vseh tock v grafu.

V polju R je zapisano trenutno minimalno barvanje. Na zacetku je v R taksno barvanje, kjer ima vsaka tocka svojo barvo.

ALGORITEM

 daj na sklad trojko (0,1,1)                //prva tocka, prva barva
 minbarv = stevilo tock v grafu
 R = barvanje, kjer ima vsaka tocka svojo barvo
 while sklad ni prazen {
   vzami s sklada trojko (T,B,Tmin)
   if (Tmin < minbarv) {                    //ali se splaca uporabiti
     pobarvaj tocko T z barvo B
     if (T == zadnja tocka) {               //nova, boljsa resitev
       shrani barvanje v R
     } else {
       razveljavi barve tock, ki sledijo T  //priredimo jim barvo 0
       U = T + 1                            //naslednja tocka
       M = mnozica moznih barv za tocko U   //le barve, ki so ze v grafu
       if (Tmin+1 < minbarv) {
         daj na sklad trojko (U,nova barva,Tmin+1)
       }
       za vse barve iz M {
         daj na sklad trojko (U,barva,Tmin)
       }
     }
   }
 }
 pobarvaj tocke tako, kot je shranjeno v R

RAZLAGA ALGORITMA

Algoritem isce v globino. Na vsakem koraku ugotovi, koliko barv je ze porabil. Vsako tocko poskusa pobarvati z vsemi ze obstojecimi barvami (ki jih nimajo sosednje tocke) in z eno novo barvo. V globino gre tako globoko, dokler ne ugotovi:

Porabil je ze toliko barv, kot jih vsebuje trenutno najboljsa resitev, v tem primeru se ne splaca nadaljevati, ker ne bomo izboljsali resitve.
Pobarval je vse tocke, v tem primeru smo nasli novo resitev, ki je boljsa od vseh prejsnjih.

Algoritem se konca, ko ni vec nobene moznosti, ki bi lahko vodila k boljsi resitvi.

ZAHTEVNOST ALGORITMA

Algoritem GraphColoring ima v najslabsem primeru eksponentno casovno in prostorsko zahtevnost.