混合圖(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]

  1.  ,[5]
  2.  .[5]

應用

編輯

調度問題

編輯

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

貝葉斯推理

編輯

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

注釋

編輯

參考文獻

編輯

外部連結

編輯