圖論 - 著色

圖著色不過是一種簡單的方法，用於在某些約束條件下標記圖的組成部分，例如頂點、邊和區域。在一個圖中，沒有兩個相鄰的頂點、相鄰的邊或相鄰的區域用最少的顏色著色。這個數字稱為色數，該圖稱為正確著色的圖。

在圖著色中，對圖設定的約束條件包括顏色、著色順序、著色方式等。顏色賦予頂點或特定區域。因此，具有相同顏色的頂點或區域構成獨立集。

頂點著色

頂點著色是將顏色分配給圖 'G' 的頂點，使得沒有兩個相鄰的頂點具有相同的顏色。簡而言之，一條邊的兩個頂點不應該具有相同的顏色。

圖 'G' 的頂點著色所需的最小顏色數稱為 G 的色數，記為 X(G)。

當且僅當 'G' 是一個空圖時，χ(G) = 1。如果 'G' 不是空圖，則χ(G) ≥ 2。

示例

注意 - 如果存在一個最多使用 n 種顏色的頂點著色，即 X(G) ≤ n，則稱圖 'G' 是 n 可覆蓋的。

區域著色是將顏色分配給平面圖的區域，使得沒有兩個相鄰的區域具有相同的顏色。如果兩個區域具有公共邊，則稱它們為相鄰的。

示例

看看下面的圖。區域 'aeb' 和 'befc' 是相鄰的，因為這兩個區域之間有一條公共邊 'be'。

類似地，其他區域也根據鄰接關係著色。該圖的著色方式如下：

示例

Kn 的色數是

考慮 K₄ 的這個例子。

在完全圖中，每個頂點都與其餘 (n – 1) 個頂點相鄰。因此，每個頂點都需要一種新的顏色。因此，K_n 的色數 = n。

圖著色是圖論中最重要概念之一。它被用於計算機科學的許多即時應用中，例如：

列印頁面