弦圖

弦圖是一種特殊的圖，很多在一般圖上的 NP-Hard 問題在弦圖上都有優秀的線性時間複雜度算法。

一些定義與性質

子圖：點集和邊集均為原圖點集和邊集子集的圖。

導出子圖（誘導子圖）：點集為原圖點集子集，邊集為所有滿足 兩個端點均在選定點集中 的圖。

團：完全子圖。

極大團：不是其他糰子圖的圖。

最大團：點數最大的團。

團數：最大團的點數，記為 \(\omega(G)\)。

最小染色：用最少的顏色給點染色使得所有邊連接的兩點顏色不同。

色數：最小染色的顏色數，記為 \(\chi(G)\)。

最大獨立集：最大的點集使得點集中任意兩點都沒有邊直接相連。該集合的大小記為 \(\alpha(G)\)。

最小團覆蓋：用最少的團覆蓋所有的點。使用團的數量記為 \(\kappa(G)\)。

弦：連接環中不相鄰兩點的邊。

弦圖：任意長度大於 \(3\) 的環都有一個弦的圖稱為弦圖。

Lemma 1：團數 \(\omega(G)\le \chi(G)\) 色數

證明：考慮單獨對最大團的導出子圖進行染色，至少需要 \(\omega(G)\) 種顏色。

Lemma 2：最大獨立集數 \(\alpha(G)\le \kappa(G)\) 最小團覆蓋數

證明：每個團中至多選擇一個點。

Lemma 3：弦圖的任意導出子圖一定是弦圖。

證明：如果弦圖有導出子圖不是弦圖，説明在這個導出子圖上存在大於 \(3\) 的無弦環，則無論原圖如何（怎麼加邊）都不會使得原圖是弦圖，矛盾。

Lemma 4：弦圖的任意導出子圖一定不可能是一個點數大於 \(3\) 的環。

證明：一個點數大於 \(3\) 的環不是弦圖，用以上定理即可。

弦圖的判定

問題描述

給定一個無向圖，判斷其是否為弦圖。

點割集

對於圖 \(G\) 上的兩點 \(u,v\)，定義這兩點間的 點割集 為滿足刪除這一集合後，\(u,v\) 兩點之間不連通。如果關於 \(u,v\) 兩點間的一個點割集的任意子集都不是點割集，則稱這個點割集為 極小點割集。

Lemma 5：圖關於 \(u,v\) 的極小點割集將原圖分成了若干個連通塊，設包含 \(u\) 的連通塊為 \(V_1\)，包含 \(v\) 的連通塊為 \(V_2\)，則對於極小點割集上的任意一點 \(a\)，\(N(a)\) 一定包含 \(V_1\) 和 \(V_2\) 中的點。

證明：若 \(N(a)\) 只包含 \(V_1\) 或 \(V_2\) 中的至多一個連通塊中的點，從點割集中刪去 \(a\) 點，仍不連通，則原點割集不是最小點割集。

Lemma 6：弦圖上任意兩點間的極小點割集的導出子圖一定為一個團。

證明：極小點割集大小 \(\le 1\) 時，導出子圖一定為一個團。

否則，設極小點割集上有兩點為 \(x,y\)，由 Lemma 5 得，\(N(x)\) 中有 \(V_1,V_2\) 中的點，設為 \(x_1,x_2\)，同樣的，設 \(y_1,y_2\)，注意，可能有 \(x_1=y_1,x_2=y_2\)。

由於 \(V_1,V_2\) 均為連通塊，則在 \(x_1,y_1\) 和 \(x_2,y_2\) 兩個點對之間存在最短路徑。設 \(x,y\) 在 \(V_1,V_2\) 內部的最短路為 \(x-x_1\sim y_1-y,x-x_2\sim y_2-y\)，則圖上存在一個環 \(x-x_1\sim y_1-y-y_2\sim x_2-x\)，該環的大小一定 \(\ge 4\)，根據弦圖的定義，此時該環上一定存在一條弦。

若這條弦連接了 \(V_1,V_2\) 兩個連通塊，則點集不是點割集。若這條弦連接了單個連通塊內部的兩個點或一個連通塊內部的一個點和一個點割集上的點，都不滿足最短路的性質。所以這條弦只能連接 \(x,y\) 兩點。

由此，可證弦圖中每個極小點割集中的兩點都有邊直接相連，故性質得證。

單純點

設 \(N(x)\) 表示與點 \(x\) 相鄰的點集。若點集 \(\{x\}+N(x)\) 的導出子圖為一個團，則稱點 \(x\) 為單純點。

Lemma 7：任何一個弦圖都至少有一個單純點，不是完全圖的弦圖至少有兩個不相鄰的單純點。

證明：數學歸納法。單獨考慮每一連通塊。

歸納基底：當圖與完全圖同構時，圖上任意一點都是單純點。當圖的點數 \(\le 3\) 時，引理成立。

若圖上的點數 \(\ge 4\) 且圖不為完全圖，可知必然存在 \(u,v\) 使得 \((u,v)\notin E\)。設 \(I\) 是圖關於 \(u,v\) 的極小點割集。設 \(A,B\) 分別是刪去 \(I\) 後的導出子圖上 \(u,v\) 所在的連通塊。由於問題的對稱性，我們只考慮 \(A\) 一側的情況，設 \(L=A+I\)。若 \(L\) 為完全圖，則 \(u\) 為單純點；若不是，因為 \(L\) 是原圖的導出子圖，一定也是弦圖，所以有兩個不相鄰的單純點，因為 \(I\) 是一個團，其上兩點都相鄰，所以 \(A\) 中一定有一個單純點。該單純點擴展到全圖也為單純點。

由於每次將整個圖分成若干個連通塊證明，大小一定減小，且都滿足性質，故歸納成立。

完美消除序列

令 \(n=|V|\)，完美消除序列 \(v_1,v_2,\ldots ,v_n\) 為 \(1,2,\ldots ,n\) 的一個排列，滿足 \(v_i\) 在 \(\{v_i,v_{i+1},\ldots ,v_n\}\) 的導出子圖中為單純點。

Lemma 8：一個無向圖是弦圖當且僅當其有一個完全消除序列。

充分性：點數為 \(1\) 的弦圖有完全消除序列。由 Lemma 3 和 Lemma 7，點數為 \(n\) 的弦圖的完美消除序列可以由點數為 \(n-1\) 的弦圖的完美消除序列加上一個單純點得到。

必要性：假設有無向圖存在結點數 \(>3\) 的環且擁有完美消除序列，設在完美消除序列中出現的第一個環上的點為 \(v\)，設 \(v\) 在環上與 \(v_1,v_2\) 相連，則有完美消除序列的性質即單純點的定義可得 \(v_1,v_2\) 直接有邊相連，矛盾。

樸素算法

每次找到一個 單純點 \(v\)，加入到完美消除序列中。

將點 \(v\) 與其相鄰的邊從圖上刪除。

重複以上過程，若所有點都被刪除，則原圖是弦圖且求得了一個完美消除序列；若圖上不存在單純點，則原圖不是弦圖。

時間複雜度 \(O(n^4)\)。

MCS 算法

最大勢算法（Maximum Cardinality Search）是一種可以在 \(O(n+m)\) 的時間複雜度內求出無向圖的完美消除序列的方法。

逆序給結點編號，即按從 \(n\) 到 \(1\) 的順序給點標號。

設 \(label_x\) 表示第 \(x\) 個點與多少個已經標號的點相鄰，每次選擇 \(label\) 值最大的未標號結點進行標號。

用鏈表維護對於每個 \(i\)，滿足 \(label_x=i\) 的 \(x\)。

由於每條邊對 \(\sum_{i=1}^n label_i\) 的貢獻最多是 \(2\)，時間複雜度 \(O(n+m)\)。

正確性證明：

設 \(\alpha(x)\) 為 \(x\) 在這個序列中的位置。我們需要證明對於任何一個弦圖，算法求出的序列一定是一個完美消除序列，即在序列中位於某個點後面且與這個點相連的所有點兩兩相連。

Lemma 9：考慮三個點 \(u,v,w\) 滿足 \(\alpha(u)<\alpha(v)<\alpha(w)\)，如果 \(uw\) 相連，\(vw\) 不相連，則 \(w\) 只給 \(u\) 的 \(label\) 貢獻，不給 \(v\) 貢獻。為了讓 \(v\) 比 \(u\) 先加入序列，需要一個 \(x\) 滿足 \(\alpha(v)<\alpha(x)\) 且 \(vx\) 相連，\(ux\) 不相連，即 \(x\) 只給 \(v\) 貢獻而不給 \(u\) 貢獻。

Lemma 10：任意一個弦圖一定不存在一個序列 \(v_0,v_1,\dots,v_k(k\ge 2)\) 滿足下列性質：

\(v_iv_j\) 相連當且僅當 \(|i-j|=1\)。
\(\alpha(v_0)>\alpha(v_i)(i\in[1,k])\)。
存在 \(i\in[1,k-1]\)，滿足 \(\alpha(v_i)<\alpha(v_{i+1})<\dots<\alpha(v_k)\) 且 \(\alpha(v_i)<\alpha(v_{i-1})<\dots<\alpha(v_1)<\alpha(v_k)<\alpha(v_0)\)。

證明：

由於 \(\alpha(v_1)<\alpha(v_k)<\alpha(v_0)\)，且 \(v_1v_0\) 相連，\(v_kv_0\) 不相連，所以由性質一，存在 \(x\) 滿足 \(\alpha(v_k)<\alpha(x)\) 且 \(v_kx\) 相連，\(v_1x\) 不相連。

考慮最小的 \(j\in(1,k]\) 滿足 \(v_jx\) 相連，我們可以推出 \(v_0x\) 不相連，否則 \(v_0v_1\cdots v_jx\) 構成了一個長度 \(\ge 4\) 且無弦的環。

如果 \(x<v_0\)，則 \(v_0,v_1,\dots,v_j,x\) 也是一個滿足性質的序列；如果 \(v_0<x\) 則 \(x,v_j,\dots,v_1,v_0\) 也是一個滿足性質的序列。

在上面的推導中，我們擴大了 \(\min(v_0,v_k)\)，於是一直推下去，一定會產生矛盾。

Theorem 1：對於任何一個弦圖，最大勢算法求出的序列一定是一個完美消除序列。

證明：考慮任意三個點 \(u,v,w\) 滿足 \(\alpha(u)<\alpha(v)<\alpha(w)\)，我們需要證明若 \(uv\) 相連，\(uw\) 相連，則 \(vw\) 一定相連。

考慮反證法，假設不相連，那麼 \(w,u,v\) 就是一個滿足 Lemma 10 中性質的序列，我們證明了這樣序列不存在，所以矛盾，\(vw\) 相連。

參考代碼：

while (cur) {
  p[cur] = h[nww];
  rnk[p[cur]] = cur;
  h[nww] = nxt[h[nww]];
  lst[h[nww]] = 0;
  lst[p[cur]] = nxt[p[cur]] = 0;
  tf[p[cur]] = true;
  for (vector<int>::iterator it = G[p[cur]].begin(); it != G[p[cur]].end();
       it++)
    if (!tf[*it]) {
      if (h[deg[*it]] == *it) h[deg[*it]] = nxt[*it];
      nxt[lst[*it]] = nxt[*it];
      lst[nxt[*it]] = lst[*it];
      lst[*it] = nxt[*it] = 0;
      deg[*it]++;
      nxt[*it] = h[deg[*it]];
      lst[h[deg[*it]]] = *it;
      h[deg[*it]] = *it;
    }
  cur--;
  if (h[nww + 1]) nww++;
  while (nww && !h[nww]) nww--;
}

如果此時原圖是弦圖，此時求出的就是完美消除序列；但是由於原圖可能不是弦圖，此時求出的一定不是完美消除序列，所以問題轉化為 判斷求出的序列是否是原圖的完美消除序列。

判斷一個序列是否是完美消除序列

樸素算法

根據定義，依次判斷完美消除序列 \(v\) 上 \(\{v_i,v_{i+1},\ldots ,v_n\}\) 中與 \(v_i\) 相鄰的點是否構成了一個團。時間複雜度 \(O(nm)\)。

優化後的算法

根據完美消除序列的定義，設 \(v_i\) 在 \({v_i,v_{i+1},\ldots , v_n}\) 中相鄰的點從小到大為 \(\{v_{c_1},v_{c_2},\ldots ,v_{c_k} \}\)，則只需判斷 \(v_{c_1}\) 與其他點是否直接連通即可。時間複雜度 \(O(n+m)\)。

jud = true;
for (int i = 1; i <= n; i++) {
  cur = 0;
  for (vector<int>::iterator it = G[p[i]].begin(); it != G[p[i]].end(); it++)
    if (rnk[p[i]] < rnk[*it]) {
      s[++cur] = *it;
      if (rnk[s[cur]] < rnk[s[1]]) swap(s[1], s[cur]);
    }
  for (int j = 2; j <= cur; j++)
    if (!st[s[1]].count(s[j])) {
      jud = false;
      break;
    }
}
if (!jud)
  printf("Imperfect\n");
else
  printf("Perfect\n");

至此，弦圖判定問題 可以在 \(O(n+m)\) 的時間複雜度內解決。

