当前位置:首页 >> 学科竞赛 >> 区间图与弦图

区间图与弦图


?

Chordal Graph and Interval Graph

?

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

/>称为图G的诱导子图

?

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

团(clique)

?

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

?

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

? (G) 团数

?

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

? (G)
色数

?

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

? (G)

?

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

? (G )

?(G) ? ? (G)
?

团数 ≤ 色数

团数<=色数: 色数不可能少于团数、、、

?(G) ? ? (G)
?

团数 ≤ 色数

? (G) ? ? (G)
?

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

? ?

最大独立集数<=最小团覆盖数:
最大独立集中的每一个节点必定都至少需要一个 团来覆盖。

?
?

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

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

? ?

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

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

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

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

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

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

?

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

?

該图为4个点的唯一弦图,其他的弦图可以视为 在它的上面增加若干个三角形,增加若干条弦构 成,每增加一个三角形都使得单纯点数不降,没 多增加一条弦实际上都是将两个弦图重叠,单纯 点数不降。

?
?

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

v6

v5

v4

?
?

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

v6

v5

v4

?

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

?

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

?

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

?

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

?

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

?
?

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

?

?
?

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

?

i=7
0 0 1

?
?

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

?

i=6
0 1 1

?
?

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

?

i=5
0 2 1

?
?

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

?

i=4
1 2 1

?
?

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

?

i=3
2 2 1

?
?

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

?

i=2
2 2 1

?
?

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

?

i=1
2 2 1

?

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

? ?
?

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

?

? ?
? ? ?

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

? ?
? ? ?

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

?

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

弦图的极大团
? ? ?

设第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) 。

弦图的极大团
? ? ?

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

?
?
?

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

弦图的极大团
?
?

判断v ? N (v) 是否为极大团

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

弦图的极大团
?
?

判断v ? N (v) 是否为极大团

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

?

p(w) < p(v)

弦图的极大团
?
?

判断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中最后的一个点。

?

弦图的极大团
?
?

判断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)

?

?

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

弦图的极大团
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)

弦图的点染色问题
?

?

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

弦图的点染色问题
?

?
?

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

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

弦图的点染色问题
?

?

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

v6

v5

v4

弦图的点染色问题
?

?

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

v6

v5

v4

弦图的点染色问题
?

?

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

v6

v5

v4

弦图的点染色问题
?

?

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

v6

v5

v4

弦图的点染色问题
?

?

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

v6

v5

v4

弦图的点染色问题
?

?

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

v6

v5

v4

弦图的点染色问题
?

?

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

v6

v5

v4

弦图的点染色问题
?

?
?

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

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

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

弦图的点染色问题
?

?
?

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

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

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

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

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

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

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

Sol 完美消除序列从前往后能选就选。
v3 v2 v1

v6

v5

v4

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

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

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

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

?

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

v6

v5

v4

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

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

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

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

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

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

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

区间图
? ?

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

?
1

3

区间图
?
?

区间图一定是弦图。

?

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

经典问题
?

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

使得区间不互相重叠。

经典问题
?

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

使得区间不互相重叠。

区间图的最大独立集

经典问题
? ?

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

经典问题
? ?

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

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

区间图
? ?

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

区间图
? ?

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

?

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

?


更多相关文档:

勾股定理与弦图

勾股定理与弦图_四年级数学_数学_小学教育_教育专区。勾股定理与弦图课前热身 ...重复以上操 作,如下图。求第 1023 个直角三角形的斜边长度是___。第___个...

勾股定理及弦图

茶陵县下东中学数学资料库 段中明 勾股定理及弦图茶陵县下东中学 段中明 2014 年 12 月 这就是一个“弦图” 。 “弦”图是由八个完全一样的直角三角形...

正方形弦图讲解及应用

正方形弦图讲解及应用 [例 1] 如图, l1、l2、l3 是同一平面内的四条平行...弦图与区间图-陈丹琦 112页 1下载券 自余弱弦图 暂无评价 6页 ¥2.00 ...

勾股与弦图

图1 证法七(赵爽弦图) 在这幅“勾股圆方图”中,以弦为边长得到正方形 ABDE 是由 4 个相等的直角三角形再加 上中间的那个小正方形组成的。每个直角三角形的...

正方形弦图讲解及应用讲

正方形弦图讲解及应正方形弦图 用讲 【例 1】 ⑴如图, C 为线段 AB 上一点, 正方形 ADEF 正方形 BCDG 的面积分别为 10cm2 5cm2, 则△EDG 的...

密不可分的弦图与面积

区间图与弦图 132人阅读 67页 1下载券 弦图之妙 178人阅读 23页 免费 勾股...龙源期刊网 http://www.qikan.com.cn 密不可分的弦图与面积 作者:李小龙 ...

中考模型解题 之 弦图模型

中考模型解题 之 弦图模型_初三数学_数学_初中教育_教育专区。中考模型解题 之 弦图模型二、专项训练【板块一】弦图基本模型 1.如图,Rt△ABC中,CD⊥AB,垂足为...

六奥第十六讲 勾股与弦图

六奥第十六讲 勾股与弦图_学科竞赛_小学教育_教育专区。第十六讲【知识概述】...图中 AF=a,DF=b,AD=c,正方形 ABCD 的面积等于 c 2 正方形的面积=4 个...

勾股定理与弦图练习题

勾股定理与弦图练习题_六年级数学_数学_小学教育_教育专区。好勾股...有四个斜边为 c 的全等直角三角形,已知其直角边 长为 a,b.利用这个图试...

勾股定理与弦图练习(含答案)

勾股定理与弦图练习(含答案)_六年级数学_数学_小学教育_教育专区。好 勾股定理与弦图练习(含答案) 勾股定理与弦图练习(含答案)判断题 ⑴在一个三角形中, ...
更多相关标签:
余弦函数单调区间 | 正弦函数单调区间 | 正弦函数的单调区间 | 余弦函数的单调区间 | 余弦函数增区间 | 正弦函数的增区间 | 正弦函数单调递增区间 | 双色球区间走势图 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com