1离散第21讲-二分图-2.ppt

第21讲二分图二分图标准形式的分配问题基本概念示例二分图的判定定理8.1：无向图G为二分图的充分必要条件为G至少有两个顶点且其所有回路的长度为偶数。证：先证必要性。设G为二分图X，E，Y。由于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必为偶数，从而C中有偶数条边。二分图的判定再证充分性。设G的所有回路具有偶数长度，且G中不少于两个顶点。假设G连通，否则可对其每个连通分支作如下讨论。令G的顶点集为V,边集为E,现构造两个集合X,Y，使X，E，Y=G。取v0?V,置X={v?v=v0或v到v0的最短通路为偶数长度}Y=V-XX非空。现证（1）Y非空，（2）且没有任何边的两个端点都在X或都在Y中.（1）因为G连通，所以v0至少有一个相邻顶点，设相邻顶点为v1，那么v1?Y（为什么？）；故Y不空。二分图的判定（2）设有边{u,v},使u?X，v?X。证明一定存在奇数长度的回路，与题设矛盾。故不可能有边{u,v}使u,v均在X中。因为u?X，v?X，所以v0到u有偶数长度的通路，或u=v0；v0到v有偶数长度的通路，或v=v0。这样，无论何种情况，连同边{u,v}均有一条从v0到v0的奇数长度的闭的拟路径，在此闭的拟路径中一定存在奇数长度的回路(回忆定理7.5)。同理可证“没有任何边的两个端点全在Y中”。作为一种数学模型,二分图是十分有用的，许多问题可以用它来刻划。例如“资源分配”、“工作安排”、“人员择偶”等等。利用二分图分析解决这类问题时，还需要有关二分图的另一个概念——匹配。匹配定义8.2:设G=X,E,Y为二分图，M?E，如果M中的任意二条边都没有公共端点，则说M是G的一个匹配。G的所有匹配中边数最多的匹配称为最大匹配。如果X(Y)中任一顶点均为匹配M中边的端点，那么称M为X(Y)-完全匹配。若M既是X-完全匹配又是Y-完全匹配，则称M为G的完全匹配。（a）既非X完全匹配也非Y完全匹配，（b）中匹配是最大的，X={a,b,c},匹配是X-完全的，（c）中匹配是G的完全匹配（从而也是最大的）。匹配的性质1)最大匹配总是存在但未必唯一；2)X(或Y)-完全匹配及G的完全匹配必定是最大的,反之不然；3)X(或Y)-完全匹配未必存在，若存在则为最大匹配。求取最大匹配定义8.3：设G=X,E,Y为二分图，M是G的一个匹配M中边的端点称为M-顶点，其它顶点称为非M-顶点。M中的边称为匹配边；其它边称为非匹配边。设P是G中以vk为起点，vh为终点的一条通路，如果vh、vk均为非M-顶点，且P中非匹配边与匹配边交替出现，则称P为G关于匹配M的一条交替链。当某边(u,v)的两端点均为非M-顶点时，(u,v)也称为交替链。交替链交替链交替链求取最大匹配?????匈牙利算法把G中任一匹配M扩充为最大匹配算法基本思想——不断寻找交替链，每找到一条交替链即将其中的匹配边和非匹配边对换，从而增加一条匹配边，直至从初始匹配扩充为最大匹配匈牙利算法(1)首先用(*)标记X中的所有非M-顶点，然后交替进行下列步骤(2)和(3)。(2)选取一个刚标记过的X中的顶点设为xi，用(xi)去标记Y中的与xi通过非匹配边相联的并且还没有被标记过的端点y，对X中新标记的结点重复上述过程。(3)选一个Y中新标记的顶点设为yj，用(yj)去标记X中的与yj通过匹配边相联的，并且还没有标记过的结点x，对Y中新标记的结点重复上述过程。(2)(3)交替执行，这一过程称为标记过程。标记到最后可能出现下列两种情况： 匈牙利算法情况(a)：标记到Y中的某一顶点y，它不是M-顶点。这时由y逆溯而上，一直到用*标记的X中的顶点x，这是一条交替链。 情况(b)：步骤(2)或(3)找不到可标记的结点，而又不是(a)，这时M已是最大匹配了。(4)当(2)、(3)步骤中断于情况(a)