Grafų teorija
5 (100%) 1 vote

Grafų teorija

1) Grafo viršūnių peržiūros metodai

Daugelio grafų teorijos uždavinių sprendimo algoritmų pagrindą sudaro sisteminga grafo viršūnių peržiūra, t.y. toks grafo viršūnių apėjimas, kad kiekviena viršūnė nagrinėjama vienintelį kartą. Todėl labai svarbus uždavinys yra rasti gerus grafo viršūnių peržiūros metodus. Apskritai kalbant, viršūnių peržiūros metodas yra “geras”, jei:

· nagrinėjamo uždavinio sprendimo algoritmas lengvai įsikomponuoja į peržiūros metodą;

· kiekviena grafo briauna analizuojama ne daugiau kaip vieną kartą (arba, kas iš esmės nekeičia situacijos, briaunos nagrinėjimo skaičius apribotas konstanta).

Pagrindiniai grafo viršūnių peržiūros metodai, tenkinantys pateiktus reikalavimus, yra paieškos gilyn metodas ir paieškos platyn metodas.

2) Paieška gilyn

Paieškos gilyn (rus. poisk v glubinu; angl. Depth first search) metodą pirmasis 1972 m. pasiūlė R.Tarjanas . Metodo idėja yra labai paprasta. Pradžioje visos grafo viršūnės yra naujos (neaplankytos). Tarkime, kad paieška pradedama iš viršūnės v0. Viršūnė v0 tampa nenauja, ir išrenkame viršūnę u, kuri yra gretima viršūnei v0. Jei viršūnė u yra nauja, peržiūros procesą tęsiame iš viršūnės u.

Tarkime, kad esame viršūnėje v.

Jei yra nauja dar neaplankyta viršūnė u, gretima viršūnei v, tai nagrinėjame viršūnę u (ji tampa nenauja) ir paiešką tęsiame iš viršūnės u.

Jei nėra nei vienos naujos viršūnės, gretimos viršūnei v, tai sakome, kad viršūnė v išsemta; grįžtame į viršūnę, iš kurios patekome į viršūnę v, ir paiešką tęsiame iš šios viršūnės.

Paiešką baigiame, kai pradinė paieškos viršūnė v0 tampa išsemta viršūne.

Pavyzdys. Panagrinėkime, kaip bus peržiūrėtos 2.8.1 a) pav. pavaizduoto grafo viršūnės, jei paieška pradedama iš viršūnės , o bet kokiai viršūnei gretimos viršūnės gretimumo struktūroje išdėstytos jų numerių didėjimo tvarka:

1: 2, 3

2: 1, 3, 4, 5

3: 1, 2, 5

4: 2, 5

5: 2, 3, 42.8.1 pav. Paieška gilyn iš 1-osios viršūnės

Paieškos gilyn metu pirmiausia iš 1-osios viršūnės einame į 2-ąją viršūnę. Kadangi 2-oji viršūnė yra nauja, tai toliau peržiūrą tęsiame iš 2-osios viršūnės. (Pirmoji ir antroji viršūnės tampa aplankytomis). Iš 2-osios viršūnės pirmiausia einame į 1-ąją viršūnę. Kadangi pirmoji viršūnė nenauja (aplankyta), tai iš 2-osios viršūnės bandome eiti į kitą jai gretimą 3-iąją viršūnę. Trečioji viršūnė nauja, todėl ją aplankome ir peržiūrą tęsiame iš 3-osios viršūnės. Iš 3-iosios viršūnės bandome eiti į pirmąją jai gretimą viršūnę, – į 1-ąją viršūnę. Ši viršūnė nenauja. Tada bandome eiti į kitą 3-ajai viršūnei gretimą 2-ąją viršūnę. Ši viršūnė taip pat aplankyta, todėl bandome eiti į paskutiniąją 3-iajai viršūnei gretimą 5-ąją viršūnę. Ši viršūnė yra nauja, todėl peržiūrą dabar tęsime iš 5-osios viršūnės. Iš 5-osios viršūnės, po bandymų keliauti į 2-ąją ir 3-iąją viršūnes, ateisime į 4-ąją viršūnę. Kadangi 4-osios viršūnės visos gretimos viršūnės nėra naujos, tai 4-oji viršūnė išsemta. Paiešką bandome tęsti iš 5-osios viršūnės, nes į 4-ąją viršūnę atėjome iš 5-osios viršūnės. 5-ąjąi viršūnei visos gretimos viršūnės yra nenaujos, todėl 5-oji viršūnė yra išsemta ir paiešką bandome tęsti iš 3-iosios viršūnės. 3-ioji viršūnė taip pat išsemta, todėl paiešką tęsime iš 2-osios viršūnės, nes į 3-iąją viršūnę atėjome iš 2-osios viršūnės. 2-ąjai viršūnei dar nenagrinėta gretima yra 5-toji viršūnė. Tačiau ši viršūnė nenauja, todėl 2-oji viršūnė tampa išsemta ir paiešką tęsiame iš 1-osios viršūnės. Iš 1-osios viršūnės bandome eiti į 3-iąją, tačiau ji jau aplankyta. Tuo būdu ir 1-oji viršūnė tampa išsemta, o tai yra paieškos gilyn algoritmo pabaiga.

Pastaba. 2.8.1 a) pav. romėniškais skaitmenimis pažymėti briaunų apėjimo eilės numeriai.

2.8.1 b) pav. ištisinėmis linijomis pavaizduotos briaunos (su nurodyta apėjimo kryptimi), kurios veda į naujas viršūnes, o punktyrais pažymėtos briaunos, kurios paieškos gilyn metu vedė į aplankytas (nenaujas) viršūnes.

Panagrinėkime, kaip programiškai organizuoti paieškos gilyn metodą. Aptarsime tris paieškos gilyn organizavimo metodus: 1) paieškos gilyn, naudojant rekursiją, būdą, 2) paieškos gilyn su mažiausia atminties apimtimi organizavimo būdą ir 3) paieškos gilyn, nenaudojant rekursijos, būdą.

3) Paieška gilyn, naudojant rekursiją

Tarkime, -grafas – nusakytas gretimumo struktūra: – aibė viršūnių, gretimų viršūnei . Kaip minėjome aukščiau, sakinį “nagrinėti viršūnes, gretimas viršūnei v”, formaliai užrašysime: for do nagrinėti u;.

Apibrėžkime masyvą naujas [1..n], čia naujas [i] = true, jei viršūnė i nauja (neaplankyta) ir naujas [i] = false, jei viršūnė i nenauja (aplankyta).

Tarkime, kad gretimumo struktūra ir masyvas naujas yra globalieji masyvai. Tada paieškos gilyn iš viršūnės v procedūra bus užrašoma taip:

procedure gylis (v);

begin

“nagrinėti viršūnę v”; naujas [v] := false;

for u Î N (v) do

if naujas[u] then gylis (u);

end;

Paieška gilyn grafe, kuris gali būti ir nejungusis, bus vykdoma taip:

begin

for vÎV do naujas [v] :=
true; {inicializacija}

for v Î V do

if naujas[v] then gylis (v);

end;

4) Paieškos gilyn su mažiausia atminties apimtimi organizavimas

Šį algoritmą aptarkime, laikydami, kad grafas G užrašytas masyvais L ir lst (žr. 2.7 paragrafą). Kitaip tariant, šios procedūros įėjimo parametrai yra:

n – grafo viršūnių skaičius,

m – grafo briaunų (lankų) skaičius,

L [1.. 2m] (neorientuotiesiems grafams) – briaunų masyvas,

(L [1.. m] (orientuotiesiems grafams) – lankų masyvas),

lst [1.. n+1] – briaunų (lankų) adresų masyvas,

v – paieškos gilyn viršūnės numeris.

Reikia organizuoti paiešką gilyn iš viršūnės v.

Vidiniai kintamieji ir darbo masyvai. Aptarkime vidinius kintamuosius ir darbo masyvus, kurie naudojami organizuojant paiešką gilyn.

Masyvas fst [1..n]; fst [i] – reiškia adresą masyve L dar nenagrinėtos viršūnės, gretimos viršūnei i, ; tiksliau briauna (jei tokia yra) yra paieškos gilyn metu dar nenagrinėta briauna, incidentiška viršūnei i. Pradinės masyvo fst elementų reikšmės yra , .

Masyvas prec [1..n]. Šio masyvo elementai naudojami keliems tikslams:Pradžioje , (visos grafo viršūnės yra naujos).

Kintamasis k žymi viršūnę, iš kurios tęsiame paiešką. Pradžioje ;

Loginis kintamasis p:

Loginis kintamasis t:

Tada paieškos gilyn procedūra gali būti užrašyta taip.

const c = 500;

type

mas = array [1..c] of integer;

matr = array [1..2, 1..c] of integer;

procedure gylis1 (v, n, m : integer; L, lst : mas);

{ Procedūra gylis1 organizuoja paiešką gilyn iš viršūnės v, kai grafas nusakytas L ir lst masyvais.

Formalūs parametrai:

v – pradinė paieškos viršūnė,

n – grafo viršūnių skaičius,

m – grafo briaunų (lankų) skaičius,

L, lst – grafą nusakantys tiesioginių nuorodu masyvai. }

var i, k, u : integer;

t, p : boolean;

fst, prec : mas;

begin

{ Inicializacija }

for i := 1 to n do begin

fst [i] := lst [i] + 1;

prec [i] := 0;

end;

k: = v;

if fst [k] <= lst [k + 1] then {yra nenagrinėtų briaunų, incidentiškų viršūnei k }

begin

t := false;

p := true;

prec [k] := k; { k – pradinė paieškos viršūnė }

{ Nagrinėti viršūnę k }

writeln(k);

end

else {viršūnė k yra arba izoliuota viršūnė, arba neturi išeinančių lankų (orientuotojo grafo atveju); paieškos pabaiga }

t: = true;

