当前位置:首页 >> IT/计算机 >>

二部图匹配网络流


二部图&网络流

二部图

二部图
为一个无向图, 定义 设 G=<V,E>为一个无向图,若能将 V分成 V1和V2 为一个无向图 分成 (V1∪V2=V,V1∩V2=?),使得 G 中的每条边的两个端点都是 , ?, 一个属于V 另一个属于V 或称二分 一个属于 1,另一个属于 2,则称 G 为二部图 ( 或称二分 偶图等 , 互补顶点子集,常将二部图G 图、偶图等 ),称V1和V2为互补顶点子集,常将二部图 记为<V 记为 1,V2,E>. 又若G是简单二部图, 中每个顶点均与V 又若 是简单二部图,V1中每个顶点均与 2中所有的顶点相 是简单二部图 则称G为完全二部图, 其中r=|V1|,s=|V2|. 邻,则称 为完全二部图,记为 Kr,s,其中 ,

2011-1-20

3 of 220

例 二部图
v1 v2
v3

二部图

v4

v5

v6

完全二部图 完全二部图 K3,3
7.3 图的矩阵表示 4 of 220

2011-1-20

二部图的判别法 无向图G=<V,E>是二部图当且 定理 无向图 是二部图当且 仅当G中无奇圈 中无奇圈. 仅当 中无奇圈

2011-1-20

5 of 220

无向简单图的 点覆盖集、点独立集、匹配

点独立集与点独立数
定义 设G=<V,E>,V*?V. , ? (1) (点)独立集 独立集V*——V*中顶点彼此不相邻 点 独立集 中顶点彼此不相邻 (2) V*为极大点独立集 为极大点独立集——V*中再加入任何顶点就不 中再加入任何顶点就不 是点独立集 最大点独立集——元素最多的点独立集 (3) 最大点独立集 元素最多的点独立集 (4) 点独立数 点独立数——最大独立集中的元素个数,记为β0 最大独立集中的元素个数, 最大独立集中的元素个数 记为β

(1)
2011-1-20

(2)

(3)
7 of 220

在图中,点独立数依次为 在图中,点独立数依次为2, 2, 3.

点覆盖集与点覆盖数
定义 设G=<V,E>, V*?V. ? (1) V*是点覆盖集 是点覆盖集——?e∈E,?v∈V*,使e与v关联 ? ∈ , ∈ , 与 关联 (2) V*是极小点覆盖集 是极小点覆盖集——V*的任何真子集都不是点覆盖 的任何真子集都不是点覆盖 集 (3) 最小点覆盖集——顶点数最少的点覆盖集 最小点覆盖集 顶点数最少的点覆盖集 (4) 点覆盖数 点覆盖数——α0(G)——最小点覆盖的元素个数 α 最小点覆盖的元素个数

图中,点覆盖数依次为 , , 图中,点覆盖数依次为3,4,7.
2011-1-20 8 of 220

点覆盖集与点独立集的关系

α0+β0=n β
点覆盖数+点独立数 点数 点覆盖数 点独立数=点数 点独立数

2011-1-20

9 of 220

匹配(边独立集)与匹配数(边独立数)
定义 设G=<V,E>, E*?E, ? , (1) 匹配(边独立集 匹配 边独立集)E*——E*中各边均不相邻 中各边均不相邻 边独立集 (2) 极大匹配 极大匹配E*——E*中不能再加其他边了 中不能再加其他边了 (3) 最大匹配 最大匹配——边数最多的匹配 边数最多的匹配 (4) 匹配数 匹配数——最大匹配中的边数,记为β1 最大匹配中的边数, 最大匹配中的边数 记为β

上图中各图的匹配数依次为3, 上图中各图的匹配数依次为 3, 4.
2011-1-20 10 of 220

关于匹配中的其他概念 中一个匹配. 定义 设M为G中一个匹配 为 中一个匹配 (1) 匹配边 匹配边——(vi,vj)∈M ∈ (2) v为M饱和点 饱和点——有M中边与 关联 中边与v关联 为 饱和点 有 中边与 (3) v为M非饱和点 非饱和点——无M中边与 关 中边与v关 为 非饱和点 无 中边与 联 (4) M的交错路径 由匹配边和非匹 的交错路径——由匹配边和非匹 配边交替构成的路径 (5) M的增广路径 的增广路径——起、终点都是 起 终点都是M 非饱和点的交错路径
2011-1-20 11 of 220

