nbhkdz.com冰点文库

弦图与区间图-cdq


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

图的基本概念
?

2009年1月 全国信息学冬令营讲稿

子图 (subgraph)
图 G ? (V , E ) G? ? (V ?, E ?),V ? ? V , E ? ?

E 为图G的子图

图的基本概念
?

2009年1月 全国信息学冬令营讲稿

诱导子图(induced subgraph)
图 G ? (V , E )
G? ? (V ?, E ?),V ? ? V , E ? ? {(u, v) | u, v ?V ?,(u, v) ? E}

称为图G的诱导子图

图的基本概念
?

2009年1月 全国信息学冬令营讲稿

团(clique)

图G的一个子图 G ? ? (V ?, E ?) ,G ?为关于 V ? 的完全图。

图的基本概念
?

2009年1月 全国信息学冬令营讲稿

团(clique)

图G的一个子图 G ? ? (V ?, E ?) ,G ?为关于 V ? 的完全图。
?

极大团(maximal clique)
一个团是极大团当它不是其它团的子集。

图的基本概念
?

2009年1月 全国信息学冬令营讲稿

团(clique)

图G的一个子图 G ? ? (V ?, E ?) ,G ?为关于 V ? 的完全图。
?

极大团(maximal clique)
一个团是极大团当它不是其它团的子集。

?

最大团(maximum clique)
点数最多的团。

? (G ) 团数

图的基本概念
?

2009年1月 全国信息学冬令营讲稿

最小染色(minimum coloring)
用最少的颜色给点染色使相邻点颜色不同。

? (G )
色数

图的基本概念
?

2009年1月 全国信息学冬令营讲稿

最大独立集(maximum independent set)
最大的一个点的子集使任何两个点不相邻。

? (G )

图的基本概念
?

2009年1月 全国信息学冬令营讲稿

最小团覆盖(minimum clique cover)
用最少个数的团覆盖所有的点。

? (G )

图的基本概念

2009年1月 全国信息学冬令营讲稿

? (G) ? ? (G)
?

团数 ≤ 色数

图的基本概念

2009年1月 全国信息学冬令营讲稿

? (G) ? ? (G)
?

团数 ≤ 色数

? (G) ? ? (G)
?

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

弦图的概念

2009年1月 全国信息学冬令营讲稿

?

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

弦图的概念

2009年1月 全国信息学冬令营讲稿

?
?

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

弦图的概念

2009年1月 全国信息学冬令营讲稿

?
?

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

? ?

弦图的判定

2009年1月 全国信息学冬令营讲稿

[例题 ] Zju1015 Fishing net 给定一个无向图,判定它是否为弦图。
?

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

弦图的判定

2009年1月 全国信息学冬令营讲稿

[例题 ] Zju1015 Fishing net 给定一个无向图,判定它是否为弦图。
?

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

弦图的判定

2009年1月 全国信息学冬令营讲稿

[例题 ] Zju1015 Fishing net 给定一个无向图,判定它是否为弦图。
?

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

?

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

弦图的判定
?
?

2009年1月 全国信息学冬令营讲稿

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

v6

v5

v4

弦图的判定
?
?

2009年1月 全国信息学冬令营讲稿

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

v6

v5

v4

弦图的判定
?

2009年1月 全国信息学冬令营讲稿

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

弦图的判定
?

2009年1月 全国信息学冬令营讲稿

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

?

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

弦图的判定
?

2009年1月 全国信息学冬令营讲稿

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

?

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

求完美消除序列
?
? ? ?

2009年1月 全国信息学冬令营讲稿

最朴素的算法:
每次找一个单纯点v,加入到完美消除序列中。 将v以及相关的边从图中删掉。 重复以上过程直到所有点都被删除(图为弦图, 得到了完美序列)或不存在单纯点v(图不是弦图)。

求完美消除序列
?
? ? ?

2009年1月 全国信息学冬令营讲稿

最朴素的算法:
每次找一个单纯点v,加入到完美消除序列中。 将v以及相关的边从图中删掉。 重复以上过程直到所有点都被删除(图为弦图, 得到了完美序列)或不存在单纯点v(图不是弦图)。

时间复杂度?? O(n4)

求完美消除序列
?
? ? ?

2009年1月 全国信息学冬令营讲稿

最朴素的算法:
每次找一个单纯点v,加入到完美消除序列中。 将v以及相关的边从图中删掉。 重复以上过程直到所有点都被删除(图为弦图, 得到了完美序列)或不存在单纯点v(图不是弦图)。

时间复杂度?? O(n4)
下面介绍两个求完美消除序列O(m + n)的算法。

LexBFS算法
?
? ?

2009年1月 全国信息学冬令营讲稿

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

?

LexBFS算法

2009年1月 全国信息学冬令营讲稿

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

LexBFS算法

2009年1月 全国信息学冬令营讲稿

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

vn

LexBFS算法

2009年1月 全国信息学冬令营讲稿

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

vn

LexBFS算法

2009年1月 全国信息学冬令营讲稿

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

vn vn-1 vn

LexBFS算法

2009年1月 全国信息学冬令营讲稿

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

vn vn-1 vn

LexBFS算法
?

2009年1月 全国信息学冬令营讲稿

算法实现

?

LexBFS算法
?

2009年1月 全国信息学冬令营讲稿

算法实现

更新一个点的list最多新建一个桶。 任何时候桶的数目不超过n。

LexBFS算法
?

2009年1月 全国信息学冬令营讲稿

算法实现

O(m + n)!!!

更新一个点的list最多新建一个桶。 任何时候桶的数目不超过n。

MCS算法
?
?

2009年1月 全国信息学冬令营讲稿

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

?

MCS算法
?
?

2009年1月 全国信息学冬令营讲稿

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

?

i=7
0 0 1

MCS算法
?
?

2009年1月 全国信息学冬令营讲稿

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

?

i=6
0 1 1

MCS算法
?
?

2009年1月 全国信息学冬令营讲稿

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

?

i=5
0 2 1

MCS算法
?
?

2009年1月 全国信息学冬令营讲稿

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

?

i=4
1 2 1

MCS算法
?
?

2009年1月 全国信息学冬令营讲稿

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

?

i=3
2 2 1

MCS算法
?
?

2009年1月 全国信息学冬令营讲稿

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

?

i=2
2 2 1

MCS算法
?
?

2009年1月 全国信息学冬令营讲稿

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

?

i=1
2 2 1

MCS算法

2009年1月 全国信息学冬令营讲稿

MCS算法
?

2009年1月 全国信息学冬令营讲稿

算法实现

?

MCS算法
?

2009年1月 全国信息学冬令营讲稿

算法实现
0 1 2

MCS算法
?

2009年1月 全国信息学冬令营讲稿

算法实现
0 1 2

O(m + n)!!!

弦图的判定
?

2009年1月 全国信息学冬令营讲稿

判断一个序列是否为完美消除序列

弦图的判定
? ?
?

2009年1月 全国信息学冬令营讲稿

判断一个序列是否为完美消除序列 朴素的算法
依次判断 {vi+1,…,vn}中所有与vi相邻的点是否构 成了一个团。 时间复杂度: O(?(deg(v))2 ) ? O(mn)

?

弦图的判定
? ?
? ? ?

2009年1月 全国信息学冬令营讲稿

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

弦图的判定
? ?
? ? ?

2009年1月 全国信息学冬令营讲稿

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

?

弦图判定问题可以在O(m + n)的时间内解决。

2009年1月 全国信息学冬令营讲稿

弦图的极大团
设第i个点在弦图的完美消除序列第p(i)个。 ? 令N(v) = {w | w与v相邻且p(w) > p(v)} ? 弦图的极大团一定是 v ? N (v ) 的形式。
?

?

证明:
设点集V的诱导子图为弦图的极大团, 设v为V中p(i)值最小的点即出现在完美消除 序列中最前面的点。由于 V ? v ? N (v) 为 一个团,V为极大团所以 V ? v ? N (v) 。

2009年1月 全国信息学冬令营讲稿

弦图的极大团
设第i个点在弦图的完美消除序列第p(i)个。 ? 令N(v) = {w | w与v相邻且p(w) > p(v)} ? 弦图的极大团一定是 v ? N (v ) 的形式。
?

?
? ?

