弦图与区间图 Chordal Graph and Interval Graph 清华大学 陈丹琦 1

图的基本概念 子图 (subgraph) 图 为图G的子图 2

图的基本概念 图 称为图G的诱导子图 3

图的基本概念 团(clique) 图G的一个子图 ， 为关于 的完全图。 4

图的基本概念 团(clique) 极大团(maximal clique) 一个团是极大团当它不是其它团的子集。 图G的一个子图 ， 为关于 的完全图。 极大团(maximal clique) 一个团是极大团当它不是其它团的子集。 5

图的基本概念 团(clique) 极大团(maximal clique) 最大团(maximum clique) 图G的一个子图 ， 为关于 的完全图。 极大团(maximal clique) 一个团是极大团当它不是其它团的子集。 最大团(maximum clique) 点数最多的团。 团数 6

图的基本概念 最小染色(minimum coloring) 用最少的颜色给点染色使相邻点颜色不同。 色数 7

图的基本概念 最大独立集(maximum independent set) 最大的一个点的子集使任何两个点不相邻。 8

图的基本概念 最小团覆盖(minimum clique cover) 用最少个数的团覆盖所有的点。 9

图的基本概念 团数 ≤ 色数 10

图的基本概念 团数 ≤ 色数 最大独立集数 ≤ 最小团覆盖数 11

弦图的概念 弦(chord)：连接环中不相邻的两个点的边。 Chord 12

弦图的概念 弦(chord)：连接环中不相邻的两个点的边。 弦图(chordal graph)：一个无向图称为弦图当图中任意长度大于3的环都至少有一个弦。 13

弦图的概念 弦(chord)：连接环中不相邻的两个点的边。 弦图(chordal graph)：一个无向图称为弦图当图中任意长度大于3的环都至少有一个弦。 弦图的每一个诱导子图一定是弦图。 弦图的任一个诱导子图不同构于Cn (n > 3) 14

弦图的判定 [例题 ] Zju1015 Fishing net 给定一个无向图，判定它是否为弦图。 单纯点(simplicial vertex)：设N(v)表示与点v相邻的点集。一个点称为单纯点当{v} + N(v)的诱导子图为一个团。 15

弦图的判定 [例题 ] Zju1015 Fishing net 给定一个无向图，判定它是否为弦图。 单纯点(simplicial vertex)：设N(v)表示与点v相邻的点集。一个点称为单纯点当{v} + N(v)的诱导子图为一个团。 16

弦图的判定 [例题 ] Zju1015 Fishing net 给定一个无向图，判定它是否为弦图。 单纯点(simplicial vertex)：设N(v)表示与点v相邻的点集。一个点称为单纯点当{v} + N(v)的诱导子图为一个团。 引理：任何一个弦图都至少有一个单纯点，不是完全图的弦图至少有两个不相邻的单纯点。 17

弦图的判定 完美消除序列(perfect elimination ordering) 定义：一个点的序列(每个点出现且恰好出现一次)v1, v2, …, vn满足vi在{vi, vi+1,…,vn}的诱导子图中为一个单纯点。 v3 v2 v1 v6 v5 v4 18

弦图的判定 完美消除序列(perfect elimination ordering) 定义：一个点的序列(每个点出现且恰好出现一次)v1, v2, …, vn满足vi在{vi, vi+1,…,vn}的诱导子图中为一个单纯点。 v3 v2 v1 v6 v5 v4 19

弦图的判定 定理：一个无向图是弦图当且仅当它有一个完美消除序列。 20

弦图的判定 定理：一个无向图是弦图当且仅当它有一个完美消除序列。 证明： 充分性 由引理知任何一个弦图都至少有一个单纯点以及弦图的诱导子图都是弦图。可以使用数学归纳法假设当点数<n的弦图一定有完美消除序列，那么点数为n的弦图的完美消除序列可以由一个单纯点加上剩余点的诱导子图的完美消除序列得到。 21

弦图的判定 定理：一个无向图是弦图当且仅当它有一个完美消除序列。 证明： 必要性 反证若无向图存在一个长度 > 3的无弦环，不妨设环中在完美消除序列中出现在最前面的点为v，设环中v与v1, v2相连，根据完美消除序列的性质知v1, v2相连，与环无弦矛盾。所以无向图为弦图。 22

求完美消除序列 最朴素的算法： 每次找一个单纯点v，加入到完美消除序列中。 将v以及相关的边从图中删掉。 23

求完美消除序列 最朴素的算法： 时间复杂度?? O(n4) 每次找一个单纯点v，加入到完美消除序列中。 将v以及相关的边从图中删掉。 24

