跳转至

圖的着色

點着色

（討論的是無自環無向圖）

對無向圖頂點着色，且相鄰頂點不能同色。若 G 是 \(k\)- 可着色的，但不是 \((k-1)\)- 可着色的，則稱 k 是 G 的色數，記為 \(\chi(G)\)。

對任意圖 G，有 \(\chi(G) \leq \Delta(G) + 1\)，其中 \(\Delta(G)\) 為最大度。

Brooks 定理

設連通圖不是完全圖也不是奇圈，則 \(\chi(G) \leq \Delta(G)\)。

證明

證明

設 \(|V(G)|=n\)，考慮數學歸納法。

首先，\(n\leq 3\) 時，命題顯然成立。

接下來，假設對於 \(n-1\) 時的命題成立，下面我們要逐步強化命題。

不妨只考慮 \(\Delta(G)\)- 正則圖，因為對於非正則圖來説，可以看作在正則圖裏刪去一些邊構成的，而這一過程並不會影響結論。

對於任意不是完全圖也不是奇圈的正則圖 G，任取其中一點 v，考慮子圖 \(H:=G-v\)，由歸納假設知 \(\chi(H)\leq\Delta(H)=\Delta(G)\)，接下來我們只需證明在 H 中插入 v 不會影響結論即可。

令 \(\Delta:=\Delta(G)\)，設 H 染的 \(\Delta\) 種顏色分別為 \(c_1,c_2,\dots,c_{\Delta}\)，v 的 \(\Delta\) 個鄰接點為 \(v_1,v_1,\dots,v_{\Delta}\)。不妨假設 v 的這些鄰接點顏色兩兩不同，否則命題得證。

接下來我們設所有在 H 中染成 \(c_i\) 或 \(c_j\) 的點以及它們之間的所有邊構成子圖 \(H_{i,j}\)。不妨假設任意 2 個不同的點 \(v_i\)，\(v_j\) 一定在 \(H_{i,j}\) 的同一個連通分量中，否則若在兩個連通分量中的話，可以交換其中一個連通分量所有點的顏色，從而 \(v_i\)，\(v_j\) 顏色相同。

這裏的交換顏色指的是若圖中只有兩種顏色 a，b，那麼把圖中原來染成顏色 a 的點全部染成顏色 b，把圖中原來染成顏色 b 的點全部染成顏色 a。

我們設上述連通分量為 \(C_{i,j}\)，那麼 \(C_{i,j}\) 一定只能是 \(v_i\) 到 \(v_j\) 的路。因為 \(v_i\) 在 H 中的度為 \(\Delta-1\)，所以 \(v_i\) 在 H 中的鄰接點顏色一定兩兩不同，否則可以給 \(v_i\) 染別的顏色，從而和 v 的其他鄰接點顏色重複，所以 \(v_i\) 在 \(C_{i,j}\) 中鄰接點數量為 1，\(v_j\) 同理。然後我們在 \(C_{i,j}\) 中取一條 \(v_i\) 到 \(v_j\) 的路，令其為 P，若 \(C_{i,j}\ne P\)，那麼我們沿着 P 順次給路上的點染色，設遇到的第一個度數大於 2 的點為 u，注意到 u 的鄰接點最多隻用了 \(\Delta-2\) 種顏色，所以 u 可以重新染色，從而使 \(v_i\)，\(v_j\) 不連通。

然後我們不難發現，對任意 3 個不同的點 \(v_i\)，\(v_j\)，\(v_k\)，\(V(C_{i,j})\cap V(C_{j,k})=\{v_j\}\)。

到這裏我們對命題的強化工作就已經做完了。

接下來就很簡單。首先，如果 v 的鄰接點兩兩相鄰，那麼命題得證。不妨設 \(v_1\)，\(v_2\) 不相鄰，在 \(C_{1,2}\) 中取 \(v_1\) 的鄰接點 w，交換 \(C_{1,3}\) 中的顏色。得到的新圖中，\(w\in V(C_{1,2})\cap V(C_{2,3})\)，矛盾。

至此命題證明完畢。

Welsh–Powell 算法

Welsh–Powell 算法是一種在 不限制最大着色數 時尋找着色方案的貪心算法。

對於無自環無向圖 G，設 \(V(G):=\{v_1,v_2,\dots,v_n\}\) 滿足。

\(\deg(v_i)\geq\deg(v_{i+1}),~\forall 1\leq i\leq n-1\)

按 Welsh–Powell 算法着色後的顏色數至多為 \(\max_{i=1}^n\min\{\deg(v_i)+1,i\}\), 該算法的時間複雜度為 \(O\left(n\max_{i=1}^n\min\{\deg(v_i)+1,i\}\right)=O(n^2)\)。

過程

  1. 將當前未着色的點按度數降序排列。
  2. 將第一個點染成一個未被使用的顏色。
  3. 順次遍歷接下來的點，若當前點和所有與第一個點顏色 相同 的點 不相鄰，則將該點染成與第一個點相同的顏色。
  4. 若仍有未着色的點，則回到步驟 1, 否則結束。

示例如下：

Orignal

（由 Graph Editor 生成）

我們先對點按度數降序排序，得：

次序 1 2 3 4 5 6 7 8 9 10 11 12 13
點的編號 4 5 0 2 9 1 3 6 10 12 7 8 11
度數 5 5 4 4 4 3 3 3 3 3 2 2 1
\(\min\{\deg(v_i)+1,i\}\) 1 2 3 4 5 4 4 4 4 4 3 3 2

所以 Welsh–Powell 算法着色後的顏色數最多為 5。

另外因為該圖有子圖 \(C_3\), 所以色數一定大於等於 3。

  • 第一次染色：

    Colored 1

    染 4 9 3 11 號點。 - 第二次染色：

    Colored 2

    染 5 2 6 7 8 號點。 - 第三次染色：

    Colored 3

    染 0 1 10 12 號點。

證明

證明

對於無自環無向圖 G，設 \(V(G):=\{v_1,v_2,\dots,v_n\}\) 滿足

\(\deg(v_i)\geq\deg(v_{i+1}),~\forall 1\leq i\leq n-1\)

令 \(V_0=\varnothing\), 我們取 \(V(G)\setminus\bigcup_{i=0}^{m-1} V_i\) 中的子集 \(V_m\), 其中的元素滿足

  1. \(v_{k_m}\in V_m\), 其中 \(k_m=\min\{k:v_k\notin\bigcup_{i=0}^{m-1} V_i\}\)

  2. 若

    \(\{v_{i_{m,1}},v_{i_{m,2}},\dots,v_{i_{m,l_m}}\}\subset V_m,~i_{m,1}<i_{m,2}<\dots<i_{m,l_m}\)

    則 \(v_j\in V_m\) 當且僅當

    1. \(j>i_{m,l_m}\)
    2. \(v_j\) 與 \(v_{i_{m,1}},v_{i_{m,2}},\dots,v_{i_{m,l_m}}\) 均不相鄰

顯然若將 \(V_i\) 中的點染成第 i 種顏色，則該染色方案即為 Welsh–Powell 算法給出的方案，顯然有

  • \(V_1\neq\varnothing\)
  • \(V_i\cap V_j=\varnothing\iff i\neq j\)
  • \(\exists \alpha(G)\in\Bbb{N}^*,\forall i>\alpha(G),~s.t.~ V_i=\varnothing\)

我們只需要證明：

\(\bigcup_{i=1}^{\alpha(G)} V_i=V(G)\)

其中

\(\chi(G)\leq\alpha(G)\leq\max_{i=1}^n\min\{\deg(v_i)+1,i\}\)

上式左邊的不等號顯然成立，我們考慮右邊。

首先我們不難得出：

