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.

Šiuo metu Jūs matote 30% šio straipsnio.
Matomi 2994 žodžiai iš 9895 žodžių.
Peržiūrėkite iki 100 straipsnių per 24 val. Pasirinkite apmokėjimo būdą:
El. bankininkyste - 1,45 Eur.
Įveskite savo el. paštą (juo išsiųsime atrakinimo kodą) ir spauskite Tęsti.
SMS žinute - 2,90 Eur.
Siųskite sms numeriu 1337 su tekstu INFO MEDIA ir įveskite gautą atrakinimo kodą.
Turite atrakinimo kodą?
Po mokėjimo iškart gausite atrakinimo kodą, kurį įveskite į laukelį žemiau:
Kodas suteikia galimybę atrakinti iki 100 straispnių svetainėje ir galioja 24 val.