第4,5章E,H图,匹配(09.3).pptVIP

§ 4.2 高效率计算机鼓轮的设计 例 §4.4 哈密尔顿图 第五章 匹配与因子分解 §5.3 Tutte定理与完美匹配 §5.4 因子分解 三、荫度 §5.5 最优匹配与匈牙利算法 二. 2－因子分解 由定义有: (1) 若一个图是2-可因子化，则每个因子一定是不相交圈的一个并。 (2) 2-可因子化的图的所有点的度一定是偶数，所以 完全图K2n不是2-可因子化的。 (3) 若一个2-因子是连通的，则它是一个H圈。 定理10 图K2n+1 是n个H圈的和。 证明 为了在 K2n+1 中构成n个边不相交的生成圈，先标定它的点v1,v2,…,v2n+1。然后，在点v1,v2,…,v2n上构成 n 条路Pi 如下：Pi =vivi-1vi+1vi-2…vi-nvi+n。 于是Pi 的第j 点是vk ，其中 k = i + (-1) j+1 ，并且所有下标取为整数1，2，…，2n（mod 2n）。生成圈Hi 是由v2n+1联接于Pi的两个端点构成。 例3 将K7分解成3个生成圈的和。 解 将K7的顶点用数码i表示，而1, 2, 3；4, 5, 6为正六边形的顶点，7是中心（图5-11（a））。其实线就是一个2－因子，它是一个Hamilton圈 H1= v7v1v2v6v3v5v4v7，若将1, 2, 3, 4, 5, 6绕中心按顺时间方向移动一个位置（图5-11（b）），则得另一个H 圈H2= v7v2v3v1v4v6v5v7，第三个H 圈必然是 H3 = v7v3v4v2v5v1v6v7，则 K7 =H1∪H2∪H3。 定理11 完全图K2n是一个1-因子和n-1个H圈的和。 定理12 每一个没有割边的3度正则图是一个1-因子和一个2-因子的和。(由定理5的推论可证) 例 彼得森图是一个1-因子和一个2-因 子的和 注 若没有割边的3度正则图中的2-因子是一些偶圈 , 则该图也是1-可因子化的. 定理13 一个连通图是2-可因子化的当且仅当它是偶数度正则的。 荫度 图G分解为边不相交的生成林的最少数目,记为σ(G)。 例 σ(K4)=2 σ(K5) =3 定理14 令G是一个非平凡图，又令ms是G的任何一个有s个点的子图中边的最多数目，则 σ(G)≥ 的证明 因为若G有n个点，则在任何一个生成林中边的最多数目是n－1。从而G的边不相交的生成林至少有 m/(n-1)个. 但G的荫度是一个整数，所以σ(G)≥ 。对于子图H，显然有σ(G)≥σ(H)，故σ(G)≥ 。 对于Kn，ms 的最大值显然在 s = n 时出现，所以 σ(Kn)= 类似地，对完全偶图Kr, p，ms 的最大值在 s = n = r + p 时取到。所以有 推论 完全图和完全偶图的荫度为 例4 分K7为生成林的最小分解如下图所示。 v7 v1 v6 v2 v5 v3 v4 v7 v1 v6 v2 v5 v3 v4 v7 v7 说明 这种构造是由K7的一个点v7为心的星形图与相应的K6的上述三条生成路形成的生成子林所组成。 人员分派问题：n 个工人 x1, x2,…, xn，n 件工作 y1, y2,…, yn。已知 xi 能胜任 ki 件工作，i =1，2，…,n。问能否存在一种工作安排方案，使每个人都能分配到他所能胜任的一件工作。假定每件工作只能一人做，若能，又如何安排？ 建模：以工人和工作为点，当且仅当 xi 能胜任工作 yj 时则连线，得偶图 G .于是一种符合要求的安排对应 G 中一个完美匹配。所以此问题实际上是求偶图的完美匹配问题. 进一步：若不要求人数与工作数相等，则问题是求偶图的饱和V1的每个点的匹配问题，其中V1是工人的集合；进一步，若问：能否存在一种安排使尽可能多的人能分到他能胜任的工作或使尽可能多的工作被分配，则问题为求偶图的最大匹配问题。 一、匈牙利算法 算法思想：先任取一个匹配 M，然后寻找M 可扩路。若不存在 M 可扩路，则 M 为最大匹配；若存在，则将可扩路中 M 与非 M 的边互