最大匹配判别定理

中最大匹配当且仅当G中不 定理 M为G中最大匹配当且仅当 中不 为 中最大匹配当且仅当 的可增广交错路径. 含M的可增广交错路径 的可增广交错路径

2011-1-20

12 of 220

二部图匹配
匈牙利算法

增广路径
x1 x2 x3 x4 y1 x1 y2 x2 y3 x3 y4 x4 y1 y2 y3 y4 x1 x2 x3 x4 y1 x1 y2 x2 y3 x3 y4 x4 y1 y2 y3 y4

匹配M={{x1,y1}, {x2,y3}, {x3,y4}}有一条增广路径γ 匹配 增广路径可构造比M大的匹配 由M增广路径可构造比 大的匹配 增广路径可构造比 存在M增广路径 增广路径? 非最大匹配 存在 增广路径?M非最大匹配 代替M 用(M-γ)∪(γ -M)代替 γ∪γ 代替
2011-1-20 14 of 220

匈牙利算法 由增广路径的定义可以推出下述三个 结论: 结论: 1、γ的路径长度必定为奇数,第一条边 、 的路径长度必定为奇数, 和最后一条边都不属于M。 和最后一条边都不属于 。 2、γ经过取对称差操作可以得到一个更 、 大的匹配M′ 大的匹配 ′。 3、M为G的最大匹配当且仅当不存在 、 为 的最大匹配当且仅当不存在 关于M的增广路径 的增广路径。 关于 的增广路径。
2011-1-20 15 of 220

匈牙利算法
用增广路径求最大匹配(称作匈牙利算法 用增广路径求最大匹配 称作匈牙利算法) 称作匈牙利算法 算法: 算法: (1)置M为空 置 为空 (2)找出一条增广路γ ,通过取对称差操作获 找出一条增广路γ 找出一条增广路 得更大的匹配M′代替M 得更大的匹配 ′代替 (3)重复 操作直到找不出增广路径为止 重复(2)操作直到找不出增广路径为止 重复

2011-1-20

16 of 220

匈牙利算法示例

图1

图2

2011-1-20

17 of 220

二部图的最小点覆盖
定理: 是二部图 是二部图, 定理 G是二部图 则α0=

β1. 二部图的最大匹配数= 即二部图的最大匹配数=最小点覆盖数
定理对一般图不成立. 注: 定理对一般图不成立

2011-1-20

18 of 220

二部图的最大独立集
定理:二部图中 定理:二部图中: 最大独立集数=顶点总数- 最大独立集数=顶点总数-最小点覆盖数 顶点总数- 也=顶点总数-最大匹配数

2011-1-20

19 of 220

例题1 Place the Robots

问题描述

有一个N*M(N,M<=50) 有一个 的棋盘, 的棋盘,棋盘的每一格是 三种类型之一:空地、 三种类型之一:空地、草 地、墙。机器人只能放在 空地上。 空地上。在同一行或同一 列的两个机器人, 列的两个机器人,若它们 之间没有墙, 之间没有墙,则它们可以 互相攻击。问给定的棋盘, 互相攻击。问给定的棋盘, 最多可以放置多少个机器 使它们不能互相攻击。 人,使它们不能互相攻击。
2011-1-20

Empty Grass Wall
20 of 220

例题1 Place the Robots(ZOJ)

模型一
以空地为顶点, 以空地为顶点,有冲突的 空地之间连边, 空地之间连边,可以得到 右边的这个图: 右边的这个图: 于是, 于是,问题转化为求图的 最大独立集问题。 最大独立集问题。
2011-1-20

1 2 3 4
1 3 8 5 7 6
21 of 220

8 7 6 5
2 4

例题1 Place the Robots

模型一

1 2 3 4
1 3 2 4

8 7 6 5

这是NP问题!
2011-1-20

8 5 7 6
22 of 220

例题1 Place the Robots(ZOJ)

模型二
将每一行, 将每一行,每一列被墙 隔开且包含空地的连续 隔开且包含空地的连续 区域称作“ 显然, 区域称作“块”。显然, 在一个块之中, 在一个块之中,最多只 能放一个机器人。把这 能放一个机器人。 些块编上号。 些块编上号。
1 2

1 3 4 5

同样, 同样,把竖直方向的块也 编上号。 编上号。
2011-1-20

3 2

4

23 of 220

例题1 Place the Robots

模型二
把每个横向块看作X部的点, 把每个横向块看作X部的点, 竖向块看作Y部的点, 竖向块看作Y部的点,若两个 块有公共的空地, 块有公共的空地,则在它们 之间连边。 之间连边。 于是, 于是,问题转化成这样的一 个二部图: 个二部图:
1 2 3 4 5

1 2 5 3 4

1 2

3

4

1
2011-1-20

2

3

4
24 of 220

例题1 Place the Robots

模型二
1 2 3 4 5

1 2 5 3 4

1

2

3

4

由于每条边表示一个空 地,有冲突的空地之间 必有公共顶点, 必有公共顶点,所以问 题转化为二部图的最大 匹配问题。 匹配问题。
2011-1-20

1 2

3

4

25 of 220

例题2 打猎 猎人要在n*n的格子里打鸟 他可以在某一行中 的格子里打鸟,他可以在某一行中 猎人要在 的格子里打鸟 打一枪,这样此行中的所有鸟都被打掉 这样此行中的所有鸟都被打掉, 打一枪 这样此行中的所有鸟都被打掉,也可 以在某一列中打,这样此列中的所有鸟都打掉 这样此列中的所有鸟都打掉. 以在某一列中打 这样此列中的所有鸟都打掉 问至少打几枪,才能打光所有的鸟? 问至少打几枪 才能打光所有的鸟? 才能打光所有的鸟 建图:二部图的X部为每一 建图:二部图的X部为每一 部为每一列, 行,Y部为每一列,如果 部为每一列 如果(i,j) 有一只鸟,那么连接X部的 部的i 有一只鸟,那么连接 部的 部的j。 与Y部的 。 部的 该二部图最小点覆盖数即是 该二部图最小点覆盖数即是 最小点覆盖数 最少要打的枪数。 最少要打的枪数。
2011-1-20

@ @ @
26 of 220

@ @

Girls and Boys
The second year of the university somebody started a study on the romantic relations between the students. The relation “romantically involved” is defined between one girl and one boy. For the study reasons it is necessary to find out the maximum set satisfying the condition: there are no two students in the set who have been “romantically involved”. The result of the program is the number of students in such a set. The input contains several data sets in text format. Each data set represents one set of subjects of the study, with the following description: the number of students the description of each student, in the following format 220 2011-1-20 27 of

Girls and Boys
student_identifier:(number_of_romantic_relations) student_identifier1 student_identifier2 ... or student_identifier:(0) The student_identifier is an integer number between 0 and n-1, for n subjects. For each given data set, the program should write to standard output a line containing the result.

2011-1-20

28 of 220

Girls and Boys
Sample Input 7 0 0: (3) 4 5 6 1: (2) 4 6 Y: (0) E: (0) 4: (2) 0 1 5: (1) 0 4 6: (2) 0 1

1

Output 5
5 6 Y E

2011-1-20

29 of 220

网络流简介

2011-1-20

31 of 220

2011-1-20

32 of 220

16,11

a
4,1

12,12 9,4

b
7,7

20,15

s

10,

t
4,4

13,8

d
14,11 12 4 5 3 11

c

5

a
11 11 5 3

b
7 15

5

s
8

t
4

d

c

2011-1-20

33 of 220

剩余图
16

增广之后的新流
b
20 16,4

a
10 4

12 9

a
10, 4,

12,4 9,4

b
7,

20,

s
13

7

t
4

s
13,

t
4,4

d
14 8 4 4 4 5 10 4

c

d
14,4

c

12

a
4 10

b
7

20 16,11

a
4,

12,4 9,4

b
7,7

20,7

s
13

t
4

s

10,7

t
4,4

d

c

13,

d
14,11

c

2011-1-20

34 of 220

剩余图
s

增广之后的新流
16,11 10,7

a
4,

12,4 9,4

b
7,7

20,7

t
4,4

13,

d
14,11

c
12,12 9,4 7,7

5

a
11 3 11

8 4 4 5 7 3 11

