资源描述：
《离散数学 第2版 教学课件 作者 王元元 离散第21讲 二分图.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、计算机专业基础课程授课人：王元元单位：计算机理论教研室理工大学指挥自动化学院PowerPointTemplate_Sub1二分图2平面图3树2第21讲二分图二分图《离散数学》第21讲Page130to134基本概念定义：无向图G=称为二分图，如果有非空集合X，Y使X∪Y=V，X∩Y=，且对每一eE，e={x,y}，xX，yY。此时常用表示二分图G。若对X中任一x及Y中任一y恰有一边eE，使e={x,y},则称G为完全二分图。当X=m，Y=n时，完全二分图G记为Km,n
2、。4第21讲二分图示例(a)二分图(b)二分图(c)完全二分图K3,3(d)非二分图(e)非二分图5第21讲二分图二分图的判定定理：无向图G为二分图的充分必要条件为G至少有两个顶点且其所有回路的长度为偶数。证：先证必要性。设G为二分图。由于X，Y非空，故G至少有两个顶点。若C为G中任一长度为k的回路，令C=(v0,v1,v2,…,vk-1,vk=v0)其中诸vi(i=0,1,…,k)必定相间出现于X及Y中，显然{v0,v2,v4,…,vk=v0}X{v1,v3,v5,…,vk-1}Y因此k必
3、为偶数，从而C中有偶数条边。6第21讲二分图二分图的判定再证充分性。设G的所有回路具有偶数长度，且G中不少于两个顶点。假设G连通，否则可对其每个连通分支作如下讨论。令G的顶点集为V,边集为E,现构造两个集合X,Y，使=G。取v0V,置X={vv=v0或v到v0的最短通路为偶数长度}Y=V-XX非空。现证Y非空，且没有任何边的两个端点都在X或都在Y中.（1）因为G连通，所以v0至少有一个相邻顶点，设相邻顶点为v1，那么v1Y（为什么？）；故Y不空。7第21讲二分图二分图的判定（2）设有边{u
4、,v},使uX，vX。证明一定存在奇数长度的回路，与题设矛盾。故不可能有边{u,v}使u,v均在X中。因为uX，vX，所以v0到u有偶数长度的通路，或u=v0；v0到v有偶数长度的通路，或v=v0。这样，无论何种情况，连同边{u,v}均有一条从v0到v0的奇数长度的闭的拟路径，在此闭的拟路径中一定存在奇数长度的回路(见练习8.5,第13题)。同理可证“没有任何边的两个端点全在Y中”。uvv0v0v08第21讲二分图匹配定义:设G=为二分图，ME，如果M中的任意二条边都没有公共端点，则说
5、M是G的一个匹配。G的所有匹配中边数最多的匹配称为最大匹配。如果X(Y)中任一顶点均为匹配M中边的端点，那么称M为X(Y)-完全匹配。若M既是X-完全匹配又是Y-完全匹配，则称M为G的完全匹配。9第21讲二分图匹配的性质1)最大匹配总是存在但未必唯一；2)X(或Y)-完全匹配及G的完全匹配必定是最大的,反之不然；3)X(或Y)-完全匹配未必存在，若存在则为最大匹配。XYXY10第21讲二分图求取最大匹配术语：设G=为二分图，M是G的一个匹配M中边的端点称为M-顶点，其它顶点称为非M-顶点。M中的
6、边称为匹配边；其它边称为非匹配边。设P是G中以vk为起点，vh为终点的一条通路，如果vh、vk均为非M-顶点，且P中非匹配边与匹配边交替出现，则称P为G关于匹配M的一条交替链。当某边(u,v)的两端点均为非M-顶点时，(u,v)也称为交替链。11第21讲二分图交替链M-顶点非M-顶点匹配边非匹配边12第21讲二分图交替链交替链13第21讲二分图交替链多了一条匹配边！14第21讲二分图求取最大匹配匈牙利算法算法基本思想——不断寻找交替链，每找到一条交替链即将其中的匹配边和非匹配边对换，从而增加一条匹配边，直至从
7、初始匹配扩充为最大匹配15第21讲二分图匈牙利算法(1)首先用(*)标记X中的所有非M-顶点，然后交替进行下列步骤(2)和(3)。(2)选取一个刚标记过的X中的顶点设为xi，用(xi)去标记Y中的与xi通过非匹配边相联的并且还没有被标记过的端点y，对X中新标记的结点重复上述过程。(3)选一个Y中新标记的顶点设为yj，用(yj)去标记X中的与yj通过匹配边相联的，并且还没有标记过的结点x，对Y中新标记的结点重复上述过程。(2)(3)交替执行，这一过程称为标记过程。标记到最后可能出现下列两种情况：16第21讲二分
8、图匈牙利算法情况(a)：标记到Y中的某一顶点y，它不是M-顶点。这时由y逆溯而上，一直到用*标记的X中的顶点x，这是一条交替链。情况(b)：步骤(2)或(3)找不到可标记的结点，而又不是(a)，这时M已是最大匹配了。(4)当(2)、(3)步骤中断于情况(a)时，将所得交替链中的匹配边与非匹配边交换即可得到一新的匹配M’，这一匹配比原匹配M多一条边。回到步骤(1)，并消除一切现有标记。(5)对一切可能
