Virzīts aciklisks grafs

Virzīts aciklisks grafs matemātikā, īpaši grafu teorijā un datorzinātnēs, ir acikliska (tāda, kam nav raksturīgs noslēgts cikls) datu struktūra bez noteiktiem cikliem. Tas sastāv no virsotnēm un šķautnēm (sauktas arī par lokiem), un katra šķautne ir vērsta no vienas virsotnes uz otru tā, ka šo virzienu ievērošana nekad neveido slēgtu cilpu. Virzīts grafs ir aciklisks tad un tikai tad, ja to var sakārtot topoloģiski, sakārtojot virsotnes kā lineāru secību, kas atbilst visiem malu virzieniem. Virzītiem acikliskiem grafiem ir daudz pielietojumu skaitļošanā un zinātnē kā tādā, sākot no bioloģijas (evolūcija, ciltskoki, epidemioloģija) līdz socioloģijai (citēšanas tīkli) un aprēķiniem (plānošanai).

Definīcija

Grafu veido virsotnes un virsotņu pārus savienojošas šķautnes, kur virsotnes var būt jebkura veida objekts, kas ir savienots pa pāriem ar šķautnēm. Virzīta grafa gadījumā katrai šķautnei ir orientācija, no vienas virsotnes uz otru virsotni. Ceļš virzītā grafā ir šķautņu virkne ar īpašību, ka katras secīgas šķautnes beigu virsotne ir tāda pati kā secības nākamās šķautnes sākuma virsotne; ceļš veido ciklu, ja tā pirmās šķautnes sākuma virsotne ir vienāda ar pēdējās šķautnes beigu virsotni. Virzīts aciklisks grafs ir virzīts grafs, kuram nav ciklu.^[1]

Tiek uzskatīts, ka virzīta grafa virsotne v ir sasniedzama no citas virsotnes u, ja pastāv ceļš, kas sākas ar u un beidzas ar v. Īpašā gadījumā katra virsotne tiek uzskatīta par sasniedzamu no sevis (pa ceļu ar nulli šķautnēm). Ja virsotne var sasniegt sevi pa netriviālu ceļu (ceļš ar vienu vai vairākām šķautnēm), tad šis ceļš ir cikls, tāpēc vēl viens veids, kā definēt virzītus acikliskus grafus, ir — ka tie ir grafi, kuros neviena virsotne nevar sasniegt sevi, izmantojot netriviālus ceļus.

Pielietojums

Datu apstrādes tīkli

Elementu apstrādes tīkla attēlošanai var izmantot virzītu aciklisku grafu. Šajā attēlojumā datus ievada apstrādes elementā caur tā ienākošajām šķautnēm un atstāj elementu caur tā izejošajām šķautnēm.

Piemēram, elektronisko shēmu projektēšanā statiskos kombinētos loģiskos blokus var attēlot kā aciklisku loģisko vārtu sistēmu, kas aprēķina ieejas funkciju, kur funkcijas ievade un izvade tiek attēlota kā atsevišķi biti. Parasti šo bloku izvadi nevar izmantot kā ievadi, ja vien to neuztver reģistrs vai stāvokļa elements, kas saglabā savas acikliskās īpašības. Elektroniskās ķēžu shēmas uz papīra vai datubāzē ir virzītu aciklisku grafu veids, izmantojot gadījumus vai komponentus, lai veidotu mērķētu atsauci uz zemāka līmeņa komponentu. Pašas elektroniskās shēmas ne vienmēr ir acikliskas vai virzītas.

Datu plūsmu programmēšanas valodas apraksta operāciju sistēmas datu plūsmās un saistību starp dažu darbību izvadēm un citu ievadēm. Šīs valodas var būt ērtas, lai aprakstītu atkārtotus datu apstrādes uzdevumus, kuros daudziem datu vienumiem tiek piemērota viena un tā pati acikliski saistītā darbību kolekcija. Tos var izpildīt kā paralēlu algoritmu, kurā katru darbību veic paralēls process, tiklīdz tam kļūst pieejama cita ievadu kopa. Kompilatoros taisnās līnijas kodu (tas ir, priekšrakstu secības bez cilpām vai nosacījumu atzariem) var attēlot ar virzītu aciklisku grafu, kas apraksta katras kodā veiktās aritmētiskās darbības ievades un izvades. Šis attēlojums ļauj kompilatoram efektīvi veikt parasto apakšizteiksmju likvidēšanu. Augstākā koda organizēšanas līmenī aciklisko atkarību princips nosaka, ka atkarībām starp lielas programmatūras sistēmas moduļiem vai komponentiem ir jāveido virzīts aciklisks grafs.

Atsauces

1. K. Thulasiraman. Graphs : theory and algorithms. New York : Wiley, 1992. ISBN 0-471-51356-3. OCLC 24468032.

Ārējās saites

• Vikikrātuvē par šo tēmu ir pieejami multivides faili. Skatīt: Virzīts aciklisks grafs.