图论第5章-课件（PPT-精）.ppt

v3 v4 v5 v6 v1 v2 v3 v4 v5 v6 v1 v2 v3 v4 v5 v6 v1 v2 则K6可分解为 定理12 每一个没有割边的3-正则图是一个1-因子和一个2-因子的并。 证明： 因每个没有割边的3-正则图存在完美匹配M，显然，G-M是一个2-因子。 例 彼得森图是一个1-因子和一个2-因子的和 。 注： 若没有割边的3度正则图中的2-因子是一些偶圈 , 则该图也是1-可因子化的。 定理13 一个连通图是2-可因子化的当且仅当它是偶数度正则的。 证明：必要性显然。 充分性：利用结论 “顶点度数为偶数的任意正则图存在一个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 时取到。 推论 完全图和完全偶图的荫度为 完全图Kn的森林分解方法： ① n=2s 将K2s分解为s条生成路 Pi =vivi+1vi-1vi+2vi-2…vi+(s-1)vi-(s-1)vi+s。 ② n=2s+1 在K2s分解得到的每条生成路上附加一个标号为v2s+1的孤立点，然后连接v2s+1与另外2s个点构成一个星形图。 v7 v1 v2 v6 v3 v5 v4 v7 v1 v2 v6 v3 v5 v4 说明 这种构造是由K7的一个点v7为心的星形图与相应的K6的上述三条生成路形成的生成森林所组成。 例 分K7为生成森林的最小分解如下图所示。 v7 v1 v6 v5 v4 v2 v3 v7 v1 v6 v5 v4 v2 v3 人员分派问题：n 个工人 x1, x2,…, xn，n 件工作 y1, y2,…, yn。已知 xi 能胜任 ki 件工作，i =1，2，…,n。问能否存在一种工作安排方案，使每个人都能分配到他所能胜任的一件工作。假定每件工作只能一人做，若能，又如何安排？ 建模：以工人和工作为点，当且仅当 xi 能胜任工作 yj 时则连线，得偶图 G 。于是一种符合要求的安排对应 G 中一个完美匹配。所以此问题实际上是求偶图的完美匹配问题。 若不要求人数与工作数相等，则问题是求偶图的饱和V1的每个点的匹配问题，其中V1是工人的集合；进一步，若问：能否存在一种安排使尽可能多的人能分到他能胜任的工作或使尽可能多的工作被分配，则问题为求偶图的最大匹配问题。 §5.5 最优匹配与匈牙利算法 一、匈牙利算法 算法思想：先任取一个匹配 M，然后寻找M 可扩路。若不存在 M 可扩路，则 M 为最大匹配；若存在，则将可扩路中M 与非 M 的边互换，得到一个比 M 多一条边的匹配 M ’，再对 M ’ 重复上面过程。 算法是从V1 的每个非饱和点出发寻找 M 可扩路的。若从V1 的每个非饱和点出发都无 M 可扩路，则 M 必无可扩路，从而 M 是最大匹配。这是因偶图中不可能存在两个端点均在 V 2 中的 M 可扩路。 定义1 设M是G中的匹配，u是X的M非饱和点，若树H?G 满足(1) u∈V(H)； (2) 对H的每个顶点v，H中唯一的（u, v）路是一条M交错路， 则称树H是一棵扎根于u的M交错树。 x1 x2 x3 x4 x5 x6 y1 y2 y3 y4 y5 y6 G的一个匹配M x6 y5