跳至內容

有向無環圖

本頁使用了標題或全文手工轉換
維基百科，自由的百科全書
  「DAG」重新導向至此。關於其他用法，請見「DAG (消歧義)」。
一個有向無環圖的例子

在圖論中，如果一個有向圖從任意頂點出發無法經過若干條邊回到該點，則這個圖是一個有向無環圖（英語：Directed Acyclic Graph，縮寫：DAG）。[1]

因為有向無環圖中從一個點到另一個點有可能存在兩種路線，因此有向無環圖未必能轉化成樹，但任何有向樹均為有向無環圖。

定義

[編輯]

圖由頂點和連接這些頂點的邊所構成。每條邊都帶有從一個頂點指向另一個頂點的方向的圖為有向圖。有向圖中的道路為一系列的邊，系列中每條邊的終點都是下一條邊的起點。如果一條路徑的起點是這條路徑的終點，那麼這條路徑就是一個環。有向無環圖即為沒有環出現的有向圖。[2][3][4]

在以藍線標識的有向無環圖中，添加紅線從而得到其遞移閉包

當存在一條從頂點u到頂點v的路徑時，頂點v被稱作是從頂點u可達（英語：Reachability）的。每個頂點都是從自身可達的（通過一條沒有邊的路徑）。如果一個頂點可以從一個非平凡路徑（一條由一個或更多邊組成的路徑）到達自身，那麼這條路徑就是一個環。因此，有向無環圖也可以被定義為沒有頂點可以通過非平凡路徑到達自身的圖。[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的遞移規約為和其有着相同可達性，邊數最少的圖。它是G的一個子圖。構造方法為當G有着一條更長的路徑連接頂點u和v的時候，消去邊u → v。 遞移約簡和遞移閉包都是有向無環圖的特有概念。相反的，對於有向有環圖，可以存在多個與原圖有着相同可達性的最簡子圖。[8]

將{ x, y, z }的冪集按包含偏序排序得到的哈斯圖

對於有向無環圖G和表達其可達性的偏序關係≤，它的遞移規約也可以看作包含G的覆蓋關係（英語：covering relation）中每一條邊的G的子圖。遞移規約在圖示有向無環圖的偏序關係時十分有用，因為它們比其他具有相同偏序關係的圖的邊數要少，這簡化了繪圖。偏序關係的哈斯圖由將遞移規約中的每條邊的起點繪製在其終點的下方而得到。[9]

拓撲排序

[編輯]

有向無環圖的拓撲排序為所有邊的起點都出現在其終點之前的排序。能構成拓撲排序的圖一定沒有環，因為環中的一條邊必定從排序較後的頂點指向比其排序更前的頂點。[3]基於此，拓撲排序可以被用來定義有向無環圖：當且僅當一個有向圖有拓撲排序，它是有向無環圖。一般情況下，拓撲排序並非唯一。有向無環圖僅僅在存在一條路徑可以包含其所有頂點的情況下，有唯一的拓撲排序方式，這時，拓撲排序與它們在這條路徑中出現的順序相同。[10]

有向無環圖的拓撲排序族等同於其可達性的線性拓展（英語：linear extension）族。 [11]因此，偏序關係相同的任意兩個圖會有相同的拓撲排序集。

組合計數

[編輯]

羅賓遜 (1973)研究了有向無環圖的圖計數（英語：graph enumeration）問題。[12] 如標號頂點在拓撲排序中出現的順序不受限制，有n個頂點的標號有向無環圖的數量為

1, 1, 3, 25, 543, 29281, 3781503, … （OEIS數列A003024）。

其中n = 0, 1, 2, 3,……。這個數列的遞歸關係式是

[12]

埃里克·韋斯坦因推測[13]，n個頂點的標號有向無環圖的數量與其中所有特徵值都為正實數的n*n邏輯矩陣的數量相同。這一點隨後被證實，證明採用了對射法：一個矩陣A是有向無環圖的一個鄰接矩陣，當且僅當A + I是一個所有特徵值都為正數的邏輯矩陣，其中I為單位矩陣。因為一個有向無環圖不允許自環，它的鄰接矩陣的對角線必定全為0。因此，加上I保持了所有矩陣因子都是0或1的特性。[14]

相關概念

[編輯]
一顆多重樹
強明確樹（英語：multitree）

多重樹（英語：polytree）由將自由樹的邊定向（英語：orienting）而得到。[15] 多重樹必定是有向無環圖。對於有根樹，將其所有邊賦予指離根的方向也可以得到有向無環圖，即樹狀圖。

強明確樹（英語：multitree）是每兩個頂點最多被一條路徑所連接的有向無環圖。等價的說，它是滿足以下性質的一個有向無環圖：對於圖中每個頂點v，從v可達的頂點組成一顆樹。[16]

相關計算問題

[編輯]

拓撲排序和辨識

[編輯]
主條目：拓撲排序

可以用線性時間複雜度的卡恩演算法來找到一個有向無環圖的拓撲排序。[17]簡單來說，開設一個存放結果的列表L，先將入度為零的節點放到L中，因為這些節點沒有任何的父節點。將與這些節點相連的邊從圖中去掉，再尋找圖中入度為零的節點。對於新找到的節點來說，他們的父節點已經都在L中了，所以也可以從末端插入L。重複上述操作，直到找不到入度為零的節點。[18] 另外一種構造拓撲排序的演算法是將深度優先搜尋的後序遍歷結果翻轉。[17]

檢查一個有向圖是否為有向無環圖亦可線上性時間內完成。一種方法是先找到一個拓撲排序，然後測試這個排序是否能符合圖中每條邊所連頂點在排序中應該出現的順序。[19] 對於卡恩演算法在內的部分拓撲排序演算法，通過在演算法終止時判斷是否滿足一定條件即可知道圖是否有環。[18]如果有環，卡恩演算法最終獲得的L中節點個數會與圖的節點總數不同。

從其他圖構建

[編輯]

任意無向圖都可以被轉化為有向無環圖。構造方法是選定一個頂點的全序關係，並將無向圖中所有邊從全序關係中較前的頂點指向較後的頂點。這種方法是定向（英語：Orientation (graph theory)）方法中的無環定向（英語：acyclic orientation）。不同的全序關係可能推出相同的無環定向，因此一個包含n個頂點的圖的無環定向數量小於n!。如果定義χ為給定圖的色多項式，無環定向數量等於|χ(−1)|。[20]

任意有環有向圖都可以被轉化為有向無環圖。只要從圖中移除反饋節點集（英語：feedback vertex set）或反饋邊集（英語：feedback arc set），即對於圖中每個環，至少包括環中一個頂點或邊的集合。不過，找到反饋節點或邊的最小集合是NP困難問題。[21] 另外一種方法將有環有向圖去環的方法是將每個強連通分量收縮為一個頂點。[22] 對於無環圖，它的最小反饋頂點或邊集為空集，它的強連通分量則為自身。

遞移閉包和遞移約簡

[編輯]

有向無環圖的遞移閉包可以通過廣度優先搜尋或深度優先搜尋對每個節點測試可達性來構建。演算法對於一個有着n個頂點和m條邊的有向無環圖的複雜度為O(mn)。[23]也可以使用矩陣乘法演算法（英語：matrix multiplication algorithm）中最快的Coppersmith–Winograd演算法（英語：Coppersmith–Winograd algorithm），其複雜度為O(n2.3728639)。這個演算法理論上在稠密圖（英語：dense graph）中快過O(mn)。[24]

不論在哪種遞移閉包演算法中，那些被一條長度至少為2的路徑所連接的頂點對，都可以和只有一條長度為1的路徑所連接的頂點對區分開。由於遞移約簡包含後者，遞移約簡可以在和遞移閉包相同的漸進時間複雜度（英語：Asymptotic computational complexity）中被構建。[25]

閉包問題

[編輯]

閉包是一個圖中沒有出邊的頂點子集，即不存在從子集中頂點指向子集外頂點的邊。閉包問題（英語：closure problem）是則是找到帶權圖中使得權之和最大或最小的子集。閉包問題可以看作最大流問題的簡化版，在多項式時間內被解決。實際上，是否有環對於找到閉包沒有影響。[26]

最短或最長路徑問題

[編輯]

基於拓撲排序的性質，有向無環圖的最短路問題和最長路徑問題可以線上性時間內解決。將頂點拓撲排序後，從前到後遍歷每一個頂點，對於遍歷到的頂點，更新其所有出邊所到達頂點的長度值。如果求最短路，則在本邊是更短路徑的一部分時更新。求最長路則反之。[27]對於非有向無環圖，最短路需要用複雜度為的戴克斯特拉演算法或的貝爾曼-福特演算法等。[28]最長路徑則是一個NP困難問題。[29]

應用

[編輯]

排程

[編輯]

有向無環圖的偏序關係可以在排程有着先後順序限制的系統任務中發揮作用。[30]排程問題的一個重要種類是串聯需要更新的物件，如電子試算表中某個儲存格的計算公式依賴於其他儲存格，或在程式的原始碼被修改後重新編譯目標文件。依賴圖（英語：dependency graph）則記錄了這種更新依賴關係。其每個頂點對應一個需要被更新的物件，邊則表示更新的關係。依賴圖中的環被稱為環狀依賴（英語：circular dependency）。環狀依賴通常是不被允許出現的，因為不能保證圈內任務排定順序的一致性。無環的依賴圖即為有向無環圖。[31]

舉例來說，當電子試算表中一個儲存格的數值發生改變，其他直接或間接依賴於該儲存格的所有儲存格的值都需要被重新計算。被排程的任務為重新計算某個特定儲存格的值。當一個儲存格的值取決於另外一個儲存格時，兩個儲存格之間則有依賴關係。每個被依賴儲存格的值的計算過程都必須先於使用它的表達式執行。使用依賴圖的拓撲排序來排程任務使得在每個儲存格的值都僅被重新計算一次的情況下，整個工作表都能被更新。[32]相似的任務排程場景出現在程式原始碼編譯的makefile，[32]和最佳化電腦程式底層執行的指令排程中。[33]

一個有着五個里程碑（注有10–50）和六個任務（注有A–F）的計劃評審圖。ADF和BC是關鍵路徑

計劃評審技術是一種基於有向無環圖的計劃排定技術，通常用於組織大型的人工專案。在計劃評審技術中，每個頂點表示專案的一個里程碑（英語：Milestone (project management)），每條有向邊表示任務或者活動，連接着表示任務開始或結束的兩個節點。每條邊則被標註上預估需時。圖中的最長路徑即為專案的關鍵路徑。關鍵路徑決定了專案所需的總時間，里程碑的完成時間取決於結束於本頂點的最長路徑。[34]

數據處理網絡

[編輯]

有向無環圖可以用於表示處理數據的元素網絡。在網絡中，數據從一個元素頂點的入邊進入，處理後從出邊離開。

在電子電路設計中，靜態組合邏輯電路塊可以被表示為由邏輯門組成的有向無環系統。每個邏輯門對輸入做一次函數處理，輸入和輸出均為一個位元組。通常，這些電路塊的輸出不能夠再作為輸入，除非它們被儲存在暫存器或者狀態單元中，以保證圖不出現環。[35]

數據式編程（英語：Dataflow programming）語言描述針對數據流的操作，以及操作的輸出和其他操作的輸入之間的關係。這類型的語言使得描繪高重複率數據處理任務的變得更加簡單，因為同樣的數據操作可以應用於許多數據項。數據操作可以用有向無環圖來表示。這些數據操作可以被並行執行，從而高效利用多核心處理器。[36]

在編譯器中，直線碼（不含條件分支和迴圈的代碼段）可以使用有向無環圖表示。圖示示出每個算術運算的輸入和輸出。這種表示法讓編譯器能執行通用子表達式刪除（英語：common subexpression elimination），使得代碼更高效。[37]

因果結構

[編輯]
主條目：貝葉斯網絡

用頂點表示事件，邊表示因果關係的圖通常是無環的。[38]事件由時間上的先後順序來排列，所有箭頭遵循從先發生事件指向後發生事件的原則，因此也不存在環。

舉例來說，貝氏網絡表示多個概率事件的關聯網絡。頂點表示事件，後續事件的發生可能性則可以通過其在有向無環圖的前驅節點的發生概率計算出來。[39]在此基礎上，一個有向無環圖的端正圖（英語：moral graph）通過以下方法而得到：將單個頂點的所有父節點之間添加一條無向邊，再將所有的有向邊換成無向邊。[40]

另外一種具有相似因果結構的圖是影響圖（英語：influence diagram）。其頂點表示決策或不確定的事件，邊表示兩個頂點之間的因果關係。[41]在流行病學中，這些表示因果關係的圖表常常用來評估不同干預手段的效果。[42][43]

系譜學和版本歷史

[編輯]
托勒密王朝的譜系圖。

譜系圖可以看作是有向無環圖，頂點代表家族成員，邊代表親子關係。[44]雖然譜系圖也被稱作為家族「樹」, 但近親結婚導致的血統崩潰（英語：pedigree collapse）會違反樹的性質。即一個孩子的祖先既可以從父親向上追溯，也可以從母親一側。[45]圖中的母系血統和父系血統則可以看作為樹。因為沒有人可以是自己的祖先，譜系圖是無環的。[46]

基於相同的原因， 一個分散式版本控制系統的版本歷史的結構也是有向無環圖。在系統中，每個版本對應一個節點。邊連接起有直接衍生關係的兩個版本。由於分支合併的存在，這個結構並不能用樹來表示。[47]

在計算幾何領域，許多隨機化演算法都會維護一個「歷史有向無環圖」，用以記錄結構變動中的舊幾何結構。例如，在德勞內三角化的隨機增量演算法中，在添加每個點時，通過用三個較小的三角形替換一個三角形，以及通過「翻轉」操作將三角形對替換為另一對三角形，來改變三角剖分。在該演算法的歷史有向無環圖中，每個在演算法中構建出的三角形對應一個頂點，邊則將每個三角形和替代它的兩個或三個三角形連接起來。這種圖結構可以高效地處理點定位（英語：point location）問題，即對於一個查詢點q，找到它在德勞內三角剖分中的位置。在歷史有向無環圖中，從起點開始，不斷移動到包含q的替代三角形組，最後到達的終點必定代表包含q的德勞內三角形。[48]

參照圖

[編輯]

在參照圖（英語：citation graph）中， 每個頂點代表單篇著作，邊代表著作之間的參照關係。1965年普萊斯的文章「科學文獻的網絡」是使用參照圖的一個經典例子。[49]在參照圖中，每篇論文的參照次數（英語：Citation impact）為對應頂點的入度。這是引文分析中的一種重要的展示方式。另一個例子是法律裁判中，法官通過參照過往案例中的判決來支持他們的結論。參照圖亦可以用來描繪專利，因為專利必須要提及現有技術，即已經公開的並且和本專利有關的先前專利。

相較於網絡科學中對一般圖的研究，有向無環圖的獨特性質可以被用來作深層次分析。例如，遞移規約可以呈現參照在不同應用領域的分佈情況，這突出了不同領域中不同的參照網構造機制。[50]參照圖的衍生概念還有主幹道路分析（英語：Main path analysis），即對參照圖中最顯著的一條路徑的分析。

數據壓縮

[編輯]
分別用trie（左）和有向無環詞圖（右）存放英文單詞「tap」，「taps」，「top」和「tops」。EOW表示單詞結束。

有向無環圖也可以用於對一系列序列的壓縮中。在這裏，有向無環圖中的路徑代表這些序列。當多個序列有共同的子序列時，子序列可以被表示為這些序列對應路徑的公共邊。比起直接列出所有序列，這種方法佔用更少空間。例如，有向無環詞圖（英語：Deterministic acyclic finite state automaton）為僅含單個源（入度為0的頂點）的有向無環圖，其每條邊附有一個或多個字元。每條其源到匯（出度為0的節點）的路徑均代表一個字串，字串可以是英文單詞。[51]與其結構不同但功能相似的樹稱為trie。相比於trie，有向無環詞圖允許多條邊指向同一個頂點，使得具有相同字尾的一些詞的詞頭可以被相同的頂點所表示，因而更省空間。[52]

二元決策圖是基於有向無環圖的一種數據結構，用於表示布林函數[53][54]。在二元決策圖中，每個非匯節點對應一個布林變數，每個匯和邊則表示0或1。要找到一個解釋的真值，只要從唯一的源頂點出發，沿着該頂點代表的布林變數的實際真值所對應的出邊一直前進，到達的匯則為其真值。如同有向無環詞圖可以被看作是trie的一種壓縮形式一樣，二元決策圖可以被看作是決策樹的壓縮形式。它通過將導向相同結果的邊重新匯合到一個頂點來節省空間。[55]

參考文獻

[編輯]
  1. ^ Introduction to Algorithms [演算法導論]. : 1172. ISBN 978-7-111-40701-0. 
  2. ^ Thulasiraman, K.; Swamy, M. N. S., 5.7 Acyclic Directed Graphs, Graphs: Theory and Algorithms, John Wiley and Son: 118, 1992, ISBN 978-0-471-51356-8 .
  3. ^ 3.0 3.1 Bang-Jensen, Jørgen, 2.1 Acyclic Digraphs, Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics 2nd, Springer-Verlag: 32–34, 2008, ISBN 978-1-84800-997-4 .
  4. ^ Christofides, Nicos, Graph theory: an algorithmic approach, Academic Press: 170–174, 1975 .
  5. ^ Mitrani, I., Simulation Techniques for Discrete Event Systems, Cambridge Computer Science Texts 14, Cambridge University Press: 27, 1982 [2020-01-18], ISBN 9780521282826, （原始內容存檔於2021-03-10） .
  6. ^ Kozen, Dexter, The Design and Analysis of Algorithms, Monographs in Computer Science, Springer: 9, 1992 [2020-01-14], ISBN 978-0-387-97687-7, （原始內容存檔於2021-03-10） .
  7. ^ Banerjee, Utpal, Exercise 2(c), Loop Transformations for Restructuring Compilers: The Foundations, Springer: 19, 1993 [2020-01-14], ISBN 978-0-7923-9318-4, （原始內容存檔於2021-03-10） .
  8. ^ Bang-Jensen, Jørgen; Gutin, Gregory Z., 2.3 Transitive Digraphs, Transitive Closures and Reductions, Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics, Springer: 36–39, 2008 [2020-01-14], ISBN 978-1-84800-998-1, （原始內容存檔於2021-03-10） .
  9. ^ Jungnickel, Dieter, Graphs, Networks and Algorithms, Algorithms and Computation in Mathematics 5, Springer: 92–93, 2012 [2020-01-15], ISBN 978-3-642-32278-5, （原始內容存檔於2021-03-10） .
  10. ^ Sedgewick, Robert; Wayne, Kevin, 4,2,25 Unique topological ordering, Algorithms 4th, Addison-Wesley: 598–599, 2011 [2020-01-17], ISBN 978-0-13-276256-4, （原始內容存檔於2021-03-10） .
  11. ^ Bender, Edward A.; Williamson, S. Gill, Example 26 (Linear extensions – topological sorts), A Short Course in Discrete Mathematics, Dover Books on Computer Science, Courier Dover Publications: 142, 2005 [2020-01-17], ISBN 978-0-486-43946-4, （原始內容存檔於2021-03-10） .
  12. ^ 12.0 12.1 Robinson, R. W., Counting labeled acyclic digraphs, Harary, F. (編), New Directions in the Theory of Graphs, Academic Press: 239–273, 1973 . See also Harary, Frank; Palmer, Edgar M., Graphical Enumeration, Academic Press: 19, 1973, ISBN 978-0-12-324245-7 .
  13. ^ Weisstein, Eric W. (編). Weisstein's Conjecture. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英語）. 
  14. ^ McKay, B. D.; Royle, G. F.; Wanless, I. M.; Oggier, F. E.; Sloane, N. J. A.; Wilf, H., Acyclic digraphs and eigenvalues of (0,1)-matrices, Journal of Integer Sequences, 2004, 7 [2020-01-19], （原始內容存檔於2021-02-24） , Article 04.3.3.
  15. ^ Rebane, George; Pearl, Judea, The recovery of causal poly-trees from statistical data, in Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987 (PDF): 222–228, 1987 [永久失效連結].
  16. ^ Furnas, George W.; Zacks, Jeff, Multitrees: enriching and reusing hierarchical structure, Proc. SIGCHI conference on Human Factors in Computing Systems (CHI '94): 330–336, 1994, ISBN 978-0897916509, doi:10.1145/191666.191778 .
  17. ^ 17.0 17.1 Cormen, Thomas H. （英語：Thomas H. Cormen）; Leiserson, Charles E. （英語：Charles E. Leiserson）; Rivest, Ronald L.; Stein, Clifford. Introduction to Algorithms 2nd. MIT Press and McGraw-Hill. 2001 [1990]. ISBN 0-262-03293-7.  Section 22.4, Topological sort, pp. 549–552.
  18. ^ 18.0 18.1 Jungnickel (2012), pp. 50–51.
  19. ^ 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, Springer: 179–181, 2009 [2020-01-21], ISBN 978-1-84800-070-4, （原始內容存檔於2021-03-10） .
  20. ^ Stanley, Richard P., Acyclic orientations of graphs (PDF), Discrete Mathematics, 1973, 5 (2): 171–178 [2020-01-22], doi:10.1016/0012-365X(73)90108-8, （原始內容存檔 (PDF)於2021-02-24） .
  21. ^ Garey, Michael R.; Johnson, David S., Problems GT7 and GT8, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman: 191–192, 1979, ISBN 0-7167-1045-5 
  22. ^ Harary, Frank; Norman, Robert Z.; Cartwright, Dorwin, Structural Models: An Introduction to the Theory of Directed Graphs, John Wiley & Sons: 63, 1965 .
  23. ^ Skiena (2009), p. 495.
  24. ^ Skiena (2009), p. 496.
  25. ^ Bang-Jensen & Gutin (2008), p. 38.
  26. ^ Picard, Jean-Claude, Maximal closure of a graph and applications to combinatorial problems, Management Science（英語：Management Science (journal)）, 1976, 22 (11): 1268–1272, MR 0403596, doi:10.1287/mnsc.22.11.1268 .
  27. ^ Cormen et al. 2001, Section 24.2, Single-source shortest paths in directed acyclic graphs, pp. 592–595.
  28. ^ Cormen et al. 2001, Sections 24.1, The Bellman–Ford algorithm, pp. 588–592, and 24.3, Dijkstra's algorithm, pp. 595–601.
  29. ^ Cormen et al. 2001, p. 966.
  30. ^ Skiena (2009), p. 469.
  31. ^ Al-Mutawa, H. A.; Dietrich, J.; Marsland, S.; McCartin, C., On the shape of circular dependencies in Java programs, 23rd Australian Software Engineering Conference, IEEE: 48–57, 2014, ISBN 978-1-4799-3149-1, doi:10.1109/ASWEC.2014.15 .
  32. ^ 32.0 32.1 Gross, Jonathan L.; Yellen, Jay; Zhang, Ping, Handbook of Graph Theory 2nd, CRC Press: 1181, 2013 [2020-01-30], ISBN 978-1-4398-8018-0, （原始內容存檔於2021-03-10） .
  33. ^ Srikant, Y. N.; Shankar, Priti, The Compiler Design Handbook: Optimizations and Machine Code Generation 2nd, CRC Press: 19–39, 2007 [2020-01-30], ISBN 978-1-4200-4383-9, （原始內容存檔於2021-03-10） .
  34. ^ Wang, John X., What Every Engineer Should Know About Decision Making Under Uncertainty, CRC Press: 160, 2002 [2020-01-31], ISBN 978-0-8247-4373-4, （原始內容存檔於2021-03-10） .
  35. ^ Sapatnekar, Sachin, Timing, Springer: 133, 2004 [2020-02-03], ISBN 978-1-4020-7671-8, （原始內容存檔於2021-03-10） .
  36. ^ Dennis, Jack B., First version of a data flow procedure language, Programming Symposium, Lecture Notes in Computer Science 19: 362–376, 1974, ISBN 978-3-540-06859-4, doi:10.1007/3-540-06859-7_145 .
  37. ^ Touati, Sid; de Dinechin, Benoit, Advanced Backend Optimization, John Wiley & Sons: 123, 2014 [2020-02-04], ISBN 978-1-118-64894-0, （原始內容存檔於2021-03-10） .
  38. ^ Gopnik, Alison; Schulz, Laura, Causal Learning, Oxford University Press: 4, 2007 [2020-06-01], ISBN 978-0-19-803928-0, （原始內容存檔於2021-03-10） .
  39. ^ Shmulevich, Ilya; Dougherty, Edward R., Probabilistic Boolean Networks: The Modeling and Control of Gene Regulatory Networks, Society for Industrial and Applied Mathematics: 58, 2010 [2020-06-01], ISBN 978-0-89871-692-4, （原始內容存檔於2021-03-10） .
  40. ^ Cowell, Robert G.; Dawid, A. Philip; Lauritzen, Steffen L.; Spiegelhalter, David J., 3.2.1 Moralization, Probabilistic Networks and Expert Systems, Springer: 31–33, 1999, ISBN 0-387-98767-3 .
  41. ^ Dorf, Richard C., The Technology Management Handbook, CRC Press: 9-7, 1998 [2020-06-01], ISBN 978-0-8493-8577-3, （原始內容存檔於2021-03-10） .
  42. ^ Boslaugh, Sarah, Encyclopedia of Epidemiology, Volume 1, SAGE: 255, 2008 [2020-06-01], ISBN 978-1-4129-2816-8, （原始內容存檔於2021-03-10） .
  43. ^ Pearl, Judea. Causal diagrams for empirical research. Biometrika. 1995, 82 (4): 669–709. doi:10.1093/biomet/82.4.669. 
  44. ^ Kirkpatrick, Bonnie B., Haplotypes versus genotypes on pedigrees, Algorithms for Molecular Biology, April 2011, 6 (10): 10, PMC 3102622 可免費查閱, PMID 21504603, doi:10.1186/1748-7188-6-10 .
  45. ^ McGuffin, M. J.; Balakrishnan, R., Interactive visualization of genealogical graphs (PDF), IEEE Symposium on Information Visualization (INFOVIS 2005): 16–23, 2005 [2020-02-07], ISBN 978-0-7803-9464-3, doi:10.1109/INFVIS.2005.1532124, （原始內容存檔 (PDF)於2021-02-24） .
  46. ^ Bender, Michael A.; Pemmasani, Giridhar; Skiena, Steven; Sumazin, Pavel, Finding least common ancestors in directed acyclic graphs, Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '01), Philadelphia, PA, USA: Society for Industrial and Applied Mathematics: 845–854, 2001 [2020-02-08], ISBN 978-0-89871-490-6, （原始內容存檔於2018-12-01） .
  47. ^ Bartlang, Udo, Architecture and Methods for Flexible Content Management in Peer-to-Peer Systems, Springer: 59, 2010 [2020-05-31], ISBN 978-3-8348-9645-2, （原始內容存檔於2021-03-10） .
  48. ^ Pach, János; Sharir, Micha, Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures, Mathematical surveys and monographs 152, American Mathematical Society: 93–94, [2020-06-01], ISBN 978-0-8218-7533-9, （原始內容存檔於2021-03-10） .
  49. ^ Price, Derek J. de Solla, Networks of Scientific Papers (PDF), Science, July 30, 1965, 149 (3683): 510–515 [2020-06-01], Bibcode:1965Sci...149..510D, PMID 14325149, doi:10.1126/science.149.3683.510, （原始內容存檔 (PDF)於2019-05-20） .
  50. ^ Clough, James R.; Gollings, Jamie; Loach, Tamar V.; Evans, Tim S., Transitive reduction of citation networks, Journal of Complex Networks, 2015, 3 (2): 189–203, arXiv:1310.8224 可免費查閱, doi:10.1093/comnet/cnu039 .
  51. ^ Crochemore, Maxime; Vérin, Renaud, Direct construction of compact directed acyclic word graphs, Combinatorial Pattern Matching, Lecture Notes in Computer Science 1264, Springer: 116–129, 1997, CiteSeerX 10.1.1.53.6273 可免費查閱, ISBN 978-3-540-63220-7, doi:10.1007/3-540-63220-4_55 .
  52. ^ Lothaire, M., Applied Combinatorics on Words, Encyclopedia of Mathematics and its Applications 105, Cambridge University Press: 18, 2005 [2020-06-01], ISBN 9780521848022, （原始內容存檔於2021-03-10） .
  53. ^ Lee, C. Y., Representation of switching circuits by binary-decision programs, Bell System Technical Journal, 1959, 38 (4): 985–999, doi:10.1002/j.1538-7305.1959.tb01585.x .
  54. ^ Akers, Sheldon B., Binary decision diagrams, IEEE Transactions on Computers, 1978, C–27 (6): 509–516, doi:10.1109/TC.1978.1675141 .
  55. ^ Friedman, S. J.; Supowit, K. J., Finding the optimal variable ordering for binary decision diagrams, Proc. 24th ACM/IEEE Design Automation Conference (DAC '87), New York, NY, USA: ACM: 348–356, 1987, ISBN 978-0-8186-0781-3, doi:10.1145/37888.37941 .
取自 "https://wiki.gdrain.workers.dev/w/index.php?title=有向无环图&oldid=81235886"