десно|оквир|Пример директног ацикличног графа
Директан ациклични граф (ДАГ) у математици и информатици је директан граф без усмерених циклуса. Састоји се од збира чворова и усмерених грана, свака грана повезује један чвор са другим, тако да не постоји начин да се почне у неком чвору в и прати редослед грана који се на крају петље опет враћа на чвор в.
ДАГ може да се користи за моделирање многих различитих врста информација. Достизање везе у ДАГ форми делимичног реда, и било ког коначно делимичног реда може бити представљен од стране ДАГ који користи достизање. Колекција задатака која се мора одредити у низу, уз ограничење да морају бити извршени одређени задаци раније од других, може бити представљен као ДАГ са чвором за сваки задатак и граном за сваку препреку; алгоритми за тополошко уређење могу се користити за одређивање исправног низа. Додатно, ДАГ може да се користи као простор ефикасне заступљености низова са преклапајућим поднизовима. ДАГ се такође користи за представљање система догађаја или потенцијалних догађаја и узрочно–последичних односа између њих. ДАГ се такође може користити за моделовање процеса у којима је проток података у доследном правцу кроз мрежу процесора, или стања репозиторијума у верзији контроле система.
Одговарајући концепт неусмерених графова је шума, један неусмерен граф без циклуса. Избор оријентације за шуме производи посебну врсту директног ацикличног графа који се зове оријентисано стабло. Међутим, постоје многе друге врсте директног ацикличног графа које нису формиране прем оријентацији грана једног неусмереног ацикличног графа. Осим тога, сваки неусмерени граф има ацикличну оријентацију, доделу правца за своје гране које га чине директним ацикличним графом. Из тих разлога било би прецизније назвати директан ациклични граф ацикличан усмерени граф или ацикличан диграф.
Математичка својства
Достизање, транзитивно затворење, и транзитивна редукција мини|300px|Хасеов дијаграм који представља парцијалан ред ⊆ између подскупова од три елемента скупа. Сваки усмерени ациклични граф доводи до парцијалног реда ≤ на својим чворовима, где је у ≤ в тачно када постоји директан пут од у до в у ДАГ. Међутим, много различитих ДАГ може довести до тог истог достижности односа:. Loop Transformations for Restructuring Compilers: The Foundations. на пример, ДАГ са две гране а → б и б → ц има исто достизање као и граф са три гране а → б, б → ц, и а → ц. Ако је Г ДАГ, његова транзитивна редукција је граф са најмањим бројем грана који представља исто достизање као и за Г, а његово транзитивно затворење је граф са највише грана који представља исто достизање. Транзитивна редукција и транзитивно затворење су јединствено дефинисани за ДАГ; насупрот томе, за усмерени граф који није ацикличан, не може бити више од једног минималног подграфа са истим достизањем односа., Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics.
Транзитивно затварање на Г има једну грану у → в за сваки везани пар у ≤ в различитих елемената у достизању односа Г, и тако се може посматрати као директан превод достизања односа ≤ у граф - теоријском смислу: сваки парцијални ред скупа може се превести у ДАГ на овај начин. Ако ДАГ Г представља парцијални ред ≤, онда је транзитивна редукција од Г подграф од Г са једном граном у → в за сваки пар у пропратном односу ≤; транзитивне редукције су корисне у визуализацији парцијалних редова које они представљају, јер имају мање грана од других графова који представљају исте редове и самим тим доводе до једноставнијих цртежа графова. Хасе дијаграм парцијалног ред је цртеж транзитивне редукције у којима је оријентација сваке гране приказана тако да је почетни чвор гране на нижем нивоу него његов крајњи чвор.
Тополошко сортирање Сваки директан ациклични граф има тополошко сортирање, тј. редослед чворова је такав да се почетак крајње тачке сваке гране јавља раније у сортирању од краја крајње тачке гране. У принципу, ово сортирање није јединствено; ДАГ има јединствено тополошко сортирање ако и само ако има усмерен пут који садржи све врхове, у ком случају сортирање је исто као и ред у којем се чворови појављују на путу.. Algorithms . Породица тополошког сортирања једног ДАГ је иста као и породица линеарних продужетака достижности у односу на ДАГ,. A Short Course in Discrete Mathematics, Dover Books on Computer Science. , тако било која два графа представљају исти парцијални ред са истим скупом тополошких редова. Комбинаторно набрајање Проблем графа набрајања бројања директног ацикличног графа испитивао је Робинсон (1973).. See also Број ДАГ са н обележених чворова, за н = 0, 1, 2, 3,....,(дозвољавајући да се ови бројеви појаве у било ком реду у тополошком сортирању ДАГ) је 1, 1, 3, 25, 543, 29281, 3781503, … (ред A003024 у OEIS).
Ови бројеви се могу израчунати понављањем везе:
Ерик В. Вејнстејн је претпоставио,Weisstein, Eric W., "Weisstein's Conjecture", MathWorld. а Макеј, Ројл, Ванлер и Оџијер доказали, да исти бројеви броје (0,1) матрице у којој су све својствене вредности позитивни реални бројеви. Доказ је бијекција: Матрица А је матрица повезаности ДАГ ако и само ако је А + И (0,1) матрица са свим својствено позитивним вредностима, где И означава матрицу идентитета. Зато што ДАГ не може имати циклус, његова суседна матрица мора имати нула дијагоналу, додајући И да сачува особине да су све матрице коефицијента 0 или 1.
Веза породице графа Оријентисано стабло је усмерени граф формиран према оријентацији грана слободног стабла.. In: Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987 (PDF). Свако оријентисано стабло је ДАГ. Конкретно, истина је да су стабла формирана на основу усмерења свих грана од споља ка корену стабла. Снажно недвосмислен граф представља усмерени граф у којем постоји највише једна усмерена путања (у оба смера) између било која два чвора; евентуално, то је ДАГ у којем, за сваки чвор в, постоји скуп чворова доступних из в обликовног стабла.
Рачунарски проблеми
Тополошко сортирање и препознавање
Тополошко сортирање је алгоритам проблема проналажења тополошког сортирања; може се решити у линеарном времену. Section 22.4, Topological sort. Канов алгоритам за тополошко сортирање гради чворове директног сортирања, одржавајући листу чворова који немају гране, повезујући их са чворовима који нису већ наведени, а више пута додајући један такав чвор на крај листе која се оснива. Алтернативно, тополошко сортирање се може конструисати уназад после сортирања нумерације од прве претраге у дубину графа.
Такође је могуће да се провери да ли је дати усмерени граф ДАГ у линеарном времену или је било покушаја да нађе тополошко сортирање а затим тестирање за сваку грану да ли је различито сортирање исправноFor depth-first search based topological sorting algorithm, this validity check can be interleaved with the topological sorting algorithm itself; see e.g. Skiena, Steven S. , The Algorithm Design Manual. или алтернативно, за неке алгоритме тополошког сортирања, проверава се да ли алгоритам успешно сортира све чворове без грешке.
Грађа цикличних графова Сваки неусмерени граф може бити у ДАГ избором укупног сортирања својих чворова и оријентације својих грана из раније крајње тачке у сортиране касније крајње тачке. Међутим, различита потпуна сортирања могу довести до исте ацикличне оријентације. Број ацикличних оријентација је једнак |χ(−1)|, где је χ хроматски полином датог графа.
Било који усмерени граф се може представити као ДАГ тако што се уклони скуп повратних чворова или скупа повратних лукова. Међутим, најмањи такав скуп је НП-тешки проблеми.Garey, Michael R.; Johnson, David S. , Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman. Problems GT7 and GT8. Произвољно усмерен граф може да се трансформише у ДАГ, назива се кондензација, уговарањем сваке од његових чврсто повезаних компоненти у један суперчвор.Harary, Frank; Norman, Robert Z.; Cartwright, Dorwin : Structural Models: An Introduction to the Theory of Directed Graphs, John Wiley & Sons. Када је граф већ ацикличан његов најмањи скуп повратних информација чворова и скуп повратних информација лукова су празни, а његова кондензација је сам граф.
Транзитивно затворење и транзитивна редукција Транзитивно затворење датог ДАГ, са n чворова и m грана, може се конструисати у времену O(mn) користећи или претрагу у ширину или претрагу у дубину ради тестирања достизања до сваког чвора. Алтернативно, може се решити и у времену O(nω) где је ω < 2.373 експонент за брзо множење алгоритама матрице; ово је теоретски напредак у односу на O(mn) везан за густе графове.
У свим овим алгоритмима транзитивног затворења, могуће је разликовати парове чворова који су доступни најмање једне путање дужине два или више од парова који се могу повезати само од дужине једне путање. Транзитивна редукција састоји се од грана чије су дужине једне путање једине путање које повезују своје крајње тачке. Стога, транзитивна редукција се може конструисати у истом асимптотском времену граничних линија као и транзитивна затвореност.
Проблем затворења
Проблем затворења узима као улаз директан ациклични граф са тежинама њених чворова и тражи минималну (или максималну) тежину затварања, скуп чворова без икаквих одлазећих грана. (Проблем може бити формулисан за усмерене графове без претпоставке да су ациклични, али без веће уопштености јер у овом случају је еквивалентан са проблемом кондензације графова.) Може се решити у полиномијалном времену користећи смањен максималан проблем тока.
Апликације
Алгоритам путање Неки алгоритми постају једноставнији када се користи ДАГ уместо општих графова, на основу принципа тополошког сортирања. На пример, могуће је наћи најкраће путеве и најдуже путеве са датим почетним чвором у ДАГ у линеарном времену обрадом чворова у тополошком реду, и израчунавање дужине пута за сваки чвор да буде минимална или максимална дужина добијена преко претходних грана. Насупрот томе, за произвољне графове најкраћи пут може захтевати спорији алгоритам као што је Дајкстрин алгоритам или Белман-Фордов алгоритам,Cormen et al. 2001, Sections 24.1, The Bellman–Ford algorithm. стр. 588–592, and 24.3, Dijkstra's algorithm. и најдужи пут у произвољном графу је НП-тешки проблеми.
Распоређивање ДАГ репрезентације парцијалног сортирања има много захтева у распореду проблема за системе задатака са ограниченим сортирањем. На пример, ДАГ може користити табелу за описивање зависности између ћелија: ако се једна ћелија израчунава по формули која укључује вредност друге ћелије, нацртати ДАГ грану од друге ћелије до прве. Ако се улазне вредности табеле промене, све преостале вредности табеле могу се прерачунати са једном променом по ћелији, од тополошког сортирања ћелија и поново вреднује сваку ћелију у том циљу. Слични проблеми задатка сортирања настаје у прављењу фајлова за компилацију програма, упутство за распоред за низак ниво оптимизације рачунарског програма,Srikant, Y. N.; Shankar, Priti . The Compiler Design Handbook: Optimizations and Machine Code Generation, . и Перт распоред за управљање великих људских пројеката. График зависности без кружне зависности облика директног ацикличног графа.
Обрада података мреже Усмерен граф може да се користи за представљање мреже за обраду елемената; у овој формулацији подаци, улазни подаци обрађују елемент преко претходних грана и напуштају елемент преко одлазећих грана. Примери овога обухватају следеће: