弦图

弦图是一种特殊的图，很多在一般图上的 NP-Hard 问题在弦图上都有优秀的线性时间复杂度算法。

一些定义与性质

子图：点集和边集均为原图点集和边集子集的图。

导出子图（诱导子图）：点集为原图点集子集，边集为所有满足 两个端点均在选定点集中 的图。

团：完全子图。

极大团：不是其他团子图的图。

最大团：点数最大的团。

团数：最大团的点数，记为 $\omega(G)$ 。

最小染色：用最少的颜色给点染色使得所有边连接的两点颜色不同。

色数：最小染色的颜色数，记为 $\chi(G)$ 。

最大独立集：最大的点集使得点集中任意两点都没有边直接相连。该集合的大小记为 $\alpha(G)$ 。

最小团覆盖：用最少的团覆盖所有的点。使用团的数量记为 $\kappa(G)$ 。

弦：连接环中不相邻两点的边。

弦图：任意长度大于的环都有一个弦的图称为弦图。

Lemma 1：团数 $\omega(G)\le \chi(G)$ 色数

证明：考虑单独对最大团的导出子图进行染色，至少需要 $\omega(G)$ 种颜色。

Lemma 2：最大独立集数 $\alpha(G)\le \kappa(G)$ 最小团覆盖数

证明：每个团中至多选择一个点。

Lemma 3：弦图的任意导出子图一定是弦图。

证明：如果弦图有导出子图不是弦图，说明在这个导出子图上存在大于的无弦环，则无论原图如何（怎么加边）都不会使得原图是弦图，矛盾。

Lemma 4：弦图的任意导出子图一定不可能是一个点数大于的环。

证明：一个点数大于的环不是弦图，用以上定理即可。

弦图的判定

问题描述

给定一个无向图，判断其是否为弦图。

点割集

对于图上的两点，定义这两点间的 点割集 为满足删除这一集合后，两点之间不连通。如果关于两点间的一个点割集的任意子集都不是点割集，则称这个点割集为 极小点割集。

Lemma 5：图关于的极小点割集将原图分成了若干个连通块，设包含的连通块为，包含的连通块为，则对于极小点割集上的任意一点，一定包含和中的点。

证明：若只包含或中的至多一个连通块中的点，从点割集中删去点，仍不连通，则原点割集不是最小点割集。

Lemma 6：弦图上任意两点间的极小点割集的导出子图一定为一个团。

证明：极小点割集大小 $\le 1$ 时，导出子图一定为一个团。

否则，设极小点割集上有两点为，由 Lemma 5 得，中有中的点，设为，同样的，设，注意，可能有。

由于均为连通块，则在和两个点对之间存在最短路径。设在内部的最短路为 $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$ ，根据弦图的定义，此时该环上一定存在一条弦。

若这条弦连接了两个连通块，则点集不是点割集。若这条弦连接了单个连通块内部的两个点或一个连通块内部的一个点和一个点割集上的点，都不满足最短路的性质。所以这条弦只能连接两点。

由此，可证弦图中每个极小点割集中的两点都有边直接相连，故性质得证。

单纯点

设表示与点相邻的点集。若点集 $\{x\}+N(x)$ 的导出子图为一个团，则称点为单纯点。

Lemma 7：任何一个弦图都至少有一个单纯点，不是完全图的弦图至少有两个不相邻的单纯点。

证明：数学归纳法。单独考虑每一连通块。

归纳基底：当图与完全图同构时，图上任意一点都是单纯点。当图的点数 $\le 3$ 时，引理成立。

若图上的点数 $\ge 4$ 且图不为完全图，可知必然存在使得 $(u,v)\notin E$ 。设是图关于的极小点割集。设分别是删去后的导出子图上所在的连通块。由于问题的对称性，我们只考虑一侧的情况，设。若为完全图，则为单纯点；若不是，因为是原图的导出子图，一定也是弦图，所以有两个不相邻的单纯点，因为是一个团，其上两点都相邻，所以中一定有一个单纯点。该单纯点扩展到全图也为单纯点。

由于每次将整个图分成若干个连通块证明，大小一定减小，且都满足性质，故归纳成立。

完美消除序列

令，完美消除序列 $v_1,v_2,\ldots ,v_n$ 为 $1,2,\ldots ,n$ 的一个排列，满足在 $\{v_i,v_{i+1},\ldots ,v_n\}$ 的导出子图中为单纯点。

Lemma 8：一个无向图是弦图当且仅当其有一个完全消除序列。

充分性：点数为的弦图有完全消除序列。由 Lemma 3 和 Lemma 7，点数为的弦图的完美消除序列可以由点数为的弦图的完美消除序列加上一个单纯点得到。

必要性：假设有无向图存在结点数的环且拥有完美消除序列，设在完美消除序列中出现的第一个环上的点为，设在环上与相连，则有完美消除序列的性质即单纯点的定义可得直接有边相连，矛盾。

