有向無環圖

在圖論中，如果一個有向圖從任意頂點出發無法經過若干條邊回到該點，則這個圖是一個有向無環圖。因為有向無環圖中從一個點到另一個點有可能存在兩種路線，因此有向無環圖未必能轉化成樹，但任何有向樹均為有向無環圖。定義.圖由頂點和連線這些頂點的邊所構成。每條邊都帶有從一個頂點指向另一個頂點的方向的圖為有向圖。有向圖中的道路為一系列的邊，系列中每條邊的終點都是下一條邊的起點。如果一條路徑的起點是這條路徑的終點，那麼這條路徑就是一個環。有向無環圖即為沒有環出現的有向圖。當存在一條從頂點u的。每個頂點都是從自身可達的到達自身，那麼這條路徑就是一個環。因此，有向無環圖也可以被定義為沒有頂點可以透過非平凡路徑到達自身的圖。數學性質.可達性，傳遞閉包和傳遞迴約.有向無環圖的可達性可以用其頂點的偏序關係"a" ≤ "b" ≤ "c"。對於一個有向無環圖G的可達性關係。有向無環圖"u" → "v"。傳遞約簡和傳遞閉包都是有向無環圖的特有概念。相反的，對於有向有環圖，可以存在多個與原圖有著相同可達性的最簡子圖。對於有向無環圖G的子圖。傳遞規約在圖示有向無環圖的偏序關係時十分有用，因為它們比其他具有相同偏序關係的圖的邊數要少，這簡化了繪圖。偏序關係的哈斯圖由將傳遞規約中的每條邊的起點繪製在其終點的下方而得到。拓撲排序.有向無環圖的拓撲排序為所有邊的起點都出現在其終點之前的排序。能構成拓撲排序的圖一定沒有環，因為環中的一條邊必定從排序較後的頂點指向比其排序更前的頂點。基於此，拓撲排序可以被用來定義有向無環圖：當且僅當一個有向圖有拓撲排序，它是有向無環圖。一般情況下，拓撲排序並非唯一。有向無環圖僅僅在存在一條路徑可以包含其所有頂點的情況下，有唯一的拓撲排序方式，這時，拓撲排序與它們在這條路徑中出現的順序相同。有向無環圖的拓撲排序族等同於其可達性的族。 因此，偏序關係相同的任意兩個圖會有相同的拓撲排序集。組合計數.如標號頂點在拓撲排序中出現的順序不受限制，有n個頂點的標號有向無環圖的數量為1, 1, 3, 25, 543, 29281, 3781503, … 。其中"n" = 0, 1, 2, 3,……。這個數列的遞推關係式是formula_1埃裡克·韋斯坦因推測，I保持了所有矩陣因子都是0或1的特性。相關概念.由將自由樹的邊而得到。 多重樹必定是有向無環圖。對於有根樹，將其所有邊賦予指離根的方向也可以得到有向無環圖，即樹狀圖。是每兩個頂點最多被一條路徑所連線的有向無環圖。等價的說，它是滿足以下性質的一個有向無環圖：對於圖中每個頂點v可達的頂點組成一顆樹。相關計算問題.拓撲排序和識別.可以用線性時間複雜度的卡恩演算法來找到一個有向無環圖的拓撲排序。簡單來說，開設一個存放結果的列表L。重複上述操作，直到找不到入度為零的節點。 另外一種構造拓撲排序的演算法是將深度優先搜尋的後序遍歷結果翻轉。檢查一個有向圖是否為有向無環圖亦可線上性時間內完成。一種方法是先找到一個拓撲排序，然後測試這個排序是否能符合圖中每條邊所連頂點在排序中應該出現的順序。 對於卡恩演算法在內的部分拓撲排序演算法，透過在演算法終止時判斷是否滿足一定條件即可知道圖是否有環。如果有環，卡恩演算法最終獲得的L中節點個數會與圖的節點總數不同。從其他圖構建.任意無向圖都可以被轉化為有向無環圖。構造方法是選定一個頂點的全序關係，並將無向圖中所有邊從全序關係中較前的頂點指向較後的頂點。這種方法是方法中的。不同的全序關係可能推出相同的無環定向，因此一個包含"χ"(−1)。任意有環有向圖都可以被轉化為有向無環圖。只要從圖中移除或，即對於圖中每個環，至少包括環中一個頂點或邊的集合。不過，找到反饋節點或邊的最小集合是NP困難問題。 另外一種方法將有環有向圖去環的方法是將每個強連通分量收縮為一個頂點。 對於無環圖，它的最小反饋頂點或邊集為空集，它的強連通分量則為自身。傳遞閉包和傳遞約簡.有向無環圖的傳遞閉包可以透過廣度優先搜尋或深度優先搜尋對每個節點測試可達性來構建。演算法對於一個有著"O"("mn")。不論在哪種傳遞閉包演算法中，那些被一條長度至少為2的路徑所連線的頂點對，都可以和只有一條長度為1的路徑所連線的頂點對區分開。由於傳遞約簡包含後者，傳遞約簡可以在和傳遞閉包相同的中被構建。閉包問題.閉包是一個圖中沒有出邊的頂點子集，即不存在從子集中頂點指向子集外頂點的邊。是則是找到帶權圖中使得權之和最大或最小的子集。閉包問題可以看作最大流問題的簡化版，在多項式時間內被解決。實際上，是否有環對於找到閉包沒有影響。最短或最長路徑問題.基於拓撲排序的性質，有向無環圖的最短路問題和最長路徑問題可以線上性時間內解決。將頂點拓撲排序後，從前到後遍歷每一個頂點，對於遍歷到的頂點，更新其所有出邊所到達頂點的長度值。如果求最短路，則在本邊是更短路徑的一部分時更新。求最長路則反之。對於非有向無環圖，最短路需要用複雜度為formula_2的戴克斯特拉演算法或formula_3的貝爾曼-福特演算法等。最長路徑則是一個NP困難問題。應用.排程.有向無環圖的偏序關係可以在排程有著先後順序限制的系統任務中發揮作用。排程問題的一個重要種類是串聯需要更新的物件，如電子試算表中某個單元格的計算公式依賴於其他單元格，或在程式的原始碼被修改後重新編譯目標檔案。則記錄了這種更新依賴關係。其每個頂點對應一個需要被更新的物件，邊則表示更新的關係。依賴圖中的環被稱為。環狀依賴通常是不被允許出現的，因為不能保證圈內任務排定順序的一致性。無環的依賴圖即為有向無環圖。舉例來說，當電子表格中一個單元格的數值發生改變，其他直接或間接依賴於該單元格的所有單元格的值都需要被重新計算。被排程的任務為重新計算某個特定單元格的值。當一個單元格的值取決於另外一個單元格時，兩個單元格之間則有依賴關係。每個被依賴單元格的值的計算過程都必須先於使用它的表示式執行。使用依賴圖的拓撲排序來排程任務使得在每個單元格的值都僅被重新計算一次的情況下，整個工作表都能被更新。相似的任務排程場景出現在程式原始碼編譯的，和最佳化計算機程式底層執行的指令排程中。計劃評審技術是一種基於有向無環圖的計劃排定技術，通常用於組織大型的人工專案。在計劃評審技術中，每個頂點表示專案的一個，每條有向邊表示任務或者活動，連線著表示任務開始或結束的兩個節點。每條邊則被標註上預估需時。圖中的最長路徑即為專案的關鍵路徑。關鍵路徑決定了專案所需的總時間，里程碑的完成時間取決於結束於本頂點的最長路徑。資料處理網路.有向無環圖可以用於表示處理資料的元素網路。在網路中，資料從一個元素頂點的入邊進入，處理後從出邊離開。在電子電路設計中，靜態組合邏輯電路塊可以被表示為由邏輯閘組成的有向無環系統。每個邏輯閘對輸入做一次函式處理，輸入和輸出均為一個位元組。通常，這些電路塊的輸出不能夠再作為輸入，除非它們被儲存在暫存器或者狀態單元中，以保證圖不出現環。語言描述針對的操作，以及操作的輸出和其他操作的輸入之間的關係。這型別的語言使得描繪高重複率資料處理任務的變得更加簡單，因為同樣的資料操作可以應用於許多資料項。資料操作可以用有向無環圖來表示。這些資料操作可以被併發執行，從而高效利用多核心處理器。在編譯器中，直線碼可以使用有向無環圖表示。圖標示出每個算術運算的輸入和輸出。這種表示法讓編譯器能執行，使得程式碼更高效。因果結構.用頂點表示事件，邊表示因果關係的圖通常是無環的。事件由時間上的先後順序來排列，所有箭頭遵循從先發生事件指向後發生事件的原則，因此也不存在環。舉例來說，貝氏網路表示多個機率事件的關聯網路。頂點表示事件，後續事件的發生可能性則可以透過其在有向無環圖的前驅節點的發生機率計算出來。在此基礎上，一個有向無環圖的透過以下方法而得到：將單個頂點的所有父節點之間新增一條無向邊，再將所有的有向邊換成無向邊。另外一種具有相似因果結構的圖是。其頂點表示決策或不確定的事件，邊表示兩個頂點之間的因果關係。在流行病學中，這些表示因果關係的圖表常常用來評估不同干預手段的效果。系譜學和版本歷史.譜系圖可以看作是有向無環圖，頂點代表家族成員，邊代表親子關係。雖然譜系圖也被稱作為家族“樹”, 但近親結婚導致的會違反樹的性質。即一個孩子的祖先既可以從父親向上追溯，也可以從母親一側。圖中的母系血統和父系血統則可以看作為樹。因為沒有人可以是自己的祖先，譜系圖是無環的。基於相同的原因， 一個分散式版本控制系統的版本歷史的結構也是有向無環圖。在系統中，每個版本對應一個節點。邊連線起有直接衍生關係的兩個版本。由於分支合併的存在，這個結構並不能用樹來表示。在計算幾何領域，許多隨機化演算法都會維護一個“歷史有向無環圖”，用以記錄結構變動中的舊幾何結構。例如，在德勞內三角化的隨機增量演算法中，在新增每個點時，透過用三個較小的三角形替換一個三角形，以及透過“翻轉”操作將三角形對替換為另一對三角形，來改變三角剖分。在該演算法的歷史有向無環圖中，每個在演算法中構建出的三角形對應一個頂點，邊則將每個三角形和替代它的兩個或三個三角形連線起來。這種圖結構可以高效地處理問題，即對於一個查詢點q的替代三角形組，最後到達的終點必定代表包含q的德勞內三角形。引用圖.在中， 每個頂點代表單篇著作，邊代表著作之間的引用關係。1965年普萊斯的文章“科學網路”是使用引用圖的一個經典例子。在引用圖中，每篇論文的為對應頂點的入度。這是引文分析中的一種重要的展示方式。另一個例子是法律裁判中，法官透過引用過往案例中的判決來支援他們的結論。引用圖亦可以用來描繪專利，因為專利必須要提及現有技術，即已經公開的並且和本專利有關的先前專利。相較於網路科學中對一般圖的研究，有向無環圖的獨特性質可以被用來作深層次分析。例如，傳遞規約可以呈現引用在不同應用領域的分佈情況，這突出了不同領域中不同的引用網構造機制。引用圖的衍生概念還有，即對引用圖中最顯著的一條路徑的分析。資料壓縮.有向無環圖也可以用於對一系列序列的壓縮中。在這裡，有向無環圖中的路徑代表這些序列。當多個序列有共同的子序列時，子序列可以被表示為這些序列對應路徑的公共邊。比起直接列出所有序列，這種方法佔用更少空間。例如，為僅含單個源的路徑均代表一個字串，字串可以是英文單詞。與其結構不同但功能相似的樹稱為trie。相比於trie，有向無環詞圖允許多條邊指向同一個頂點，使得具有相同字尾的一些詞的詞頭可以被相同的頂點所表示，因而更省空間。二元決策圖是基於有向無環圖的一種資料結構，用於表示布林函式。在二元決策圖中，每個非匯節點對應一個布林變數，每個匯和邊則表示0或1。要找到一個解釋的真值，只要從唯一的源頂點出發，沿著該頂點代表的布林變數的實際真值所對應的出邊一直前進，到達的匯則為其真值。如同有向無環詞圖可以被看作是trie的一種壓縮形式一樣，二元決策圖可以被看作是決策樹的壓縮形式。它透過將導向相同結果的邊重新匯合到一個頂點來節省空間。