IEVADS
Šis darbs dot pārskatu par dažām grafu aprakstīšanas,
parmeklēšanas un kārtošanas metodēm. Pārmeklēt grafu nozīmē sistemātiski
izsekot grafa lokus, tātad iziet grafa virsotnes. Ir vairāki grafu
pārmeklēšanas algoritmi. Daudzi no tiem balstās uz to, ka no sākuma tiek iegūta
informāciju par grafa struktūru, un tikai tad notiek grafa pārmeklēšana. Citi
algoritmi strādā vienkārši izvēršot virsotni pēc virsotnes. Paši pa sevīm grafu
parmeklēšanas algoritmi dot iespeju arī atklāt grafa struktūru un tie aizņem
svarīgu daļu grafu algoritmos.
Darba pirmā nodaļā būs apskatīti divi vissizplatītākie
grafa aprakstīšanas veidi: blakus virsotņu saraksts un blakus
virsotņu matrica. Otrā nodaļā aprakstīts vienkārš grafa pārmeklēšanas
algoritms - pārmeklēšana plašumā, un arī tiek parādīts kā tiek
konstruēts pārmeklēšanas plašumā koks. Trešā nodaļā apskatīsim dziļumā
pārmeklēšanas algoritmu, un piemēru kurā var redzēt kādā kartībā
dziļumā pārmeklēšanas algoritms apskata virsotnes. Ceturtā nodaļa būs veltīta topoloģiskai
grafa kārtošanai. Un beidzot piektajā nodaļā ir aprakstīts tāds
jēdziens kā stingri savienotās komponentes un arī tiek apskatīta
procedūra kura sameklē tās virzītā grafā.
1. GRAFU ATTĒLOŠANA
Ir divi standarta veidi kā aprakstīt grafu G = (V, E) (V
– virsotņu kopa, E – loku kopa): proti ar blakus virsotņu saraksta
vai ar blakus virsotņu matricas palīdzību. Blakus virsotņu
sarakstu lieto parasti biežāk, tapēc, ka tas nodrošina iespeju kompakti
aprakstīt izretinātu grafu – tas ir tāds grafs kur |E| ir daudz
mazāks par |V²|. Blakus virsotņu matricas izmantošana grafa aprakstīšanai var
būt piemērota tad, kad grafs ir blīvs, proti |E| skaits ir tuvs
|V²| skaitam, vai arī tad, kad ir vajadzība ātri noskaidrot vai divas virsotnes
ir savā strarpā savienotas ar loku.

1. att. Divi veidi kā aprakstīt
nevirzītu grafu. (a) Grafs G
sastāv no piecām virsotnēm un septiņiem lokiem.
(b) Grafs G aprakstīts ar blakus virsotņu saraksta
palīdzību. (c) Grafs G ir aprakstīts ar blakus virsotņu
matricu.

2. att. Divi veidi kā aprakstīt
virzītu grafu. (a) Grafs G sastāv
no sešām virsotnēm un astoņiem lokiem. (b) Grafs G aprakstīts ar blakus virsotņu
saraksta palīdzību. (c) Grafs G ir aprakstīts ar blakus virsotņu
matricu.
Saistīto virsotņu saraksts kas
apraksta kādu grafu G = (V,E) sastāv no kopas Adj, kas satur |V| virsotņu
sarakstu. Sarakstā ir tik rindas cik ir virsotņu grafā. Priekš katras virsotnes
u ∈ V saistīto virsotņu saraksts Adj[u] satur visas virsotnes ar kurām
virsotne ir saistīta ar lokiem. Virsotnes blakus virsotņu sarakstā parasti
izvieto patvaļīgā kartībā. Attēlā 1(b) ir redzams blakus virsotņu saraksts
nevirzītam grafam no attēla 1(a). Respektīvi attēlā 2(b) arī redzams blakus
virsotņu saraksts virzītam grafam no attēla 2(a).
Ja grafs G ir virzīts grafs, tad loku
garumu summa blakus virsotņu sarakstā ir vienāda ar |E|, bet ja G ir nevirzīts
grafs tad loku garumu summa blakus virsotņu sarakstā ir vienāda ar 2|E|, tas ir
tapēc kā aprakstot nevirzītu grafu viens un tas pats loks sarakstā parādās
divas reizes.
Neatkarīgi no tā vai grafs ir virzīts
vai nav, blakus virsotņu sarakstam piemīt tāda īpašība: nepieciešamā atmiņa lai
aprakstīt grafu ir O(max(V,E)) = O(V+E)
Blakus virsotņu saraksts var būt
viegli pārveidots lai aprakstīt svērtu grafu, tas ir tāds grafs
kur katrai virsotnei atbilst kaut kāds svars, parasti aprakstāms ar svara
funkciju w : E à R. Piemēram, pieņemsim ka
grafs G ir svētrs grafs ar svara funkciju w. Loka (u,v) ∈ E
svars w(u,v) var viegli glabāties kopā ar virsotni v
blakus virsotņu sarakstā. Blakus virsotņu saraksts ir diezgan universāls, tapēc
tas var būt modificēts lai aprakstītu daudzus citus grafa veidus.
Blakus virsotņu saraksta potenciālais
trūkums ir tas, ka te nav iespejas ātri noteikt vai dotais loks (u,v) eksistē
grafā. Tur pretī šo trūkumu var novērst lietojot grafa aprakstīšanai blakus
virsotņu matricu, bet maksa par to ir vairāk patērētās atmiņas aprakstot to
pašu grafu.
Lai aprakstīt grafu G = (V,E) ar
blakus virsotņu matricu mēs pieņemam, ka virsotnes ir numurētas 1,2,...,|V|
brīvi izvēlētā kārtībā. Tad blakus virsotņu matrica būs |V| x |V| liela. A = (aij) kur
ì 1 ja (i,j) ∈ E,
aij = í
î 0 pretējā gadijumā
Attēlā 1.(c) un 2.(c) ir redzamas blakus virsotņu matricas attiecīgi priekš
nevirzīta un virzīta grafa. Grafa blakus virsotņu matrica prasa atmiņas apjomu
V² neatkarīgi no virsotņu skaita.
Ievērojot simetriju gar
blakus virsotņu matricas A = (aij) galveno diagonāli
(att. 1.(c)) mēs varam konstruēt tai
apgrieztu matricu AT = (aTij) noteiktu ar aTij=aij.
Tā kā nevirzītā grafā (u,v) un (v,u) apraksta blakus virsotņu matricas A vienu
un to pašu loku, no tā seko ka blakus virsotņu matrica nevirzītam grafam būs
vienāda ar apgriesto A = AT. Dažās programmās izmanto šo īpašību un
aprakstot nevirzītu grafu saglabā tikai galveno diagonāli un elementus, kas ir
virs tās. Tas dot iespeju ieekonomēt gandrīz pusi no atmiņas nepieciešamās
aprastot grafu ar blakus virsotņu matricu.
Kā blakus virsotņu
saraksts, tā arī blakus virsotņu matrica var būt lietota aprakstot svērtu
grafu. Piemēram ja grafs G = (V, E) ir svērts grafs ar loku svara funkciju w,
tad loka (u,v) ∈ E svars w(u,v) tiek vinkārši saglabāts rindā u un kolonnā v blakus virsotņu
matricā. Ja tāds loks neeksistē svara vietā tiek saglabāta NIL vērtība, vai arī
dažreiz izdevīgi izmantot tādas vērtības kā 0 vai ∞.
Kaut gan grafa
aprakstīšana ar blakus virsotņu saraksta palīdzību ir tik pat efektīva kā
aprakstīšana ar blakus virsotņu matricu, blakus virsotņu matricas vienkāršība
var būt vairāk vēlama aprakstot īpaši mazus grafus. Turklāt ja grafs ir
nesvērts tai ir tāda papildus priekšrocība, saglabājot matricas ierakstu var
izmantot nevis mašīnas vārdu( divi baiti), bet tikai vienu bitu priekš šī
ieraksta glabāšanas. Tas protams ir ļoti izdevīgi atmiņas ziņā.
2. Pārmeklēšana plašumā
Pārmeklēšana plašumā ir viens no vienkāršākiem grafu
pārmeklēšanas algoritmiem un ir par prototipu priekš daudziem citiem svarīgiem
grafu algoritmiem. Deikstras algoritms īsākā ceļa meklēšanai un Primas
algoritms minimālā karkasa atrašanai izmanto līdzīgu pārmeklēšanai plašumā
principu.
Apskatīsim
sīkāk algoritma darbības principu. Dots grafas G = (V,E) ar sākuma virsotni s.
Pārmeklēšanas plašumā algoritms no sākuma sistēmātiski izpēta visas grafa
virsotnes kuras var tieši sasniegt no virsotnes s, tālāk izrēķina
attālumu no s līdz visām tādām tieši sasniedzāmām virsotnēm. Un arī izveido
“pārmeklēšanas plašumā koku”, kas sastāv no saknes virsotnes s un visām
tām virsotnēm kuras var sasniegt no tās. Priekš jebkuras virsotnes v kuru
var tieši sasniegt no virsotnes s, ceļš pārmeklēšanas plašumā kokā no s līdz v
atbilst “īsākam ceļam” no virsotnes s uz v grafā G. Algoritms strādā ar abiem
grafu veidiem gan ar virzītiem, gan nevirzītiem.
Pārmeklēšanas
plašumā algoritms ir dabujis tādu nosaukumu pateicoties tā darbības principam,
tas no sākuma pārmeklē visas virstones kuras var sasniegt attālumā k no
apskatāmās virsotnes ejot it kā plašumā. Un pāriet pie virsotņu apskata
attālumā k + 1 tikai tad, kad būs apskatītas visas virstnes attālumā k
no virsotnes s.
Lai
saglabāt pārmeklēšanas processa gaitu, pārmeklēšanas plašumā algoritms izmanto
trīs krāsas lai apzīmētu katru virsotni, proti balto, pelēko un melno.
Algoritmam uzsākot darbību visas virsotnes ir baltas, bet vēlāk tās var kļūt pelēkas
un pēc tam melnas. Virsotne kura atklāta pirmo reizi, tas ir sastapta
meklēšanas gaitā, kļūst par ne batlu. Tātad pelēkas un melnas vitsotnes ir
apskatītās virsotnes, bet algoritms atšķir tās savā starpā lai nodrošinātu
pārmeklēšanai plašumā līdzīgu pārmeklēšanu. Ja loks (u,v) ∈
E un virsotne u ir melna tad virsotne v ir arī vai nu pelēka vai melna,
tātad visas virsotnes kas ir saistītas ar melno virsotni jau bijušas atklātas.
Pelēkai virsotnei blakus var atrasties baltas, vēl neatklātas virsotnes, kuras
it kā representē robežu starp atklātām un neatklātām virstonēm.
Pārmeklēšanas
plašumā algoritms savā darbības laikā konstruē pārmeklēšanas plašumā koku. No
sākuma tas koks satur tikai saknes virsotni s. Kad balta virsotne v
tiek atklāta, blakus virsotņu saraksta skanēšanas gaitā, jau atklātai virsotnei
u, virsotne v un loks (u,v) tiek pievienoti kokam. Mēs sakam ka u ir
virsotnes v priekštecis pārmeklēšanas plašumā kokā. No tā laika kad
virsotne ir atklāta vienreiz tāi ir vismas viens priekštecis. Priekšteča un
pēcteča attiecības parmeklēšanas plašumā algoritmā tiek definētas attiecībā
pret saknes virsotni s Piemēram, ja ceļā no virsotnes s uz virsotni v
atrodas virsotne u, tad virsotne u ir virsotnes v
priekštecis, un virsotne u ir virsotnes v pēctecis.
2.1. Procedūra BFS
Pārmeklēšanas
plašumā zemāk parādītā procedūra BFS pieņem ka ieejas dati par grafu G = (V,E)
ir doti kā blakus virsotņu saraksts. Tā uztur arī papildus datu struktūras
informācijas glabāšanai par katru grafa virsotni. Katras virsotnes u ∈
V krāsa tiek glabāta mainīgajā color[u], Virsotnes u prieķštecis tiek
glabāts mainīgajā p[u].
Ja gadījumā virsotnei u nav priekšteča, mainīgam p[u]
tiek piešķirta NIL vērtība. Algoritma izrēķinātais attālums no sākuma virsotnes
līdz virsotnei u tiek glabāts mainīgajā d[u]. Algoritms arī lieto FIFO (
pirmais iekšā pirmais ārā ) rindas struktūru lai pārzināt un vadīt pelēko
virsotņu kopu.
BFS ( G,s)
1
priekš katras virsotnes u ∈ V [ G ] – { s }
2
darīt
color[ u ] ß BALTA
3
d
[ u ] ß ∞
4
p [ u ] ß NIL
5
color [ s ] ß PELĒKA
6
d [ s ] ß 0
7
p [ s ] ß NIL
8
Q ß { s }
9
kamēr
Q ¹ 0
10
darīt
u ß head [ Q ]
11
priekš
katras v ∈
Adj [ u ]
12
darīt
ja color [ v ] = BALTA
13
tad
color [ v ] ß PELĒKA
14
d
[ v ] ß d [ u ] + 1
15
p [ u ] ß u
16
Enqueue
( Q , v )
17
Dequeue(
Q )
18
color
[ u ] ß MELNA
Attēlā 3. tiek parādīta procedūras BFS gaita grafā.
Procedūra BFS strādā
sekojoši. Rindā 1 – 4 katra virsotne tiek padarīta par baltu, atāluma no saknes
virsotnes glabāšanas mainīgam d[u] tiek piešķirta vērtība ∞ un
priekštēča glabāšanas mainīgam p[u] tiek piešķirta vērtību NIL.
Rindā 5 virsotni s padara par pelēku, lai tad kad procedūra sāks darbību s jau
būtu atklāta. Rinda 6 inicializē mainīgo d[s] piešķirot tam 0, un rinda 7
piešķir saknes virsotnes prieķšteča glabāšanas mainīgam NIL. Rindā 8 tiek inicializēta Q, rinda kura tālāk
saturēs tikai pelēkās virsotnes.
Galvenā procedūras
cilpa atrodas no 9 līdz 18 rindai. Procedūra atrodas galvenajā cilpā tik ilgi
kamēr ir atlikušas pelēkas virstones. Rindā 10 tiek noteikta pelēkā virsotne u
kas atrodas rindas Q sākumā. Cikls no 11 līdz 16 rindai apskata katru virsotni v
blakus virsotņu sarakstā kas ir saistīta ar virsotni u. Ja virsotne v
ir balta, tad tā vēl nav bijusi atklāta un algoritms atklā to izpildot rindas 13
– 16, pirmkārt padarot to par pelēku, otrkārt piešķir tās attāluma glabāšanas
mainīgam d[v] vērtību d[u] + 1, treškārt ierakstot virsotni u kā šīs
virstones priekšteci, un beidzot virsotne tiek ievietota rindas Q galā. Kad
visas virostnes u saistītās virsotnes blakus virsotņu sarakstā tiek
apskatītas, tad virsotne tiek padarīta par melnu un tiek izmesta no rindas Q,
tas notiek 17 un 18 rindā.

