混合圖

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

定義和標識

混合圖的實例

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

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

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

着色

混合圖實例

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

實例

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

強着色和弱着色

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

$c:V\rightarrow [k]$

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

存在

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

計算弱色多項式

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

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

應用

調度問題

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

貝葉斯推理

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

參考文獻

• 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.