求完美消除序列 最朴素的算法： 时间复杂度?? O(n4) 每次找一个单纯点v，加入到完美消除序列中。 将v以及相关的边从图中删掉。 下面介绍两个求完美消除序列O(m + n)的算法。 25

LexBFS算法 字典序广度优先搜索(Lexicographic BFS) 从n到1的顺序依次给点标号。 每个点维护一个list记录与它相邻的已标号点的标号，list中的标号按照按从大到小排序。 每次选择list字典序最大的未标号点标号。 26

LexBFS算法 LexBFS与BFS不同在于每次扩展的节点加了特殊的顺序。 27

LexBFS算法 LexBFS与BFS不同在于每次扩展的节点加了特殊的顺序。 vn 28

LexBFS算法 LexBFS与BFS不同在于每次扩展的节点加了特殊的顺序。 vn 29

LexBFS算法 LexBFS与BFS不同在于每次扩展的节点加了特殊的顺序。 vn vn-1 vn 30

LexBFS算法 LexBFS与BFS不同在于每次扩展的节点加了特殊的顺序。 vn vn-1 vn 31

LexBFS算法 ? 算法实现 32

LexBFS算法 算法实现 更新一个点的list最多新建一个桶。 任何时候桶的数目不超过n。 33

LexBFS算法 算法实现 O(m + n)!!! 更新一个点的list最多新建一个桶。 任何时候桶的数目不超过n。 34

MCS算法 最大势算法 Maximum Cardinality Search 从n到1的顺序依次给点标号(标号为i的点出现在完美消除序列的第i个)。 设label[i]表示第i个点与多少个已标号的点相 邻，每次选择label[i]最大的未标号的点进行标号。 35

MCS算法 最大势算法 Maximum Cardinality Search i = 7 从n到1的顺序依次给点标号(标号为i的点出现在完美消除序列的第i个)。 设label[i]表示第i个点与多少个已标号的点相 邻，每次选择label[i]最大的未标号的点进行标号。 0 0 1 0 i = 7 0 0 1 36

MCS算法 最大势算法 Maximum Cardinality Search i = 6 从n到1的顺序依次给点标号(标号为i的点出现在完美消除序列的第i个)。 设label[i]表示第i个点与多少个已标号的点相 邻，每次选择label[i]最大的未标号的点进行标号。 0 0 2 0 i = 6 0 1 1 37

MCS算法 最大势算法 Maximum Cardinality Search i = 5 从n到1的顺序依次给点标号(标号为i的点出现在完美消除序列的第i个)。 设label[i]表示第i个点与多少个已标号的点相 邻，每次选择label[i]最大的未标号的点进行标号。 0 1 2 0 i = 5 0 2 1 38

MCS算法 最大势算法 Maximum Cardinality Search i = 4 从n到1的顺序依次给点标号(标号为i的点出现在完美消除序列的第i个)。 设label[i]表示第i个点与多少个已标号的点相 邻，每次选择label[i]最大的未标号的点进行标号。 0 2 2 0 i = 4 1 2 1 39

MCS算法 最大势算法 Maximum Cardinality Search i = 3 从n到1的顺序依次给点标号(标号为i的点出现在完美消除序列的第i个)。 设label[i]表示第i个点与多少个已标号的点相 邻，每次选择label[i]最大的未标号的点进行标号。 1 2 2 0 i = 3 2 2 1 40

MCS算法 最大势算法 Maximum Cardinality Search i = 2 从n到1的顺序依次给点标号(标号为i的点出现在完美消除序列的第i个)。 设label[i]表示第i个点与多少个已标号的点相 邻，每次选择label[i]最大的未标号的点进行标号。 2 2 2 0 i = 2 2 2 1 41

MCS算法 最大势算法 Maximum Cardinality Search i = 1 从n到1的顺序依次给点标号(标号为i的点出现在完美消除序列的第i个)。 设label[i]表示第i个点与多少个已标号的点相 邻，每次选择label[i]最大的未标号的点进行标号。 2 2 2 0 i = 1 2 2 1 42

MCS算法 43

MCS算法 ? 算法实现 44

MCS算法 算法实现 1 2 45

MCS算法 算法实现 O(m + n)!!! 1 2 46

弦图的判定 判断一个序列是否为完美消除序列 47

弦图的判定 判断一个序列是否为完美消除序列 朴素的算法 依次判断 {vi+1,…,vn}中所有与vi相邻的点是否构成了一个团。 时间复杂度: 48

弦图的判定 判断一个序列是否为完美消除序列 优化后的算法 设{vi+1,…,vn}中所有与vi相邻的点依次为vj1, …, vjk。 只需判断vj1是否与vj2, …, vjk相邻即可。 时间复杂度: O(m + n) 49

