离散数学一些特殊的图省名师优质课赛课获奖课件市赛课一等奖课件.pptVIP

第8章一些特殊图;8.1二部图;二部图;例完全二分图Km,n=(V1,V2,E)共有

多少条边?;二部图判别法;例：判断下列图是否为二部图。;匹配;如在下列图中，假如用a1,a2,a3,a4表示4位教师，b1,b2,b3表示三门待开课程。当某位教师能开某门课程时，则把它们对应顶点用边连接起来。假如要求一个教师只能担任一门课程，那么匹配M就表示了一个排课方案。为了使排课方案能最大程度地作到“各尽其能”，这就是最大匹配概念。;匹配(续);定义设G=V1,V2,E为二部图,|V1|?|V2|,M是G中最

大匹配,若V1中顶点全是M饱和点,则称M为G中V1

到V2完备匹配.当|V1|=|V2|时,完备匹配变成完美

匹配.;M1;设G=?V1,V2,E?是二部图，M是G一个匹配，假如对G任意匹配M′，都有|M′|≤|M|，则M为G最大匹配

为了寻求二部图最大匹配，以下引进交替通路和增加通路两个概念。

;比如，在图中匹配M={(a1,b2),(a2,b3),(a3,b5)}，

路L1：a1b2a2b3a3，L2：a2b3a3b5a4，

L3：b1a3b5a4，L4：b1a1b2a2b3a3b5a4

都是M交替通路，其中后两条交替通路L3和L4始点和终点都是M非饱和点，所以这两条路是M增加通路。;设G=?V1,V2,E?是二部图，M是G一个匹配，P是G中一条M增加通路。把P中全部属于M边从M中去掉，而把P中全部不属于M边添加到M中，得到一个新边集M′，则M′也是一个匹配，其所含边数比匹配M所含边数多1。;比如在图中，把M增加通路L3：b1a3b5a4中属于M边(a3,b5)从M中去掉，而把L3中不属于M边(a3,b1)和(a4,b5)添加到M中，得到一个新边集M′=?(a1,b2),(a2,b3),(a3,b1),(a4,b5)?，显然M′也是匹配且M′边数比M边数多l，即|M′|＝|M|+1。;由此可见，利用增加通路能够增加匹配所含边数。不停地寻求G增加通路，直到再也找不到新增加通路，就可得到一个最大匹配。将这个结论写成以下定理。

定理设G=?V1,V2,E?是二部图，M为G最大匹配充分必要条件是G中不存在M增加通路。

;在子图H中，任一顶点至多与M中一条边关联且与M1中一条边关联。因而任一顶点度数是1或2。故H连通分支是一条路，或者是一个回路。

假如H连通分支是一条路P，则它是M交替路，也是M1交替路。假如P两个端点均与M中边关联，则P是M1可扩路。由假设知，M1是最大匹配，所以，不存在M1可扩路，得到矛盾。假如P两个端点均与M1边关联，那么P是一条M可扩路与题设矛盾。故P只能是一个端点与M中边关联，另一个端点与M1中边关联，这么P中属于M边数与属于M1边数相等。

;假如H连通分支是一个回路，回路中边交替地属于M和M1，因而属于M边数与属于M1边数相等。

从上面能够看到，H中属于M边与属于M1边数目相等。再加上既属于M又属于M1边，能够得出：M中边数与M1中边数相等。所以M是最大匹配。;有了上面准备以后，就能够深入讨论怎样在二部图中求最大匹配问题。

设G=?V1,V2,E?是二部图，通常先作G一个匹配M，再看V1中有没有M非饱和点。假如没有，那么M必定是最大匹配；假如有，就从这些点出发找M增加通路。由M增加通路作出一个更大匹配。所以，在G中求最大匹配关键是寻找M增加通路。

;寻找增加通路一个有效方法是标识法，其基本思想以下：

设G=?V1,V2,E?是二部图，在G中作一个匹配M，用(*)标识V1中全部M非饱和点，然后交替地进行以下①和②两步：

;直至标识到一个V2中M非饱和点。从该顶点倒向追踪到标识有(*)顶点，就得到了一个M增加通路。把M增加通路中全部属于M边从M中去掉，而把M可扩路中全部不属于M边添加到M中，得到一个新匹配M′且其所含边数比匹配M所含边数多1。对M′重复上述过程，……，直到G中已不存在增加通路，此时匹配就是最大匹配。;【例】如图是二部图，求其最大匹配。

;【例】如图是二部图，求其最大匹配。

;解：取二部图一个匹配M={(a3,b1),(a5,b2)}。用(*)标识V1中全部M非饱和点a1,a2,a4。

①选V1新标识过顶点a