Grafu attēlošana

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 A^T = (a^T_ij) noteiktu ar a^T_ij=a_ij. 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 = A^T. 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 ( v₁, v₂, …,v_r), kur virsotne v₁ ir rindas sākumā un virsotne ir v_r rindas galā. Tad d[ v_r ] £ d[ v₁ ] + 1 un d[ v_i ] £ d[ v_i+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 v₁ tiek izslēgta, tad par jaunu rindas sākuma virsotni kļūst virsotne v₂. Bet tad mums ir d[ v_r ] £ d[ v₁ ] + 1 £ d[ v₂ ] + 1 un pārējās nevienādības paliek neietekmētas. Tatad teorēma izpildās arī ja rindas sākuma virsotne ir v₂. 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 v_r+1, rindas sākuma virsotne v₁ ir faktiski virsotne u kuras blakus virsotņu saraksts jau tika skanēts. Tādejādi d[v_r+1] = d[v] = d[u] + 1 = d[v₁] + 1. Mēs arī iegūstam d[v_r] £ d[v₁] + 1 = d[u] + 1 = d[v] = d[v_r+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 V_k apzīmē virsotņu kopu kas atrodas attālumā k no virsotnes s, tas ir

V_k = { 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 ∈ V_k, 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 ∈ V_k-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. V₀ = {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ā v₁, v₂,…,v_r, tad attāluma sekvence monotoni palielinās: d[v_i] £ d[v_i+1]  kur I = 1,2,…,r-1.

            Tagad aplūkosim nejauši izvēlētu virsotni v ∈ V_k 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 V_k-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 ∈ V_k-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 V_k-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 V_j kur j < k - 1, pretējā gadijumā v nevar piederēt pie V_k un pēc pieņēmuma u ir pirmā virsotne atklāta V_k-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 V_k, induktīva hipotēze ir pieradīta.

            Lai pabeigt pierādījumu piezīmēsim ka ja v ∈ V_k, tad tas ko mēs redzēsim ir p[v] ∈ V_k-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 G_p = (V_p, E_p), kur

V_p = { v ∈ V: p[v] ¹ NIL } È { s }

un

V_p = { ( p [v], u ) ∈ E: v ∈ V_p  - { s } }

Priekšteča apakšgrafs G_p ir pārmeklēšanas plašumā koks ja V_p sastāv no  virsotnēm kuras var sasniegt no s, un priekš visām v ∈ V_p ir unikāls vienkāršs ceļš no s uz v grafā G_p, 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 |E_p| = |V_p| -1. Loki E_p 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 G_p = (V_p, E_p) 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 V_p sastāv no V virsotnēm sasniedzāmām no v. Kopš G_p veido koku tas satur unikālu ceļu no s uz katru virsotni V_p. 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  G_p = (V,E_p) kur

E_p = { ( 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. E_p 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 G_p 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žā G_p 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žā G_p. 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 G^T 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 G^T. (c) Ir aciklisks komponenšu grafs G^SCC 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 G^T = (V,E^T), kur E^T={(u,v):(v,u)∈E)}. Tas ir G^T esošie loki ir apgriezti otrādā virzienā nekā grafā G. Lai konstruētu grafu G^T izmantojot informāciju no blakus virsotņu saraksta ir nepieciešams O(V+E) laiks. Ir japiezime ka G un G^T 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ā G^T. 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š G^T.

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 G^T

3             Izsauc DFS( G^T ) 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ā G^T.

            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 G^T 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 G^T 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ā G^T. 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ā G^T.

            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ā G^T ir atsevišķā stingri savienotā komponente. Katrs solis indukcijā pierāda ka pārmeklēšanas dziļumā koks kas tiek veidots pārmeklējot grafu G^T 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 G^T. 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.