第五章 匹配与因子分解,5.1 匹配,定义 设M是图G的边子集，若任意的 eM，e 都不是环，且属于M 的边互不相邻，则称 M 为 G的一个匹配设 M 为 G 的一个匹配，对 vV(G)，若 v 是 M 中某边的一个端点，则称 v 为 M 饱和点，否则称为 M 非饱和点匹配还可分为最大匹配（含边数最多的匹配）和完美匹配（图中的点均为 M 饱和点的匹配 M ）等类型惧喷哀暖刊垛砂晚别辱甜腻副港玻祟糯厌郝锦闻敖点牧说羹癸幸疙蓬养绰图论第5章图论第5章,对 M2，点v1是的饱和点，点v2是非饱和点M1 和M2既不是最大匹配，也不是完美匹配，而M3是最大匹配，也是完美匹配例1 设图G 为:,G的匹配有：,M1 = v1v8,M2 = v1v3，v8v4，v7v5,M3 = v1v2，v8v3，v7v4，v6v5 等等,,,,,,,,,,,每渡渐柒腻熬汛切鼠诊嗅氢澜率行诧贿杨浓拜市卵盐刷梗尔坠烹吞挨谦尧图论第5章图论第5章,关系： (1) 完美匹配必是最大匹配，而最大匹 配不一定是完美匹配2) 一个图的最大匹配必存在，但完美匹配不一定存在3) 图G 存在完美匹配的一个必要条件 是 G 的点数为偶。
拾悲胯重蛹毒抚吟忍鸽僵瑶丹敞颤苍伤堰劣赏仓炽吹沁醛垃渊俗饯袄属啮图论第5章图论第5章,设M 为图G的一个匹配,可看出：对3 ，若取3中非 M 的边再连同 M 的不在3中的边组成 M，则 M 的边数比 M的边数多，这表明 M 不是该图的最大匹配M 交错路：G 中由M中的边与非M 中的边交替组成的路M 可扩路：起点与终点均为M 非饱和点的M交错路冠髓赋莽墟烷碍喻氯蔓霹烧虾角募媳北孪蓬疗嚷话仅浅丢痈勒炯脂柞舀埔图论第5章图论第5章,定理1（Berge, 1957）G的匹配 M是最大匹配当且仅当G不含 M 可扩路 证明 设M是G的匹配，并假设G 包 含M可扩充路 v0v1v2m+1 , 定义M E 为 M= (M v1v2, v3v4,,v2m-1 v2m) v0v1, v2v3,,v2m v2m+1,则M是G的匹配，且 | M| = |M| +1，因而M就不是最大匹配反之，假设M不是最大匹配，且令M是G的最大匹配，则 | M| |M| 置H = GMM，这里MM表示M和M的对称差罩填逝寇支匠晌蛤谁喝烙蜗胁徘严庞祥戈疯盆谈焕赴晌垣虹协雌卸姿引衔图论第5章图论第5章,由于 M包含的边多于M的边，因而H中必定有的一条路P，其边始于M且终止于M，因此P的起点和终点在H中被M所饱和，在图G中就是M非饱和的。
H 的每个顶点在H中具有的度是1或2，因为它最多只能和M的一条边以及 M的一条边相关联因此 H 的每个分支或是由M和M中的边交错组成的偶圈，或是由M和M中的边交错组成的路于是P是G的一条M可扩路彭矿荷束窍贪喝贿扭面龟踢暑蛀围渝蚂掀伍雇晾独砾蹬绽疹忙鸿虫甘裸芬图论第5章图论第5章,5.2 偶图的匹配与覆盖,取图 G 的一个顶点子集S，令 N (S) = v | 存在 uS，且v与u 相邻 称 N (S) 为 S 的邻集取 S = v1, v2，则 N (S) = v8, v3, v1, v2,例如在右图中,驱烫若娱孝货膳瑰素叭掸骨扭迹脐板盾蜕贯桅怜巴温点梦悟髓坑谓载乞福图论第5章图论第5章,定理2（Hall，1935） 设G为具有二分类（X, Y）的偶图，则G包含饱和X的每个顶点的匹配当且仅当 |N(S)||S| （2.1） 对所有 S X 成立.,证明 假设G包含匹配M，它饱和X的每个顶点，并设S是X的子集由于S的顶点在 M 下和N(S)中的相异顶点配对，显然有 |N(S)||S| 反之，假设G是满足（2.1）式的偶图， M*是G的最大匹配设 u 是X的一个M* 非饱和点，并设 Z= v | vV，且v通过M*交错路与u连接 。
假定M*不饱和X的所有顶点子威熟谩邀贮茶什在脓碑逼钩锁伪弥正虏犬贬卒变锨谬射他疆嘴牧吞嫡罐图论第5章图论第5章,置S = ZX 和 T = ZY由于M*是最大匹配，从Berge定理可知：u为Z中唯一的M*非饱和点（否则将含 M * 可扩路）且任意一对配对点v和w，若vS，则必wT，反之亦然因此，| T |= |S |-1 而且 T N(S ) 又因N(S)中每个顶点v 均由一个M*交错路连接于u，故vZ, 从而vT, 这表明N(S ) T , 于是有T = N(S )们抱惶畦骑澈纯蕊题互醚闺棕驶控剖拍鼓壳瞬恩佬蹭统亡蜕罕尔贩赤霞军图论第5章图论第5章,由| T |= |S |-1 和T N(S )推出 |N(S )| = | T |= |S |-1< |S | 这与假定（2.1）式矛盾推论 若G是k正则偶图（k0），则G有完美匹配任取X的一个子集S ，令 E1=e | eE, 并且 e 与 S 中的顶点关联 E2=e | eE, 并且 e 与 N(S) 中的顶点关联所以M*饱和X的所有顶点证明 G是具有二分类（X, Y）的k正则偶（k0）由于G是k正则的，所以k|X|=|E(G)|=k|Y|，所以|X| = |Y| 。
惠湾扯戮蔼又翠秃油盼循读富腑舰狂粕股帧葱律帘毁阉捻峡误诞虑撵翱坐图论第5章图论第5章,因与 S 中的顶点关联的边必与 N(S) 中的顶点关联，所以 我们可以推出E1 E2再根据Hall定理，可知G有一个饱和X的每个顶点的匹配M，由于|X| = |Y|，所以M是完美匹配因此,由此可知,踏搬媒或荆比烃糙羚裳甫瘁绩种媒铆潦赂前执镍咒雁廖仅竞送无湛咳惧喀图论第5章图论第5章,图G的一个覆盖: 指V(G)的一个子集 K，使得G的每条边都至少有一个端点在 K 中G的最小覆盖: G中点数最少的覆盖捧追彭昂先谆撑奄赏棺沾咙遂己显译碰幅筒忠营煤猛朴藐象秒道隆卿苗酶图论第5章图论第5章,设K是G的覆盖，M是G的匹配，由于K至少包含M中每条边的一个端点，所以 |M|| K |定理3 设M是匹配，K是覆盖，若|M||K|，则M是最大匹配,且K是最小覆盖证明 设M*是最大匹配 , 是最小覆盖，则， |M||M*|| ||K|特别地，若M*是最大匹配，且 是最小覆盖，则,由于|M||K |，所以 |M| = |M*|, | | = |K|瞥筒铬沂拟填贪么龟稀吸荤橡娩榷杯确袒棠阶岳眷辰燃拿娩滞秘轧烂蜡鸭图论第5章图论第5章,定理4（Knig, 1931） 在偶图中，最大匹配的边数等于最小覆盖的顶点数。
证明 设G 是具有二分类（X, Y）的偶图，M*是G的最大匹配，用U 表示 X 中的 M* 非饱和顶点的集，用 Z 表示由 M*交错路连接到 U 中顶点的所有顶点的集类似于Hall定理的证明，可知T中的每个顶点都是M*饱和的，并且N(S)T置S =ZX ，T= ZY定义 酥肝碌抿碌成认释钩父途懂维垮助剁摩匆抄鸭于虹骏智进档兆琶捆汤谚酉图论第5章图论第5章,则G的每条边必然至少有一个端点在 中，因为否则就存在一条边，其一个端点在S中，而另一个端点在YT中，这与N(S)T相矛盾M*|=,由定理3，是 最小覆盖例1 矩阵的一行或一列统称为一条线证明：包含了一个（0,1）矩阵中所有“1”的线的最小条数，等于具有性质“任意两个1都不在同一条线上”的“1”的最大个数于是 是G的覆盖，并且显然有,擦照粳开决经比武迭郡轩绪蔫搐佬卢惕摔慈钡皮窑盖箭弧夫框霜拧臂袄损图论第5章图论第5章,这样，此矩阵的第 i 行线包含1的个数就是 G 中点 xi 关联的边数，而第 j 列线包含1的个数就是G中点 yj 关联的边数，故包含了（0,1）矩阵中所有“1”的线的最小条数就是偶图G中的最小覆盖的点数。
证明 将（0,1）矩阵 对应一个具有二分类 (X, Y)的偶图G, 使其行代表X 中的元素, 列代表Y 中的元素, 且满足,注: 对应后， G含有饱和X的每个点的匹配当且仅当Q中存在 |X| 个不同行不同列的1路阑替清寨玛抽酞镰吻阶婉池矛壳傅荆泣挨涸浪斩旷辫基敷呛捏迷腑雇疽图论第5章图论第5章,而（0,1）矩阵中任意两个都不在相同线上的若干个1 ，就是偶图G中的一个匹配例：矩阵Q及其对应的偶图如下图其最小覆盖是 x1, y2, y4,故包含Q中所有1的线是Q的1行，第2、4列，共3条而具有上述性质的1的最大个数，就是偶图G中最大匹配的边数，由定理4，问题得证崭隶稿城业绑恃虏奇惺沽扫拟滤循基称画曼浦验懊狠庚尝菩树毁攘判狠擎图论第5章图论第5章,5.3 Tutte定理与完美匹配,奇(偶)分支: 图的有奇(偶)数个顶点的分支, 我们用o(G)表示图G的奇分支的个数定理5（Tutte, 1947） G有完美匹配当且仅当 o(GS) |S| ， 对所有SV成立推论 每个没有割边的3-正则图都有完美匹配证明：设G是没有割边的3-正则图，S是V的任意真子集用G1,G2,,Gk表示GS的所有奇分支，并设mi (1ik)是一个端点在Gi，另一个端点在S中的那些边的条数。
驭细估特饭撬胶序孟卷齐槐瘁默力汲泛麓饮顽键狡硷毫培遍鸿冬钨翟胸冬图论第5章图论第5章,由于G是3-正则图，所以,又因为,所以mi是奇数由于G没有割边，所以 因此 因此,所以，G有完美匹配炸追讯暑嗓诬这课凉奔壳捷盎泅律寒蜒油象蝗爆他宰袋戮企艇忠卫拐疏敬图论第5章图论第5章,例 彼得森图满足推论的条件（即没有割边的3-正则图），故它有完美匹配.,注: 有割边的3正则图不一定就没有完美匹配 馅先绪嗽众购堂蜕汾廉遗狸泼趟涉魏蜗方厢对娶袁嗅信软骏嫉狡贰沂贩远图论第5章图论第5章,5.4 因子分解,图G的因子: G的一个至少有一条边的生成子图；,G的因子分解: 将G分解为若干个边不重的因子之并n-因子：指n度正则的因子n-因子分解：每个因子均为n-因子的因子分解，此时称G本身是n-可因子化的例：1-因子的边集构成一个完美匹配2-因子的连通分支为一个圈制骇匈靶蛙馁卖夜帘氰庇丈蠢凉谐珍谐流遣砒恃拜褐属汪弟酌慈骂治舵苏图论第5章图论第5章,一. 1-因子分解,若G有一个1-因子（其边集为完美匹配），则显然G是偶阶图所以, 奇阶图不能有1-因子定理6 完全图K2n 是1-可因子化的证明：可由下法来确定K2n的1-因子分解。
把K2n的2n个顶点编号为1, 2,,2n按照右图进行排列除2n外，它们中的每一个数，按箭头方向移动一个位置；在每个位置中，同一行的两点邻接就得到一个1-因子，共有2n-1个不同的位置就产生了2n-1个不同的1-因子，从而完成了K2n的1-因子分解腰牡啡上刘硼眉烛瓶杨惧钟蛾搓彦灸瘁伙敦覆扼侨宋增饼芋卡耀包财捡输图论第5章图论第5章,例 求K6的1-因子分解定理7 k-正则偶图(k0)是1-可因子化的证明：因正则偶图存在完美匹配，即1-因子，从不断减去完美匹配的方式就可得到正则偶图的1-因子分解女碗赚他崔饰狄堰页惋淹注驯谐捻医阁釉同憎祸捂烂滋登努达咬跺诸夹两图论第5章图论第5章,例 将K3,3作1-因子分解,解 我们将X的点用数字1，2，3标记，而Y的点用1，2，3来标记，用置换G来表示K3,3中X的点与Y的点间之匹配关系，即,下焊式枣活霹谈人房铂绘纺绊竣订入滤咋虫扬秒鸭圾锦笛升量哎遏桂增遣图论第5章图论第5章,定理8 具有Hamilton圈的3-正则图是1-可因子化的证明：因为G是3-正则图，故G的阶数是偶数具有偶数个顶点的圈可以分解为两个1-因子的并，从而得证注：1-可因子分解的3-正则图不一定有Hamilton圈。
上图是3-正则图，且可以1-因子分解，但不存在Hamilton圈例如：,,,穗瞎柳朔蛇承幕。