3. att. Procedūras BFS darbības gaita
apstrādājot nevirzītu grafu. Loku koks tiek izcelts ar melnu treknu līniju tādā
kārtībā kādā to veido BFS procedūra. Katrai virsotnei u ir redzama
vērtība d[u]. Ri,nda Q ir parādīta katras iterācijas sākumā. Virsotņu
attālumi ir redzami apakšā zem rindas Q virsotnēm.
2.2. Procedūras BFS darbības analīze.
Pirms pierādīt
pārmeklēšanas plašumā algoritma dažādas īpašības mēs izdarīsim vienu vieglāku
darbu, proti izanalizēsim grafa G = (V,E) apstrādes laiku. Pēc inicializācijas,
ne visas virsotnes ir vieinmēr baltas un tādejādi pārbaude 12 rindā garantē ka
katra virsotne būs pievienota rindai lielākais tikai vienu reizi, un izslēgta
no rindas arī tikai vienu reizi. Rindai pievienošanas un no rindas izslēgšanas
operācijas aizņem O(1) laika, tātad kopumā laiks, kas būs veltīts operācijām ar
rindu aizņems O(V). Tapēc ka blakus virsotņu saraksts tiek skanēts tikai tad,
kad virsotne tiek izslēgta no rindas, blakus virsotņu saraksts priekš katras
virsotnes tiks skanēts ne vairāk kā vienu reizi. Ja visu saraksta ierakstu
garumu summa ir Q(E), tad kopumā maksimālais laiks kas
nepieciešams blakus virsotņu saraksta skanēšanai ir O(E). Klāt vēl ir
japieskaita laiks kas nepieciešams inicializācijai O(V), un tātād kopējais
grafa apstrādes laiks būs O( V + E ). Tātad procedūras darbības laiks ir
lineāri atkarīgs no blakus virsotņu saraksta izmēra, kas apraksta kādu grafu G.
2.3. Īsākais ceļš.
Tātad nodaļas
sākumā mēs apgalvojām ka pārmeklēšanas plašumā algoritms atrod attālumu līdz
katrai sasniedzamāi virsotnei grafā G = (V,E) no saknes virsotnes s ∈ V. Definēsim īsāko ceļu d(s,v) no virsotnes s uz v,
kā minimālo virsotņu skaitu kuru mums jaiziet ejot no virsotnes s uz
virsotni v, un pretēji ∞ (ar bezgalības zīmi) ja ceļš no virsotnes s
uz v neeksistē. Ceļa garumu no virsotnes s uz virsotni v
sauksim par īsāko ceļu no s uz v. Pirms parādīt
kādā veidā pārmeklēšanas plašumā algoritms izrēķina īsākā ceļa garumu,
izpētīsim svarīgu īsākā ceļa attāluma īpašību.
2.4. Teorēma 1
Lai G = (V,E)
ir virzīts vai nevirzīts grafs un lai s ∈ V ir nejauši izvēlēta virsotne. Tad priekš
jebkura loka (u,v) ∈ E, ir spēkā izteiksme
d(s,v) £ d(s,u) + 1
Pierādījums Ja u ir sasniedzama no s tad tā
ir v. Šajā gadijumā īsākais ceļš no s uz v nevar būt
garāks par īsāko ceļu no s uz u, seko no loka (u,v) un
nevienādība ir spēkā. Ja u nav sasniedzama no s tad d(s,v) = ∞ un nevienādība ir arī spēkā.
Mēs gribam
parādīt kā procedūra BFS pareizi izskaitļo d[u] = d(s,v) priekš katras virsotnes v ∈
V. No sākumā parādīsim ka d[u] saistīts ar d(s,v).
2.5.
Teorēma 2
Lai G = (V,E) ir virzīts vai nevirzīts
grafs un pieņemam ka BFS ir palaista uz grafa G no dotās sākuma virsotnes s ∈ V. Tad tās darbības beigās priekš katras virsotnes v ∈ V izrēķinātā vērtība d[v] atbildīs nevienādībai
d [ v
] ³ d(s,v)
Pierādījums Mēs lietojam indukciju ievietojot virsotni rindā Q. Mūsu indukcijas
hipotēze ir sekojoša, ka d [ v ] ³ d(s,v) priekš visām v ∈ V.
Indukcijas pamats ir situācija tūlīt pēc s tiek ievietota rindā Q procedūrā BFS
8 rindā. Induktīvā hipotēze ir spēkā te tāpēc ka d[s] = 0 = d(s,s) un d[v] = ∞ ³ d(s,v) priekš visām v ∈ V - { s }.
Priekš induktīva soļa aplūkosim baltu
virsotni v kas ir atklāta
pārmeklēšanas gaitā no virstones u.
Induktīvā hipotēze pieņem ka d[u] ³ d(s,u). No piešķiršanas
procedūras 14 rindā un no teorēmas 1.1 iegūstam
d [ v ] = d
[ u ] + 1
³
d(s,u) + 1
³
d(s,u)
Virsotne v pēc tam tiek
pievienota rindai Q un tā netiek pievienota velāk vēlreiz, jo tā ir pelēka, un
procedūras tad bloks no 13 līdz 16
rindai tiek izpildīts tikai priekš baltām virstonēm. Tādejādi vērtība d[v]
nekad nemainās atkal un induktīvā hipotēze var tikt apgalvota.
Lai
pierādīt ka d[v] = d(s,u) mums
no sākuma jaapskatās precīzāk kādā veidā rinda Q mainās procedūras izpildes
gaitā, ir vismaz divas d vērtības
rindā.
2.6. Teorēma 3
Pieņemsim ka procedūras BFS grafa G =
(V,E) apstrādes gaitā, rinda Q satur virsotnes ( v1, v2,
…,vr), kur virsotne v1 ir rindas sākumā un
virsotne ir vr rindas
galā. Tad d[ vr ] £ d[ v1 ] + 1 un d[ vi ] £ d[ vi+1 ]
kur I = 1,2,…,r – 1.
Pierādījums Sākumā kad rinda satur tikai s, teorēma noteikti izpildās. Priekš induktīva soļa mums ir jāpierāda teorēmas izpildīšanos arī pēc abām darbībām, gan virsotnes pievienošanas rindai, gan tās izslēgšanas no rindas. Ja rindas sākuma virsotne v1 tiek izslēgta, tad par jaunu rindas sākuma virsotni kļūst virsotne v2. Bet tad mums ir d[ vr ] £ d[ v1 ] + 1 £ d[ v2 ] + 1 un pārējās nevienādības paliek neietekmētas. Tatad teorēma izpildās arī ja rindas sākuma virsotne ir v2. Virsotnes izslēgšanas no rindas darbība prasa sīkāku koda izpēti. Procedūras BFS 16 rindā, kad virsotne v tiek pievienōta rindai tādejādi kļūstot par vr+1, rindas sākuma virsotne v1 ir faktiski virsotne u kuras blakus virsotņu saraksts jau tika skanēts. Tādejādi d[vr+1] = d[v] = d[u] + 1 = d[v1] + 1. Mēs arī iegūstam d[vr] £ d[v1] + 1 = d[u] + 1 = d[v] = d[vr+1] un pārējās nevienādības tiek neieteikmētas. Tātad teorēma izpildās arī kad virsotne tiek pievienota.
Tagad
mēs varam pierādīt ka pārmeklēšana plašumā atrod patiešām īsāko ceļu.
2.7. Teorēma 4
Lai G = (V,E) ir
virzīts vai nevirzīts grafs, un pieņemsim ka BFS procedūra apstrādā to sākot no
sākuma virsotnes s ∈ V. Tad procedūras izpildes laikā tā atklās katru
virsotni v ∈ V, kas ir sasniedzama no saknes virsotnes s un
līdz tās beigām d[v] = d(s,v)
priekš visām v ∈ V. Turklāt priekš katras virsotnes v
¹ s kas ir
sasniedzama no s, viens no īsākiem ceļiem no virsotnes s uz v
ir īsākais ceļš no s uz p[v] sekojot
pa loku (p[v], v).
Pierādījums Mēs sāksim ar gadijuma kad v ir nesasniedzama no virsotnes s. Kopš teorēma 2 apgalvoja ka d[v] ³ d(s,v) = ¥, virsotne v nevar saturēt mainīgajā d[v] vērtību kas uzstādīta 14 rindā. Pēc indukcijas tur nevar būt pirmās virsotnes kuras d vērtībai būtu piešķirts ¥ procedūras 14 rindā. Procedūras 14 rinda tāpēc tiek izpildīta tikai priekš virsotnēm ar ierobežotu d vērtību. Tātad ja v ir nesasniedzama virsotne tā nekad nevar būt atklāta.
Galvenā
pierādījuma daļa ir priekš virsotnēm sasniedzāmām no virsotnes s. Lai Vk
apzīmē virsotņu kopu kas atrodas attālumā k no virsotnes s, tas
ir
Vk = { v ∈ V : d(s,v) = k }. Pierādījums darbosies inducējot k. Kā induktīvā
hipotēzē, mēs pieņemam, ka priekš katras virsotnes v ∈ Vk, ir tieši viens punkts BFS procedūras
izpildīšanas laikā kur
·
v ir pelēka
·
d[v] tiek piešķirta vērtība k,
·
Ja v ¹ s, tad [v]
tiek piešķirta u priekš dažām u ∈ Vk-1
un
·
V tiek pievienota rindai Q
Kā jau mēs piezīmējām agrāk, būs ne
vairāk par vienu tādu punktu.
Pamatā
priekš k = 0. V0 = {s}, kopš sākuma virsotne s
ir vienīgā virsotne kas atrodas attālumā 0 no s. Iniciālizācijas laikā s
tiek padarīta par pelēku, d[s] tiek piešķirts 0, un s tiek
ievietota rindā Q, tātad induktīvā hipotēze ir spēkā.
Priekš
induktīva soļa mēs sāksim ar piezīmi ka rinda Q nekad nav tukša līdz tam
laikam, kad algoritms beidz darbu un, ja vienreiz virsotne u ir ievietota
rindā, ne d[u], ne p[u] netiks
mainīti. No teorēmas 3 seko ka ja virsotnes ir ievietotas rindā algoritma
darbības laikā kārtībā v1, v2,…,vr,
tad attāluma sekvence monotoni palielinās: d[vi] £ d[vi+1] kur I = 1,2,…,r-1.
Tagad
aplūkosim nejauši izvēlētu virsotni v ∈ Vk kur
k ³ 1. Monotonitātes
īpašību kombinējpt ar d[v] ³ k (teorēma 2), un lietojot induktīvu hipotēzi var
secināt to, ka virsotnei v ir jābūt atklātai pēc visām virsotnēm Vk-1
kuras tika pievienotas rindai, ja tā tiks atklāta vispār.
Kopš
d(s,v) = k, ir ceļš no virsotnes s uz
v, kas sastāv no k lokiem, un tātad eksistē virsotne u ∈ Vk-1 līdzīga (u,v) ∈ E. Bez liekas
paviršības lai u ir tāda pirmā pēlēka virsotne, kam ir jānotiek. Pēc
indukcijas visas virsotnes Vk-1 tiek pataisītas pelēkas. Procedūras
kods pievienos rindai katru pelēku virsotni un tādejādi u ir galu galā
jāparādās rindas sākumā procedūras rindā 10. Kad virsotne u pārādās
rindas sākumā tās blakus virsotņu saraksts tiek skanēts un v tiek
atklāta. ( Virsotne v nevar būt atklāta agrāk tikmēr tā nav blakus kādai
virsotnei no Vj kur j < k - 1, pretējā gadijumā v
nevar piederēt pie Vk un pēc pieņēmuma u ir pirmā virsotne
atklāta Vk-1 kurai v ir blakus virsotne.) 13 rindā virsotne v
tiek pataisīta par pelēku, 14 rindā d[v] = d[u] + 1 = k.
15 rindā p[u] vērtība
tiek piešķirta u, un 16 rindā virsotne tiek ievietota rindā. Kopš v
ir nejauši izvēlēta virsotne Vk, induktīva hipotēze ir pieradīta.
Lai
pabeigt pierādījumu piezīmēsim ka ja v ∈ Vk,
tad tas ko mēs redzēsim ir p[v] ∈ Vk-1. Tātad mēs varam iegūt īsāko ceļu no
virsotnes s uz v ejot pa
īsāko ceļu no s uz p[u] un šķērsojot loku (p[v],v).
2.8. Pārmeklēšanas plašumā koks
Darbības laikā procedūra BFS veido
grafa pārmeklēšanas plašumā koku kā parādīts attēlā 3. Koks ir representēts ar p lauka palīdzību priekš katras virsotnes. Priekš grafa G
= (V,E) ar sākuma virsotni s, mēs varam definēt priekšteča apakšgrafu Gp = (Vp, Ep), kur
Vp = { v ∈ V: p[v] ¹ NIL } È { s }
un
Vp = { ( p [v], u ) ∈ E: v ∈ Vp - { s } }
Priekšteča apakšgrafs Gp ir pārmeklēšanas
plašumā koks ja Vp sastāv no virsotnēm kuras var sasniegt no s, un
priekš visām v ∈ Vp ir unikāls vienkāršs ceļš no s uz v grafā
Gp, kas arī ir
īsākais ceļš no s uz v grafā G. Pārmeklēšanas plašumā koks ir
patiešām koks kopš tas ir savienots un |Ep| = |Vp| -1. Loki Ep tiek saukti par
koka lokiem.
Pēc
tam kad procedūra BFS tiek palaista apstrādāt grafu G, sekojoša teorēma pierāda
ka priekšteča apakšgrafs ir pārmeklēšanas plašumā koks.
2.9. Teorēma 5
BFS procedūras darbības rezultāta,
apstrādājot kādu virzītu vai nevirzītu grafu, konstruētais p tas ir priekšteča
grafs Gp = (Vp, Ep) ir pārmeklēšanas
plašumā koks.
Pierādījums Procedūras 15 rindā piešķirs p[v] = u tikai ja (u,v) ∈ E un d(s,v) < ¥ , citiem vārdiem tas ir tad, ja v ir sasniedzama no s un tādejādi Vp sastāv no V virsotnēm sasniedzāmām no v. Kopš Gp veido koku tas satur unikālu ceļu no s uz katru virsotni Vp. Pielietojot teorēmu 4 induktīvi, mēs secinam ka katrs tāds ceļš būs īsākais ceļš.
Sekojoša procedūra izvadīs īsāko ceļu
no virsotnes s uz virsotni v pieņemot protams ka procedūra BFS
jau tika pirms tam palaista un īsāko ceļu koks tika izveidots.
PRINT-PATH( G,s,v)
1
Ja v = s
2
Tad izvadīt s
3
citādi
ja p [v] = NIL
4
tad izvadīt “ceļš no
virsotnes s uz v neeksistē”
5
citādi PRINT-PATH(G,s, p [v])
6
izvadīt v
Šīs procedūras izpildes laiks ir
lineāri atkarīgs no virsotņu skaita ceļā, priekš katras ceļa virsotnes tiek
veikts viens rekursīvs procedūras izsaukums.
3. Pārmeklēšana dziļumā
Pārmeklēšanas
dziļumā algoritma stratēģija ir meklēt grafā tik dziļi cik iespejams, to jau
var secināt no nosaukuma. Pārmeklēšanā dziļumā tiek no sākuma izpētiti loki kas
iziet no pēdējās atklātās virsotnes v, ja tai tādi ir. Kad visi
virsotnes v loki tiek izpētīti tad pārmeklēšanas algoritms taisa
atkāpšanos ( angl. backtrack ), un pāriet pie iepriekšējās virsotnes loku
izpētes un tā tālāk. Šis process turpinās tik ilgi kamēr netiks izpētītas visas
virsotnes kuras var sasniegt no pārmeklēšanas sākuma virsotnes s. Ja
paliek kādas neatklātas virsotnes, tad viena no tām tiek atkal izvēlēta par
pārmeklēšanas sākuma virsotni un pārmeklēšana turpinās no tās. Un šis process turpinās tik ilgi, kamēr
netiks atklātas visas virsotnes.
Pārmeklēšanā dziļumā tā pat kā
pārmeklēšanas plašumā algoritmā, jebkad, kad virsotne v tiek atklāta
skanējot blakus virsotņu sarakstu priekš jau agrāk atklātās virsotnes u,
algoritms ieraksta šo notikumu piešķirot virsotnes v priekšteča laukam p [v] = u.
Atšķirībā no plašumā pārmeklēšanas algoritma kura priekšteču apakšgrafa forma
ir koks, pārmeklēšanas dziļumā priekšteču apakšgrafs var sastāvēt no vairākiem
kokiem, tas ir tāpēc ka meklēšana var turpināties no vairākām virsotnēm. Tātad
pārmeklēšanas dziļumā priekšteču apakšgrafs tiek definēts nedaudz
savādāk nekā priekšteču apakšgrafs pārmeklēšanai plašumā. Lai Gp = (V,Ep) kur
Ep = { ( p[ v ], v ) : v ∈ V un p [ v ] ¹ NIL}.
Pārmeklēšanas
dziļumā priekšteču apakšgrafi veido pārmeklēšanas dziļumā mežu
kas sastāv no pārmeklēšanas dziļumā kokiem. Ep loki tiek saukti par koka lokiem.
Tāpat kā pārmeklēšanas plašumā
algoritmā virsotnes pārmeklēšanas gaitā tiek iekrāsotas atbilstoši to
stāvokļiem. Pārmeklēšanas sākumā katra virsotne ir balta, tālāk kad virsotne
tiek atklāta tā kļūst par pelēku, un kad tā tiek pabeigta, tas ir
visas ar to saistītās virsotnes tiek atklātas tā klūst par melnu. Tāda
pārmeklēšanas tehnika garantē to ka katra virsotne tiks ievietota tikai vienā
pārmeklēšanas dziļumā kokā un tā tad koki būs sadalīti.
Bez tam ka pārmeklēšana dziļumā
procedūra veido pārmeklēšanas dziļumā koku, katrai virsotnei tiek uzliktas laika
zīmes. Katra virsotne v tiek marķēta divas reizes, tātad tā
satur divas laika zīmes. Pirmo laika zīmi d[v] tā iegūst tad, kad tiek
atklāta pirmo reizi ( kad kļūst pelēka ), un otru laika zīmi f[v] iegūst
tad, kad kļūst par melnu. Šādas laika zīmes tiek izmantotas daudzos grafu
algoritmos un parasti ir ļoti lietderīgas kad nepieciešams iegūt informāciju
par pārmeklēšanas procedūras uzvedību.
Zemāk aprakstītā procedūra DFS
ieraksta vērtību mainīgajā d[u] kad tā atklāj virsotni u, un kad
pabeidz virsotni ( kļūst par melnu) ieraksta vērtību mainīgajā f[u]. Šās
laika zīmes ir veseli skaitļi robežās no 1 līdz 2|V|. Katrai virsotnei ir spēkā
nevienādība
d [ u ] < f
[ u ]
Virsotne u
ir balta pirms laika d[u], pelēka laika intervālā no d [u] līdz f
[u], un melna pēc f[u]. Manuprāt tas ir loģiski.
Zemāk redzamais pseidokods ir pamats
pārmeklēšanas dziļumā algoritmam. Ieejas grafs G var būt gan nevirzīts, gan
virzīts. Mainīgais time ir globāls mainīgais kas tiek lietots
piešķirot laika zīmi virsotnei.
3.1.
Procedūras DFS un DFS-Visit.
DFS ( G )
1
priekš katras virsotnes u ∈ V [ G ]
2
darīt
color [ u ] ß BALTA
3
p [ u ] ß NIL
4
time ß 0
5
priekš katras virsotes u ∈ V [ G ]
6
datīt
ja color [ u ] = BALTA
7
tad
DFS-Visit( u )
DFS-Visit( u )
1 color
[ u ] ß PELĒKA //
balta virsotne u tiko tika atklāta
2 d [ u ] ß time ß time +1
3 priekš katras
v Adj[ u ] // Atklā loku (u,v)
4
datīr ja color [ u ] = BALTA
5
tad
p [ u ] ß u
6
DFS-Visit(v)
7
color [ u ] ß MELNA
8
f [ u ] ß time ß time + 1
Attēls 4
ilustrē procedūras DFS darba gaitu apstrādājot grafu kas redzams attēlā 2.
Procedūra DFS strādā sekojoši. No 1 līdz
3 rindai notiek visu virsotņu iniciālizācija, proti tās tiek pataisītas par
baltām un to mainīgam p tiek piešķirta vērtība NIL. Rinda 4 piešķir globālam laika skaitītājam
vērtību 0. No 5 līdz 7 tiek pārmeklētas pēc kartas visas virsotnes, kas pieder
V, un tad ja balta virsotne tiek atrasta tā tiek apmeklēta izsaucot DFS-Visit.
Katru reizi kad DFS-Visit(u) tiek izsaukta 7 rindā, virsotne u
kļūst par sakni jaunam kokam pārmeklēšanas dziļumā mežā. Kad DFS atgriežas
katrai virsotnei u ir piešķirta laika zīme d[u] tā tiek piešķirta
virsotnes atklāšanas laikā, un f[u] tiek piešķirta kad virsotne tiek
pabeigta.
Izsaucot procedūru DFS-Visit(u) katra
virsotne nosākuma ir balta. Tad rinda 1 procedūrā DFS-Visit padara to par
pelēku un rinda 2 ieraksta mainīgajā d[u] atklāšanas laiku un palielina
globālo laika skaitītāju par 1. No 3 līdz 6 rindai tiek pārbaudīta katra
virsotnes v blakus virsotne u un rekursīvi tiek apmeklēta v
ja tā ir balta. Kad katra virsotne v ∈
Adj[u] tiek apskatīta rindā 3, mēs sakam ka loks (u,v) ir
pārmeklēts ar pārmeklēšanas algoritmu. Kad katrs loks tiek atstāts u
tiek pilnībā pārmeklēta un rindas 7 un 8 padara to par melnu un uzliek
pabeigšanas laiku mainīgājā f[u].

4. att. Tiek parādīta pārmeklēšanas
dziļumā algoritma darbības gaita virzītā grafā. Loki kurus algoritms atklāja
tiek ieenoti ( ja tie ir koka loki) vai pretējā gadijumā tiek apzīmēti at
raustītu līniju. Kokam nepiederošie loki tiek apzīmēti ar B, C vai F attiecīgi
vai tie ir atpakaļ (back), krustošanas (cross) vai uz priekšu (forward)
virzītie loki. Virsotnēs uzliktās vērtības ir laika iezīmes, proti atklāšanas
laiks/pabeigšanas laiks.
Noskaidrosim cik laika patērēs
algoritms lai pārmeklēt grafu. Procedūras DFS cilpa no 1 – 2 un no 5 - 7 rindās
aizņem laiku Q(V), izņēmums ir procedūras DFS-Visit izsaukšana. Procedūra DFS-Visit
tiek izsaukta tieši vienu reizi priekš katras virsotnes v ∈ V, pie kam tā tiek izsaukta tikai priekš baltām virsotnēm un kad to
izsauc pirmā lieta ko tā dara - padara virsotni par pelēku. Tātad procedūras
DFS-Visit(v) izpildīšanas laikā cilpa no 3 līdz 6 rindai tiek izpildīta
|Adj[v]| reizes. Kur
å |Adj[v]| = Q(E)
v ∈ V
kopējais
patērētājs laiks izpildot rindas 2-5 procedūras DFS-Visit ir Q(E). Tad procedūras DFS kopējais izpildīšanas laiks būs Q(V + E).
3.2.
Pārmeklēšanas dziļumā algoritma īpašības
Pārmeklēšanas dziļumā algoritms dot
iespeju iegūt vairāk informācijas par grafa struktūru. Laikam vissvarīgākā
pārmeklēšanas dziļumā algoritma īpašība ir tā ka priekšteču apakšgrafs Gp patiešām veido mežu no kokiem, pie kam pārmeklēšanas dziļumā koku
struktūra tieši atspoguļo rekursīvas DFS-Visit procedūras izsaukumus. Tas ir u
= p [v] tad un tikai tad, ja DFS-Visit(v) tika
izsaukta u virsotnes blakus virsotņu saraksta pārmeklēšanas laikā.
Otra svarīga pārmeklēšanas dziļumā
algoritma īpašība ir tā ka virsotnes atklāšanas un pabeigšanas laikiem ir intervāla struktūra. Ja mēs
reprezentējam virsotnes u atklāšanu ar intervāla kreiso pusi ”(u”
un tās pabeigšanu ar intervāla labo pusi “u)”, tad atklāšanas uz
pabeigšanas vēsture tiek veidota ar labi formētu izteiksmi gadijumā, ja
intervāli bija pareizi noteikti. Piemēram pārmeklēšanas dziļumā intervālu
sadalīšana grafam no attēla 5(a) atbists attēls 5(b).
3.3.
Teorēma 6 ( Intervālu teorēma )
Ja uz kāda
virzīta jeb nevirzīta grafa G=(V,E) tiek veikta pārmeklēšana dziļumā virsotnēm u
un v, tieši viens no sekojošiem trijiem nosacījumiem izpildās:
·
Intervāls [ d [u], f [u]
] un intervāls [ d [v], f [u] ] nepārklājās.
·
Intervāls [d [u], f [u]
] ir pilnīgi ietverts intervālā [d [v], f [v] ], un virsotne u
ir virsotnes v pēcnācējs pārmeklēšanas dziļumā kokā.
·
Intervāls [d [v], f [v]
] ir pilnīgi ietverts intervālā [d [u], f [u] ], un virsotne v
ir virsotnes u pēcnācējs pārmeklēšanas dziļumā kokā.
Pierādījums Mēs sāksim ar gadijumu kad d[u] < d[v]. Šī gadijumā ir
iekļauti vēl divi apakšgadijumi, respektīvi d [v] < f [u] vai
arī ne. Pirmā apakšgadijumā d[v] < f[u], tas ir kad v
bija atklāta kamēr u vēl bija pelēka. Tas implicē to, ka virsotne v
ir virsotnes u pēcnāceja. Pat vairāk tā kā v bija atklāta vēlāk
par u tad visi no tās izejošie loki arī ir atklāti, un v tiek
pabeigta pirms pārmeklēšana atgriezīsies un pabeigs u. Šajā gadijumā
intervāls [ d [v], f [v] ] tiek pilnīgi iekļauts inervālā [d[u],f[u]]. Otrā apakšgadījumā f[u] < d[v]
un vienādība 1.1 implicē to ka intervāls [ d [u], f [u] ] un intervāls [ d [v], f [v] ]
nepārklājās.
Gadijums kad d
[v] < d [u] ir pilnīgi
līdzīgs tiko aprakstītam, pie nosacījuma ka visus v burtus japamaina uz u.
3.4.
Secinājums 7
Virsotne v
ir virsotnes u pēcnācējs pārmeklēšanas dziļumā kokā priekš virzīta jeb
nevirzīta grafa G tad un tikai tad kad d [u] < d [v] < f [v]
< f [u].
Pierādījums Seko no teorēmas 6.