while not t do { paieška nebaigta }

begin

{ Pirmyn }

while p do

begin

u := L [fst [k]];

if prec [u]=0 then {virsunė u nauja}

begin { Nagrinėti viršūnę u }

writeln (u);

prec [u] := k;{į viršūnę u atėjome iš viršūnės k}

if fst [u] <= lst [u + 1] then {viršūnė u neišsemta}

k : =u

else {viršūnė u išsemta}

p := false;

end

else

p := false; {viršūnė u nenauja}

end;

{Atgal}

while not p and not t do

begin

{ Imama nauja, dar nenagrinėta briauna, incidentiška viršūnei k }

fst [k] := fst [k] + 1;

if fst[k] <= lst [k + 1] then { tokia briauna egzistuoja }

p := true

else {viršūnė k išsemta}

if prec [k] = k then { pradinė paieškos viršūnė išsemta; paieškos pabaiga }

t := true

else { grįžome į viršūnę, iš kurios buvome atėję į

viršūnę k } k := prec [k];

end;

end;

end;

5) Paieška gilyn, nenaudojant rekursijos

Tarkime, -grafas – nusakytas gretimumo struktūra , , čia – viršūnei v gretimų viršūnių aibė.

Aibes vaizduosime vienryšiais sąrašais. Kiekvienas v-ojo sąrašo elementas yra įrašas r, nusakantis viršūnę r.viršūnė ir rodyklę r.pėdsakas, rodančią, kur yra patalpintas kitas aibės elementas.

Jei r.pėdsakas = nil, tai reiškia, kad r.viršūnė yra paskutinysis v-ojo sąrašo elementas (paskutinysis aibės elementas).

Kiekvieno sąrašo pradinio elemento adresas saugomas masyve (lentelėje) Pradžia. Tiksliau, Pradžia [v] yra rodyklė (adresas), nurodantis kur yra patalpintas pradinis v-ojo sąrašo elementas.

Pavyzdys. 2.8.2 pav. pavaizduotas grafas ir jo gretimumo struktūra, kaip vienryšių sąrašų aibė.2.8.2 pav. Grafas a) ir jo gretimumo struktūra b) – vienryšių sąrašų masyvas

Aprašysime paieškos gilyn organizavimo, nenaudojant rekursijos, procedūrą, kai grafo gretimumo struktūra nusakoma vienryšių sąrašų masyvu. Tam tikslui įveskime steko sąvoką.

Stekas – tai tiesinis sąrašas, kuriame naujų elementų patalpinimas bei elementų šalinimas atliekamas viename sąrašo gale.

Dažnai stekas vadinamas vardu LIFO, nuo angliškų žodžių: Last In First Out (paskutinis į sąrašą, pirmas iš jo).

Steką patogu realizuoti vienmačiu masyvu, pavyzdžiui, . Jis charakterizuojamas vienu parametru top – steko viršūnė.

Stekas tuščias

top := 0;

Elemento patalpinimas į steką {E Ü naujas elementas}

top := top + 1;

if top <= n then E [top] := naujas elementas

else “persipildymas”;

Elemento pašalinimas iš steko {y Ü E}

if top = 0 then “stekas tuščias”

else begin y := E [top]; top := top – 1; end;

Viršutinio steko elemento nuskaitymas, neperskaičiuojant steko viršūnės {u := top(E)}

if top = 0 then “stekas tuščias”

else u := E [top];

Paieškos gilyn organizavimas, nenaudojant rekursijos

Imkime rekursyvinę procedūrą gylis(v) (žr. 8.2.1.1 paragrafą) ir rekursiją pašalinkime standartiniu būdu – naudodami steką. Kiekviena aplankyta viršūnė talpinama į steką STEK ir šalinama iš jo po jos išsėmimo.

procedure gylis2(v); [Lip88]

{Paieška
gilyn grafe iš viršūnės v. Nerekursyvinė procedūros gylis versija (žr. 2.8.1.1 paragrafą).

Tarkime, kad paieškos proceso pradžioje P[v] = rodyklė (ląstelės adresas) į pirmąjį N(v) elementą kiekvienai viršūnei v Î V.

Masyvai P ir Naujas – globalieji.}

begin

STEK := Æ; STEK Ü v; nagrinėti v;

Naujas [v] := false;

while STEK ¹ Æ do

begin

t := top(STEK); {t – viršutinis steko elementas}

{Sąraše N(t) rasti pirmą naują viršūnę}

if P[t] = nil then b:= false

else b := not Naujas [P[t]­.viršūnė];

while b do

begin

P[t] := P[t]­.pėdsakas;

if P[t] = nil then b:= false

else b := not Naujas[P[t]­.viršūnė];

end;

if P[t] ¹ nil then {Radome naują viršūnę}

begin

t := P[t]­.viršūnė;

STEK Ü t;

nagrinėti t;

Naujas[t] := false;

end

else {viršūnė t išsemta}

{Viršūnę t šalinti iš steko, t.y. šalinti viršutinį steko elementą.}

t Ü STEK;

end; {while}

end; {gylis2}

6) Paieška platyn

Dabar aptarsime grafo viršūnių peržiūros iš viršūnės v0 paieškos platyn metodą (rus. poisk v širinu; angl. Breadth first search).

Kaip ir paieškos gilyn metode, pradžioje visos grafo viršūnės yra naujos (neaplankytos, neperžiūrėtos). Tarkime, kad paiešką pradedame iš viršūnės v0. Nagrinėjame viršūnę v0; ji tampa nenauja (aplankyta). Toliau nagrinėjamos ir tampa nenaujomis visos viršūnės, gretimos viršūnei v0, t.y. nagrinėjamos viršūnės, kurios nuo viršūnės v0 nutolę atstumu, lygiu 1. Po to nagrinėjamos ir tampa nenaujomis visos naujos viršūnės, gretimos prieš tai nagrinėtoms viršūnėms, t.y. nagrinėjamos visos naujos viršūnės, kurios nuo viršūnės v0 nutolę atstumu, lygiu 2. Apskritai, k-ajame žingsnyje nagrinėjamos ir tampa nenaujomis visos naujos viršūnės, gretimos (k-1)-ajame žingsnyje nagrinėtoms viršūnėms, t.y. viršūnės, kurios nuo viršūnės v0 nutolę atstumu, lygiu k. Paieška platyn baigiama, kai visos grafo viršūnės tampa nenaujomis, t.y. kai peržiūrimos visos viršūnės.

Paieškos platyn organizavimas. Paiešką platyn patogu organizuoti naudojant eilę.

Priminsime, kad eilė – tai tiesinis sąrašas, kuriame naujas elementas talpinamas viename sąrašo gale, o elementas šalinamas (aptarnaujamas) kitame sąrašo gale. Todėl sąrašą dar vadina FIFO vardu, nuo žodžių first in first out (pirmas į eilę, pirmas iš eilės).

Yra įvairių eilės organizavimo būdų: naudojant užciklintą vienmatį masyvą, dinaminį atminties paskirstymą ir kt. Čia aptarsime eilės organizavimą panaudojant paprasčiausią duomenų struktūrą – užciklintą vienmatį masyvą: Eilė [1.. n];

Eilė charakterizuojama dviem parametrais: r ir f, – r žymi eilės galą, o f – eilės pradžią (žr. 2.8.3 pav.), tiksliau, f rodo į prieš pirmąjį eilės elementą esančią ląstelę.

Aptarsime operacijas su eile. Prie operacijos riestiniuose skliaustuose rašysime simbolinį šios operacijos žymėjimą.

Eilei priskiriama tuščia aibė { Eilė := Æ}

r := 1; f := 1;

Ar Eilė tuščia? { Eilė = Æ}

if r = f then {Eilė tuščia} …;2.8.3 pav. Eilė kaip viematis užciklintas masyvas

Naujo elemento patalpinimas į užciklintą eilę {Eilė Ü naujas elementas}

if r = n then r := 1

else r := r + 1;

if r = f then “eilės persipildymas”

else Eilė [r] := naujas elementas;

Elemento šalinimas iš eilės {u Ü Eilė}

if r = f then “eilė tuščia”

else

begin

if f = n then f := 1

else f := f + 1;

u := Eilė [f];

end;

Tarkime, kad paieškos platyn procedūroje -grafas G nusakytas gretimumo struktūra: N (v) – aibė viršūnių, gretimų viršūnei v. Be to, visos grafo viršūnės yra naujos. Tą žymi masyvas naujas [1.. n], čia naujas [v] = true, jei viršūnė v – nauja ir naujas [v] = false – priešingu atveju. Laikykime, kad gretimumo struktūra ir masyvas naujas yra globalieji kintamieji. Tada paieška platyn iš viršūnės v užrašoma taip:

procedure plotis (v);

begin

Eilė := Æ;

Eilė Ü v;

naujas [v] := false;

while Eilė ¹ Æ do

begin

p Ü Eilė;

aplankyti (nagrinėti) p;

for u Î N(p) do

if naujas [u] then

begin

Eilė Ü u;

naujas [u] := false;

end;

end;

end;

Aptarti paieškos gilyn ir paieškos platyn metodai plačiai taikomi sprendžiant įvairius grafų teorijos uždavinius.

Kaip buvo minėta aukščiau, apskaičiuojant grafo jungiąsias komponentes, vienas iš uždavinių yra rasti aibę viršūnių, į kurias galima nukeliauti iš pasirinktosios viršūnės, neprilausančios jau apskaičiuotoms jungiosioms komponentėms. Aišku, kad “orakulas”, nurodantis tokią viršūnių aibę, yra arba “paiešką gilyn” arba “paieška platyn”.

Dabar bei tolesniame dėstyme aptarsime paieškos gilyn ir paieškos platyn metodų taikymą, sprendžiant grafų teorijos uždavinius.

7) Trumpiausių kelių besvoriniame grafe ieškojimo uždavinys