弦图的判定 判断一个序列是否为完美消除序列 优化后的算法 弦图判定问题可以在O(m + n)的时间内解决。 设{vi+1,…,vn}中所有与vi相邻的点依次为vj1, …, vjk。 只需判断vj1是否与vj2, …, vjk相邻即可。 时间复杂度: O(m + n) 弦图判定问题可以在O(m + n)的时间内解决。 50

弦图的极大团 设第i个点在弦图的完美消除序列第p(i)个。 令N(v) = {w | w与v相邻且p(w) > p(v)} 弦图的极大团一定是 的形式。 证明： 设点集V的诱导子图为弦图的极大团，设v为V中p(i)值最小的点即出现在完美消除序列中最前面的点。由于 为一个团，V为极大团所以 。 51

弦图的极大团 推论：弦图最多有n个极大团。 设第i个点在弦图的完美消除序列第p(i)个。 令N(v) = {w | w与v相邻且p(w) > p(v)} 弦图的极大团一定是 的形式。 推论：弦图最多有n个极大团。 如何找到弦图的所有极大团呢? 即判断每个 是否为极大团 52

弦图的极大团 判断 是否为极大团 设A = ，若存在B = 使得 则A不是极大团。 53

弦图的极大团 判断 是否为极大团 设A = ，若存在B = 使得 则A不是极大团。 p(w) < p(v) 54

弦图的极大团 判断 是否为极大团 设A = ，若存在B = 使得 则A不是极大团。 判断 是否为极大团 设A = ，若存在B = 使得 则A不是极大团。 p(w) < p(v) 设next(v) 表示N(v)中最前的点。令w*表示所有满足 的w中最后的一个点。 55

弦图的极大团 判断 是否为极大团 设A = ，若存在B = 使得 则A不是极大团。 判断 是否为极大团 设A = ，若存在B = 使得 则A不是极大团。 p(w) < p(v) 设next(v) 表示N(v)中最前的点。令w*表示所有满足 的w中最后的一个点。 next(w*) = v (否则next(w*)也是满足条件的w) 56

弦图的极大团 Next(w) = v 当且仅当 |N(v)| + 1 ≤ |N(w)| 57

弦图的极大团 Next(w) = v 只需判断是否存在一个w，满足Next(w) = v 且|N(v)| + 1 ≤ |N(w)|即可。 当且仅当 |N(v)| + 1 ≤ |N(w)| 只需判断是否存在一个w，满足Next(w) = v 且|N(v)| + 1 ≤ |N(w)|即可。 时间复杂度：O(m + n) 58

弦图的点染色问题 用最少的颜色给每个点染色使得相邻的点染的颜色不同。 [例题] HNOI2008《神奇的国度》 59

弦图的点染色问题 用最少的颜色给每个点染色使得相邻的点染的颜色不同。 [例题] HNOI2008《神奇的国度》 完美消除序列从后往前依次给每个点染色，给每个点染上可以染的最小的颜色。 60

弦图的点染色问题 用最少的颜色给每个点染色使得相邻的点染的颜色不同。 [例题] HNOI2008《神奇的国度》 v3 v2 v1 v6 v5 61

弦图的点染色问题 用最少的颜色给每个点染色使得相邻的点染的颜色不同。 [例题] HNOI2008《神奇的国度》 v3 v2 v1 v6 v5 62

弦图的点染色问题 用最少的颜色给每个点染色使得相邻的点染的颜色不同。 [例题] HNOI2008《神奇的国度》 v3 v2 v1 v6 v5 63

弦图的点染色问题 用最少的颜色给每个点染色使得相邻的点染的颜色不同。 [例题] HNOI2008《神奇的国度》 v3 v2 v1 v6 v5 64

弦图的点染色问题 用最少的颜色给每个点染色使得相邻的点染的颜色不同。 [例题] HNOI2008《神奇的国度》 v3 v2 v1 v6 v5 65

弦图的点染色问题 用最少的颜色给每个点染色使得相邻的点染的颜色不同。 [例题] HNOI2008《神奇的国度》 v3 v2 v1 v6 v5 66

弦图的点染色问题 用最少的颜色给每个点染色使得相邻的点染的颜色不同。 [例题] HNOI2008《神奇的国度》 v3 v2 v1 v6 v5 67

弦图的点染色问题 用最少的颜色给每个点染色使得相邻的点染的颜色不同。 [例题] HNOI2008《神奇的国度》 证明： 设使用了T种颜色, 则T ≥ 色数 T = 团数 ≤ 色数 团数 = 色数 = T 时间复杂度： O(m + n) 68

