二部图匹配网络流

二部图&网络流1/11/20231二部图1/11/20232二部图定义

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

K3,31/11/202347.3图的矩阵表示二部图的判别法定理

无向图G=<V,E>是二部图当且仅当G中无奇圈.1/11/20235无向简单图的

点覆盖集、点独立集、匹配1/11/20236点独立集与点独立数定义

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

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

(1)(2)(3)

1/11/20237点覆盖集与点覆盖数定义

设G=<V,E>,V*V.(1)V*是点覆盖集——eE，vV*，使e与v关联(2)V*是极小点覆盖集——V*的任何真子集都不是点覆盖集(3)最小点覆盖集——顶点数最少的点覆盖集(4)点覆盖数——0(G)——最小点覆盖的元素个数图中，点覆盖数依次为3，4，7.1/11/20238点覆盖集与点独立集的关系0+0=n

点覆盖数+点独立数=点数1/11/20239匹配(边独立集)与匹配数(边独立数)定义

设G=<V,E>,E*E，(1)匹配(边独立集)E*——E*中各边均不相邻(2)极大匹配E*——E*中不能再加其他边了(3)最大匹配——边数最多的匹配(4)匹配数——最大匹配中的边数，记为1上图中各图的匹配数依次为3,3,4.

1/11/202310关于匹配中的其他概念定义

设M为G中一个匹配.(1)匹配边——(vi,vj)M(2)v为M饱和点——有M中边与v关联(3)v为M非饱和点——无M中边与v关联(4)M的交错路径——由匹配边和非匹配边交替构成的路径(5)M的增广路径——起、终点都是M非饱和点的交错路径1/11/202311最大匹配判别定理定理

M为G中最大匹配当且仅当G中不含M的可增广交错路径.1/11/202312二部图匹配匈牙利算法1/11/202313增广路径匹配M={{x1,y1},{x2,y3},{x3,y4}}有一条增广路径x1x2y1y2x3x4y3y4x1x2y1y2x3x4y3y4x1x2y1y2x3x4y3y4由M增广路径可构造比M大的匹配存在M增广路径M非最大匹配用(M-)(

-M)代替Mx1x2y1y2x3x4y3y41/11/202314匈牙利算法由增广路径的定义可以推出下述三个结论：1、的路径长度必定为奇数，第一条边和最后一条边都不属于M。2、经过取对称差操作可以得到一个更大的匹配M。3、M为G的最大匹配当且仅当不存在关于M的增广路径。1/11/202315匈牙利算法用增广路径求最大匹配(称作匈牙利算法)算法：(1)置M为空(2)找出一条增广路

，通过取对称差操作获得更大的匹配M代替M(3)重复(2)操作直到找不出增广路径为止1/11/202316匈牙利算法示例

图1图2

1/11/202317二部图的最小点覆盖定理:G是二部图,则0=1.即二部图的最大匹配数=最小点覆盖数

注:定理对一般图不成立.1/11/202318二部图的最大独立集定理：二部图中:最大独立集数＝顶点总数－最小点覆盖数

也＝顶点总数－最大匹配数1/11/202319例题1

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

WallGrass

Empty1/11/202320例题1

PlacetheRobots（ZOJ）模型一5467832112346578于是，问题转化为求图的最大独立集问题。以空地为顶点，有冲突的空地之间连边，可以得到右边的这个图：1/11/202321例题1

PlacetheRobots模型一5467832112346578这是NP问题！1/11/202322将每一行，每一列被墙隔开且包含空地的连续区域称作“块”。显然，在一个块之中，最多只能放一个机器人。把这些块编上号。同样，把竖直方向的块也编上号。例题1

PlacetheRobots（ZOJ）模型二1234512341/11/202323例题1

PlacetheRobots模型二123451234把每个横向块看作X部的点，竖向块看作Y部的点，若两个块有公共的空地，则在它们之间连边。于是，问题转化成这样的一个二部图：1122334451/11/202324由于每条边表示一个空地，有冲突的空地之间必有公共顶点，所以问题转化为二部图的最大匹配问题。例题1

PlacetheRobots模型二1234123541122334451/11/202325例题2

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

Thesecondyearoftheuniversitysomebodystarteda

studyontheromanticrelationsbetweenthestudents.

Therelation“romanticallyinvolved”isdefinedbetween

onegirlandoneboy.Forthestudyreasonsitisnecessary

tofindoutthemaximumsetsatisfyingthecondition:

therearenotwostudentsinthesetwhohavebeen

“romanticallyinvolved”.Theresultoftheprogramisthe

numberofstudentsinsuchaset.

Theinputcontainsseveraldatasetsintextformat.

Eachdatasetrepresentsonesetofsubjectsofthestudy,

withthefollowingdescription:

thenumberofstudents

thedescriptionofeachstudent,inthefollowingformat1/11/202327GirlsandBoysstudent_identifier:(number_of_romantic_relations)

student_identifier1student_identifier2...

or

student_identifier:(0)

Thestudent_identifierisanintegernumberbetween0

andn-1,fornsubjects.

Foreachgivendataset,theprogramshouldwritetostandardoutputalinecontainingtheresult.

1/11/202328GirlsandBoysSampleInput

70:(3)4561:(2)46Y:(0)E:(0)4:(2)015:(1)06:(2)01

Output501YE4561/11/202329网络流简介

1/11/2023301/11/2023311/11/202332sadbct16,1113,810,4,112,1220,157,79,414,114,4sadbct551131257534811411151/11/202333剩余图增广之后的新流sadbct161310412207914420,sadbct16,413,10,4,12,47,9,414,44,4sadbct124482075104104413420,7sadbct16,1113,10,74,12,47,79,414,114,41/11/202334剩余图增广之后的新流20,7sadbct16,1113,10,74,12,47,79,414,114,4134sadbct51111875334111347sadbct16,1113,810,4,112,1220,157,79,414,114,41/11/202335剩余图增广之后的新流sadbct16,1113,810,4,112,1220,157,79,414,114,4sadbct55113125753481141115sadbct16,1113,1210,4,112,1220,197,79,14,114,411sadbct5111312179341211191/11/20233622134222221342222,21342,22,22,02,022134222222,21342,02,22,22,21234222221/11/20233722134222212342222212342222a2b22c2d21/11/202338剩余图sabt10001000110001000解决方法：(1)EK算法:在剩余图中找最短增广路径(2)最大容量增广算法:找最大瓶颈容量1/11/202339练习1:无向图的网络流下图为某地区运输网.边上的数字表示运输能力（单位：万吨/小时），则从顶点1到顶点5的最大运输能力可以达到_____万吨/小时.12042410106853241/11/202340练习2《算法导论》P40026.1-91/11/202341阿P与阿Q都是四驱车好手，他们各有N辆四驱车。为了一比高下，他们约好进行一场比赛。这次比赛共有M个分站赛，赢得分站赛场次多的获得总冠军。每个分站赛中，两人各选一辆自己的赛车比赛。分站赛的胜负大部分取决于两车的性能，但由于种种原因（如相互之间的干扰），性能并不是决定胜负的唯一指标，有时会出现A赢B、B赢C、C赢D、D又赢A的局面。幸好有一种高智能机器，只要给定两