推论:弦图最多有n个极大团。
如何找到弦图的所有极大团呢?
即判断每个 v ? N (v) 是否为极大团

2009年1月 全国信息学冬令营讲稿

弦图的极大团
? ?

判断 v ? N (v) 是否为极大团 设A = v ? N (v) ,若存在B = w ? N ( w) 使 得 A ? B 则A不是极大团。

2009年1月 全国信息学冬令营讲稿

弦图的极大团
? ?

判断 v ? N (v) 是否为极大团 设A = v ? N (v) ,若存在B = w ? N ( w) 使 得 A ? B 则A不是极大团。

?

p(w) < p(v)

2009年1月 全国信息学冬令营讲稿

弦图的极大团
? ?

判断 v ? N (v) 是否为极大团 设A = v ? N (v) ,若存在B = w ? N ( w) 使 得 A ? B 则A不是极大团。

?

p(w) < p(v)
设next(v) 表示N(v)中最前的点。令w*表示 所有满足 A ? B 的w中最后的一个点。

?

2009年1月 全国信息学冬令营讲稿

弦图的极大团
? ?

判断 v ? N (v) 是否为极大团 设A = v ? N (v) ,若存在B = w ? N ( w) 使 得 A ? B 则A不是极大团。

?

p(w) < p(v)
设next(v) 表示N(v)中最前的点。令w*表示 所有满足 A ? B 的w中最后的一个点。 next(w*) = v (否则next(w*)也是满足条件的w)

?

?

2009年1月 全国信息学冬令营讲稿

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

2009年1月 全国信息学冬令营讲稿

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

只需判断是否存在一个w,满足Next(w) = v 且|N(v)| + 1 ≤ |N(w)|即可。 时间复杂度:O(m + n)

2009年1月 全国信息学冬令营讲稿

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

2009年1月 全国信息学冬令营讲稿

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

?

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

2009年1月 全国信息学冬令营讲稿

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

v3

v2

v1

v6

v5

v4

2009年1月 全国信息学冬令营讲稿

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

v3

v2

v1

v6

v5

v4

2009年1月 全国信息学冬令营讲稿

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

v3

v2

v1

v6

v5

v4

2009年1月 全国信息学冬令营讲稿

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

v3

v2

v1

v6

v5

v4

2009年1月 全国信息学冬令营讲稿

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

v3

v2

v1

v6

v5

v4

2009年1月 全国信息学冬令营讲稿

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

v3

v2

v1

v6

v5

v4

2009年1月 全国信息学冬令营讲稿

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

v3

v2

v1

v6

v5

v4

2009年1月 全国信息学冬令营讲稿

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

证明: ? 设使用了T种颜色, 则T ≥ 色数 ? T = 团数 ≤ 色数 ? 团数 = 色数 = T
? ?

时间复杂度: O(m + n)

2009年1月 全国信息学冬令营讲稿

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

证明: ? 设使用了T种颜色, 则T ≥ 色数 ? T = 团数 ≤ 色数 团数 = 色数 !!! ? 团数 = 色数 = T
? ?

时间复杂度: O(m + n)

2009年1月 全国信息学冬令营讲稿

弦图的最大独立集和最小团覆盖
?
?

最大独立集
选择最多的点使得任意两个点不相邻。

2009年1月 全国信息学冬令营讲稿

弦图的最大独立集和最小团覆盖
?
? ?

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

v6

v5

v4

2009年1月 全国信息学冬令营讲稿

弦图的最大独立集和最小团覆盖
?
?

最小团覆盖
用最少个数的团覆盖所有的点。

2009年1月 全国信息学冬令营讲稿

弦图的最大独立集和最小团覆盖
?
?

最小团覆盖
用最少个数的团覆盖所有的点。

?

Sol 设最大独立集为{p1 , p2 , …, pt},则 {p1∪N(p1), …, pt∪N(pt)}为最小团覆盖。
v3 v2
v1

v6

v5

v4

2009年1月 全国信息学冬令营讲稿

弦图的最大独立集和最小团覆盖
?

证明 ? {p1 , p2 , …, pt}为一个独立集。 t ≤ ? (G )

2009年1月 全国信息学冬令营讲稿

弦图的最大独立集和最小团覆盖
?

