一些定义

最大团点数最多的团, 记为团数 ω(G)\omega(G)

弦(chord)：连接环中不相邻的两个点的边。

弦图(chordal graph)：一个无向图称为弦图当图中任意长度大于3的环都至少有一个弦。

弦图的每一个诱导子图一定是弦图。

单纯点(simplicial vertex)：设 N(v)N(v) 表示与点 vv 相邻的点集。一个点称为单纯点当 {v}+N(v)\{v\} + N(v) 的诱导子图为一个团。

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

完美消除序列

定义

定义：一个点的序列(每个点出现且恰好出现一次) v1,v2,⋯ ,vnv_1, v_2,\cdots, v_n 满足 viv_i 在{vi,vi+1,⋯ ,vn}\{v_i, v_{i+1},\cdots,v_n\} 的诱导子图中为一个单纯点。

定理

一个无向图是弦图当且仅当它有一个完美消除序列。

从 nn 到 11 的顺序依次给点标号 (标号为 ii 的点出现在完美消除序列的第 ii 个)。

设 labeli\text{label}_i 表示第 ii 个点与多少个已标号的点相邻，每次选择 labeli\text{label}_i 最大的未标号的点进行标号。

不难发现 labeli\text{label}_i 的值是单调的，且权值在 [0,n][0,n] 之间，所以只要对每一个权值开一个链表，再维护一个指针即可做到 O(n+m)O(n+m)。

弦图的点染色问题

用最少的颜色给每个点染色使得相邻的点染的颜色不同。

HNOI2008 神奇的国度

团数 ω(G)\omega(G) = 色数 χ(G)\chi(G)

完美消除序列从后往前依次给每个点染色，给每个点染上可以染的最小的颜色。

代码

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
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
  cin.tie(nullptr)->sync_with_stdio(0);

  int n , m;
  cin >> n >> m;

  vector<vector<int>> G(n + 1 , vector<int>());

  for (int i = 1 ; i <= m ; i++) {
    int u , v;
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }

  vector<vector<int>> p(n + 1 , vector<int>());

  vector<int> vis(n + 1) , label(n + 1);

  for (int i = 1 ; i <= n ; i++) {
    p[0].push_back(i);
  }

  int cur = 0;

  for (int i = n ; i >= 1 ; i--) {
    int flag = true , u = 0; 
    while (flag) {
      for (int j = p[cur].size() - 1 ; j >= 0 ; j--) {
        int v = p[cur][j];
        if (!vis[v]) {
          vis[v] = 1 , flag = 0;
          u = v;
          break;
        }
        p[cur].pop_back();
      }
      if (flag) --cur;
    }
    for (int v : G[u]) {
      if (vis[v]) continue;
      p[++label[v]].push_back(v);
      cur = max(cur , label[v]);
    }
  }

  cout << *max_element(label.begin() , label.end()) + 1 << endl;

  return 0;
}

最大独立集

完美消除序列 从前往后能选就选 , 最大独立集记为 α(G)\alpha(G)

最小团覆盖

设最大独立集为 {p1,p2,⋯ ,pt}\{p_1 , p_2 , \cdots , p_t\} ，则 {p1∪N(p1),⋯ ,pt∪N(pt)}\{p_1 \cup N(p_1), \cdots, p_t \cup N(p_t)\} 为最小团覆盖。 记为 κ(G)\kappa(G)

最大独立集数 = 最小团覆盖数

完美图与伴完美图

完美图 (Perfect Graph) 的概念

一个图 GG 称为完美图若它的每一个诱导子图都满足 ω(G)=χ(G)\omega(G)=\chi(G)

伴完美图 (Co-perfect Graph) 的概念

一个图 GG 称为伴完美图若它的每一个诱导子图都满足 α(G)=κ(G)\alpha(G) = \kappa(G)

完美图 = 伴完美图 , 弦图属于完美图。

区间图

区间图 (Interval Graph) 定义

给定一些区间，定义一个相交图为每个顶点表示一个区间，两个点有边当且仅当两个区间的交集非空。

一个图为区间图当它是若干个区间的相交图。

区间图一定是弦图。

区间图完美序列求法

给定 nn 个区间，所对应的区间图为 GG

GG 的一个完美消除序列：将所有的区间按照右端点从小到大排序。

例题1

给定 nn 个区间，要求选择最多的区间使得区间不互相重叠

即求区间图的最大独立集。

将所有的区间按照右端点从小到大排序，依次处理每个区间，如果与已选区间没有重叠则选择该区间。

时间复杂度：O(nlog⁡n)O(n\log n)

例题2

有 nn 个积木，高度均为 11 ，第 ii 个积木的宽度范围为 [Li,Ri][L_i, R_i] ，选择一个积木的下落顺序使得最后积木总高度尽可能小。

即求区间图的最小染色。积木下落顺序：按照颜色标号从小到大落下。

将所有的区间按照右端点从大到小排序，依次处理每个区间，选择一个可以染的最小的颜色染色。

时间复杂度：O(nlog⁡n)O(n\log n)