弦图的点染色问题 团数 = 色数!!! 用最少的颜色给每个点染色使得相邻的点染的颜色不同。 [例题] HNOI2008《神奇的国度》 证明： 设使用了T种颜色, 则T ≥ 色数 T = 团数 ≤ 色数 团数 = 色数 = T 团数 = 色数!!! 时间复杂度： O(m + n) 69

弦图的最大独立集和最小团覆盖 最大独立集 选择最多的点使得任意两个点不相邻。 70

弦图的最大独立集和最小团覆盖 最大独立集 选择最多的点使得任意两个点不相邻。 Sol 完美消除序列从前往后能选就选。 v3 v2 v1 v6 71

弦图的最大独立集和最小团覆盖 最小团覆盖 用最少个数的团覆盖所有的点。 72

弦图的最大独立集和最小团覆盖 最小团覆盖 用最少个数的团覆盖所有的点。 Sol 设最大独立集为{p1 , p2 , …, pt}，则{p1∪N(p1), …, pt∪N(pt)}为最小团覆盖。 v3 v2 v1 v6 v5 v4 73

弦图的最大独立集和最小团覆盖 证明 {p1 , p2 , …, pt}为一个独立集。 t ≤ 74

弦图的最大独立集和最小团覆盖 证明 {p1 , p2 , …, pt}为一个独立集。 t ≤ {p1∪N(p1), …, pt∪N(pt)}为一个团覆盖。 t ≥ 75

弦图的最大独立集和最小团覆盖 证明 {p1 , p2 , …, pt}为一个独立集。 t ≤ {p1∪N(p1), …, pt∪N(pt)}为一个团覆盖。 t ≥ 由 知 最大独立集数 = 最小团覆盖数!!! 76

完美图与伴完美图 完美图(Perfect Graph)的概念 一个图G称为完美图若它的每一个诱导子图都满足 。 77

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

完美图与伴完美图 完美图(Perfect Graph)的概念 伴完美图(Co-perfect Graph)的概念 完美图 = 伴完美图 完美图 = 伴完美图 弦图属于完美图。 79

区间图 区间图(Interval Graph)定义 给定一些区间，定义一个相交图为每个顶点表示一个区间，两个点有边当且仅当两个区间的交集非空。 一个图为区间图当它是若干个区间的相交图。 1 2 2 5 3 3 1 4 5 4 80

区间图 区间图一定是弦图。 证明： 若区间图中存在一个长度 > 3的无弦环 {v0 ,v1 ,…, vl-1 , vl = v0}, l > 3，设第i个点对应的区间为Ii。由Ii与Ii+1相交, 取 ，由于Ii与Ii+2不相交，则pi一定严格递增或严格递减。由 及 得到 ，与I0与I2不相交矛盾。所以区间图一定是弦图。 81

经典问题 [例题1] 给定n个区间，要求选择最多的区间 使得区间不互相重叠。 82

经典问题 [例题1] 给定n个区间，要求选择最多的区间 使得区间不互相重叠。 区间图的最大独立集 83

经典问题 [例题2] Tetris 有n个积木，高度均为1，第i个积木的宽度范围为[Li, Ri]，选择一个积木的下落顺序使得最后积木总高度尽可能小。 84

经典问题 区间图的最小染色 [例题2] Tetris 有n个积木，高度均为1，第i个积木的宽度范围为[Li, Ri]，选择一个积木的下落顺序使得最后积木总高度尽可能小。 区间图的最小染色 积木下落顺序：按照颜色标号从小到大落下。 85

区间图 给定n个区间，所对应的区间图为G G的一个完美消除序列： 将所有的区间按照右端点从小到大排序。 86

区间图 [例题1] 将所有的区间按照右端点从小到大排序，依次处理每个区间，如果与已选区间没有重叠则选择该区间。 给定n个区间，所对应的区间图为G G的一个完美消除序列： 将所有的区间按照右端点从小到大排序。 [例题1] 将所有的区间按照右端点从小到大排序，依次处理每个区间，如果与已选区间没有重叠则选择该区间。 时间复杂度：O(nlog2n) 87

区间图 [例题2] 将所有的区间按照右端点从大到小排序，依次处理每个区间，选择一个可以染的最小的颜色染色。 给定n个区间，所对应的区间图为G 将所有的区间按照右端点从小到大排序。 [例题2] 将所有的区间按照右端点从大到小排序，依次处理每个区间，选择一个可以染的最小的颜色染色。 线段树或堆维护 时间复杂度：O(nlog2n) 88

