离散数学：08图论e－二部图.ppt

1二部图二部图一、二部图一、二部图定义定义1：若无向图：若无向图G＝＝的顶点集合的顶点集合V可以划分成两个子集可以划分成两个子集X 和和Y，使，使G中的每一条边中的每一条边e的一个端点在的一个端点在X中，另一个端点中，另一个端点 在在Y中，则称中，则称G为为二部图二部图或或偶图偶图二部图可记为二部图可记为 G＝＝，，X和和Y称为称为互补结点子集互补结点子集 二部图不会有自回路二部图不会有自回路定义定义2：： 二部图二部图G＝＝中，若中，若X的每一顶点都与的每一顶点都与Y的每一的每一顶点邻接，则称顶点邻接，则称G为为完全二部图完全二部图，， 记为记为Km,n，这里，这里m=|X|，， n=|Y|K2,4K3,32一、二部图一、二部图定理定理1：无向图：无向图G＝＝为二部图的充要条件为为二部图的充要条件为G中所有中所有 回路的长度均为偶数回路的长度均为偶数证明：必要性证明：必要性:设设G是具有互补结点子集是具有互补结点子集X和和Y的二部图，的二部图，C是是G中任中任一回路，一回路，C：：(v0,v1,v2,…,vk,v0)。

不妨设设不妨设设v0∈∈X，则，则v0,v2,v4,…∈∈X，，v1,v3,v5,…∈∈Y，，k必必为奇数，否则，不存在边为奇数，否则，不存在边(vk,v0)于是由C中共有中共有k＋＋1条条边，故边，故C是偶数长度的回路是偶数长度的回路3 证明：充分性证明：充分性设设G是连通图，否则对是连通图，否则对G的每个连通分图进行证明设的每个连通分图进行证明设 G=只含有偶数长度的回路，定义互补结点子集只含有偶数长度的回路，定义互补结点子集X和和Y如如 下：任取一个顶点下：任取一个顶点v0，，v0∈∈V，， 取取X＝＝{x|x ∈∈V且且d(v0,x)=偶数偶数}，，Y＝＝V－－X Y ＝＝{y| y ∈∈V且且d(v0,y)=奇数奇数} 反证：假设存在一条边反证：假设存在一条边(vi,vj)，， vi,vj∈∈Y由于图是连通由于图是连通 的，所以从的，所以从v0到到vi有一条最短路径，其长度为奇数；同理，有一条最短路径，其长度为奇数；同理， 从从v0到到vj有一条长度为奇数的最短路径于是由有一条长度为奇数的最短路径于是由(vi,vj)及以及以 上两条最短路径构成的回路长度为奇数，这与题设矛盾。

则上两条最短路径构成的回路长度为奇数，这与题设矛盾则Y 的任两结点间不存在边同理可证的任两结点间不存在边同理可证X的任两结点间不存在边的任两结点间不存在边 所以所以G是二部图是二部图一、二部图一、二部图4二、匹配二、匹配定义定义3：给定一个二部图：给定一个二部图G＝＝，如果，如果E的子集的子集M中的边无中的边无公共端点，则称公共端点，则称M为二部图为二部图G的一个的一个匹配匹配含有最多边数的含有最多边数的匹配称为匹配称为G的的最大匹配最大匹配若G中的一个顶点中的一个顶点v与与M中一条边关中一条边关联，则称联，则称v是关于是关于M的的饱和点饱和点，否则称，否则称v为关于为关于M的的非饱和点非饱和点x1x2x3x4y1y2y3y4y5XY例：上例：上图中，中，M＝＝{(x1,y5),(x3,y1),(x4,y3)}是是G的一个匹配的一个匹配5定义定义4：如果二部图：如果二部图G中的一条链由不属于匹配中的一条链由不属于匹配M的边和属于的边和属于M的的 边交替组成，且链的两端点不是边交替组成，且链的两端点不是M中的边的端点，那么称此链为中的边的端点，那么称此链为G中关于匹配中关于匹配M的的交替链交替链，首尾相接的交替链称为，首尾相接的交替链称为交替回路交替回路；若；若交替链的起点和终点都是非饱和点，则该路径称为交替链的起点和终点都是非饱和点，则该路径称为M的的可增广可增广交替链交替链。

最短的最短的交替链交替链是由一条边组成，该边的两端点不是是由一条边组成，该边的两端点不是M中边的端点中边的端点x1x2x3x4y1y2y3y4y5XY例：上例：上图中中(x2,y1,x3,y4)是是交替交替链三、最大匹配三、最大匹配6三、最大匹配三、最大匹配 交替链可用标记法求出，过程如下：交替链可用标记法求出，过程如下：首先把首先把X中所有中所有不是不是M的边的端点的边的端点用用(*)加以标记，然后加以标记，然后交替交替进行以进行以下所述的过程下所述的过程I)和和II)ØI) 选一个选一个X的新标记过的结点，例如的新标记过的结点，例如xi，用，用(xi)标记标记不通过不通过M中的边中的边与与xi邻接且邻接且未标记过未标记过的的Y的所有结点对所有的所有结点对所有X的新标记过的结点重复这的新标记过的结点重复这一过程；一过程；ØII) 选一个选一个Y的新标记过的结点，例如的新标记过的结点，例如yi，用，用(yi)标记标记通过通过M中的边中的边与与yi邻接且邻接且未标记过未标记过的的X的所有结点对所有的所有结点对所有Y的新标记过的结点重复这的新标记过的结点重复这一过程；一过程；直至标记到直至标记到一个一个Y的不与的不与M中任何边邻接的结点中任何边邻接的结点，或者已，或者已不可能标不可能标记更多结点记更多结点时为止。