Aptarkime uždavinio: “besvoriniame grafe rasti trumpiausius kelius nuo viršūnės s iki likusių viršūnių” sprendimą.

Duota: n – grafo viršūnių skaičius,

m – grafo briaunų skaičius,

grafas, nusakytas masyvais L [1.. 2m] (neorientuotojo grafo atveju) arba L [1.. m] (orientuotojo grafo atveju) ir lst [1.. n+1],

s – viršūnė, nuo kurios norime rasti trumpiausius kelius.

Rasti: d [1..n], čia , t.y. ilgis trumpiausio kelio nuo viršūnės s iki viršūnės i,

prec [1.. n], čia

Tuo būdu masyvo d elementai

trumpiausių kelių ilgius, o masyvo prec elementai nurodys, per kurias viršūnes šie keliai eina. Šio uždavinio sprendimui panaudosime paiešką platyn, kadangi paieškos platyn k-tojo žingsnio metu yra nagrinėjamos (aplankomos) viršūnės, nutolusios nuo pradinės paieškos viršūnės atstumu k. Įvertinant tai, kad atstumas tarp viršūnių yra trumpiausio kelio, jungiančio šias viršūnes, ilgis, nesunku suvokti, kad trumpiausių kelių nuo viršūnės s iki likusių besvorinio grafo viršūnių uždavinio sprendimo algoritmas natūraliai įsilieja į paieškos platyn algoritmą.

Pradžioje visos grafo viršūnės naujos. Tą žymi masyvo naujas elementas:Atstumų masyvo d pradinės reikšmės yra “begalybė”. Kadangi besvoriniame grafe nėra nei vieno kelio, kuris būtų ilgesnis už briaunų skaičių m plius 1, tai pradžioje visi , . Vadinasi, jei grafas yra nejungusis, tai, įvykdžius žemiau pateiktą procedūrą, masyvo d elementai, atitinkantys grafo viršūnes, nepriklausančias viršūnės s jungiąjai komponentei, bus lygūs m + 1.

Pradžioje visi masyvo prec elementai yra lygūs nuliui. Taip pat aišku, kad , o .

Tarkime, kad paieškos platyn k-ajame žingsnyje nagrinėjame naują viršūnę u, gretimą -ojo žingsnio viršūnei p (žr. 2.9.1 pav.).2.9.1 pav. Trumpiausias kelias nuo viršūnės s iki viršūnės u

Tada, kaip matyti iš 2.9.1 pav., , o .

Aišku, kad pagal šias formules apskaičiuosime visus masyvo d ir prec elementus, atitinkančius paieškos platyn k-ojo žingsnio naujoms viršūnėms.

Žemiau pateikta trumpiausių kelių besvoriniame grafe apskaičiavimo procedūra, kai eilė organizuojama užciklintu vienmačiu masyvu.

const c=500;

type

mas = array [1..c] of integer;

procedure kelias (s, n, m : integer; L, lst : mas; var d, prec : mas);

{ Procedūra kelias apskaičiuoja trumpiausius kelius nuo viršūnės s iki likusių grafo viršūnių besvoriniame grafe, kai grafas nusakytas L ir lst masyvais.

Formalūs parametrai:

s – pradinė kelio viršūnė,

n – grafo viršūnių skaičius,

m – grafo briaunų (lankų) skaičius,

L, lst – grafą nusakantys tiesioginių nuorodų masyvai;

d [1..n] – trumpiausių kelių masyvas;

d [v] = d(s,v);

prec [1..n] – trumpiausių kelių medis;

jei prec [v] = k, tai trumpiausias kelias į viršūnę v ateina iš viršūnės k. }

var r f, i, p, u, c : integer;

naujas ,eile : mas;

begin

c := n + 1;

for i := 1 to n do

begin

naujas[i] := 1;

d[i] := m + 1;

prec [i] := 0;

end;

{ Eile = Æ }

r := 1; f := 1;

{ Eile s }

if r = c then r := 1 else r := r + 1;

if r = f then begin

writeln( ‘eilės persipildymas’ );

exit;

end

else eile [r] :=s ;

naujas [s] := 0;

d [s] := 0;

prec [s] := s;

{ while eilė netuščia do }

while r <> f do

begin

{ p eile }

if r = f then begin

writeln(‘eilė tuščia’);

exit;

end

else begin

if f = c then f := 1

else f := f + 1;

p:=eile [f];

end;

for i := lst [p] + 1 to lst [p + 1] do

begin

u := L [i];

if naujas [u] = 1 then

begin

d [u] := d [p] + 1;

prec [u] := p;

naujas [u] := 0;

{ eilė u }

if r = c then r := 1 else r := r + 1;

if r = f then begin

writeln (‘eilės persipildymas’);

exit;

end

else eile[r]:=u;

end;

end;

end;

end;

Pavyzdys. Panagrinėkime trumpiausius kelius nuo 1-osios viršūnės iki likusių grafo, pavaizduoto 2.9.2 pav., viršūnių.2.9.2 pav. Grafo trumpiausi keliai

Po procedūros kelias įvykdymo, kai , gausime tokius d ir prec masyvus:

2.9.2 pav. grafas turi 12 viršūnių, 15 briaunų ir nėra jungusis, todėl . Tai ir reiškia, kad iš 1-osios viršūnės nėra nei vieno kelio, vedančio į šias viršūnes.

Elementas reiškia, kad ir kelias, kaip rodo masyvas prec, eina per viršūes 12, 5, 6, 1.

Pastaba. Procedūra kelias leidžia apskaičiuoti visas besvorinio grafo metrines charakteristikas (žr. 2.4 paragrafą).

8) Dvidalis grafas

Kaip buvo minėta aukščiau, -grafas – yra dvidalis, jei jo viršūnių aibę V galima išskaidyti į du poaibius A ir B taip, kad visų grafo G briaunų galai priklausytų skirtingiems poaibiams. Todėl dvidalį grafą dažnai žymime . Čia aptarsime du dvidalio grafo uždavinius:

· dvidalio grafo kriterijaus uždavinį,

· dalinio dvidalio grafo konstravimo uždavinį.

Dvidalio grafo kriterijaus uždavinys. Tarkime, kad duotas grafas . Nustatyti, ar šis grafas yra dvidalis.

Šį uždavinį 1936 metais išsprendė D.Kionigas.

Teorema. (Kionigo teorema). Būtina ir pakankama sąlyga, kad grafas būtų dvidalis yra ta, kad jis neturėtų nelyginio ilgio ciklų.

Pateiksime šios teoremos įrodymą, nes šis įrodymas yra konstruktyvus, t.y. iš jo išplaikia algoritmas, leidžiąs nustatyti, ar grafas yra dvidalis.

Būtinumas. Tarkime, G – dvidalis grafas, o m – vienas iš jo ciklų, kurio ilgis yra k. Apeikime visas šio ciklo briaunas jų surašymo tvarka, pradedant viršūne v. Po k žingsnių grįšime į viršūnę v. Kadangi dvidalio grafo kiekvienos briaunos galai priklauso skirtingoms dalims(aibėms), tai k yra lyginis skaičius.

Pakankamumas. Nesiaurinant uždavinio, galime laikyti, kad grafas G yra jungusis, nes dvidalių grafų sąjunga yra dvidalis grafas.

Tarkime, kad -grafas neturi nelyginio ilgio ciklų, o v – bet kuri grafo viršūnė. Viršūnių aibę V į dvi dalis A ir B išskaidysime taip: grafo viršūnes u, kurioms yra lyginis skaičius, talpinsime į aibę A, o viršūnes,
kurioms yra nelyginis skaičius – į aibę B.

Belieka įrodyti, kad šių aibių indukuoti pografiai yra tuštieji.

Tarkime priešingai, kad egzistuoja dvi gretimos viršūnės u ir w,kurios priklauso vienai iš aibių. Aišku, kad nei viena iš šių viršūnių nesutaps su viršūne , nes visos viršūnei v gretimos viršūnės yra aibėje B.2.10.1 pav. Kionigo teoremos iliustracija

Tarkime, kad U – trumpiausia -grandinė, o W – trumpiausia -grandinė. Tarkime, kad šių grandinių paskutinė (skaičiuojant nuo viršūnės v) bendra viršūnė yra v1 (žr. 2.10.1 pav.). Simboliais Xu ir Yu atitinkamai pažymėkime grandinės U subgrandines ir , o simboliais Xw ir Yw – grandinės W subgrandines ir . Aišku, kad subgrandinių Xw ir Xu ilgiai yra lygūs. Vadinasi, Yw ir Yu ilgiai turi tą patį lyginumo charakterį.

Tačiau, tada, sujungus subgrandines Yu, Yw ir briauną gausime elementarųjį nelyginio ilgio ciklą.

Išvada. Grafas yra dvidalis tada ir tiktai tada, kai jis neturi elementariųjų nelyginio ilgio ciklų.

Kionigo teoremos įrodymas nusako metodą, leidžiantį nustatyti, ar grafas yra dvidalis. Šis metodas susideda iš dviejų etapų.

1. Pasirenkama bet kuri grafo viršūnė s, ir 2.9 paragrafe aprašytos procedūros kelias pagalba randame atstumus nuo viršūnės s iki visų likusių viršūnių. Tada viršūnės, kurioms šis atstumas yra lyginis skaičius, talpinamos į aibę A, o likusios – į aibę B.

2. Tikriname kiekvieną grafo briauną , ar jos galai priklauso skirtingoms aibėms.

Jei visoms grafo briaunoms viršūnės u ir v priklauso skirtingoms aibėms (A ir B), tai grafas yra dvidalis, t.y. .

Jei egzistuoja bent viena briauna , kurios abi viršūnės u ir v priklauso arba aibei A, arba aibei B, tai grafas G nėra dvidalis.

Realizuoti 2-ąjį etapą galima įvairiais būdais. Labai patogus šio etapo realizavimo būdas būtų toks.