树的分解(Tree Decomposition) 定义 对于一个无向图G = (V, E), 树的分解定义为(X, T), X = {X1 , X2 , …, Xm}其中Xi为V的一个子集，T是一棵树，点集为X。T满足以下几个性质： 89

树的分解(Tree Decomposition) 定义 对于一个无向图G = (V, E), 树的分解定义为(X, T), X = {X1 , X2 , …, Xm}其中Xi为V的一个子集，T是一棵树，点集为X。T满足以下几个性质： X1 ∪ X2 ∪ … ∪ Xm =V 90

树的分解(Tree Decomposition) 定义 对于一个无向图G = (V, E), 树的分解定义为(X, T), X = {X1 , X2 , …, Xm}其中Xi为V的一个子集，T是一棵树，点集为X。T满足以下几个性质： X1 ∪ X2 ∪ … ∪ Xm =V 图G中任何一条边(u, v)存在一个Xi使得u, v∈ Xi。 91

树的分解(Tree Decomposition) 定义 对于一个无向图G = (V, E), 树的分解定义为(X, T), X = {X1 , X2 , …, Xm}其中Xi为V的一个子集，T是一棵树，点集为X。T满足以下几个性质： X1 ∪ X2 ∪ … ∪ Xm =V 图G中任何一条边(u, v)存在一个Xi使得u, v∈ Xi。 对于每一个点v，P(v)={Xi | v ∈Xi}，则T中P(v)的诱导子图是连通的。 92

树的分解(Tree Decomposition) 93

Clique Tree 一个无向图G的极大团树T(Clique Tree)定义为： T的顶点为图G的所有极大团 94

Clique Tree Clique Tree是一种tree decomposition. 95

Clique Tree Clique Tree是一种tree decomposition. 一个无向图G为弦图当且仅当它存在一个Clique Tree. 96

Clique Tree Clique Tree是一种tree decomposition. 一个无向图G为弦图当且仅当它存在一个Clique Tree. 构建弦图的一个Clique Tree 找出弦图的所有极大团。 构图 ：极大团为点, 两个点之间的边权为两个极大团的交集的点的个数。 求图 的一个最大生成树。 97

Clique Tree Clique Tree是一种tree decomposition. 一个无向图G为弦图当且仅当它存在一个Clique Tree. 98

Clique Tree 一个无向图G为区间图当且仅当它存在一个Clique Tree是一条链。 99

区间图的判定 判断是否是弦图 O(m + n) 如果是弦图，找出所有的极大团 O(m + n) 判断是否存在一个连续的极大团序列即包含每个点的极大团在序列中都是连续的。 100

区间图的判定 判断是否是弦图 O(m + n) 如果是弦图，找出所有的极大团 O(m + n) 判断是否存在一个连续的极大团序列即包含每个点的极大团在序列中都是连续的。 101

区间图的判定 PQ树 给定一个0, 1矩阵要求将矩阵的列重排使得每一行的1是连续的。 102

区间图的判定 PQ树 给定一个0, 1矩阵要求将矩阵的列重排使得每一行的1是连续的。 P节点 [子节点可以任意重排] Q节点 [原顺序或反序] 103

区间图的判定 PQ树 给定一个0, 1矩阵要求将矩阵的列重排使得每一行的1是连续的。 FABEDCHGIJ P节点 [子节点可以任意重排] [原顺序或反序] FABEDCHGIJ 104

区间图的判定 元素集合为X, 初始元素顺序任意。 有若干个限制, 每一个限制集合I表示要将I内的元素变成连续的。 利用PQ树每一个限制可以在O(|I|)内解决, 总的时间复杂度为 。 105

区间图的判定 元素集合为X, 初始元素顺序任意。 有若干个限制, 每一个限制集合I表示要将I内的元素变成连续的。 利用PQ树每一个限制可以在O(|I|)内解决, 总的时间复杂度为 。 区间图判定 最多有n个极大团, |X| ≤ n 每个点最多属于deg(v)个极大团, 时间复杂度为O(n + m)。 106

例 X = {A, B, C, D} 107

例 X = {A, B, C, D} I1 = {A, B, C} 108

例 X = {A, B, C, D} I1 = {A, B, C} I2 = {A, D} 109

区间图的判定 PQ树的实现 感兴趣的同学欢迎与我联系。 很复杂 -______- 110

区间图的判定 PQ树的实现 很复杂 -______- 感兴趣的同学欢迎与我联系。 其他区间图判定方法： Hsu [1992], Hsu and Ma [1999] decomposition, off-line 《A new Test for Interval Graphs》 111

Thank you. My Email: cdq10131@gmail.com 112