朴素算法

每次找到一个 单纯点 ，加入到完美消除序列中。

将点与其相邻的边从图上删除。

重复以上过程，若所有点都被删除，则原图是弦图且求得了一个完美消除序列；若图上不存在单纯点，则原图不是弦图。

时间复杂度。

MCS 算法

最大势算法（Maximum Cardinality Search）是一种可以在的时间复杂度内求出无向图的完美消除序列的方法。

逆序给结点编号，即按从到的顺序给点标号。

设表示第个点与多少个已经标号的点相邻，每次选择值最大的未标号结点进行标号。

用链表维护对于每个，满足的。

由于每条边对 $\sum_{i=1}^n label_i$ 的贡献最多是，时间复杂度。

正确性证明：

设 $\alpha(x)$ 为在这个序列中的位置。我们需要证明对于任何一个弦图，算法求出的序列一定是一个完美消除序列，即在序列中位于某个点后面且与这个点相连的所有点两两相连。

Lemma 9：考虑三个点满足 $\alpha(u)<\alpha(v)<\alpha(w)$ ，如果相连，不相连，则只给的贡献，不给贡献。为了让比先加入序列，需要一个满足 $\alpha(v)<\alpha(x)$ 且相连，不相连，即只给贡献而不给贡献。

Lemma 10：任意一个弦图一定不存在一个序列 $v_0,v_1,\dots,v_k(k\ge 2)$ 满足下列性质：

相连当且仅当。
$\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)$ ，且相连，不相连，所以由性质一，存在满足 $\alpha(v_k)<\alpha(x)$ 且相连，不相连。

考虑最小的 $j\in(1,k]$ 满足相连，我们可以推出不相连，否则 $v_0v_1\cdots v_jx$ 构成了一个长度 $\ge 4$ 且无弦的环。

如果，则 $v_0,v_1,\dots,v_j,x$ 也是一个满足性质的序列；如果则 $x,v_j,\dots,v_1,v_0$ 也是一个满足性质的序列。

在上面的推导中，我们扩大了 $\min(v_0,v_k)$ ，于是一直推下去，一定会产生矛盾。

Theorem 1：对于任何一个弦图，最大势算法求出的序列一定是一个完美消除序列。

证明：考虑任意三个点满足 $\alpha(u)<\alpha(v)<\alpha(w)$ ，我们需要证明若相连，相连，则一定相连。

考虑反证法，假设不相连，那么就是一个满足 Lemma 10 中性质的序列，我们证明了这样序列不存在，所以矛盾，相连。

参考代码：

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_i,v_{i+1},\ldots ,v_n\}$ 中与相邻的点是否构成了一个团。时间复杂度。

优化后的算法

根据完美消除序列的定义，设在 ${v_i,v_{i+1},\ldots , v_n}$ 中相邻的点从小到大为 $\{v_{c_1},v_{c_2},\ldots ,v_{c_k} \}$ ，则只需判断 $v_{c_1}$ 与其他点是否直接连通即可。时间复杂度。

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");

至此，弦图判定问题 可以在的时间复杂度内解决。

弦图的极大团

令为满足与直接有边相连且在完美消除序列上的之后的序列。则弦图的极大团一定为 $\{x\}+N(x)$ 。

证明：考虑弦图的一个极大团，其中的点在完美消除序列中出现的第一个点，一定有 $V\subseteq \{x\}+N(x)$ ，又因为是极大团，所以 $V=\{x\}+N(x)$ 。

弦图最多有个极大团。求出弦图的每个极大团，可以判断每个 $\{x\}+N(x)$ 是否为极大团。

设 $A=\{x\}+N(x),B=\{y\}+N(y)$ ，若 $A\subsetneqq B$ ，则不是极大团。此时在完美消除序列上显然有在前。

设表示中在完美消除序列上最靠前的点，表示所有满足 $A\subseteq B$ 的中的最靠后的点。此时必然有 $nxt_{y*}=x$ ，否则不是最靠后的，令 $y*=nxt_{y*}$ 仍然满足条件。

$A\subsetneqq B$ 当且仅当 $|A|+1\le |B|$ 。

问题转化为判断是否存在，满足且 $|N(x)|+1\le |N(y)|$ 。时间复杂度。

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;
}

弦图的色数/弦图的团数

一种构造方法：按完美消除序列从后往前依次给每个点染色，给每个点染上可以染的最小颜色。时间复杂度。

正确性证明：设以上方法使用了种颜色，则 $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)\} \}$ 为图的最小团覆盖。时间复杂度均为。

正确性证明：设以上方案独立集数和团覆盖数为，由定义得 $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.

本页面最近更新：2024/3/27 06:46:12，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：StudyingFather, chenjy2003, Enter-tainer, Henry-ZHR, hsfzLZH1, ImpleLee, TianyiQ, Tiphereth-A
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用