若 \(v\notin\bigcup_{i=1}^mV_i\)，則 v 與 \(V_1,V_2,\dots,V_m\) 中分別至少有一個點相鄰，從而有 \(\deg(v)\geq m\)

進而

\(v_j\in\bigcup_{i=1}^{\deg(v_j)+1}V_i\)

另一方面，基於序列 \(\{V_i\}\) 的構造方法，我們不難發現

\(v_j\in\bigcup_{i=1}^j V_i\)

兩式結合即得證。

邊着色

對無向圖的邊着色，要求相鄰的邊塗不同種顏色。若 G 是 k- 邊可着色的，但不是 \((k-1)\)- 邊可着色的，則稱 k 是 G 的邊色數，記為 \(\chi'(G)\)。

Vizing 定理

設 G 是簡單圖，則 \(\Delta(G) \leq \chi'(G) \leq \Delta(G) + 1\)

若 G 是二部圖，則 \(\chi'(G)=\Delta(G)\)

當 \(n\) 為奇數（\(n \neq 1\)）時，\(\chi'(K_n)=n\); 當 \(n\) 為偶數時，\(\chi'(K_n)=n-1\)

二分圖 Vizing 定理的構造性證明

證明

按照順序在二分圖中加邊。

我們在嘗試加入邊 \((x,y)\) 的時候，我們嘗試尋找對於 \(x\) 和 \(y\) 的編號最小的尚未被使用過的顏色，假設分別為 \(l_x\) 和 \(l_y\)。

如果 \(l_x=l_y\) 此時我們可以直接將這條邊的顏色設置為 \(l_x\)。

否則假設 \(l_x<l_y\), 我們可以嘗試將節點 \(y\) 連出去的顏色為 \(l_x\) 的邊的顏色修改為 \(l_y\)。

修改的過程可以被近似的看成是一條從 \(y\) 出發，依次經過顏色為 \(l_x,l_y,\cdots\) 的邊的有限唯一增廣路。

因為增廣路有限所以我們可以將增廣路上所有的邊反色，即原來顏色為 \(l_x\) 的修改為 \(l_y\)，原來顏色為 \(l_y\) 的修改為 \(l_x\)。

根據二分圖的性質，節點 \(x\) 不可能為增廣路節點，否則與最小未使用顏色為 \(l_x\) 矛盾。

所以我們可以在增廣之後直接將連接 \(x\) 和 \(y\) 的邊的顏色設為 \(l_x\)。

總構造時間複雜度為 \(O(nm)\)。

示例代碼 UVa10615 Rooks 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <iostream>

typedef char chr;

const int maxN = 100;

int t;
int n;
chr a[maxN + 10][maxN + 10];
int c[maxN + 10][maxN + 10];
int ans;

namespace graph {
struct Vertex {
  int head;
  int deg;
  int vis[maxN + 10];
} vertex[2 * maxN + 10], e;

struct Edge {
  int head;
  int next;
  int col;
} edge[2 * maxN * maxN + 10];

int ecnt;

void init() {
  std::fill(c[0], c[0] + sizeof(c) / 4, 0);
  for (int i = 1; i <= 2 * maxN; i++) vertex[i] = e;
  for (int i = 0; i <= 2 * maxN * maxN; i++) edge[i].col = 0;
  ecnt = 1;
  ans = 0;
  return;
}

void addEdge(int tail, int head) {
  ecnt++;
  edge[ecnt].head = head;
  edge[ecnt].next = vertex[tail].head;
  vertex[tail].head = ecnt;
  vertex[tail].deg++;
  return;
}

int get(int u) {
  for (int i = 1; i <= n; i++)
    if (!vertex[u].vis[i]) return i;
}

void DFS(int u, int ori, int upd) {
  if (vertex[u].vis[ori] == 0) {
    vertex[u].vis[upd] = 0;
    return;
  }
  int e = vertex[u].vis[ori];
  int v = edge[e].head;
  DFS(v, upd, ori);
  edge[e].col = upd;
  edge[e ^ 1].col = upd;
  vertex[u].vis[upd] = e;
  vertex[v].vis[upd] = e ^ 1;
  return;
}

void AddEdge(int u, int v) {
  addEdge(u, v);
  addEdge(v, u);
  return;
}

void solve() {
  for (int u = 1; u <= n; u++) {
    for (int e = vertex[u].head; e; e = edge[e].next) {
      int v = edge[e].head;
      if (edge[e].col) continue;
      int lu = get(u);
      int lv = get(v);
      if (lu < lv) DFS(v, lu, lv);
      if (lu > lv) DFS(u, lv, lu);
      int l = std::min(lu, lv);
      vertex[u].vis[l] = e;
      vertex[v].vis[l] = e ^ 1;
      edge[e].col = l;
      edge[e ^ 1].col = l;
    }
  }
}

void generate() {
  for (int u = 1; u <= n; u++) {
    for (int e = vertex[u].head; e; e = edge[e].next) {
      int v = edge[e].head;
      c[u][v - n] = edge[e].col;
    }
  }
  return;
}
}  // namespace graph

void mian() {
  graph::init();
  std::cin >> n;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) std::cin >> a[i][j];
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      if (a[i][j] == '*') graph::AddEdge(i, j + n);
  for (int i = 1; i <= n * 2; i++) ans = std::max(ans, graph::vertex[i].deg);
  graph::solve();
  graph::generate();
  std::cout << ans << '\n';
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) std::cout << c[i][j] << ' ';
    std::cout << '\n';
  }
  return;
}