Apibrėžkime masyvą , čia , jei viršūnė i priklauso aibei A (jei procedūros kelias atstumų masyvo elementas yra lyginis skaičius), ir , jei viršūnė i priklauso aibei B ( – nelyginis skaičius).

Tada briaunos galai priklausys skirtingoms aibėms, jei ; priešingu atveju viršūnės u ir v priklausys vienai aibei.

Pastaba. Ar briaunos galai priklauso skirtingoms aibėms, galima nustatyti tiesiogiai iš procedūros kelias masyvo :

if ((d[n] + d[v]) mod 2) = 0 then “briaunos galai priklauso tai pačiai aibei, t.y. grafas nėra dvidalis”.

Dalinio dvidalio grafo konstravimo uždavinys. Duotas grafas . Rasti šio grafo dalinį grafą, atmetant dalį pradinio grafo briaunų taip, kad atmetamų briaunų skaičius būtų nedidesnis nei , čia .

Toks dalinis grafas konstruojamas taip:

; ;

;

for and do

if then

else ;

čia – viršūnės v aplinka, t.y. viršūnei v gretimų viršūnių aibė.

Tada parodo atmetamų briaunų skaičių, jei viršūnę v talpiname į aibę A, o – atmetamų briaunų skaičių, jei viršūnę talpintume į aibę B. Vadinasi, skaidant aibę V į dvi aibes A ir B, kiekvieną kartą viršūnę v talpinsime į tą aibę, kad atmetamų briaunų skaičius būtų mažiausias ir neviršytų , čia – v-osios viršūnės laipsnis.

Aišku, kad taip konstruojant dalinį dvidalį grafą, atmetamų briaunų skaičius bus nedidesnis nei .

9) Pagrindiniai grafų teorijos skaičiai

Pagrindiniai grafų teorijos skaičiai yra:

1) ciklomatinis skaičius,

2) chromatinis (spalvinis) skaičius,

3) nepriklausomumo (vidinio stabilumo) skaičius,

4) dominavimo (išorinio stabilumo) skaičius.

10) Ciklomatinis skaičius

Nagrinėsime neorientuotuosius grafus, kurie gali būti ir multigrafai. Grafo ciklomatinis skaičius apibrėžiamas formule

,

čia m – briaunų skaičius, n – viršūnių skaičius, o p – jungiųjų komponenčių skaičius. Pavyzdžiui, grafui, pavaizduotam 2.11.1 pav., ciklomatinis skaičius .2.11.1 pav. Grafo ciklomatinis skaičius

Kiekvienam grafo ciklui galima priskirti m-matį vektorių tokiu būdu:

1. sunumeruokime briaunas ir kiekvienai briaunai laisvai suteikime orientaciją (žr. 2.11.1 b) pav.);

2. jei apeinant ciklą, k-toji briauna rodyklės kryptimi praeinama s kartų, o prieš rodyklę – t kartų, tai šiam ciklui atitinkančio vektoriaus k-oji komponentė lygi .

Pavyzdžiui, 2.11.1 b) pav. ciklą atitiks vektorius o ciklą – vektorius

Nepriklausomiems vektoriams atitinkantys ciklai yra nepriklausomi.

Teorema. Multigrafo G ciklomatinis skaičius lygus didžiausiam nepriklausomų ciklų skaičiui.

Išvados.

· Grafas G neturi ciklų tada ir tik tada, kai .

· Grafas G turi vienintelį ciklą tada ir tiktai tada, kai .

Pavyzdžiui, 2.11.1 a) grafui nepriklausomų ciklų aibė (bazė) yra ciklai: , , , .

Aišku, kad nepriklausomų ciklų rinkinys yra nevienintelis. Pavyzdžiui, tam pačiam 2.11.1 a) grafui nepriklausomų ciklų bazę sudaro ir ciklai , , , . Šie ciklai yra tiesiškai nepriklausomi, nes kiekvienas iš jų turi bent po vieną unikalią briauną, nepriklausančią likusiems ciklams. Ciklas turi unikalią briauną , – , – ir – arba .

Nepriklausomų ciklų apskaičiavimo uždavinys. Duotas jungusis neorientuotasis -grafas (ne multigrafas) . Rasti nepriklausomų ciklų bazę.

Įveskime atvirkštinės briaunos sąvoką. Tarkime, kad yra grafo G dalinis grafas, neturintis ciklų. Toks dalinis grafas vadinamas
dengiančiu medžiu. (Apie medžius bus kalbama 2.13 paragrafe). Dengiantis medis turi briauną ir neturi ciklų.

Apibrėžimas. Grafo G briauna yra atvirkštinė briauna (styga), jei ji nepriklauso dengiančio medžio H briaunų aibei.

Kadangi , tai atvirkštinių briaunų skaičius yra lygus , t.y. kiekviena atvirkštinė briauna drauge su dengiančio medžio briaunomis, priklausančiomis grandinei, jungiančiai viršūnę u su viršūne v, sudaro vieną nepriklausomą grafo G ciklą. Šį ciklą žymėsime .

Vadinasi, kiekvienas grafo G dengiantis medis apibrėš nepriklausomų ciklų aibę. Be to, neizomorfinių medžių nepriklausomų ciklų aibės bus skirtingos.

Pastaba. Taip apibrėžus nepriklausomus ciklus, visus kitus grafo ciklus galima išreikšti per nepriklausomų ciklų simetrinį skirtumą (sumą moduliu 2).

Apibrėžimas. Grafo briaunų aibė C vadinama pseudociklu, jei grafo visų viršūnių laipsniai yra lyginiai.

Tuščia aibė ir bet koks grafo ciklas yra pseudociklas.

Priminsime aibių simetrinio skirtumo operaciją:

.

Šią operaciją taikysime didesniam aibių skaičiui:

.

Nesunku įsitikinti, kad aibių simetrinį skirtumą, nepriklausomai nuo skliaustų, nurodančių veiksmų atlikimo tvarką, sudėjimo sudarys tik tie elementai, kurie priklauso nelyginiam skaičiui poaibių (žr. 2.11.2 pav.)2.11.2 pav. Aibių A, B ir C simetrinis skirtumas A Å B Å C

Lema. Bet kokio skaičiaus pseudociklų simetrinis skirtumas yra pseudociklas.

Įrodymas. Aišku, kad pakanka panagrinėti dviejų pseudociklų ir atvejį.

Simboliais , ir pažymėkime viršūnei v incidentiškų briaunų skaičių atitinkamai pseudocikluose C1, ir . Aišku, kad aibių ir elementų skaičius yra lyginis. Tadataip pat yra lyginis skaičius, ir C yra pseudociklas.

Teorema. Tarkime, – jungusis neorientuotasis grafas, o – jį dengiantis medis. Tada bet koks grafo G ciklas C vienareikšmiškai išreiškiamas per nepriklausomus ciklus Ce taip:

.

Įrodymas. Simetrinis skirtumas , remiantis lema, yra pseudociklas, susidedantis iš atvirkštinių briaunų (stygų) aibės C T ir kažkokių medžio T briaunų. Tai išplaukia iš to fakto, kad kiekviena atvirkštinė briauna priklauso tik vienam nepriklausomam ciklui .

Aibė , remiantis lema, taip pat nusakys pseudociklą, kurį gali sudaryti tik medžio T briaunos. (Pseudociklo C atvirkštinės briaunos e priklauso ir pseudociklui , todėl jos nepriklausys aibei ). Kadangi medis T neturi ciklų, tai šis pseudociklas yra tuščioji aibė. Vadinasi, . šios formulės vienareikšmiškumas išplaukia iš to, kad ciklas yra vienintelis nepriklausomas ciklas, turintis atvirkštinę briauną e.

Iš šio nagrinėjimo išplaukia, kad grafo nepriklausomus ciklus patogu ieškoti, naudojant paieškos gilyn metodą, aptartą 2.8.2 paragrafe.

Kaip paieškos gilyn metodu formaliai nustatyti atvirkštinę briauną (stygą)?

Tam tikslui reikia žinoti viršūnių aplankymo eilės numerius. Įveskime masyvą , čia yra i-osios viršūnės aplankymo eilės numeris.

Tarkime, kad paieškos gilyn metu iš viršūnės u atėjome į viršūnę v. Briauna bus atvirkštinė briauna (styga) ir iššauks nepriklausomą ciklą, jei bus teisinga sąlyga: “viršūnė v nenauja” and “į viršūnę u buvome atėję ne iš viršūnės v” and “ , t.y. viršūnė v buvo aplankyta anksčiau nei viršūnė u”.

2.8.1.2 paragrafe aprašytam paieškos gilyn algoritme ši sąlyga bus užrašoma taip: and and .

Žinant šią atvirkštinės briaunos sąlygą nesunku modifikuoti 2.8.1.2 paragrafe aprašytą paieškos gilyn metodą taip, kad jis apskaičiuotų nepriklausomus cilus. Žemiau ir pateikta ši nepriklausomų ciklų apskaičiavimo procedūra.

const c = 500;

type

mas = array [1..c] of integer;

procedure ciklai(v, n, m : integer; L, lst : mas);

{ Procedūra ciklai, naudodama paiešką gilyn iš viršūnės v, kai grafas nusakytas L ir lst masyvais, apskaičiuoja grafo nepriklausomus ciklus.

Formalūs parametrai:

v – pradinė paieškos viršūnė,

n – grafo viršūniu skaičius,

m – grafo briaunų (lanku) skaičius,

L, lst – grafą nusakantys tiesioginių nuorodų masyvai. }

var i, k, u : integer;

sk, j : integer;

t, p : boolean;

fst, prec : mas;

nr : mas;

begin

{ Inicializacija }

for i:=1 to n do begin

fst [i]:= lst [i] + 1;

prec [i] := 0;

end;

k := v;

if fst [k] <= lst [k+1] then {yra nenagrinetų briaunų, incidentiškų viršūnei k}

begin

t := false;

p := true;