b
7

13 16,11

a
4,1

b

20,15

s
13

t
4

s

10,

t
4,4

d

c

13,8

d
14,11

c

2011-1-20

35 of 220

剩余图
16,11

增广之后的新流
a
4,1 12,12 9,4 7,7

b

20,15

s a
11 11 5 8 3 12 4 5 3 11 5 7

10,

t
4,4

13,8 5

d a
4,1 14,11 12,12 9, 7,7

c b

b
15

5

s

t
4

16,11

20,19

s

10,

t
4,4

d a
11 11 1 3

c b
9 7

13,12

d
14,11

c

12

1 19 4
36 of 220

s
12

t

d

3 11

c

2011-1-20

1

2

2
2

2

3
2

2

4

1

2,2

2

2,2

3

2,2

4

2,0

2,0

1
2 2,2

2

3
2 2,0 2,2

4

1

2

2
2

2

3
2

2

4

1

2

3

4 1

2

2
2

2

4
2
37 of 220

2,2
2011-1-20

2,2

2

3

1

2

2
2

2

3
2

2

4

2
2

2

2
2

2

2

c
2

2

1
2

4
2

1
2

d

2

4
2

3

a
2

b
2

3

2011-1-20

38 of 220

剩余图
1000

a
1

1000

s
1000

t
1000

b

解决方法: (1) EK算法:在剩余图中找最短增广路径 (2) 最大容量增广算法: 找最大瓶颈容量
2011-1-20 39 of 220

练习1: 练习 无向图的网络流
下图为某地区运输网. 边上的数字表示运输能 下图为某地区运输网 单位:万吨/小时),则从顶点 到顶点5 小时),则从顶点1到顶点 力(单位:万吨 小时),则从顶点 到顶点 的最大运输能力可以达到_____万吨 小时. 的最大运输能力可以达到 万吨/小时 万吨 小时 3 8 2 4 20 1 10 2 4 10 6 4
2011-1-20

5

40 of 220

练习2 练习

《算法导论》 P400 26.1-9 算法导论》

2011-1-20

41 of 220

与阿Q都是四驱车好手 阿P与阿 都是四驱车好手,他们各有 辆四 与阿 都是四驱车好手,他们各有N辆四 驱车。 为了一比高下, 驱车 。 为了一比高下 , 他们约好进行一场比 这次比赛共有M个分站赛 个分站赛, 赛 。 这次比赛共有 个分站赛 , 赢得分站赛 场次多的获得总冠军。 每个分站赛中, 场次多的获得总冠军 。 每个分站赛中 , 两人 各选一辆自己的赛车比赛。 各选一辆自己的赛车比赛 。 分站赛的胜负大 部分取决于两车的性能,但由于种种原因 如相互之间的干扰) ( 如相互之间的干扰 ) , 性能并不是决定胜 负的唯一指标,有时会出现A赢 、 赢 、 负的唯一指标,有时会出现 赢B、B赢C、C 又赢A的局面 赢 D、 D又赢 的局面 。 幸好有一种高智能机 、 又赢 的局面。 只要给定两辆四驱车, 器 , 只要给定两辆四驱车 , 就能立刻判断谁 会赢,在总比赛前它就已经把阿p的每辆车与 会赢,在总比赛前它就已经把阿 的每辆车与 的每辆车都两两测试过了, 阿q的每辆车都两两测试过了,并且还把输赢 的每辆车都两两测试过了 表输入了电脑。 表输入了电脑。 2011-1-20 42 of 220

另外,由于比赛的磨损, 另外,由于比赛的磨损,每辆四驱车都 有自己的寿命( 即它们能参加分站赛的 有自己的寿命 ( 场次) 不同的四驱车寿命可能不同, 场次 ) , 不同的四驱车寿命可能不同 , 但最多不会超过50场 但最多不会超过 场 。 两辆四驱车最多 只能交手一次。 只能交手一次。 现 给 定 N 、 M ( 1<=N<=100 , 1<=M<=1000)、N*N的一个输赢表、每 的一个输赢表、 ) 的一个输赢表 辆四驱车的寿命, 辆四驱车的寿命 , 并假设每次分站赛两 人都有可选的赛车,请你计算一下阿P最 人都有可选的赛车,请你计算一下阿 最 多能够赢得多少个分站赛。 多能够赢得多少个分站赛。
2011-1-20 43 of 220