int main() {
  std::cin >> t;
  while (t--) mian();
  return 0;
}
一道很不簡單的例題 uoj 444 二分圖

本題為筆者於 2018 年命制的集訓隊第一輪作業題。

首先我們可以發現答案下界為度數不為 k 倍數的點的個數。

下界的構造方法是對二分圖進行拆點。

若 \(degree \bmod k \neq 0\), 我們將其拆為 \(degree/k\) 個度數為 k 的節點和一個度數為 \(degree \bmod k\) 的節點。

若 \(degree \bmod k = 0\), 我們將其拆為 \(degree/k\) 個度數為 k 的節點。

拆出來的點在原圖中的意義相同，也就是説，在滿足度數限制的情況下，一條邊端點可以連接任意一個拆出來的點。

根據 Vizing 定理，我們顯然可以構造出該圖的一種 k 染色方案。

刪邊部分由於和 Vizing 定理關係不大這裏不再展開。

有興趣的讀者可以自行閲讀筆者當時寫的題解。

色多項式

\(P(G,k)\) 表示 G 的不同 k 着色方式的總數。

\(P(K_n, k) = k(k-1)\cdots(k-n+1)\)

\(P(N_n, k) = k^n\)

在無向無環圖 G 中，

  1. \(e=(v_i, v_j) \notin E(G)\)，則 \(P(G, k) = P(G \cup e, k)+P(G\setminus e, k)\)
  2. \(e=(v_i, v_j) \in E(G)\)，則 \(P(G,k)=P(G-e,k)-P(G\setminus e,k)\)

定理：設 \(V_1\) 是 G 的點割集，且 \(G[V_1]\) 是 G 的 \(|V_1|\) 階完全子圖，\(G-V_1\) 有 \(p(p \geq 2)\) 個連通分支，則：

\(P(G,k)=\frac{\Pi_{i=1}^{p}{(P(H_i, k))}}{P(G[V_1], k)^{p-1}}\)

其中 \(H_i=G[V_1 \cup V(G_i)]\)

參考資料

  1. Graph coloring - Wikipedia
  2. Welsh, D. J. A.; Powell, M. B. (1967), "An upper bound for the chromatic number of a graph and its application to timetabling problems", The Computer Journal, 10 (1): 85–86
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用