prec [k] := k; { k – pradinė paieškos viršūnė }

{ Nagrinėti viršūnę k }

nr[k] := 1;

sk := 1; { Aplankytų viršūnių skaičius }

end

else {viršūnė k yra arba izoliuota viršūnė, arba neturi išeinančių lankų (orientuotojo grafo atveju); paieškos pabaiga }

t := true;

while not t do { paieška nebaigta}

begin

{ Pirmyn }

while p do

begin

u := L [fst [k]];

if prec [u] = 0 then {viršūnė u nauja}

begin

{ Nagrinėti viršūnę u }

sk := sk + 1;

nr [u] := sk;

prec [u] := k;{ į viršūnę u atėjome iš viršūnės k }

if fst [u] <= lst [u + 1] then { viršūnė u neišsemta }

k:=u

else {viršūnė u išsemta} p:=false;

end

else

begin

p := false; { viršūnė u nenauja}

if (prec [k] <> u) and (nr [k] > nr [u]) then

{ Briauna (k, u) yra atvirkštinė briauna. Spausdinti ciklą }

begin

writeln;

write (u : 3);

write (k : 3);

j := k;

while prec [j]
do

begin

j := prec [j];

write (j : 3);

end;

write(u : 3);

writeln;

end;

end;

end;

{ Atgal }

while not p and not t do

begin

{Imama nauja, dar nenagrinėta briauna, incidentiška viršūnei k}

fst [k] := fst [k] + 1;

if fst [k] <= lst[k + 1] then { tokia briauna egzistuoja }

p := true

else { viršūnė k išsemta }

if prec [k] = k then { pradinė paieškos viršūnė išsemta; paieškos pabaiga } t := true

else { grįžome i viršūnę, iš kurios buvome atėję į viršūnę k } k := prec [k];

end;

end;

end;

Aptarkime dar vieną nepriklausomų ciklų apskaičiavimo, naudojant rekursiją, procedūrą.

Šią procedūrą patogu organizuoti naudojant steką (žr. 2.8.1.3 paragrafą).

Tarkime, kad grafas nusakytas gretimumo struktūra, t.y. –aibė viršūnių, gretimų viršūnei v.

const c = 500;

type

mas = array [0..c] of integer;

matr = array [1..2, 1..c] of integer;

procedure ncikl (v : integer);

{ Grafo G jungiosios komponentės, turinčios savyje viršūnę v, nepriklausomų ciklų apskaičiavimas.

Kintamieji num, top, stec, nr, L, lst – globalieji }

var u, i, top1 : integer;

begin

top := top +1;

stek [top] := v;

num := num + 1;

nr [v] := num;

for i := lst [v] + 1 to lst [v + 1] do

begin

u: = L [i];

if nr [u] = 0 then ncikl (u)

else

if (nr [v] > nr [u]) and (u <> stek [top – 1]) then

{ Briauna (v,u) – atvirkštinė briauna. Įsiminti ciklą, einantį per viršūnes: u, stek [top], stek [top – 1], …, stek [c], čia stek [c] = u. }

begin

writeln;

write (u : 3);

top1 := top;

while stek [top1] <> u do

begin

write (stek[top1]:3);

top1:=top1-1;

end;

write (u : 3);

writeln;

end;

end;

top := top – 1; { Išsemta viršūnė v šalinama iš steko. }

end; { ncikl }

11) Chromatinis skaičius

-grafo chromatinis skaičius yra mažiausias skaičius spalvų, kurioms grafo viršūnes galima nudažyti taip, kad bet kokios dvi gretimos viršūnės būtų nudažytos skirtinga spalva. Šį skaičių žymėsime .

Pavyzdžiui, 2.11.3 pav. grafui chromatinis skaičius yra 3. Aišku, kad šio grafo negalima nudažyti su mažesniu spalvų skaičiumi, nes jis turi ilgio 3 ciklų.2.11.3 pav. Grafo chromatinis skaičius

Aišku, kad grafo chromatinis skaičius lygus n, o bet koks dvidalis grafas yra bichromatusis: aibės A viršūnės dažomos pirmąja spalva, o aibės B viršūnės – antrąja spalva.

Perfrazavus Kionigo teoremą, galime teigti, kad grafas yra bichromatusis tada ir tiktai tada, kai jis neturi nelyginio ilgio ciklų.

Chromatinio skaičiaus apskaičiavimo uždavinys yra diskrečiojo optimizavimo uždavinys. Formaliai jį galima užrašyti taip.

, čia p – spalvų skaičius,

esant apribojimams:

a) kiekviena viršūnė turi būti dažoma viena spalva,

b) bet kokios gretimos viršūnės turi būti nudažytos skirtinga spalva.

Šiems apribojimams užrašyti įvesime kintamuosius, .

Tada a) apribojmas bus užrašomas taip:

o b) apribojimas –

čia – incidencijų matricos (žr. 2.7 paragrafą) elementas.

Pavyzdžiui, 2.11.3 pav. grafui optimalus šio uždavinio sprendinys yra:

.

Kaip buvo minėta aukščiau, šis uždavinys yra NP pilnasis [GD82] ir neturi efektyvių sprendimo algoritmų. todėl jis sprendžiamas naudojant įvairias euristikas.

Dažniausiai naudojami grafų dažymo algoritmai remiasi tokiomis euristikomis:

· pirma spalva, po to viršūnė,

· pirma viršūnė, po to spalva.

Detaliau aptarkime šiuos euristinius algoritmus.

Euristinis algoritmas, paremtas principu “pirma spalva, o po to viršūnė”

Šios euristikos idėja yra labai paprasta. Pagal kokį nors požymį sudaroma grafo viršūnių seka. Po to imama nauja spalva ir šia spalva iš eilės dažomos, jeigu galima, sekos viršūnės. Taip elgiamės iki nudažome visas grafo viršūnes.

Tuo būdu šis algoritmas susideda iš dviejų etapų.

Grafo viršūnės išrikiuojamos jų laipsnių mažėjimo tvarka , čia ir , .

; {spalvų skaičius}

while “yra nenudažytų viršūnių” do

begin

;

Pradedant pirmąja nenudažyta sekos viršūne, p spalva nuosekliai viena po kitos dažomos, jei galima, nenudažytos sekos viršūnės.

end;

Pavyzdys. Panagrinėkime grafo, pavaizduoto 2.11.4 pav., dažymą, laikantis principo “pirma spalva, o po to viršūnė”.

2.11.4 pav. pavaizduotam grafui seka viršūnių, išrikiuotų jų laipsnių mažėjimo tvarka, yra: 2, 5, 1, 3, 6, 7, 4, 8.

2.11.4 pav. Grafo dažymas laikantis principo “pirma spalva, o po to viršūnė”

Pirmąja spalva dažome 2-ąją viršūnę, po to pirmąja spalva galime dažyti tik 1-ąją viršūnę. Gausime:

.

Imame antrąją spalvą ir dažome pirmąją nenudažytą sekos viršūnę –

5-ąją, po to antrąja spalva galime dažyti 6-ąją viršūnę. Gausime:

.

Trečiąja spalva pirmiausia dažome 3-ąją viršūnę, po to – 4-ąją viršūnę ir, galiausiai, 8-ąją viršūnę. Gausime:

.

Kadangi dar yra nenudažytų viršūnių, tai imame IV-ąją spalvą ir dažome 7-ąją viršūnę, t.y. gausime:

.

Gautas sprendinys nėra optimalus. Šį grafą galima nudažyti trimis spalvomis (žr. euristiką “pirma viršūnė, o po to spalva”).

Žemiau pateikta grafo dažymo, naudojant euristiką “pirma spalva, o po to viršūnė” procedūra.

const c = 500;

type

mas = array [1..c] of integer;

matr = array [1..2, 1..c] of integer;

procedure grfdaz1 (n, m : integer; b : matr; var p: integer; var
mas);

{ Procedūra grafdaz1 dažo grafo viršūnes, remdamasi euristika “pirma spalva, o po to viršūnė”.

Formalūs parametrai:

n – grafo viršūnių skaičius,

m – grafo briaunų (lankų) skaičius,

b – grafo briaunų matrica ,

p – spalvų skaičius,

d [1..n] – viršūnių spalvų masyvas;

jei d [i] = k, tai reiškia, kad i-oji viršūnė dažoma k-ąja spalva. }

var i, k, z, sv, u,j ,x : integer;

t : boolean;

L, lst, v, s : mas;

begin

BLlst(n,m,b,L,lst);

{ Pradinių reikšmių suteikimas darbo masyvams ir kintamiesiems }

for i := 1 to n do

begin

v [i] := i; { Masyve v iš eilės surašomi viršūnių numeriai }

s [i] := lst [i + 1] – lst [i]; {s [i] – i-tosios viršnės laipsnis }

d[i] := 0;

end;

{ Viršūnes masyve v išrikiuojame jų laipsnių mažėjimo tvarka }

for k := 1 to n – 1 do

for i: = 1 to n – k do

if s [i] < s [i + 1] then { Keičiame vietomis s [i] su s [i + 1] ir v [i] su v [i + 1] }

begin

z := s [i]; s [i] := s [i + 1]; s [i + 1] := z;

z := v [i]; v [i] := v [i + 1]; v [i + 1] := z;

end;

p := 0; { p – spalvų skaičius }

sv := 0; {sv – nudažytų viršūnių skaičius }

while sv < n do

begin

p := p + 1;

for i:=1 to n do

begin

u := v [i];

if d [u] = 0 then {Viršūnė u – nenudažyta.

Ar ją galima dažyti p-ąja spalva? }

begin

{ Ar viršūnių, gretimų viršūnei u, tarpe yra viršūnė,nudažyta p-ąja spalva? }

j := lst [u] + 1; t := false;

{ Jei t = false, tai viršūnę u galima dažyti p-ąja spalva }

while (j <= lst [u + 1]) and not t do

begin

