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ė,

Šiuo metu Jūs matote 50% šio straipsnio.
Matomi 4948 žodžiai iš 9895 žodžių.
Siųskite sms numeriu 1337 su tekstu INFO MEDIA (kaina 1,45 €) ir įveskite gautą kodą į laukelį žemiau:
Kodas suteikia galimybę atrakinti iki 100 straispnių svetainėje ir galioja 24 val.