5. att.
Pārmeklēšanas dziļumā īpasības. (a) Pārmeklēšanas dziļumā algoritma
darbības rezultāts pārmeklējot virzītu grafu. Virsotnēm tiek liktas laika zīmes
un loki tiek apzīmēti pēc tāda paša principa kā attēlā 4. (b) Priekš
katras virsotnes tiek parādīti tō atklāšanas laiks un un pabeigšanas laiks.
Katrs taisnstūris rāda intervālu starp virsotnes atklāšanu un pabeigšanu. Koka
loki tiek parādīti arī. Divu intervālu pārklājumā, kad viens tiek pilnīgi
iekļauts otrā, virsotne, kas atrodas mazākā intervālā ir pēcnāce virsotnei kas
atrodas lielākā intervālā. (c) Grafs kas dots (a) pārzīmēts ar visiem
kokiem un uz priekšu virzītiem lokiem, un ar lokiem kas virzīti no pēcnācēja
virsotnēm uz priekšteča virsotnēm.
Nākamā teorēma
dos nākamo svarīgo raksturojumu kad viena virsotne ir citas virsotnes pēctecis
pārmeklēšanas dziļumā mežā.
3.5. Teorēma 8 ( Baltā
ceļa teorēma )
Pārmeklēšanas
plašumā mežā (virzīta vai nevirzīta) grafa G = (V,E), virsotne v ir
virsotnes u pēctecis tad un tikai tad, ja laikā d[u] kurā
virsotne u atklāta, virsotne v bija sasniegta no virsotnes u
ejot pa ceļu kas sastāv tikai no baltām virsotnēm.
Pierādījums Pieņemsim
ka virsotne v ir virsotnes u pēctecis. Lai w ir virsotne ceļā no u
uz v pārmeklēšanas dziļumā kokā, tātad w ir virsotnes u
pēctecis. Pēc teorēmas 7 d[u] < d[w] un tātad w ir
balta laikā d[u].
Pieņemsim ka virsotne v ir
sasniedzama no virsotnes u ejot pa ceļu kas sastāv no baltām virsotnēm
laikā d[u], bet v nekļūst par u pēcteci pārmeklēšanas
dziļumā kokā. Bez liekas vispārības pieņemam ka jebkura cita virsotne kas
sastopas ceļā klūst par virsotnes u pēcteci. Lai virsotne w ir
virsotnes v priekštecis ceļā. Tātad w ir u pēctecis (
patiesībā w un u var būt viena un tā pati virsotne) un pēc secinājuma
7 f[w] £ f[u]. Piezīmesim ka v jābūt atklātai pēc virsotnes u
atklāšanas, bet pirms w ir pabeigta. Tādejādi d[u] < d[v]
< f[w] £ f [u]. Teorēma 6 implicē to ka intervāls [d[v], f[v]]
ir pilnīgi iekļauts intervālā [d[u],f[u]]. Pēc secinājuma 7 virsotnei
v pēc visa ir jābūt virsotnes u pēctecim.
3.6. Loku klasifikācija.
Cita interesanta pārmeklēšanas dziļumā algoritma īpašība ir tā ka viņš
var būt lietots apstrādājamā grafa G = (V,E) loku klasifikācijai. Šī loku
klasifikaciju var lietot gadijumā kad ir nepieciešams iegūt svarīgu informāciju
par grafu. Piemēram nākamā sekcijā mēs redzēsim, kā virzīts grafs ir aciklisks
tad un tikai tad ja pārmeklēšana dziļumā nepieļaus “atpakaļ” ejošus lokus (
teorēma 10).
Mēs varam definēt četrus loku tipus kurus var sastapt pārmeklēšanas
dziļumā mežā Gp kas tika veidots pārmeklēšanas dziļumā procedūras darbības rezultātā.
1.
Koka loki – ir loki pārmeklēšanas plašumā mežā Gp. Loks (u,v) ir koka loks ja v ir atklāta pirmā pētot loku (u,v)
2.
Atpakaļ virzīti loki – ir tie loki (u,v) kas savieno virsotni u ar priekšteci v
pārmeklēšanas dziļumā kokā. Parasti cilpas satur atpakāļ virzītus lokus.
3.
Uz priekšu virzīti loki – ir tie ne koka loki (u,v) kas savieno virsotni u ar
pēcteci v pārmeklēšanas dziļumā kokā.
4.
Krust loki – visi pārējie loki. Tie var būt loki kas savieno savā starpā netiešus
pēctečus ar priekštečiem, vai arī tie var savienot savā starpā virsotnes
dažādos pārmeklēšanas dziļumā kokos.
Attēlā 4 un 5
loki tiek apzīmēti atbilstoši to tipiem. Attēlā 5(c) arī tiek parādīts kā
attēlā 5(a) grafs var būt pārzīmēts tādā veidā
ka visi koki un uz priekšu virzīti loki ir virzīti lejup pārmeklēšanas
dziļumā kokā, un visi atpakaļ virzīti loki virzīti augšup. Jebkurš grafs var
būt pārzīmets tādā veidā.
DFS algoritms var būt modificēts
nolūkam klasificēt lokus. Pamat ideja ir tāda ka loks (u,v) var būt
klasificēts pēc virsotnes v krāsas, kas ir sasniedzāma kad loks pirmo
reiz tiek izpētīts.
1.
BALTA liecina par to ka tas ir
koka loks,
2.
PELĒKA liecina par to ka tas ir
atpakaļ virzīts loks, un
3.
MELNĀ liecina par uz priekšu
virzītu vai krust loku.
Pirmais gadijums izriet no algoritma specifikācijas. Otram gadijumam
ievērosim to, ka pelēkas virsotnes vienmēr veido lineāru ķēdi no pēctečiem
procedūras DFS-Visit piesaucēju rindā. Pelēko virsotņū skaits ir par vienu
vairāk nekā nesen atklāto virsotņu skaits pārmeklēšanas dziļumā kokā.
Pārmeklēšana vienmēr turpinās no dziļākās pelēkās virsotnes, tātad loks kas
sasniedz citu pelēku virsotni sasniedz pēcteci. Trešais gadijums aplūko
atlikušās iespejas; loks (u,v) var tikt klasificēts kā uz priekšu
virzīts loks ja d[u] < d[v] un var būt uzskatīts par krust
loku ja d[u] > d[v].
Nevirzītā grafā var būt dažas neskaidrības loku tipu klasifikācijā jo (u,v)
un (v,u) ir viens un tas pats loks. Tādā gadijumā loks tiek klasificēts
ar pirmo loka tipu kam loku tipu sarakstā izpildās augstāk aprakstītie
nosacījumi. Ekvivalenti tiek klasificēti abi loki gan (u,v), gan (v,u)
kurus sastop pārmeklēšana dziļumā pārmeklējot nevirzītu grafu.
Tagad mēs parādīsim, ka uz priekšu virzīti un krust loki nekad nav
sastopami pārmeklēšanā dziļumā pārmeklējot nevirzītu grafu.
3.7. Teorēma 9
Pārmeklēšanā
dziļumā pārmeklējot nevirzītu grafu G, visi grafa G loki ir vai nu koka loki
vai nu atpakaļ virzīti loki.
Pierādījums Lai (u,v)
ir nejauši izvēlēts grafa G loks, un pieņemsim ka d[u] < d[v].
Tad v ir jābūt atklātai un pabeigtai pirms būs pabeigta u
virsotne, kopš v ir virsotnes u blakus virsotņu sarakstā. Ja loks
(u,v) ir atklāts no sākumā virzienā no u uz v, tad loks (u,v)
tiks uzskatīts koka loku. Un ja loks (u,v) tiks atklāts virzienā no v
uz u, tad (u,v) tiks uzskatīts par atpakaļ virzītu loku.
4. TOPOLOĢISKA
KĀRTOŠANA
Šī nodaļā tiks parādīts kā pārmeklēšana dziļumā var būt lietota lai
veikt topoloģisko kārtošanu virzītā acikliskā grafā, jeb “mudžeklī” kā tas pa
laikam tiek saukts. Mudžekļa G = (V,E) topoloģiskā kārtošana ir visu to
virsotņu lineāra sakārtošana tādā veidā, ka ja G satur loku (u,v) tad virsotne
u parādīsies pirms virsotes v pēc sakārtošanas ( ja grafs nav aciklisks tad
lineāra kārtošana nav iespejama). Grafa topoloģiskā kārtošana var būt apskatīta
kā virsotņu novietošana gar horizontālas līnijās tādā veidā ka visi virzīti
loki ies no kreisās puses uz labo.
Virzīts aciklisks grafs tiek lietots daudzās aplikācijās lai parādītu
notikumu prioritāti jeb secību. Attēlā 6 ir parādīts piemērs kur redzama
darbību secība ko izpilda profesors Bums apģērbjoties no rīta. Profesoram
jauzvelk noteiktus apģērbus pirms tiks uzvilki citi ( piemēram zeķes pirms
apaviem). Citi apģērbi var būt uzvilki patvaļīgā secībā ( piemēram zeķes un
apakšbikses). Attēlā 6(a) grafa virzīts loks (u,v) rāda ka apģērbam u jābūt
uzvilktam pirms apģērba v. Šī mudžekļa topoloģiskā kārtošana dos secību kādā
drēbes jāvelk. Attēls 6(b) rāda topoloģiski sakārtotu mudžekli kā virsotņu
izvietošanu gar horizontālu līniju tādā kārtībā ka visi virzīti loki iet no
kreisās puses uz labo.

