混合圖
混合圖(mixed graph)G = (V, E, A)是由頂點 (節點)的集合V、無向邊的集合E和有向邊的集合A所組成的數學物件。[1]
定義和標識
編輯考慮一對相鄰的頂點 。有向邊,是一個有方向的邊,其可以表示為 或 (即該有向邊為由 指向 )。[2] 同樣地,無向邊,是一個沒有方向的邊,其可以表示為 或 。[2]
在以下給出的應用實例中,我們不考慮混合圖中包含自環或多重邊的情況。
混合圖或混合循環中的循環,是由有向邊在混合圖中構成的循環。[1]如果不能從有向邊形成循環,則認為混合圖的方向是無環的。[1]如果一個混合圖的所有方向都是無環的,我們稱它為有向無環圖。[1]
着色
編輯混合圖着色可以看作是使用k種不同顏色(其中k是正整數)對混合圖頂點進行標記或賦值。[3]通過邊連接的兩端頂點必須顏色不同。顏色可以由1到k的數字表示,對於有向邊,箭頭後端的顏色對應數字必須小於箭頭前端的顏色對應數字。[3]
實例
編輯例如右圖,我們可用於混合圖的k着色方式為 。由於 和 之間有邊連接,他們必須用不同顏色進行標記(如將 和 分別標記為1和2)。 和 之間為有向邊連接,因此箭頭後端 的顏色標記必須小於箭頭前段 的顏色標記。
強着色和弱着色
編輯混合圖的k着色方式是一個函數。
其中 ,當 (無向邊)時 ,當 (有向邊)時 。[1]再回到實例中,這意味着我們可以將有向邊的前端和後端 均標記為正整數2。
存在
編輯假設混合圖為G,能否做到將其完全着色是不確定的。為了使混合圖有一個k着色方式,圖中不能包含任何有向循環。[2] 如果這樣的k着色方式存在,那麼我們為了給整個圖着色的最小着色數(k值)可記為 。[2] 我們可以通過構建k的多項式函數來計算合理的k着色方式的數量,其被稱為圖G的着色多項式(可用無向圖的着色多項式來類比),其定義式為 。[1]
計算弱色多項式
編輯塔特多項式中的刪除–收縮方法可用於計算弱色多項式的混合圖。這個方法涉及刪除(或移除)有向或無向邊,合併(或關聯)與該無向或有向邊相連的其餘頂點形成一個頂點。[4] 在刪除無向邊 之後,從之前的混合圖 可得到新的混合圖 。[4] 可將刪除無向邊 之後剩餘的邊表示為 。類似地,在刪除有向邊 之後,將剩餘的邊表示為 ,可獲得新的混合圖 。[4] 同樣,我們可以將合併 和 分別表示為 和 。[4] 根據以上給出的條件,我們得到以下方程來計算混合圖的着色多項式:[4]
應用
編輯調度問題
編輯混合圖可用於對車間調度問題進行建模,例如在一定的時間限制下執行一系列任務的問題。在這類問題中,無向邊可用於設定兩個任務不兼容(不能同時執行)的約束。有向邊可用於優先級約束,即其中一個任務必須先於另一個任務執行。用這種方法從調度問題的角度定義的圖稱為析取圖。混合圖着色問題可用於規劃執行所有任務的最小長度。[2]
貝葉斯推理
編輯混合圖也用作貝葉斯推理的概率圖模型。下文中無環混合圖(沒有有向邊循環的圖)也稱為鏈圖。這些圖的有向邊用來表示兩個事件之間的因果關係,其中第一個事件的結果影響第二個事件的概率。相反的是,無向邊則表示兩個事件之間的非因果關係。鏈圖的無向子圖的連通分量稱為鏈。一個鏈圖可以通過構造它的道德圖從而轉化為一個無向圖,鏈圖可以在其含有同一鏈的頂點對之間添加無向邊,然後忽略有向邊的方向從而形成無向圖。
註釋
編輯- ^ 1.0 1.1 1.2 1.3 1.4 1.5 Beck 等人 (2013, p. 1)
- ^ 2.0 2.1 2.2 2.3 2.4 Ries (2007, p. 1)
- ^ 3.0 3.1 Hansen,Kuplinsky & de Werra (1997, p. 1)
- ^ 4.0 4.1 4.2 4.3 4.4 Beck 等人 (2013, p. 4)
- ^ 5.0 5.1 Beck 等人 (2013, p. 5)
參考文獻
編輯- Beck, M.; Blado, D.; Crawford, J.; Jean-Louis, T.; Young, M., On weak chromatic polynomials of mixed graphs, Graphs and Combinatorics, 2013, arXiv:1210.4634 , doi:10.1007/s00373-013-1381-1.
- Cowell, Robert G.; Dawid, A. Philip; Lauritzen, Steffen L.; Spiegelhalter, David J., Probabilistic Networks and Expert Systems: Exact Computational Methods for Bayesian Networks, Springer-Verlag New York: 27, 1999 [2019-05-21], ISBN 0-387-98767-3, doi:10.1007/0-387-22630-3, (原始內容存檔於2020-06-12)
- Hansen, Pierre; Kuplinsky, Julio; de Werra, Dominique, Mixed graph colorings, Mathematical Methods of Operations Research, 1997, 45 (1): 145–160, MR 1435900, doi:10.1007/BF01194253.
- Ries, B., Coloring some classes of mixed graphs, Discrete Applied Mathematics, 2007, 155 (1): 1–6, MR 2281351, doi:10.1016/j.dam.2006.05.004.