Virzīts aciklisks grafs

Matemātikā, īpaši grafu teorijā un datorzinātnēs, virzīts aciklisks (tāds, kam nav raksturīgs noslēgts cikls) grafs ir datu struktūra bez noteiktiem cikliem. Tas ir, 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.<ref>{{Grāmatas atsauce|title=Graphs : theory and algorithms|url=https://www.worldcat.org/oclc/24468032|publisher=Wiley|date=1992|location=New York|isbn=0-471-51356-3|oclc=24468032|first=K.|last=Thulasiraman}}</ref>

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 tas, ka tie ir grafi, kuros neviena virsotne nevar sasniegt sevi, izmantojot netriviālus ceļus.