6. att. (a)
Profesors Bums topoloģiski kārto savas drēbes kad ģērbjas. Katrs virzīts loks
(u,v) nozīme to ka drēbei u jābūt uzvilktai pirms būs uzvilkta drēbe v. Katras
virsotnes atklāšanas un pabeigšanas laiks tiek parādīts tai blakus. (b) tas pats grafs parādīts jau
topoloģiski sakārtots. Tā virsotnes tiek sakārtotas no kreisās uz labo pusi
pabeigšanas laika samazināšanas virzienā. Visi virzīti loki iet no kreisās uz
labo pusi.
Sekojošais
vienkāršais algoritms topoloģiski sakārto mudžekli.
4.1. Procedūra
Topological-Sort
Topological-Sort
( G )
1 izcauc DFS (G) lai
izrēķināt beigu laiku f[v] priekš katras virsotnes v
2
kad virsotne ir pabeigta, ievieto
to saistītā saraksta priekšā
3
atgriež virsotņu saistīto sarakstu
Attēls 6(b) rāda
kā topoloģisķi sakartotas virsotnes parādās pretējā kārtībā to pabeigšanas
laikam.
Mēs varam veikt topoloģisko
kārtošanu laikā Q( V + E ), kur pārmeklēšana dziļumā aizņem Q( V + E ) laika un O(1) laiks ir nepiecešams lai ievietot katru |V|
virsotni saistītā saraksta priekšā.
Pierādīsim šī algoritma patiesumu
lietojot sekojošu teorēmu kas raksturo virzītu aciklisku grafu.
4.2. Teorēma 10
Virzīts grafs G
ir aciklisks tad un tikai tad ja pārmeklēšana dziļumā pārmeklējot grafu G
neatgriež atpakaļ virzītus lokus.
Pierādījums Pieņemsim
ka ir atpakaļ virzīts loks (u,v). Tad virsotne v ir virsotnes u priekštecis
pārmeklēšanas dziļumā mežā. Tātad ir ceļs no v uz u grafā G, un
atpakaļ virzīts loks (u,v) veido ciklu.
Pieņemsim ka
grafs G satur ciklu c. Mēs parādīsim ka pārmeklēšana dziļumā izveidos
atpakaļ virzītus lokus. Lai v ir pirmā atklātā cikla c virsotne,
un lai (u,v) ir iepriekšējais loks ciklā c. Laikā d[v] ir
ceļš kas sastāv no baltām virsotnēm no virsotnes v uz virsotni u.
Pēc baltā ceļa teorēmas, virsotne u kļūst par virsotnes v pēcteci
pārmeklēšanas dziļumā mežā. Tātad loks (u,v) ir atpakaļ virzīts loks.
4.3. Teorēma 11
Procedūra Topological-Sort(G)
izpilda virzīta acikliska grafa G topoloģisko kārtošanu.
Pierādījums Pieņemsim ka procedūra DFS tiek palaista dotam mudžeklim G=(V,E) lai
noteikt katras virsotnes pabeigšanas laiku. Tas ir pietiekami lai parādītu ka
ja eksistē loks grafā G no u uz v, priekš jebkura noteikta
virsotņu pāra u,v ∈ V, tad f[v]u]. Aplūkosim kadu loku (u,v)
kuru atklāja procedūra DFS(G). Kad šis loks tiek atklāts, virsotne v
nevar būt pelēka, kopš tā laika v var būt u priekštecis un (u,v)
var būt atpakaļ virzīts loks, noliedzot teorēmu 10. Tāpēc v ir jābūt vai
nu baltai vai nu melnai virsotnei. Ja v ir balta virstone, tad tā kļūst
par u virsotnes pēcnācēju un f[v] < f[u]. Ja v
ir melna virsotne, tad f[v] < f[u] tāpat. Tatad priekš jebkura
loka (u,v) mudžeklī mēs iegūstam ka f[v] < f[u], līdz
ar to teorēma ir pierādīta.
5. STINGRI SAVIENOTAS KOMPONENTES
Tātad tagad mēs aplūkosim klasisku
pārmeklēšanas dziļumā aplikāciju, kas sadala virzītu grafu stingri savienotās
komponentēs. Šī nodaļa parāda kādā veidā izpildīt šo dekompozīciju izmantojot
divas pārmeklēšanas dziļumā. Daudzi algoritmi kas strādā ar virzītiem grafiem
uzsāk savu darbu ar šādu dekompozīciju. Šī pieeja bieži ļauj sadalīt vienu
lielu problēmu vairākās apakšproblēmās, piesaistot atbilstoši katru apakšproblēmu savai stingri savienotai
komponentei. Kombinējot apakšproblēmu risinājumus var izsekot savienojumu
struktūru starp stingri savienotām komponentēm. Šī struktūra var būt attēlota
izmantojot tā saukto “komponenšu” grafu.