证明 ? {p1 , p2 , …, pt}为一个独立集。 t ≤ ? (G ) ? {p1∪N(p1), …, pt∪N(pt)}为一个团覆盖。 t ≥ ? (G )

2009年1月 全国信息学冬令营讲稿

弦图的最大独立集和最小团覆盖
?

证明 ? {p1 , p2 , …, pt}为一个独立集。 t ≤ ? (G ) ? {p1∪N(p1), …, pt∪N(pt)}为一个团覆盖。 t ≥ ? (G ) ? 由? (G) ? ? (G) 知 ? (G) ? ? (G) ? t
?

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

2009年1月 全国信息学冬令营讲稿

完美图与伴完美图
?
?

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

2009年1月 全国信息学冬令营讲稿

完美图与伴完美图
?
?

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

?
?

伴完美图(Co-perfect Graph)的概念
一个图G称为完美图若它的每一个诱导 子图都满足 ? (G) ? ? (G) 。

2009年1月 全国信息学冬令营讲稿

完美图与伴完美图
?
?

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

?
?

伴完美图(Co-perfect Graph)的概念
一个图G称为完美图若它的每一个诱导 子图都满足 ? (G) ? ? (G) 。

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

2009年1月 全国信息学冬令营讲稿

区间图
? ?

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

?

1

3

2009年1月 全国信息学冬令营讲稿

区间图
?
?

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

?

2009年1月 全国信息学冬令营讲稿

经典问题
?

[例题1] 给定n个区间,要求选择最多的区间

使得区间不互相重叠。

2009年1月 全国信息学冬令营讲稿

经典问题
?

[例题1] 给定n个区间,要求选择最多的区间

使得区间不互相重叠。

区间图的最大独立集

2009年1月 全国信息学冬令营讲稿

经典问题
? ?

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

2009年1月 全国信息学冬令营讲稿

经典问题
? ?

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

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

2009年1月 全国信息学冬令营讲稿

区间图
? ?

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

2009年1月 全国信息学冬令营讲稿

区间图
? ?

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

?

[例题1] 将所有的区间按照右端点从小到大排
序,依次处理每个区间,如果与已选区间没有重 叠则选择该区间。 时间复杂度:O(nlog2n)

?

2009年1月 全国信息学冬令营讲稿

区间图
? ?

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

?

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

?

?

树的分解(Tree Decomposition)
?
?

2009年1月 全国信息学冬令营讲稿

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

树的分解(Tree Decomposition)
?
?

2009年1月 全国信息学冬令营讲稿

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

X1 ∪ X2 ∪ … ∪ Xm =V

树的分解(Tree Decomposition)
?
?

2009年1月 全国信息学冬令营讲稿

定义
对于一个无向图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。

树的分解(Tree Decomposition)
?
?

2009年1月 全国信息学冬令营讲稿

定义
对于一个无向图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)的 诱导子图是连通的。

树的分解(Tree Decomposition)

2009年1月 全国信息学冬令营讲稿

Clique Tree
?

2009年1月 全国信息学冬令营讲稿

一个无向图G的极大团树T(Clique Tree)定义 为: T的顶点为图G的所有极大团 包含每个点的所有极大团为T的一个连 通子图。

Clique Tree
?

2009年1月 全国信息学冬令营讲稿

Clique Tree是一种tree decomposition.

Clique Tree
? ?

2009年1月 全国信息学冬令营讲稿

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

Clique Tree
? ?

2009年1月 全国信息学冬令营讲稿

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

?

?
?

?

Clique Tree
? ?

2009年1月 全国信息学冬令营讲稿

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

Clique Tree
?

2009年1月 全国信息学冬令营讲稿

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

区间图的判定
?

2009年1月 全国信息学冬令营讲稿

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

区间图的判定
?

2009年1月 全国信息学冬令营讲稿

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

区间图的判定
? ?

2009年1月 全国信息学冬令营讲稿

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

区间图的判定
? ?

2009年1月 全国信息学冬令营讲稿

PQ树
给定一个0, 1矩阵要求将矩阵的列重排 使得每一行的1是连续的。
P节点 [子节点可以任意重排]

Q节点 [原顺序或反序]

区间图的判定
? ?

2009年1月 全国信息学冬令营讲稿

