混合圖

混合圖（mixed graph）G = (V, E, A)是由頂點 （節點）的集合V、無向邊的集合E和有向邊的集合A所組成的數學物件。^[1]

定義和標識

混合圖的實例

考慮一對相鄰的頂點 ${\displaystyle u,v\in V}$。有向邊，是一個有方向的邊，其可以表示為 ${\displaystyle {\overrightarrow {uv}}}$ 或 ${\displaystyle (u,v)}$ (即該有向邊為由${\displaystyle u}$指向${\displaystyle v}$)。^[2] 同樣地，無向邊，是一個沒有方向的邊，其可以表示為 ${\displaystyle uv}$ 或 ${\displaystyle [u,v]}$。^[2]

在以下給出的應用實例中，我們不考慮混合圖中包含自環或多重邊的情況。

混合圖或混合循環中的循環，是由有向邊在混合圖中構成的循環。^[1]如果不能從有向邊形成循環，則認為混合圖的方向是無環的。^[1]如果一個混合圖的所有方向都是無環的，我們稱它為有向無環圖。^[1]

着色

混合圖實例

混合圖着色可以看作是使用k種不同顏色(其中k是正整數)對混合圖頂點進行標記或賦值。^[3]通過邊連接的兩端頂點必須顏色不同。顏色可以由1到k的數字表示，對於有向邊，箭頭後端的顏色對應數字必須小於箭頭前端的顏色對應數字。^[3]

實例

例如右圖，我們可用於混合圖的k着色方式為 ${\displaystyle \{1,2,3\}}$。由於 ${\displaystyle u}$ 和 ${\displaystyle v}$ 之間有邊連接，他們必須用不同顏色進行標記(如將${\displaystyle u}$ 和 ${\displaystyle v}$ 分別標記為1和2)。 ${\displaystyle v}$ 和${\displaystyle w}$之間為有向邊連接，因此箭頭後端${\displaystyle v}$的顏色標記必須小於箭頭前段${\displaystyle w}$的顏色標記。

強着色和弱着色

混合圖的k着色方式是一個函數。

${\displaystyle c:V\rightarrow [k]}$

其中${\displaystyle [k]={1,2,\dots ,k}}$，當${\displaystyle uv\in E}$（無向邊）時${\displaystyle c(u)\neq c(v)}$，當${\displaystyle {\overrightarrow {uv}}\in A}$（有向邊）時${\displaystyle c(u)\leq c(v)}$。^[1]再回到實例中，這意味着我們可以將有向邊的前端和後端 ${\displaystyle (v,w)}$均標記為正整數2。

存在

假設混合圖為G，能否做到將其完全着色是不確定的。為了使混合圖有一個k着色方式，圖中不能包含任何有向循環。^[2] 如果這樣的k着色方式存在，那麼我們為了給整個圖着色的最小着色數（k值）可記為${\displaystyle \chi (G)}$。^[2] 我們可以通過構建k的多項式函數來計算合理的k着色方式的數量，其被稱為圖G的着色多項式（可用無向圖的着色多項式來類比），其定義式為${\displaystyle \chi _{G}(k)}$。^[1]

計算弱色多項式

塔特多項式中的刪除–收縮方法可用於計算弱色多項式的混合圖。這個方法涉及刪除(或移除)有向或無向邊，合併（或關聯）與該無向或有向邊相連的其餘頂點形成一個頂點。^[4] 在刪除無向邊${\displaystyle e}$之後，從之前的混合圖 ${\displaystyle G=(V,E,A)}$ 可得到新的混合圖 ${\displaystyle (V,E-e,A)}$。^[4] 可將刪除無向邊${\displaystyle e}$之後剩餘的邊表示為 ${\displaystyle G-e}$。類似地，在刪除有向邊${\displaystyle a}$之後，將剩餘的邊表示為${\displaystyle G-a}$，可獲得新的混合圖${\displaystyle (V,E,A-a)}$。^[4] 同樣，我們可以將合併${\displaystyle e}$和${\displaystyle a}$分別表示為${\displaystyle G/e}$ 和 ${\displaystyle G/a}$。^[4] 根據以上給出的條件，我們得到以下方程來計算混合圖的着色多項式：^[4]

1. ${\displaystyle \chi _{G}(k)=\chi _{G-e}(k)-\chi _{G/e}(k)}$,^[5]
2. ${\displaystyle \chi _{G}(k)=\chi _{G-a}(k)+\chi _{G/a}(k)-\chi _{G_{a}}(k)}$.^[5]

應用

調度問題

混合圖可用於對車間調度問題進行建模，例如在一定的時間限制下執行一系列任務的問題。在這類問題中，無向邊可用於設定兩個任務不兼容(不能同時執行)的約束。有向邊可用於優先級約束，即其中一個任務必須先於另一個任務執行。用這種方法從調度問題的角度定義的圖稱為析取圖。混合圖着色問題可用於規劃執行所有任務的最小長度。^[2]

貝葉斯推理

混合圖也用作貝葉斯推理的概率圖模型。下文中無環混合圖(沒有有向邊循環的圖)也稱為鏈圖。這些圖的有向邊用來表示兩個事件之間的因果關係，其中第一個事件的結果影響第二個事件的概率。相反的是，無向邊則表示兩個事件之間的非因果關係。鏈圖的無向子圖的連通分量稱為鏈。一個鏈圖可以通過構造它的道德圖從而轉化為一個無向圖，鏈圖可以在其含有同一鏈的頂點對之間添加無向邊，然後忽略有向邊的方向從而形成無向圖。

註釋

1. Beck et al. (2013，第1頁)
2. Ries (2007，第1頁)
3. Hansen, Kuplinsky & de Werra (1997，第1頁)
4. Beck et al. (2013，第4頁)
5. Beck et al. (2013，第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.

外部連結

• 埃里克·韋斯坦因. Mixed Graph. MathWorld.