8. att. (a) virzīts
grafs G. Stingri savienotās komponentes tiek parādītas kā ieenoti apgabali.
Katra virsotne tiek marķēta ar tās atklāšanas un pabeigšanas laiku. Koka loki
tiek ieenoti. (b) Grafs GT ir apgriezts grafa G grafs.
Pārmeklēšanas dziļumā koks kas tiek izskatļots procedūras
Strongly-Connected-Componensts 3 rindā tiek attēlots ar ieenotiem lokiem. Katra
stingri savienotā komponente atbilst vienam pārmeklēšanas dziļumā kokam.
Virsotnes b,c,g un h kuras ir iekrāsotas melnā krāsā ir katra savas stingri
savienotās komponentes pirmsteči, un tās arī ir koku saknes kuri tiek veidoti
pārmeklēšanas dziļumā procedūras darbības gaitā apstrādājot grafu GT.
(c) Ir aciklisks komponenšu grafs GSCC kas iegūstams
attveidojot katru stingri savienoto komponenti kā atsevišķu virsotni.
Virzīta grafa
G = (V,E) stingri savienotās komponentes
ir maksimālā virsotņu UÍV kopa, kur priekš katra virsotņu u
un v ∈ U pāra, ir abas u⇝v un v⇝u, tas ir virsotnes u un v
sasniedzamas viena no otras. Attēlā 8. var redzēt piemēru.
Mūsu apskatāmais algoritms priekš
stingri savienoto komponenšu meklēšanas grafā G = (V,E) lieto apgriesto grafu GT = (V,ET), kur
ET={(u,v):(v,u)∈E)}. Tas ir GT
esošie loki ir apgriezti otrādā virzienā nekā grafā G. Lai konstruētu grafu GT
izmantojot informāciju no blakus virsotņu saraksta ir nepieciešams O(V+E)
laiks. Ir japiezime ka G un GT satur tieši tās pašas stingri
savienojamās komponentes: virsotnes u un v ir sasniedzamas viena no otras grafā
G tad un tikai tad ja tās ir sasniedzamas viena no otras grafā GT.
Attēlā 8(b) tiek parādīts apgriezts grafs grafam no attēlā 8(a) ar ieenotām
stingri savienotām komponentēm.
Nākamais lineārs laika algoritms ( Q(V+E) laiks nepieciešams tā darbībai) nosaska grafa G=(V,E) stingri
savienotās komponentes lietojot divas pārmeklēšanas dziļumā, vienu priekš grafa
G, un otru priekš GT.
5.1.
Procedūra Strongly-Connected-Components
Strongly-Connected-Components(G)
1
izsaukt DFS( G ) lai noteikt
katras virsotnes u pabeigšanas laiku f[u].
2
Izveido GT
3
Izsauc DFS( GT ) bet
galvenājā procedūras cilpā apskata virsotnes f[u] vērtības
sasmazināšanas kārtībā
4
Izvada katra koka no pārmeklēšanas
dziļumā mežā virsotnes ( tie veidoti 3 solī) kā atdalītas stingri savienotās
komponentes
Izskatās ka
šis vienkāršais algoritms nedara neko, kas būtu saistīts ar stingri savienoto
komponenšu izveidi. Atlikušaja nodaļas daļā mēs izvējināsim noslēpumainību un
pierādīsim šī algoritma pareizību. Sāksim ar noderīgo teorēmu apskatu.
5.2.
Teorēma 12
Ja divas virsotnes atrodas vienā
stingri savienotājā komponentē tad ceļš kas ved no vienas tādas virsotnes uz
otru nekad neiziet no šīs stingri savienotās komponentes.
Pierādījums Lai u un v ir divas virsotnes vienā un tā pašā stingri
savienotā komponentē. Pēc stingri savienotās komponentes definīcijas eksistē
ceļš kas savieno u ar v un v ar u. Lai virsotne w
ir kādā ceļā u⇝ w⇝ v, tātād w ir sasniedzama no u. Turklāt kopš ir
ceļš no v⇝u, mēs zinam ka u ir sasniedzama no w
pa ceļu w⇝ v⇝ u. No tā seko, ka u un w atrodas vienā un tājā
patī stirngri savienotā komponentē. Tā
kā w ir izvēlēta nejauši teorēma ir pierādīta.
5.3.
Teorēma 13
Jebkurā pārmeklēšanā dziļumā, visas
vienas stingri savienotās komponentes virsotnes tiek ievietotas vienā un tā
patī pārmeklēšanas dziļumā kokā.
Pierādījums No virsotnēm stingri savienotā komponentē ļausim virsotnei r būt
pirmai atklātai virsotnei. Tākā virsotne r ir pirmā, tad tās atklāšanas laikā
visas pārējās virsotnes stingri savienotajā komponentē ir baltas. No virsotnes r
eksistē ceļš uz pārējām stingri savienotās komponentes virsotnēm, tākā šis ceļš
neiziet no stingri savienotās komponentes robežas tad visas virsotnes tājā ir
baltas. Tātad pēc baltā ceļa teorēmas katra virsotne stingri savienotājā
komponentē kļūst par virsotnes r pēcteci pārmeklēšanas dziļumā kokā.
Šīs sekcijas atlikušajā daļā apzīmēsim
ka d[u] un f[u] ir attiecīgi atklāšanas uz pabeigšanas laiks, kas
tiek noteikts procedūras Strongly-Connected-Components 1 rindā. Līdzīgi u⇝v apzīmēs eksistējošu ceļu grafa G, ne grafā GT.
Lai pierādīt procedūras
Strongly-Connected-Components pareizību, iepazīsimies ar apzīmējumu virsotnes u
sencis f(u), kas ir virsotne w sasniedzama no u, kas ir
pedejā pabeigtā pārmeklēšanas dziļumā rindā 1. Citiem vārdiem
f(u) = tā virsotne w kuras u⇝w un f[w] vērība ir maksimāla.
Piezīmēsim ka f(u) = u ir iespejama tapēc ka u ir sasniedzama no
sevis pašas un tādejādi
f [u] £ f [ f(u) ]
Mēs arī varam
parādīt ka f(f(u)) = f(u) spriežot sekojoši. Priekš
jebkurām virsotnēm u,v ∈ V, u ⇝v implicē f[f (v)] £ f[f (u)], kopš {w:v⇝w}Í{w:u⇝w} un pirmstecim ir maksimālais pabeigšanas laiks no visām
sasniedzāmām virsotnēm. Kopš f(u) ir sasniedzama no u,
formula 3 implicē f[f(f(u))] £ f[f(u)], un tātad mēs ieguvām f(f(u)) = f(u), kopš divas virsotnes kas tiek
pabeigtas vienā laikā ir faktiski viena un tā pati virsotne.
Kā mēs varam redzēm katrai stingri
savienotai komponentei ir viena virsotne kura ir katras stingi savienotas
komponentes virsotņu pirmstecis, to vēl citādi sauc par stingri savienotās
virsotnes “pārstāvja virsotni”. Grafu pārmeklējot ar pārmeklēšanu
dziļumā pārstāvja virsotne tā ir pirmā virsotne kas tiek atklāta un ir pēdējā
virsotne kas tiek pabeigta. Pārmeklējot grafu GT tā ir saknes
virsotne priekš pārmeklēšanas dziļumā koka. Tagad mēc pierādīsim šīs īpašības.
5.4.
Teorēma 14
Virzītā grafā
G = (V,E) jebkurā pārmeklēšanā dziļumā jebkuras virsotnes u∈V pirmstecis ir f(u).
Pierādījums Ja f(u) = u, tad teorēma ir triviāli patiesa. Ja f(u) ¹ u, aplūkosim virsotņu krāsas laikā d[u]. Ja f(u) virsotne ir meklna, tad f[f(u)] < f[u], kas ir pretrunā ar nevienādību (2). Ja f(u) ir pelēka, tad tā ir u priekštecis un teorēma ir
pierādīta.
Palika tikai pierādīt kad f(u) nav balta. Te ir divi gadijumi, atbilstoši tam kādā krāsā ir
starp virsotnes jebkurā ceļā no virsotnes u uz f(u).
1. Ja visas starp virsotnes ir baltas, tad f(u) kļūst par u pēcteci, pēc baltā ceļa teorēmas. Bet tad
f[f(u)] < f[u] un tas ir pretrunā ar nevienādību (2).
2. Ja kāda no starp virsotnēm ir nebalta, lai t ir pēdējā nebaltā
virsotne ceļā no u uz f(u). Tad t ir jābūt pelēkai,
jo nekad nevar būt loka no melnās virsotnes uz balto, un t pēctecis ir
balts. Bet tad ir ceļš kas sastāv no baltām virsotnēm no t uz f(u), un f(u) ir virsotnes t pēctecis
pēc bāltā ceļa teorēmas. Tas implicē ka f[t] > f[f(u)], noliedzot mūsu izvēli f(u), kopš ir ceļs no virsotnes u uz t.
5.5.
Secinājums 15
Pārmeklējot
dziļumā jebkuru virzītu grafu G = (V,E), virsotnes u un f(u), priekš visām u ∈
V, atrodas vienā stingri savienotā komponentē.
Pierādījums Mēs zinam ka u⇝f(u), pēc pirmsteča definīcijas, un f(u)⇝u, kopš f(u) ir u
priekštecis.
Nākamā teorēma
dot stingru attiecību kura pastāv starp
stingri savienoto komponenti un tās pirmsteci.
5.6.
Teorēma 16
Virzītā grafā
G = (V,E) divas virsotnes u,v ∈ V atrodas vienā
stingri savienotājā komponentē tad un tikai tad ja tiem ir viens un tas pats
pirmstecis pārmeklēšanā dziļumā.
Pierādījums Pieņemsim ka u un v atrodas vienā un tajā patī stingri
savienotā komponentē. Katra virsotne kas
ir sasniedzama no virsotnes u ir arī sasniedzama no virsotnes v
un otrādi, pie kam ir ceļš starp u un v abos virzienos. Pēc
pirmsteča definīcijas mēs varam secināt ka f(u) = f(v).
Pieņemsim ka f(u) = f(v). Pēc secinājuma 15, u atrodas vienā un tajā patī
stingri savienotajā komponentē kur atrodas f(u), un v atrodas vienā stingri savinotajā komponentē ar f(v). Tatad u un v atrodas vienā un tajā pašā
stingri savienotājā komponentē.
Ar teorēmu 16
rokā agoritma Strongly-Connected-Components darbība var būt vieglāk saprotama.
Stingri savienotā komponente ir virsotņu kopa kurām ir kopīgs pirmstecis. Pat
vairāk, pēc teorēmas 14 un teorēmas 6, procedūras Strongly-Connected-Components
1 rindas izpildīšanas pārmeklēšanas dziļumā laikā pirmstecis ir, gan pirmā
atklātā virsotne, gan pēdējā pabeigtā virsotne stingri savienotajā komponentē.
Lai saprast kapēc mēs palaižam
pārmeklēšanu dziļumā uz grafa GT Strongly-Connected-Components
procedūras 3 rindā, apskatīsim virsotni r ar lielāko pabeigšanas laiku,
kas tika noteikts arī ar pārmeklēšanu dziļumā 1 rindā. Pēc pirmsteča
definīcijas virsotne r ir jābūt pirmstecim, tā kā tā ir pati sev
pirmstecis, tad tā var sasniegt pati sevi, un nevienai citai virsotnei grafā
nav lielāks pabeigšanas laiks. Kuras ir citas virsotnes kas atrodas r
stingri savienotājā komponentē ? Tās ir tās virsotnes kuru pirmstecis ir r
un kuras nevar sasniegt citas virsotnes kurām pabeigšanas laiks ir lielāks par
virsotnes r pabeigšanas laiku. Bet virsotnes r pabeigšanas laiks
ir lielākais par jebkuras citas virsotnes grafā G, tātad r stingri
savienotā komponentē sastāv tikai no šīm virsotnēm kas var sasniegt virsotni r.
Ekvivalenti stingri savienotā komponente r sastāv no tām virsotnēm kurās var
sasniegt virsotne r grafā GT. Tātad pārmeklēšana dziļumā 3 rindā
identificē visas virsotnes kuras pieder stingri savienotaj komponentei un
padara tās par melnām.
Pēc tam, kad tika noteiktas visas
virsotnes dotājā stingri savienotājā komponentē ar pārmeklēšanas dziļumā
palīdzību 3 rindā, darbība turpinās ar citu virsotni r’ kurai ir
maksimālais pabeigšanas laiks, bet kas nepieder stingri savienotaj komponentei r.
Virsotnei r’ ir jābūt pašai sev par pirmsteci, tā kā tā nevarētu
sasniegt kādu citu virsotni ar lielāku pabeigšanas laiku. Nu un līdzīgi visām
virsotnēm kuras var sasniegt r’ un kuras vēl nav melnas jāpieder stingri
savienotaj komponentei r’. Tātad turpinoties 3 rindā pārmeklēšanai
dziļumā tā nosaka un padara par melnām visas virsotnes kas pieder r’
stingri savienotāj komponentei pārmeklējot r’ grafā GT.
Tātad
pārmeklēšana dziļumā procedūras 3 rindā izdala stingri savienotās komponentes vienu
pēc otras. Katra komponente tiek identificēta procedūras DFS 7 rindā izsaucot
procedūru DFS-Visit un nosūtot tai kā argumentu komponentes pirmsteci.
Rekursīva procedūras DFS-Visit izsaukšana galu galā pataisa katru virsotni
komponentes robežās par melnu. Kad DFS-Visit atgriežas procedūrā DFS,
apstrādājamā komponente tiek pilnīgi pataisīta par melnu un tiek it kā atlikta
malā. Procedūra DFS atrod virsotni ar maksimālo pabeigšanas laiku starp tām
virsotnēm kas vēl nav pataisītas par melnām, šī virsotne ir nākamās stingri
savienotās komponentes pirmstecis, un process turpinās.
Nākamā teorēma
formalizē šo argumentu.
5.7. Teorēma 17
Procedūra
Stronly-Connected-Components(G) pareizi nosaka virzīta grafa G stingri
savienotās komponentes.
Pierādījums Mēs pierādījām ar indukcijas palīdzību ka katrs pārmeklēšanas dziļumā koks kas tiek veidots darbojoties pārmeklēšanai dziļumā grafā GT ir atsevišķā stingri savienotā komponente. Katrs solis indukcijā pierāda ka pārmeklēšanas dziļumā koks kas tiek veidots pārmeklējot grafu GT ir stingri savienotā komponente pieņemot, ka visi iepriekš izveidotie pārmeklēšanas dziļumā koki ir stingri savienotās komponentes. Pamats indukcijai ir triviāls, pie kam priekš pirmā izveidotā koka nav iepriekš izveidoto koku, tātad šis pieņēmums ir triviāli pareizs.
Apskatīsim
pārmeklēšanas dziļumā koku T ar saknes virsotni r, kas tika izveidots ar
pārmeklēšanu dziļumā pārmeklējot grafu GT. Lai C(r) apzīmē
virsotņu kopu kuru pirmstecis ir virsotne r:
C (r) = { v
∈ V, f(v) = r }
Tagad mēs pierādīsim to ka virsotne u
pieder T tad un tikai tad ja u ∈ C(r).
Teorēma
1.13 implicē to ka katra virsotne no kopas C(r) vienam un tam pašam
pārmeklēšanas dziļumā kokam. Kopš r ∈ C(r) un r
ir T saknes virsotne, katrs elements no kopas C(r) ∈ T.
Tagad
parādīsim ka jebkura virsotne w tāda kurai f [f(w)] > f
[r] vai f[f(w)]r],
neietilpst T, apskatīsim šos divus gadijumus atsevišķi. Pēc indukcijas
pārmeklēšanas kokos kuri tika izveidoti, jebkura virsotne w tāda kurai
f[ f(w)]>f[r]
neietilpst kokā T, kopš laika kad r tiek izvelēta w jau bija
jābūt kokā ar sakni f(w).
Jebkura virsotne w tāda kurai f[f(w)]r] nevar ietilpst kokā T, jo ja
tā ietipstu kokā tas nozīmētu to ka w ⇝r, tātad pēc
formulas 3 un pēc īpašības ka r = f(r), mēs iegūstam ka f[f(w)] ³ f[r] = f[r],
kas ir pretrunā f[f(w)]r].
Tādejādi
T satur tikai tās virsotnes u kurām f(u) = r.
Tas nozīmē to ka T ir tieši ekvivalenta stingri savienotajai komponentei C(r),
kas savukārt pierāda induktīvo pierādījumu.
6. NOBEIGUMS
Tātad savā darbā esmu aplūkojis dažus
svarīgus algoritmus no grafu teorījas. Ar dažiem no tiem esmu jau agrāk
sastapies macot tādus priekšmetus kā ‘Grafu teorija’ un ‘Mākslīgais intelekts’.
Tāpēc grafu aprakstīšanas veidi, pārmeklēšanas plašumā un dziļumā algoritmi man
nebija par jaunumu. Bet gan jāpiebilsts ka tie dotajā darbā tiek apskatīti
daudz sīkākā līmenī ar daudzām teorēmām un pierādījumiem, kuru tulkošana bija
nesevišķi interesnata.
Līdz šim neesmu sastapies ar tādu
algoritmu kā topoloģiskā kārtošana. Un arī jauns bija jēdziens par stingri
savienotām komponentēm un to notiekšanas algoritms, kas savukārt bālstās uz
pārmeklēšanu dziļumā.
Uzskatu ka šis darbs bija ļoti
lietderīgs jo tas atsvaidzināja manas jau esošas zināšanas par grafu teoriju un
papildināja tās ar dažām jaunām lietām. Uzskatu arī ka grafu teorijai ir liela
loma mūsu pašreizējā zinātniskā dzīvē, jo uz tās teorijām balstās daudzas
datoru programmatūras veidošanas nozares.
Ļoti labs Darbs! Paldies.
AtbildētDzēst