跳至內容

混合圖

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

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

貝葉斯推理

[編輯]

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

注釋

[編輯]

參考文獻

[編輯]

外部連結

[編輯]