x := l [j];

if d[x] = p then t:=true

else j:=j+1;

end;

if not t then

begin

d [u] := p;

sv := sv + 1;

end;

end;

end;

end;

end;

Euristinis algoritmas, paremtas principu “pirma viršūnė, o po to spalva”

Šios euristikos idėja yra ta, kad pirmiausia pagal kažkokį kriterijų išrenkama grafo viršūnė, o po to ji dažoma, jei galima, viena iš anksčiau panaudotų spalvų; jei išrinktos viršūnės negalima nudažyti nei viena iš anksčiau panaudotų spalvų, tai ji dažoma nauja spalva.

Viršūnės išrinkimo kriterijus

Apibrėžimas. Viršūnės h laipsnis – tai skaičius spalvų, kuriomis šios viršūnės negalima dažyti, t.y. šiai viršūnei negalimų spalvų skaičius.

Apibrėžimas. Viršūnės k laipsnis – tai šiai viršūnei gretimų nenudažytų viršūnių skaičius.

Pirmiausia pasirinksime viršūnę, kurios h laipsnis yra didžiausias.

Jei yra kelios viršūnės su tuo pačiu didžiausiu h laipsniu, tai iš jų išsirinksime viršūnę, kurios k laipsnis yra didžiausias.

Jei ir šiuo atveju bus daugiau nei viena viršūnė, imsime viršūnę, kurios numeris mažiausias.

Tuo būdu algoritmas aprašomas taip.

begin

;

while “yra nenudažytų viršūnių” do

begin

1) pagal aukščiau aprašytą kriterijų parenkama nenudažyta viršūnė v;

2) jei galima, viršūnę v dažome viena iš anksčiau panaudotų spalvų (paprastai, pirmąja iš galimų), t.y. viena iš aibės galimų spalvų;

3) jei viršūnės v negalima nudažyti nei viena iš anksčiau panaudotų spalvų, tai , ir viršūnę v dažome p-ąją spalva;

4) visoms nenudažytoms viršūnėms perskaičiuojame h ir k laipsnius;

end;

end;

Pavyzdys. Panagrinėkime, kaip bus dažomos 2.11.4 pav. grafas. Skaičiavimai parodyti 2.11.1 lentelėje, o 2.11.5 pav. pavaizduotas nudažytas grafas.

2.11.1 lentelė. Grafo dažymas

NR h – laipsnis k – laipsnis spalva *

1 0 1 2 3 2 1 III 5

2 0 4 I 1

3 0 1 2 3 2 1 I 4

4 0 1 2 1 II 6

5 0 1 4 3 II 2

6 0 1 2 3 2 1 I 7

7 0 1 2 3 2 1 III 3

8 0 1 2 1 0 II 8

čia * – viršūnės išrinkimo eilės numeris.

2.11.5 pav. Grafo dažymas laikantis principo “pirma viršūnė, o po to spalva”

Žemiau pateikta grafo dažymo, naudojant euristiką “pirma viršūnė, o po to spalva” procedūra.

const c = 500;

type

mas = array [1..c] of integer;

matr = array [1..2, 1..c] of integer;

procedure grfdaz2(n, m : integer; b : matr; var p : integer; var d : mas);

{ Procedūra grafdaz2 dažo grafo viršūnes, remdamasi euristika “pirma viršūnė, o po to spalva”.

Formalūs parametrai:

n – grafo viršūnių skaičius,

m – grafo briaunų (lankų) skaičius,

b – grafo briaunų matrica ,

p – spalvų skaičius,

d [1..n] – viršūnių spalvų masyvas;

jei d [i] = k, tai reiškia, kad i-oji viršūnė dažoma k-ąja spalva. }

var i, sv, max, maxka, v, u, j, x, sp : integer;

t,st : boolean;

L,lst,h,ka : mas;

begin

BLlst (n, m, b, L, lst);

{ Pradinių reikšmių suteikimas darbo masyvams ir kintamiesiems }

for i := 1 to n do

begin

ka [i] := lst [i + 1] – lst [i]; { ka [i] – i-tosios viršūnės laipsnis }

d[i] := 0;

h[i] := 0;

end;

p := 0; { p – spalvų skaičius }

sv := 0; {sv – nudažytų viršūnių skaičius }

while sv < n do

begin

{ Viršūnės išrinkimas }

max := –1;

for i := 1 to n do

if (d [i] = 0) and (max < h [i]) then max := h [i];

maxka := –1;

for i:=1 to n do

if (d [i] = 0) and (h[i] = max) and (maxka < ka [i]) then

begin

maxka := ka [i];

v:=i;

end;

{ Kuria spalva dažyti viršūnę v ? }

sv := sv + 1; { Dažome viršūnę v }

t := false; { t = false, jei viršūnei v spalva neparinkta }

i := 1; { Bandome viršūnę v dažyti spalva i }

while (i <= p) and (not t) do

begin

{ Tikriname, ar viršūnei v gretimų viršūnių tarpe yra viršūnė, kuri nudažyta i-ąja spalva }

j:=lst [v] + 1;

st := false; { Jei st = false,
tai reiškia, kad viršūnei v gretimų viršūnių tarpe spalvos i nėra }

while (j <= lst [v + 1]) and (not st) do

begin

u := L [j];

sp:=d[u];

if i = sp then st := true

else j:=j+1;

end;

if st then i := i + 1 { Bandome naują spalvą }

else t:=true; { Viršūnė v gali būti dažoma i-ąja spalva }

end;

if t then d [v] := i { Viršūnę v dažome i-ąja spalva }

else begin

p := p + 1; { Įvedame naują spalvą }

d [v] := p; { Viršūnę v dažome nauja spalva }

end;

{ h ir ka laipsnių perskaičiavimas nenudažytoms viršūnėms, gretimoms viršūnei v }

for i:=lst[v]+1 to lst[v+1] do

begin

u := L [i];

if d [u] = 0 { Viršūnė u , gretima viršūnei v, – nenudažyta } then

begin

ka[u] := ka [u] – 1;{ Viršūnei u gretimų nenudažytų viršūnių skaičius sumažėjo }

j := lst [u] + 1;

t := false; { Nei viena iš viršūnei u gretimų viršūnių nenudažyta d [v] spalva }

while (j <= lst [u + 1]) and ( not t) do

begin

x:=L[j];

if (x <> v) and (d [x] = d [v]) then t := true

else j := j + 1;

end;

if not t { Viršūnei u gretimų nudažytų viršūnių x tarpe nėra spalvos, lygios d[v] }

then h [u] := h [u] + 1;

end;

end;

end;

end;

Uždavinys, analogiškas grafo viršūnių dažymo uždaviniui, yra briaunų dažymo uždavinys.

Mažiausias skaičius spalvų, kuriomis grafo briaunas galima nudažyti taip, kad bet kurios dvi gretimos briaunos būtų nudažytos skirtinga spalva, vadinamas grafo chromatine klase.

Aišku, kad -grafo G chromatinė klasė yra lygi šiam grafui atitinkančio briauninio grafo (žr. 2.5 paragrafą) chromatiniam skaičiui.

Vadinasi, aukščiau aptarti chromatinio skaičiaus apskaičiavimo algoritmai tinka ir grafo chromatinei klasei apskaičiuoti. Tik šiuo atveju reikia nagrinėti grafui G atitinkanti briauninį grafą.

Reikia pabrėžti, kad eilė praktinių uždavinių yra formuluojami kaip grafo dažymo uždaviniai. Šiems uždaviniams būdinga tai, kad kai kurie objektai dėl vienokių ar kitokių priežasčių negali būti jungiami į grupes.

Pirmas pavyzdys. Tarkime, kad per galimai trumpiausią laiką reikia perskaityti keletą paskaitų. Kiekvienos paskaitos trukmė yra 1 valanda ir kai kurias paskaitas skaito tas pats lektorius. Sudarykime grafą G, kurio viršūnės vaizduoja paskaitas, o dvi viršūnės yra gretimos, jei jų negalima skaityti vienu metu, t.y. jei jas skaito tas pats lektorius. Aišku, kad bet koks teisingas grafo nudažymas apibrėžia paskaitų skaitymo tvarkaraštį, t.y. paskaitos, atitinkančios viršūnėms, kurios nudažytos ta pačia spalva, gali būti skaitomos vienu metu. Vadinasi, grfo chromatinis skaičius bus lygus mažiausiam valandų skaičiui, kuris reikalingas perskaityti paskaitų ciklą.

Antras pavyzdys. Duota darbų aibė ir mechanizmų aibė. Visų darbų trukmės yra lygios, o darbams atlikti naudojami aibės S mechanizmai. Aišku, kad tas pats mechanizmas vienu metu negali būti naudojamas keliems darbams atlikti. Mechanizmus reikia paskirstyti taip, kad bendras visų darbų atlikimo laikas būtų trumpiausias.

Sudarykime grafą G, kurio viršūnių aibė yra darbų aibė V. Viršūnės ir yra gretimos, jei šių darbų atlikimui reikia vieno ir to paties mechanizmo. Aišku, kad teisingai nudažius grafą, darbai, nudažyti ta pačia spalva, gali būti vykdomi tuo pačiu metu.

Chromatinio skaičiaus įverčiai [EM90]. Kadangi chromatinio skaičiaus apskaičiavimo uždavinys yra sunkus, tai svarbu žinoti chromatinio skaičiaus įverčius.

Simboliais ir atitinkamai pažymėkime grafo G mažiausią ir didžiausią viršūnių laipsnį, t.y. , o . Tada jungiajam grafui G galima nurodyti tokius chromatinio skaičiaus įverčius.

1. Grafo G chromatinis skaičius tenkina nelygybę .

2. Brukso teorema (1941). Jei G – jungusis ir nepilnasis grafas, kuriam , tai .

3. (Welsh, Powell).

4. (Elphick).

