Loading AI tools
来自维基百科，自由的百科全书
在圖論中，如果一個有向圖從任意頂點出發無法經過若干條邊回到該點，則這個圖是一個有向無環圖（英語：Directed Acyclic Graph，縮寫：DAG）。[1]
因為有向無環圖中從一個點到另一個點有可能存在兩種路線，因此有向無環圖未必能轉化成樹，但任何有向樹均為有向無環圖。
圖由頂點和連接這些頂點的邊所構成。每條邊都帶有從一個頂點指向另一個頂點的方向的圖為有向圖。有向圖中的道路為一系列的邊，系列中每條邊的終點都是下一條邊的起點。如果一條路徑的起點是這條路徑的終點，那麼這條路徑就是一個環。有向無環圖即為沒有環出現的有向圖。[2][3][4]
當存在一條從頂點u到頂點v的路徑時，頂點v被稱作是從頂點u可達的。每個頂點都是從自身可達的（通過一條沒有邊的路徑）。如果一個頂點可以從一個非平凡路徑（一條由一個或更多邊組成的路徑）到達自身，那麼這條路徑就是一個環。因此，有向無環圖也可以被定義為沒有頂點可以通過非平凡路徑到達自身的圖。[5]
有向無環圖的可達性可以用其頂點的偏序關係≤來表示。在偏序關係中，如果存在一條路徑從頂點u指向頂點v，它們的偏序關係可被寫作u ≤ v。這也被稱作v是從u可達的。[6]不同的有向無環圖可以有着相同的可達關係和偏序關係。[7]例如，有兩條邊a → b，b → c的有向無環圖，和有三條邊的a → b, b → c，a → c的有向無環圖有着相同的偏序關係a ≤ b ≤ c。
對於一個有向無環圖G，它的遞移閉包等同於一個在保持與其相同可達性的情況下，邊數最多的圖。在這個圖中，當u可達v的時候，邊u → v必定存在。換句話說，每個G中的非相同元素偏序關係對u ≤ v都在這個圖中有一條邊。這可以被視作用圖來視覺化圖G的可達性關係。
有向無環圖G的遞移規約為和其有着相同可達性，邊數最少的圖。它是G的一個子圖。構造方法為當G有着一條更長的路徑連接頂點u和v的時候，消去邊u → v。 遞移約簡和遞移閉包都是有向無環圖的特有概念。相反的，對於有向有環圖，可以存在多個與原圖有着相同可達性的最簡子圖。[8]
對於有向無環圖G和表達其可達性的偏序關係≤，它的遞移規約也可以看作包含G的覆蓋關係中每一條邊的G的子圖。遞移規約在圖示有向無環圖的偏序關係時十分有用，因為它們比其他具有相同偏序關係的圖的邊數要少，這簡化了繪圖。偏序關係的哈斯圖由將遞移規約中的每條邊的起點繪製在其終點的下方而得到。[9]
有向無環圖的拓撲排序為所有邊的起點都出現在其終點之前的排序。能構成拓撲排序的圖一定沒有環，因為環中的一條邊必定從排序較後的頂點指向比其排序更前的頂點。[3]基於此，拓撲排序可以被用來定義有向無環圖：當且僅當一個有向圖有拓撲排序，它是有向無環圖。一般情況下，拓撲排序並非唯一。有向無環圖僅僅在存在一條路徑可以包含其所有頂點的情況下，有唯一的拓撲排序方式，這時，拓撲排序與它們在這條路徑中出現的順序相同。[10]
有向無環圖的拓撲排序族等同於其可達性的線性拓展族。 [11]因此，偏序關係相同的任意兩個圖會有相同的拓撲排序集。
羅賓遜 (1973)研究了有向無環圖的圖計數問題。[12] 如標號頂點在拓撲排序中出現的順序不受限制，有n個頂點的標號有向無環圖的數量為
其中n = 0, 1, 2, 3,……。這個數列的遞歸關係式是
埃里克·韋斯坦因推測[13]，n個頂點的標號有向無環圖的數量與其中所有特徵值都為正實數的n*n邏輯矩陣的數量相同。這一點隨後被證實，證明採用了對射法：一個矩陣A是有向無環圖的一個鄰接矩陣，當且僅當A + I是一個所有特徵值都為正數的邏輯矩陣，其中I為單位矩陣。因為一個有向無環圖不允許自環，它的鄰接矩陣的對角線必定全為0。因此，加上I保持了所有矩陣因子都是0或1的特性。[14]
多重樹由將自由樹的邊定向而得到。[15] 多重樹必定是有向無環圖。對於有根樹，將其所有邊賦予指離根的方向也可以得到有向無環圖，即樹狀圖。
強明確樹是每兩個頂點最多被一條路徑所連接的有向無環圖。等價的說，它是滿足以下性質的一個有向無環圖：對於圖中每個頂點v，從v可達的頂點組成一顆樹。[16]
可以用線性時間複雜度的卡恩演算法來找到一個有向無環圖的拓撲排序。[17]簡單來說，開設一個存放結果的列表L，先將入度為零的節點放到L中，因為這些節點沒有任何的父節點。將與這些節點相連的邊從圖中去掉，再尋找圖中入度為零的節點。對於新找到的節點來說，他們的父節點已經都在L中了，所以也可以從末端插入L。重複上述操作，直到找不到入度為零的節點。[18] 另外一種構造拓撲排序的演算法是將深度優先搜尋的後序遍歷結果翻轉。[17]
檢查一個有向圖是否為有向無環圖亦可線上性時間內完成。一種方法是先找到一個拓撲排序，然後測試這個排序是否能符合圖中每條邊所連頂點在排序中應該出現的順序。[19] 對於卡恩演算法在內的部分拓撲排序演算法，通過在演算法終止時判斷是否滿足一定條件即可知道圖是否有環。[18]如果有環，卡恩演算法最終獲得的L中節點個數會與圖的節點總數不同。
任意無向圖都可以被轉化為有向無環圖。構造方法是選定一個頂點的全序關係，並將無向圖中所有邊從全序關係中較前的頂點指向較後的頂點。這種方法是定向方法中的無環定向。不同的全序關係可能推出相同的無環定向，因此一個包含n個頂點的圖的無環定向數量小於n!。如果定義χ為給定圖的色多項式，無環定向數量等於|χ(−1)|。[20]
任意有環有向圖都可以被轉化為有向無環圖。只要從圖中移除反饋節點集或反饋邊集，即對於圖中每個環，至少包括環中一個頂點或邊的集合。不過，找到反饋節點或邊的最小集合是NP困難問題。[21] 另外一種方法將有環有向圖去環的方法是將每個強連通分量收縮為一個頂點。[22] 對於無環圖，它的最小反饋頂點或邊集為空集，它的強連通分量則為自身。
有向無環圖的遞移閉包可以通過廣度優先搜尋或深度優先搜尋對每個節點測試可達性來構建。演算法對於一個有着n個頂點和m條邊的有向無環圖的複雜度為O(mn)。[23]也可以使用矩陣乘法演算法中最快的Coppersmith–Winograd演算法，其複雜度為O(n2.3728639)。這個演算法理論上在稠密圖中快過O(mn)。[24]
不論在哪種遞移閉包演算法中，那些被一條長度至少為2的路徑所連接的頂點對，都可以和只有一條長度為1的路徑所連接的頂點對區分開。由於遞移約簡包含後者，遞移約簡可以在和遞移閉包相同的漸進時間複雜度中被構建。[25]
閉包是一個圖中沒有出邊的頂點子集，即不存在從子集中頂點指向子集外頂點的邊。閉包問題是則是找到帶權圖中使得權之和最大或最小的子集。閉包問題可以看作最大流問題的簡化版，在多項式時間內被解決。實際上，是否有環對於找到閉包沒有影響。[26]
基於拓撲排序的性質，有向無環圖的最短路問題和最長路徑問題可以線上性時間內解決。將頂點拓撲排序後，從前到後遍歷每一個頂點，對於遍歷到的頂點，更新其所有出邊所到達頂點的長度值。如果求最短路，則在本邊是更短路徑的一部分時更新。求最長路則反之。[27]對於非有向無環圖，最短路需要用複雜度為的戴克斯特拉演算法或的貝爾曼-福特演算法等。[28]最長路徑則是一個NP困難問題。[29]
有向無環圖的偏序關係可以在排程有着先後順序限制的系統任務中發揮作用。[30]排程問題的一個重要種類是串聯需要更新的物件，如電子試算表中某個儲存格的計算公式依賴於其他儲存格，或在程式的原始碼被修改後重新編譯目標文件。依賴圖則記錄了這種更新依賴關係。其每個頂點對應一個需要被更新的物件，邊則表示更新的關係。依賴圖中的環被稱為環狀依賴。環狀依賴通常是不被允許出現的，因為不能保證圈內任務排定順序的一致性。無環的依賴圖即為有向無環圖。[31]
舉例來說，當電子試算表中一個儲存格的數值發生改變，其他直接或間接依賴於該儲存格的所有儲存格的值都需要被重新計算。被排程的任務為重新計算某個特定儲存格的值。當一個儲存格的值取決於另外一個儲存格時，兩個儲存格之間則有依賴關係。每個被依賴儲存格的值的計算過程都必須先於使用它的表達式執行。使用依賴圖的拓撲排序來排程任務使得在每個儲存格的值都僅被重新計算一次的情況下，整個工作表都能被更新。[32]相似的任務排程場景出現在程式原始碼編譯的makefile，[32]和最佳化電腦程式底層執行的指令排程中。[33]
計劃評審技術是一種基於有向無環圖的計劃排定技術，通常用於組織大型的人工專案。在計劃評審技術中，每個頂點表示專案的一個里程碑，每條有向邊表示任務或者活動，連接着表示任務開始或結束的兩個節點。每條邊則被標註上預估需時。圖中的最長路徑即為專案的關鍵路徑。關鍵路徑決定了專案所需的總時間，里程碑的完成時間取決於結束於本頂點的最長路徑。[34]
有向無環圖可以用於表示處理數據的元素網絡。在網絡中，數據從一個元素頂點的入邊進入，處理後從出邊離開。
在電子電路設計中，靜態組合邏輯電路塊可以被表示為由邏輯門組成的有向無環系統。每個邏輯門對輸入做一次函數處理，輸入和輸出均為一個位元組。通常，這些電路塊的輸出不能夠再作為輸入，除非它們被儲存在暫存器或者狀態單元中，以保證圖不出現環。[35]
數據式編程語言描述針對數據流的操作，以及操作的輸出和其他操作的輸入之間的關係。這類型的語言使得描繪高重複率數據處理任務的變得更加簡單，因為同樣的數據操作可以應用於許多數據項。數據操作可以用有向無環圖來表示。這些數據操作可以被並行執行，從而高效利用多核心處理器。[36]
在編譯器中，直線碼（不含條件分支和迴圈的代碼段）可以使用有向無環圖表示。圖示示出每個算術運算的輸入和輸出。這種表示法讓編譯器能執行通用子表達式刪除，使得代碼更高效。[37]
用頂點表示事件，邊表示因果關係的圖通常是無環的。[38]事件由時間上的先後順序來排列，所有箭頭遵循從先發生事件指向後發生事件的原則，因此也不存在環。
舉例來說，貝氏網絡表示多個概率事件的關聯網絡。頂點表示事件，後續事件的發生可能性則可以通過其在有向無環圖的前驅節點的發生概率計算出來。[39]在此基礎上，一個有向無環圖的端正圖通過以下方法而得到：將單個頂點的所有父節點之間添加一條無向邊，再將所有的有向邊換成無向邊。[40]
另外一種具有相似因果結構的圖是影響圖。其頂點表示決策或不確定的事件，邊表示兩個頂點之間的因果關係。[41]在流行病學中，這些表示因果關係的圖表常常用來評估不同干預手段的效果。[42][43]
譜系圖可以看作是有向無環圖，頂點代表家族成員，邊代表親子關係。[44]雖然譜系圖也被稱作為家族「樹」, 但近親結婚導致的血統崩潰會違反樹的性質。即一個孩子的祖先既可以從父親向上追溯，也可以從母親一側。[45]圖中的母系血統和父系血統則可以看作為樹。因為沒有人可以是自己的祖先，譜系圖是無環的。[46]
基於相同的原因， 一個分散式版本控制系統的版本歷史的結構也是有向無環圖。在系統中，每個版本對應一個節點。邊連接起有直接衍生關係的兩個版本。由於分支合併的存在，這個結構並不能用樹來表示。[47]
在計算幾何領域，許多隨機化演算法都會維護一個「歷史有向無環圖」，用以記錄結構變動中的舊幾何結構。例如，在德勞內三角化的隨機增量演算法中，在添加每個點時，通過用三個較小的三角形替換一個三角形，以及通過「翻轉」操作將三角形對替換為另一對三角形，來改變三角剖分。在該演算法的歷史有向無環圖中，每個在演算法中構建出的三角形對應一個頂點，邊則將每個三角形和替代它的兩個或三個三角形連接起來。這種圖結構可以高效地處理點定位問題，即對於一個查詢點q，找到它在德勞內三角剖分中的位置。在歷史有向無環圖中，從起點開始，不斷移動到包含q的替代三角形組，最後到達的終點必定代表包含q的德勞內三角形。[48]
在參照圖中， 每個頂點代表單篇著作，邊代表著作之間的參照關係。1965年普萊斯的文章「科學文獻的網絡」是使用參照圖的一個經典例子。[49]在參照圖中，每篇論文的參照次數為對應頂點的入度。這是引文分析中的一種重要的展示方式。另一個例子是法律裁判中，法官通過參照過往案例中的判決來支持他們的結論。參照圖亦可以用來描繪專利，因為專利必須要提及現有技術，即已經公開的並且和本專利有關的先前專利。
相較於網絡科學中對一般圖的研究，有向無環圖的獨特性質可以被用來作深層次分析。例如，遞移規約可以呈現參照在不同應用領域的分佈情況，這突出了不同領域中不同的參照網構造機制。[50]參照圖的衍生概念還有主幹道路分析，即對參照圖中最顯著的一條路徑的分析。
有向無環圖也可以用於對一系列序列的壓縮中。在這裏，有向無環圖中的路徑代表這些序列。當多個序列有共同的子序列時，子序列可以被表示為這些序列對應路徑的公共邊。比起直接列出所有序列，這種方法佔用更少空間。例如，有向無環詞圖為僅含單個源（入度為0的頂點）的有向無環圖，其每條邊附有一個或多個字元。每條其源到匯（出度為0的節點）的路徑均代表一個字串，字串可以是英文單詞。[51]與其結構不同但功能相似的樹稱為trie。相比於trie，有向無環詞圖允許多條邊指向同一個頂點，使得具有相同字尾的一些詞的詞頭可以被相同的頂點所表示，因而更省空間。[52]
二元決策圖是基於有向無環圖的一種數據結構，用於表示布林函數[53][54]。在二元決策圖中，每個非匯節點對應一個布林變數，每個匯和邊則表示0或1。要找到一個解釋的真值，只要從唯一的源頂點出發，沿着該頂點代表的布林變數的實際真值所對應的出邊一直前進，到達的匯則為其真值。如同有向無環詞圖可以被看作是trie的一種壓縮形式一樣，二元決策圖可以被看作是決策樹的壓縮形式。它通過將導向相同結果的邊重新匯合到一個頂點來節省空間。[55]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