弦圖的極大團

令 \(N(x)\) 為滿足與 \(x\) 直接有邊相連且在完美消除序列上的 \(x\) 之後的序列。則弦圖的極大團一定為 \(\{x\}+N(x)\)。

證明：考慮弦圖的一個極大團 \(V\)，其中的點在完美消除序列中出現的第一個點 \(x\)，一定有 \(V\subseteq \{x\}+N(x)\)，又因為 \(V\) 是極大團，所以 \(V=\{x\}+N(x)\)。

弦圖最多有 \(n\) 個極大團。求出弦圖的每個極大團，可以判斷每個 \(\{x\}+N(x)\) 是否為極大團。

設 \(A=\{x\}+N(x),B=\{y\}+N(y)\)，若 \(A\subsetneqq B\)，則 \(A\) 不是極大團。此時在完美消除序列上顯然有 \(y\) 在 \(x\) 前。

設 \(nxt_x\) 表示 \(N(x)\) 中在完美消除序列上最靠前的點，\(y*\) 表示所有滿足 \(A\subseteq B\) 的 \(y\) 中的最靠後的點。此時必然有 \(nxt_{y*}=x\)，否則 \(y*\) 不是最靠後的，令 \(y*=nxt_{y*}\) 仍然滿足條件。

\(A\subsetneqq B\) 當且僅當 \(|A|+1\le |B|\)。

問題轉化為判斷是否存在 \(y\)，滿足 \(nxt_y=x\) 且 \(|N(x)|+1\le |N(y)|\)。時間複雜度 \(O(n+m)\)。

for (int i = 1; i <= n; i++) {
  cur = 0;
  for (vector<int>::iterator it = G[p[i]].begin(); it != G[p[i]].end(); it++)
    if (rnk[p[i]] < rnk[*it]) {
      s[++cur] = *it;
      if (rnk[s[cur]] < rnk[s[1]]) swap(s[1], s[cur]);
    }
  fst[p[i]] = s[1];
  N[p[i]] = cur;
}
for (int i = 1; i <= n; i++) {
  if (!vis[p[i]]) ans++;
  if (N[p[i]] >= N[fst[p[i]]] + 1) vis[fst[p[i]]] = true;
}

弦圖的色數/弦圖的團數

一種構造方法：按完美消除序列從後往前依次給每個點染色，給每個點染上可以染的最小顏色。時間複雜度 \(O(m+n)\)。

正確性證明：設以上方法使用了 \(t\) 種顏色，則 \(t\ge \chi(G)\)。由於團上每個點都是不同的顏色，所以 \(t=\omega(G)\)，由 Lemma 1，\(t=\omega(G)\le \chi(G)\)。綜上，可得 \(t=\chi(G)=\omega(G)\)。

無需染色方案，只需求出弦圖的色數/團數時，可以取 \(|\{x\}+N(x)|\) 的最大值得到。

for (int i = 1; i <= n; i++) ans = max(ans, deg[i] + 1);

弦圖的最大獨立集/最小團覆蓋

最大獨立集：完美消除序列從前往後，選擇所有沒有與已經選擇的點有直接連邊的點。

最小團覆蓋：設最大獨立集為 \(\{v_1,v_2,\ldots ,v_t\}\)，則團的集合 \(\{\{v_1+N(v_1)\},\{v_2+N(v_2)\},\ldots ,\{v_t+N(v_t)\} \}\) 為圖的最小團覆蓋。時間複雜度均為 \(O(n+m)\)。

正確性證明：設以上方案獨立集數和團覆蓋數為 \(t\)，由定義得 \(t\le \alpha(G),t\ge \kappa(G)\)，由 Lemma 2 得，\(\alpha(G)\le \kappa(G)\)，所以 \(t=\alpha(G)=\kappa(G)\)。

for (int i = 1; i <= n; i++)
  if (!vis[p[i]]) {
    ans++;
    for (vector<int>::iterator it = G[p[i]].begin(); it != G[p[i]].end(); it++)
      vis[*it] = true;
  }

習題

SPOJ FISHNET - Fishing Net

P3196[HNOI2008] 神奇的國度

P3852[TJOI2007] 小朋友

參考資料

弦圖相關

2009 WC 講稿

弦圖總結 - 租酥雨

R. E. Tarjan and M. Yannakakis, Simple linear-time algorithms to test chordality of graphs,test acyclicity of hypergraphs,and selectively reduce acyclic hypergraphs, SIAM J. Comput., 13 (1984), pp. 566–579.

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用