5. Teorema (A.P.Eršovas, G.I.Kožuchinas, 1962).čia simbolis [×] žymi skaičiaus sveikąją dalį, o {×} – skaičiaus trupmeninę dalį.

Šio paragrafo pabaigoje paminėsime G.Hadvigerio 1943 m. iškeltą hipotezę.

Hadvigerio hipotezė. Bet koks jungusis n-chromatinis grafas gali būti sutrauktas į grafą.

Ši hipotezė įrodyta, kai . Plačiau apie tai žr. lit. [EM90].

12) Nepriklausomumo skaičius

Apibrėžimas. -grafo viršūnių poaibis yra nepriklausomoji aibė (kitur literatūroje – vidiniai stabilioji aibė), jei aibę A sudarančios viršūnės tarpusavyje nėra gretimos.

Pavyzdžiui, 2.11.6 pav. grafui aibės , yra nepriklausomosios.2.11.6 pav. Nepriklausomumo skaičius

Akivaizdu, jei A yra nepriklausomoji aibė, tai bet koks šios aibės poaibis taip pat bus nepriklausomasis. Vadinasi, kiekvienam grafui galima sudaryti nepriklausomųjų aibių šeimą T.

Apibrėžimas. Nepriklausomoji aibė, kuri nėra nei vienos kitos nepriklausomosios aibės tikrinis poaibis, vadinama maksimaliąja nepriklausomąja aibe.

Apibrėžimas. Nepriklausomoji aibė, turinti didžiausią elementų skaičių, vadinama didžiausiąja nepriklausomąja aibe.

Apibrėžimas. Skaičius , t.y. didžiausios nepriklausomosios aibės elementų skaičius, vadinamas grafo nepriklausomumo skaičiumi.

Pavyzdžiui, 2.11.3.1 pav. grafui didžiausia nepriklausomoji aibė yra , o nepriklausomumo skaičius .

Nepriklausomumo skaičiaus radimo uždavinys yra diskrečiojo programavimo uždavinys, ir, kaip ir chromatinio skaičiaus ieškojimo
uždavinys, neturi efektyvių sprendimo algoritmų. Kitaip tariant, visų tikslų šio uždavinio sprendimo algoritmų veiksmų skaičius išreiškiamas eksponentiškai, grubiai kalbant, nuo grafo viršūnių skaičiaus.

Pavyzdžiui, grafo nepriklausomumo skaičiaus ieškojimo uždavinį galime formalizuoti taip.

Įveskime kintamuosius

, .

Tada reikia maksimizuoti tikslo funkciją:

,

esant apribojimamsčia – grafo incidencijų matricos elementas; šis apribojimas reiškia, kad nepriklausomosios aibės viršūnės tarpusavyje nėra gretimos.

.

Kadangi šis uždavinys neturi tikslių efektyvių sprendimo algoritmų, tai jis sprendžiamas įvairiais euristiniais algoritmais.

Viena iš populiariausių euristikų yra “godus” algoritmas, kai, formuojant nepriklausomąją aibę, kiekviename žingsnyje į šią aibę įtraukiame mažiausio laipsnio viršūnę. Šį euristinį algoritmą galima užrašyti taip.

begin

;

while “grafas turi viršūnių” do

begin

1) Rasti mažiausio laipsnio viršūnę v.

2) ;

3) Iš grafo pašalinti viršūnę v ir jai gretimas viršūnes, t.y. pašalinti viršūnių aibę.

end;

end;

Aišku, kad šis algoritmas visada apskaičiuos maksimaliąją, tačiau ne visada didžiausiąją nepriklausomąją aibę.

Žemiau pateikta šį algoritmą realizuojanti procedūra.

const c = 100;

type

mas = array [1..c] of integer;

procedure neprk (n, m : integer; L,l st : mas; var alfa : integer; var a : mas);

{ Procedūra neprk apskaičiuoja grafo, nusakyto masyvais L ir lst, nepriklausomumo skaičių alfa ir didžiausią nepriklausomą aibę a.

Formalūs parametrai:

n – grafo viršūnių skaičius,

m – grafo briaunų (lankų) skaičius,

L, lst – grafą nusakantys tiesioginių nuorodų masyvai,

alfa – grafo nepriklausomumo skaičius,

a – didžiausia nepriklausoma aibė. }

var s, i, k, u, v, min : integer;

p : boolean;

r, d : mas;

begin

alfa := 0;

{ Visos viršūnės – nenudažytos }

for i := 1 to n do d [i] := 1;

p := true; { Nepriklausoma aibė – neapskaičiuota }

while p do

begin

{ Viršūnių laipsnių apskaičiavimas }

for i := 1 to n do

if d [i] = 1 then

begin

s := 0;

for k := lst [i] + 1 to lst [i + 1] do

begin

u :=l [k];

s := s + d [u];

end;

r [i] := s;

end;

{ Rasti mažiausio laipsnio viršūnę }

min := n;

for i := 1 to n do

if (d [i] = 1) and (min > r[i]) then

begin

min := r [i];

k := i;

end;

if min = n then p := false

else

begin

{ Viršūnę k talpiname į aibę a }

alfa := alfa + 1;

a [alfa] := k;

{ Šaliname viršūnę k ir visas jai gretimas viršūnes }

d [k] := 0;

for i := lst [k] + 1 to lst [k + 1] do

begin

v := L [i];

d [v] := 0;

end;

end;

end;

end;

Eilė praktinių uždavinių yra formuluojami kaip grafo nepriklausomumo skaičiaus ieškojimo uždaviniai.

Pirmas pavyzdys (Gausas). Ar galima šachmatų lentoje sustatyti 8 valdoves taip, kad jos nekirstų viena kitos?

Pastaba. Analogišką uždavinį galima formuluoti vietoj valdovių imant kitas šachmatų figūras, t.y. kokį didžiausią skaičių tų pačių šachmatų figūrų galima šachmatų lentoje sustatyti taip, kad jos nekirstų viena kitos.

Sudarykime 64 viršūnių grafą. Šio grafo viršūnės vaizduoja šachmatų lentos langelius. Viršūnes u ir v jungsime briauna, jei iš šachmatų lentos langelio u galime patekti į langelį v valdovės ėjimu.

Tada, jei šio grafo nepriklausomumo skaičius yra lygus 8, tai šis uždavinys turi sprendinį, ir valdoves reikia statyti į didžiausios nepriklausomosios aibės viršūnes atitinkančius šachmatų lentos langelius.

1854 m. Berlyno šachmatų žurnale buvo paskelbta 40 šio uždavinio sprendinių. Gausas galvojo, kad yra 76 šio uždavino sprendiniai. Iš tikro jų yra 92 ir juos galima sutraukti į 12 diagramų:

(7, 2, 6, 3, 1, 4, 8, 5), (6, 1, 5, 2, 8, 3, 7, 4), (5, 8, 4, 1, 7, 2, 6, 3),

(3, 5, 8, 4, 1, 7, 2, 6), (4, 6, 1, 5, 2, 8, 3, 7), (5, 7, 2, 6, 3, 1, 4, 8),

(1, 6, 8, 3, 7, 4, 2, 5), (5, 7, 2, 6, 3, 1, 8, 4), (4, 8, 1, 5, 7, 2, 6, 3),

(5, 1, 4, 6, 8, 2, 7, 3), (4, 2, 7, 5, 1, 8, 6, 3), (3, 5, 2, 8, 1, 7, 4, 6).

Kaip šifruoti diagramas? Pavyzdžiui, pirmoji diagrama reiškia, kad, sunumeravus šachmatų lentos eilutes iš apačios į viršų skaičiais nuo 1 iki 8, valdoves statysime taip: 8-ojoje (viršutinėje) eilutėje valdovę statysime 7-ajame stulpelyje, 7-ojoje eilutėje valdovę statysime 2-ajame stulpelyje ir t.t. Kitos diagramos iššifruojamos taip pat.

Kiekviena diagrama, išskyrus paskutiniąją (3, 5, 2, 8, 1, 7, 4, 6), duoda 8 sprendinius, kurie gaunami pasukus šachmatų lentą 90°, 180° ir 270° bei paėmus kiekvieno varianto veidrodinį atspindį pagrindinės įstrižainės atžvilgiu.

Paskutinioji diagrama duoda tik 4 sprendinius, nes, pasukus lentą 180°, digrama transformuojasi pati į save.

Antras pavyzdys. Tai maksimaliosios klikos radimo uždavinys.

Apibrėžimas. -grafo viršūnių poaibis vadinams klika, jei bet kokios dvi šio poaibio viršūnės yra gretimos, t.y. jei šio poaibio indukuotas poaibis yra pilnasis.

Klika yra maksimalioji, jei ji nėra didesnės klikos pografis.

Didžiausioji klika – tai klika, kurios viršūnių skaičius tarp visų klikų yra didžiausias.

Didžiausiosios klikos viršūnių skaičius vadinamas grafo tankiu (arba klikiniu skaičiumi) ir žymimas , t.y. , čia – maksimaliųjų klikų šeima.

Aišku, kad grafo G didžiausioji klika sutampa su grafo
papildomojo grafo didžiausiąja nepriklausomąja aibe, t.y. .

Pastaba. Visų maksimaliųjų klikų radimo algoritmas išnagrinėtas lit. [RND80, 389 – 396 p.p.].

Reikia pabrėžti, kad grafo maksimaliųjų klikų skaičius gali augti eksponentiškai, priklausomai nuo viršūnių skaičiaus.

Pavyzdžiui, panagrinėkime Muno ir Mozerio gautą . Šis grafas turi 3n viršūnių, kurios išskaidytos triadomis:

{1, 2, 3}, {4, 5, 6},…,{3n-2, 3n-1, 3n};

grafe kiekvienos triados viršūnės tarpusavyje nėra gretimos, tačiau kiekvienos triados viršūnės yra gretimos visoms likusioms viršūnėms. 2.11.7 pav. pavaizduoti M1, M2 ir M3 grafai.

Naudojant indukciją, galime įrodyti, kad turi 3n maksimaliųjų klikų ir kiekviena klika turi n viršūnių.

Tai akivaizdu, kai ir . Tarkime, kad turi 3n-1 maksimaliųjų klikų, turinčių po n-1 viršūnę. Tada kiekviena iš trijų viršūnių, pridedamų formuojant grafą, duoda kliką su kiekviena grafo klika. Vadinasi, maksimaliųjų klikų skaičius yra , ir kiekviena klika turi n viršūnių.2.11.7 pav. Muno ir Mozerio grafai

Trečias pavyzdys (15-os mergaičių uždavinys). Pensione mokosi 15-ka megaičių, kurias pažymėkime taip:a, b, c, d, e, f, g, h, i, j, k, l, m, n, o. Mergaitės po tris kiekvieną dieną eina pasivaikščioti. Ar galima taip sudaryti savaitės pasivaikščiojimų tvarkaraštį, kad bet kurios dvi mergaitės į trejetą patektų ne daugiau kaip vieną kartą?

Keli, pasinaudodamas simetrija, rado šio uždavinio sprendinį, kuris pateiktas mergaičių pasivaikščiojimo tvarkaraščio lentelėje (žiūr 2.11.2 lentelę).

Norėdami išspręsti šį uždavinį, pirmiausia spręskime pagalbinį uždavinį: ar galima 15 mergaičių suskirstyti į 35 trejetus, kad bet kurios dvi mergaitės nepatektų į trejetą daugiau kaip vieną kartą?

2.11.2 lentelė. Mergaičių pasivaikščiojimo tvarkaraštis

Pirma-dienis Antra-dienis Trečia-dienis Ketvir-tadienis Penkta-dienis Šesta-dienis Sekma-dienis

afk abl alm ado agn ahj aci

bgl cno bcf bik bdj bmn bho

cmh dfl deh cjl cek cdg dkm

din gkh gio egm fmo efi eln

ejo ijm jkn fhn hil klo fgj

Šiam uždaviniui spręsti sudarykime 455 viršūnių grafą. Kiekviena viršūnė vaizduoja trejetą. Dvi viršūnės u ir v jungiamos briauna, jei u ir v trejetuose yra tos pačios dvi mergaitės. Raskime šio grafo nepriklausomumo skaičių ir šį skaičių atitinkančią nepriklausomąją aibę. Kadangi kiekviena mergaitė negali būti daugiau kaip 7-iuose trejetuose, tai didžiausioji nepriklausomoji aibė turės trejetus.

Turėdami šio pagalbinio uždavinio sprendinį, sudarykime grafą, kurio viršūnės vaizduoja sprendinio trejetus. Dvi viršūnės jungiamos briauna, jei ta pati mergaitė priklauso abiem trejetams. Jei šio grafo chromatinis skaičius lygus 7, tai trejetai, nudažyti ta pačia spalva, yra mergaičių pasivaikščiojimų vienos dienos tvarkaraštis. Reikia pastebėti, kad ne kiekvienas pagalbinio uždavinio sprendinys duoda 15-os mergaičių uždavinio sprendinį.

Nepriklausomumo skaičiaus įverčiai

1. (Wei).

2. (Myers, Liu), čia – vidutinis viršūnės laipsnis.

3. (Jeršovas, Kožuchinas).

4. , čia , ir atitinkamai grafo gretimumo matricos teigiamų, neigiamų ir nulinių tikrinių reikšmių skaičius (D.Cvetkovičius, 1973).

5. (Brooks).

Primename, kad šiose formulėse n – viršūnių skaičius, m – briaunų skaičius, o – v-osios viršūnės laipsnis.

Dar kartą apie grafo dažymą. Chromatinis skaičius ir nepriklausomumo skaičius surišti nelygybe: .

Aišku, kad grafo viršūnes galima išskaidyti į nepriklausomųjų poaibių: poaibį sudaro viršūnės, nudažytos ta pačia spalva. Kadangi kiekvieno šio poaibio elementų skaičius neviršija , tai . Kyla klausimas, ar tarp šių skaičių nėra glaudesnio ryšio? Gal chromatinį skaičių galima rasti tokiu būdu. Pirmiausia apskaičiuojame grafo G didžiausiąją nepriklausomąją aibę A1 ir šios aibės viršūnes nudažome pirmąja spalva. Po to randame pografio, kurį indukuoja aibė , didžiausiąją nepriklausomąją aibę A2 ir šias viršūnes dažome antrąja spalva ir t.t., kol nudažome visas grafo viršūnes.

Reikia pabrėžti, kad šis metodas gali apskaičiuoti neoptimalų chromatinį skaičių (žr. 2.11.8 pav.). Šiam grafui . Tamsiais taškais pažymėtos didžiausios nepriklausomosios aibės viršūnės. Jei visas jas nudažysime viena spalva, tai likusio grafo viršūnėms nudažyti dar teks panaudoti keturias naujas spalvas. Vadinasi, aukščiau pateiktas metodas duos neoptimalų chromatinį skaičių.2.11.8 pav. Ryšys tarp a(G) ir g(G)

13) Dominavimo skaičius

Apibrėžimas. -grafo viršūnių poaibis A yra dominuojančioji aibė (kitur literatūroje išoriškai stabilioji aibė), jei kiekviena grafo viršūnė, nepriklausanti poaibiui A, yra gretima bent vienai poaibio A viršūnei, t.y. jei visos likusios grafo viršūnės, nutolusios nuo bent vienos dominuojančios aibės viršūnės atstumu, lygiu vienetui.

Pavyzdžiui, 2.11.9 pav. grafui aibės , , .2.11.9 pav. Dominavimo skaičius

Akivaizdu, kad jei A yra dominuojančioji aibė ir , tai B taip pat dominuojančioji aibė.

Apibrėžimas. Dominuojančioji aibė, kurios bet kuris tikrinis poaibis nėra dominuojančioji aibė, vadinama minimaliąja dominuojančiąja aibe.

Apibrėžimas. Dominuojančioji aibė,
mažiausią elementų skaičių, vadinama mažiausiąja dominuojančiąja aibe.

Apibrėžimas. Skaičius , čia T – grafo G dominuojančiųjų aibių šeima., t.y. mažiausios dominuojančiosios aibės elementų skaičius, vadinamas grafo dominavimo skaičiumi.

2.11.9 pav. grafo dominavimo skaičius yra 2, o mažiausia dominuojančioji aibė – .

Mažiausios dominuojančiosios aibės, o tuo pačiu ir dominavimo skaičiaus radimo uždavinys yra tipiškas padengimo uždavinys.

Padengimo uždavinį galima formuluoti taip. Duota aibė ir aibės S poaibių šeima . Rasti tokį mažiausią poaibių Ai rinkinį (padengimą), kad kiekvienas aibės S elementas sk priklausytų (būtų padengtas) bent vienam rinkinio poaibiui Ai.

Formalai šį uždavinį galime užrašyti taip.

Įveskime kintamuosius

Poaibių Ai šeimą vaizduokime formato matrica , , , čia

t.y. j-asis matricos A stulpelis vaizduoja poaibį Aj. Tada padengimo uždavinys ekvivalentiškas tokiam optimizavimo uždaviniui:

esant apribojimams:

· “kiekvienas elementas priklauso bent vienam į padengimą įeinančiam poaibiui”,

· ,

· .

Dominavimo skaičiaus ieškojimo atveju aibė S yra grafo viršūnių aibė V. Kiekviena grafo viršūnė apibrėžia viršūnių poaibį , . Reikia rasti tokį mažiausią poaibių Av skaičių (viršūnių v aibę), kad kiekviena grafo viršūnė priklausytų bent vienam rinkinio poaibiui Av.

Kadangi visi tikslūs padengimo uždavinio sprendimo metodai yra neefektyvūs, tai paprastai šis uždavinys sprendžiamas euristiniais algoritmais. Viena iš populiariausių euristikų yra “godaus” algoritmo euristika: “kol yra nepadengtų viršūnių, kiekviename žingsnyje į dominuojančiąją aibę (padengimą) įtrauksime tokią aibę Av, kuriai priklauso didžiausias skaičius nepadengtų viršūnių, t.y. tokią viršūnę, kurios laipsnis yra didžiausias”.

Formalai šį algoritmą galime užrašyti taip.

begin

; {A – mažiausioji dominuojančioji aibė}

while “grafas turi viršūnių” do

begin

1. Rasti didžiausio laipsnio viršūnę v.

2.

3. Iš grafo pašalinti viršūnių aibę.

end;

end;

Nesunku pastebėti, kad šis algoritmas yra analogiškas didžiausios nepriklausomosios aibės apskaičiavimo algoritmui. Aišku, kad šis algoritmas visada apskaičiuos minimaliąją dominuojančiąją aibę, tačiau ji ne visada bus mažiausioji. Pavyzdžiui, 2.11.10 pav. grafui mažiausioji dominuojančioji aibė yra , o pagal algoritmą apskaičiuota minimalioji dominuojančioji aibė yra .2.11.10 pav. “Godus” algoritmas neapskaičiuoja minimaliosios dominuojančiosios aibės

Aptarsime keletą pavyzdžių, kuriuos sprendžiant reikia apskaičiuoti mažiausiąją dominuojančiąją aibę.

Pirmas pavyzdys. Uždavinys apie sargybinius. Tarkime, kad grafas G (pvz. žr. 2.11.9 pav.) yra N-miesto kalėjimo planas. Grafo viršūnės vaizduoja kameras, kuriose įkalinti pavojingi nusikaltėliai. Viršūnės u ir v jungiamos briauna, jei jas jungia tiesus koridorius. Reikia rasti mažiausią skaičių sargybinių, kad jie galėtų sekti visų kamerų duris.

Antras pavyzdys. Penkių valdovių uždavinys. Kiek mažiausiai šachmatų lentoje reiki