1、建立N个点代表阿 的N辆车,分别以 到N标号; 、建立 个点代表阿 个点代表阿P的 辆车 分别以1到 标号 辆车, 标号; 2、建立N个点代表阿 的N辆车,分别以N+1到2N标号; 、建立 个点代表阿Q的 辆车,分别以 到 标号; 个点代表阿 辆车 标号 3、如果阿 的第 辆车能够跑赢阿 的第 辆车,则加一条 、如果阿P的第 辆车能够跑赢阿Q的第 辆车, 的第I辆车能够跑赢阿 的第J辆车 弧I N+J,容量为 ,表示两辆四驱车最多只能交手一次; ,容量为1,表示两辆四驱车最多只能交手一次; 4、增加一个源点 ,S与 1到N中的每一个结点 都连一条 、增加一个源点S, 与 到 中的每一个结点 中的每一个结点I都连一条 的第I辆车的寿命 弧S I,容量为阿 的第 辆车的寿命; ,容量为阿P的第 辆车的寿命; 5、增加一个汇点 , N+1到2N中的每一个结点 、 增加一个汇点T, 中的每一个结点N+J到T都 到 中的每一个结点 到 都 连一条弧N+J T,容量为阿 的第 辆车的寿命; 的第J辆车的寿命 连一条弧 ,容量为阿Q的第 辆车的寿命; 再增加一个源点S 加一条弧S 容量为M 6 、 再增加一个源点 S2 , 加一条弧 S2 S , 容量为 M , 表示 最多M 最多M场分站赛 。
2011-1-20 44 of 220

2011-1-20

45 of 220


赞助商链接
相关文章:
网络流模型与方法
网络流模型与方法_理学_高等教育_教育专区。图论与网络...2 1 3 4 图1 有向图 一种通常的表示方法是图...匹配问题 匹配问题模型:有 N 件物体,设法以最小的...
网络流构图总结
则就可以建 立二分图模型,利用网络流解决。 【例4】 混合图的欧拉回路《算法...利用特殊性进行增广【例1】 二分图匹配问题 】由于二分图匹配问题均是单位流量...
网络流题目集锦
网络流题目集锦_IT/计算机_专业资料。网络流题目集锦( 网络流题目集锦(转) (...id=1486 题意:二分图的必须边 解法:需正真理解最大匹配算法,详见 http://...
二分图的最大匹配经典之匈牙利算法
Doctor 的图论计划之——二分图最大匹配第一讲 二分图的最大匹配经典之匈牙利...无法快速实现,于是我们就提出 了更为高效的算法,这种算法是从网络流演变而来,但...
网络流模型总结
网络流模型总结_IT/计算机_专业资料。59146965.doc 福州一中 肖汉骏 网络流模型...九、二部图的最大匹配与网络最大流的关系 二部图的最大匹配与网络最大流的...
网络流详解(C++版)_图文
图 5-1 图 5-2 2.网络与网络流 给一个有向图 N=(V,E),在 V 中指定一点,称为源点(记为 vs,和另一点,称 为汇点(记为 vt),其余的点叫中间点,...
算法学习:图论之用匈牙利算法求二分图的最大匹配
二分图的最大匹配有两种 求法,第 一种是最大流(我在此假设读者已有网络流的知识) ;第二种就是我现在要讲的匈牙利算法。这个算法说白 了就是最大流的算法,...
网络流经典题(含部分其他图论题)
网络图例题 5页 1下载券 网络图例题 2页 1下载券 第八章 网络流图问题 10页 1下载券 习题图(网络图) 2页 4下载券喜欢此文档的还喜欢 ...
浅谈网络流算法与几种模型转换
则称之为网络流图,记为 G = (V, E, C) 介绍完最大流问题后,下面介绍...这样的流称为最小费用最大流。 二、算法思想 用 Ford-Fulkerson 算法的思想,...
线性规划与网络流24题 问题一览
代码中所有网络最大流算 法均用 Dinic 实现。 3. 读者应具备图论、最短路径...二分图最大匹配 最大权闭合图 有向无环图最小路径覆盖 有向无环图最小路径...
更多相关标签: