在圖論中，混合圖G=（V，E，A）是由一組頂點V、一組（無定向）邊E和一組定向邊（或弧）A組成的圖。

考慮相鄰的頂點u,v∈V{displaystyleu,vinV}。.一條有向邊，稱為弧，是一條有方向的邊，可以表示為uv→{displaystyle{overrightarrow{uv}}或｝或(u,v){displaystyle(u,v)}(注意u{displaystyleu}是尾巴。是尾巴，而v{displaystylev}是弧的頭部。是弧的頭部）。另外，一條無定向的邊，或稱邊，是一條沒有方向的邊，可以表示為uv{displaystyleuv}或或[u,v].{displaystyle[u,v]}。.在我們的應用實例中，我們將不考慮混合圖的循環或多條邊。一個混合圖中的行走是一個序列{displaystylev_{0},c_{1},v_{1},c_{2},v_{2},dots,c_{k},v_{k}}的頂點和邊/弧，這樣，對于所有的指數是圖的一個弧。如果這個行走沒有重復任何邊、弧或頂點，可能除了xxx個和最后一個頂點之外，它就是一條路徑。如果一條路徑的xxx個和最后一個頂點是相同的，那么它就是封閉的；如果一條封閉的路徑除了xxx個和最后一個頂點之外沒有重復頂點，那么它就是一個循環。如果一個混合圖不包含一個循環，那么它就是無循環的。著色混合圖的著色可以被認為是對混合圖的頂點進行標記或分配k種不同的顏色（其中k是一個正整數）。不同的顏色必須分配給由邊連接的頂點。顏色可以用1到k的數字表示，對于一個有向弧，弧尾的顏色必須比弧頭的數字小。我們可用來給混合圖著色的k色是{1，2，3}。由于u和v由一條邊連接，它們必須得到不同的顏色或標簽（u和v分別被標為1和2）。

我們還有一條從v到w的弧。由于方位指定了一個順序，我們必須給弧的尾部（v）貼上比弧的頭部（w）更小的顏色（或我們集合中的整數）。在我們的弧上可以應用一個更弱的條件，我們可以認為一個混合圖的弱的適當的k-coloring是一個函數c:V→[k]其中[k]:={1,2,...,k}，如果uv∈E，c(u)≠c(v)，如果c(u)≤c(v)存在性對于一個混合圖來說，著色可能存在也可能不存在。為了使一個混合圖有一個k著色，該圖不能包含任何有向循環。如果這樣的k染色存在，那么我們就把為圖正確著色所需的最小k稱為色度數，表示為χ(G)。我們可以將適當的k著色的數量計算為k的多項式函數，這被稱為圖G的色度多項式（與無定向圖的色度多項式相類似），可以表示為χG(k)。計算弱色度多項式可以用刪除-收縮法來計算混合圖的弱色度多項式。這種方法包括刪除（或移除）一條邊或弧，并收縮（或連接）與該邊（或弧）相關的其余頂點，以形成一個頂點。從混合圖G=（V，E，A）中刪除一條邊e后，我們得到混合圖（V，E-e，A）。同樣，從一個混合圖中刪除一個弧，a，我們得到（V，E，A-a），我們可以把刪除a的行為表示為G-a。根據上述命題，我們可以得到以下公式來計算混合圖的色度多項式。

混合圖可以用來模擬工作車間的調度問題，在這個問題中，要執行一系列的任務，并受到某些時間限制。在這種問題中，無向邊可以用來模擬兩個任務不兼容的約束（它們不能同時執行）。有向邊可被用來建模，即兩個任務是不相容的（不能同時執行）。