PQ树
给定一个0, 1矩阵要求将矩阵的列重排 使得每一行的1是连续的。
P节点 [子节点可以任意重排]

Q节点 [原顺序或反序]

FABEDCHGIJ

区间图的判定
?

2009年1月 全国信息学冬令营讲稿

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

区间图的判定
?

2009年1月 全国信息学冬令营讲稿

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

时间复杂度为O(n + m)。


?

2009年1月 全国信息学冬令营讲稿

X = {A, B, C, D}


? ?

2009年1月 全国信息学冬令营讲稿

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


? ? ?

2009年1月 全国信息学冬令营讲稿

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

区间图的判定
? ?

2009年1月 全国信息学冬令营讲稿

PQ树的实现 很复杂 -______感兴趣的同学欢迎与我联系?。

区间图的判定
? ?

2009年1月 全国信息学冬令营讲稿

PQ树的实现 很复杂 -______感兴趣的同学欢迎与我联系?。

?

其他区间图判定方法:

?

Hsu [1992], Hsu and Ma [1999] decomposition, off-line ? 《A new Test for Interval Graphs》

2009年1月 全国信息学冬令营讲稿

My Email: cdq10131@gmail.com

2009年1月 全国信息学冬令营讲稿


CDQ-B型燃料点火枪

干熄焦技术(CDQ) 4页 2下载券 弦图与区间图-cdq 122页 免费 三CDQ水质标准...陕西秦川热工技术有限公司 诚信交朋友 质量为根本 CDQ-B 型燃料点火枪使用说明...

河北省唐山市2016届高三第三次模拟考试数学(文)试题(清晰图片版-附答案)

12 分 Q 因为 B 为⌒ AC 的中点,所以∠CQB=∠ACB, 所以∠PQC+∠CQB=∠CBD+∠ACB, 即∠PQD=∠CDQ, P C 故△DPQ 为等腰三角形. …5 分(Ⅱ)设 CD...

浙江省宁波市“十校”2016年高三联考数学理试卷

m ? (5a? 4c , 4b ) 与向量 宁波市高三“十...(Ⅱ)若椭圆 E 的所有都不能被直线 l : y ?...(理科)试卷 4—8 (此区间没说明,扣 1 分)???...

文科数学 - 答案(新)

2 4 1 5 3 则三棱锥P - CDQ的体积为V ? ?...0时,f ( x)的单调递增区间为(0, ??), 当a ...笑翻神图 爆笑图片汇集 搞笑图片乐翻人 cs3简单制作...

高二作业

(II)Q f ( x) g ( x) 在区间 ( ?∞, ( a + 1) ] 上都是...CDQ 中,有 (a ? t ) 2 +4 . ……4 分 N A M Q C B 2 2 2 ...

安徽十校联考2016中考四模试卷--数学(解析版)

(2) 以图中的 O 为位似中心, 在△ A1B1C1 ...如图,AB 是⊙O 的直径, CD⊥AB 于点 E,点 ...与半圆 O 相切;②;③∠ADQ=2∠CBP;④cos∠CDQ=...

2014年长宁区初三数学一模

A N Q P B M 第 25 题图① A N C B M ...(2 分) ∴圆心 O 到 AB 的距离 6 2 (1 ...证出∠QCD=90°,QD=QP,CD=BP 在 Rt△CDQ 中 ...

08.深圳市2016年高考模拟试题命题比赛参赛试题(文科数学)

(6)如右图所示,执行程序框图输出的结果是()(A) ...(同一组中的数据用该组区间的中点值作代表) ;(3...VP ?CDQ ? ?h ? 2 6 3 深圳市数学命题比赛(...

测试 2016春季 期中复习

图(2)由弦图变化得到,它是由八个全等的直角三角形拼接而成,记图中正方形 ...(1)当△ CDQ≌△CPQ 时,求 AQ 的长; (2)取 CQ 的中点 M,连接 MD,MP...

九年级数学热点专题五 图形与变换、图形与坐标

一次或两次轴对称后的图 形; 能利用轴对称进行图案...圆当中求关于、半径等问题时, 通常要转化到三角...与点 B 重合时, 易证 △APD ∽△CDQ .此 亿库...