出现前一情况，说明已找到了一条可增广交替链时为止出现前一情况，说明已找到了一条可增广交替链(逆着标记次序，返回到标记着逆着标记次序，返回到标记着(*)的结点，所经过的路径就是所求的结点，所经过的路径就是所求)出现后一情况，说明出现后一情况，说明G中不存在关于中不存在关于M的交替链的交替链7n下图中，标记过程如下：下图中，标记过程如下：Ø把把x2标记为标记为(*)；；Ø从从x2出发，应用过程出发，应用过程I，把，把y1和和y3标记为标记为(x2)；；Ø从从y1出发，应用过程出发，应用过程II，把，把x3标记为标记为(y1)，从，从y3出发，应出发，应 用用过程过程II，把，把x4标记为标记为(y3)；；Ø从从x3出发，应用过程出发，应用过程I，把，把y4标记为标记为(x3)，因为，因为y4不是不是M中中 边的端点，说明已找到了一条可增广交替链边的端点，说明已找到了一条可增广交替链P，即，即(x2,y1,x3,y4)y1)(y3)(*)(x2)(x2)(x3)x1x2x3x4y1y2y3y4y5XY三、最大匹配三、最大匹配8n在二部图在二部图G中，如果能找出一条关于匹配中，如果能找出一条关于匹配M的交替链的交替链L，则把，则把L中属于中属于M的边从的边从M中删去，而把中删去，而把L中不属于中不属于M的边添到的边添到M中，中，得到一个新集合得到一个新集合M’，此，此M’也是也是G的匹配。

因为添入的边自身的匹配因为添入的边自身不相交，又不与不相交，又不与M中不属于中不属于L的边相交的边相交x1x2x3x4y1y2y3y4y5XYn前面图变换后，得到的前面图变换后，得到的M’如上图所示，比如上图所示，比M多了一条边于多了一条边于 是，反复进行这样的过程，直至找不出关于是，反复进行这样的过程，直至找不出关于M的交替链为止，的交替链为止， 即可求出即可求出G的最大匹配的最大匹配三、最大匹配三、最大匹配9 对于已知匹配：对于已知匹配： M＝＝{(x1,y5),(x3,y1),(x4,y3)} 设上面找到的一条交替链设上面找到的一条交替链P:(x2,y1,x3,y4)可表示为可表示为 E(P)={( x2,y1),(y1,x3),(x3,y4)}，， 则更大的匹配为则更大的匹配为 M E(P)={(x1,y5),( x2,y1),(x3,y4),(x4,y3)}三、最大匹配三、最大匹配x1x2x3x4y1y2y3y4y5XY定理定理2：： 无向图无向图G＝＝为二部图，为二部图，M为为G的最大匹配的的最大匹配的 充要条件是充要条件是G中不存在关于中不存在关于M的可增广的交替链。

的可增广的交替链10n例：求例：求图示二部示二部图的最大匹配的最大匹配1、置、置M为Ф，，M＝＝ Ф；；2、找出一条、找出一条边的可增广交替的可增广交替链(x2,y2)，，M＝＝{(x2,y2)};3、找出一条、找出一条边的可增广交替的可增广交替链(x3,y3)，，M＝＝{(x2,y2),(x3,y3)};4、找出一条、找出一条边的可增广交替的可增广交替链(x4,y4)，，M＝＝{(x2,y2),(x3,y3),(x4,y4)};5、用、用标记法找出一条可增广交替法找出一条可增广交替链(x1,y3,x3,y2,x2,y1)，，进行行变换得得M={(x1,y3),(x2,y1),(x3,y2),(x4,y4)};x1x2x3x4x5x6y1y2y3y4y5y6三、最大匹配三、最大匹配116、再用、再用标记法找可增广交替法找可增广交替链，但已找不到所以，但已找不到所以M={(x1,y3),(x3,y2),(x2,y1),(x4,y4)}就是所求的最大匹配就是所求的最大匹配x1x2x3x4x5x6y1y2y3y4y5y6三、最大匹配三、最大匹配12例：在某电视台的姻缘速配节目中，有例：在某电视台的姻缘速配节目中，有6个女青年个女青年L1,L2,L3,L4,L5,L6，，6个男青年个男青年G1,G2,G3,G4,G5,G6，经过，经过相互了解后，每人心中都有一个表，只愿意和表中的人交相互了解后，每人心中都有一个表，只愿意和表中的人交朋友，现在知道女青年的表分别为：朋友，现在知道女青年的表分别为：L1：：{G1,G2,G4}；；L2：：{G3,G5}；；L3：：{G1,G2,G4}；；L4：：{G2,G5,G6}；；L5：：{G3,G6}；；L6：：{G2,G5,G6}；；男青年的表分别为：男青年的表分别为：G1：：{L1,L3,L6}；；G2：：{L2,L4,L6}；；G3：：{L2,L5}；；G4：：{L1,L3}；；G5：：{L2,L6}；；G6：：{L3,L4,L5}；；请问如何匹配，使得男女双方都满意且速配的对数最多。

请问如何匹配，使得男女双方都满意且速配的对数最多三、最大匹配三、最大匹配13解：令解：令X＝＝{L1,L2,L3,L4,L5,L6}，，Y＝＝{G1,G2,G3,G4,G5,G6}，， 根据男女青年的表作无向二部图根据男女青年的表作无向二部图G＝＝，如下图所示，，如下图所示， 其中，其中，∈∈E当且仅当当且仅当Li与与Gj彼此愿意交朋友彼此愿意交朋友L1L2L3L4L5L6G1G2G3G4G5G6三、最大匹配求得一个最大匹配为：求得一个最大匹配为：{(L1,G1),(L2,G3),(L3,G4),(L4,G2),(L5,G6),(L6,G5)}14作作业：： 习题8.5 1, 4。