图论第5章 独立集与匹配
{y2,x1} {y3,x3}
{x4}
{y2,y3} {y2,y3} {y2,y3}
y2饱和 y3饱和
{x4,x1} {y2} {x4,x1, x 3} {y2, y3}
注意: (1)最小支配集必是一个极小支配集,反之不然。 (2)任一支配集必含有一个极小支配集。 (3)极小支配集不唯一,最小支配集一般也不唯一。 (4)对二部图 G ( X , Y ) ,X 和 Y 都是支配集。
在国际象棋的比赛中,首 先出现了支配集的概念。1862 年,De考虑了控制整个棋盘所 需要的最少的皇后个数问题。 他指出在一个的棋盘具有处在 配置下的64个格子,在所给某 个位置的皇后控制着同行、同 列以及包含这个格子的两条斜 线上的所有格子,这种皇后的 最少个数为5,左图显示了一 种放置方法。
第五章 独立集与匹配
独立集、支配集、覆盖集、匹配
独立集
设G=<V,E>是简单图无向图, SV, S, 若S 中任何两个顶点都不相邻,则称这个顶点集合S 为图G的独立集。 若S是图G的独立集,但是任意增加一个顶点 就破坏它的独立性,则称这个独立集S为极大独 立集。 独立集S称为最大独立集,如果不存在独立集S’, 使 S’> S ,其中S为集合S的数。 G的最大独立集S的基数称为G的独立数,记作 (G)。
说明: (1)完美匹配是最大匹配,反之未必然; (2)匹配的定义与边的方向无关,故匹配是针对无向图。
(可增广路):设M是图G的匹配,P是G的一条路, 且在P中,M的边和E(G)-M的边交替出现,则称P是 G的一条交错路。若M交错路P的两个端点为M非饱 和点,则称P为M可增广路。
例:下图中虚线所示为匹配,则(2,3,5,6,9,10) 是一条交错路,而(1,2,3,5,6,8)是一条 可增广路。
证明: 设S1是G的最大独立集, S2是G的最小点覆 盖,由前面的定理知V(G)-S1是点覆盖,V(G)-S2是 独立集。因而 V(G)- (G)= V(G) -S1 (G) V(G)- (G)= V(G) –S2 (G) 所以 (G)+(G)=V(G)。
边覆盖
例:如图(a)所示,V1={x1,x2,x3,x4,x5},V2={y1,y2,y3,y4,y5} 试求图G的最大匹配。
X1 x2 x3 x4 x5x1x2x3x4
x5
y1 y2 y3 y4
图(a)
y5
y1
y2
y3
y4
y5
图(b)
解:任取初始匹配M={x2y2,x3y3,x5y5},如图(b)中虚线所 示。解题过程如下表:
8 1 7
1
7
8
2
3
6 2 3 6
4
5
4
5
G
G
支配集 设G=<V,E>是无向简单图,SV,S, 若对于xV-S,x与S里至少一个顶点相 邻,则称S是图G的支配集。 S是图G的支配集,若S的任何真子集都不 是支配集,则称S为图G的极小支配集。 S是图G的支配集,若不存在任何其他支 配集S’,使得S’ <S,则称S是图G的最 下支配集, S为图G的支配数,记作(G)。
3 2 1 4 5 9 10 6
8
7
3 2 1 4 5
10 6 9
8
7
练习
如果一个图的连通分支有奇数个结点,则称这 个连通分支为奇分支; 如果一个图的连通分支有偶数个结点,则称这 个连通分支为偶分支。 我们用 O G 表示图的奇分支个数。
例:
设G是3-正则图,且不含割边,证明: G必含有完美匹配。
任给初始匹配M
M饱和V1?
Y
停止 M为最大匹配
N
找x∈V为非饱和点 S={x},T=∅
N(S)=T?
Y
无法继续匹配 停止
N
找一顶点y∈N(S)T
y已经饱和?
Y
存在边{y,u}∈M S:=S∪{u} T:=T∪{y}
N
一条从x到y的M可 增光路P M:=M⊕P
匈牙利算法步骤: 设G是具有二部划分(V1,V2)的二分图。 (1)任给初始匹配M; (2)若M饱和V1则结束。否则转(3); (3)在V1中找一非M饱和点x,置S={x},T=; (4)若N(S)=T,则停止,否则任选一点yN(S)-T; (5)若y为M饱和点转(6),否则作 求一条从x到y的M可增广路P,置M=MP,转(2) (6)由于y是M饱和点,故M中有一边{y,u},置 S=S{u},T=T{y},转(4)。
注意:不是每个支配集都是独立集;
也不是每个最小支配集都是独立集。
2 1 8 7
3
4
5
6
9
10
12
11
支配集的实际应用背景:要在n座城市中建一 个通信系统,需在这n个城市中选其中的几 个建立通讯站,为减少造价,要使通讯站数目 最少,应如何选址? 问题解决办法:作图G:以城市作为图G的顶 点,当两城市之间有直通讯线路时,相应的两 顶点连一边,则图G的最小支配集为所求。
设G=<V,E>是无向简单图,LV,L。若 G中每个顶点都与L中某条边关联,则称L为G的 边覆盖。 如果G中的任何异于L的边覆盖L’,均有L’ L ,则称S为G的最小边覆盖。 最小边覆盖L的基数 L 称为G的边覆盖数, 记作Θ(G)。
独立集的应用举例
例:(收款台的设置问题)某大型商场为加强经营 管理,对商品的零售收入实行统一收款制度。 为了使顾客在任何一个货架前都能看到收款台, 问收款台应设置在什么地方且至少要设置多少 个收款台? 问题分析:建立简单无向图G=<V,E>,该商场两排货架 之间的通道为G的边,通道交叉处为G的顶点.为使顾客 在任何一个货架前都能看到收款台。从尽可能减少收 款台的数目来说。收款台应设在通道的交叉处。故收 款台的设置问题转化为在G中找出一个最小点覆盖或G 的一个最大独立集。
求极小支配集的一种布尔运算方法
例:求在下图的全部极小支配集。
v2 v4 v5
v1
v3
v6
匹配
匹配问题是运筹学的重要问题之一,也是图论研究 的终点内容,它提供了解决“人员分配问题”和“最优 分配问题”一种新的思想。 设G=<V,E>是无环图,ME(G),M,若M中任意两 条边都不相邻,则称M是图G的一个匹配。 若对图G的任何匹配M’ ,均有M’ <M,则称M是 图G的最大匹配,最大匹配中的边数称为匹配数记作η(G)。 设M是图G的匹配,G中与M中的边关联的顶点称为M 饱和点。 若图G的顶点都是M饱和,则称M为G的完美匹配。
例:通过矩阵平移运算,求下图G的极大独立集。
v2 v1 v3 G v6
v4
v5
团
(图G的团)设G=<V,E>是无向简单图,TV, T。若T中任意两个顶点都相邻,则称T 是图G的团。若T是图G的团,但任意增加一 个新顶点后,它就不是团,则称T是图G的 极大团。
例:求下图的极大独立集
点覆盖
设G=<V,E>, V*V, (1) V*是点覆盖(点覆盖集)——eE,vV*,使e 与v关联; (2) V*是极小点覆盖——V*的任何真子集都不是点覆 盖集; (3) 最小点覆盖——顶点数最少的点覆盖集; (4) 点覆盖数——(G)——最小点覆盖的元素个数。
图中,点覆盖数依次为3,4,7。
Q
Q
Q
Q
Q
若要求任两个皇后都不互相攻击,即 任两个皇后都不在同一行、同一列或一斜 线上,那么这种皇后的最少个数为7,下图 显示了一种放置方法。
Q
Q
Q
Q
Q
Q
Q
支配集的几个性质定理
定理:图G的支配集S是G的极小支配集当且仅当S中
的每个顶点x满足如下条件之一: (1)存在yV(G)-S使得N(y)S={x},其中N(y)为y的邻接点 集合。 (2) N(x)S=。
定理:设G=<V,E>是无向简单图,SV,S,S 是G的独立集V-S是G的点覆盖。
证:S是G的独立集G中每条边的两端点都不同 时属于S G中每条边至少有一端点在V-S中 V-S是G的点覆盖。 推论:S是G的极大独立集V-S是G的极小点覆盖。
推论:(G)+(G)=V(G)。
匈牙利算法
基本思想:
设G是具有二部划分(V1,V2)的二分图,从图G的 任意匹配M开始。若M饱和V1,则M是G的匹配。若M 不能饱和V1,则在V1中选择一个非M饱和点x,若G中 存在以x为起点的M可增广路P,则M’=MP就是比M 更大的匹配,利用M’代替M,并重复这个过程。若G 中不存在以x为起点的M可增广路,则令H是根在x的M 交错子图的顶点集,并令S=HV1,T=HV2,由前述 定理,T=NG(S),且G中不存在以x为起点的M可增广路, 此时称x为检验过的非M饱和点。对V1中其它未检验过 的非M饱和点重复该过程,直到V1中的所有非M饱和 点全部检验过为止。当整个过程结束时,由于G中不 存在M可增广路,从而M为G的最大匹配。
矩阵变换求独立集
设G=<V,E>是简单无向图,同时将 G的邻 接矩阵第i行与第j行, 第i列与第j列互换, 称为一次平移变换。 说明:平移变换不改变邻接矩阵所表示图G 的各顶点之间的关系,紧紧仅仅改变了i, j的编号。也就是说,邻接矩阵的平移变 换对应于图中结点的一个重新编号。反 之,结点的重新编号对应于邻接矩阵的 一系列平移变换。
例: 某工厂生产由六种不同颜色的纱织成的 双色布,由这个工厂所生产的双色布中,每一 种颜色至少和其他三种颜色搭配。证明可以挑 选出三种不同的双色布,它们含有所有的六种 颜色。
例:有n张纸牌,每张纸牌的正反两面都写上 1,2,…,n的某一个数。证明:如果每个数字都 恰好出现两次,那么这些纸牌一定可以这样摊 开,使朝上的面中1,2,…,n都出现。