几种特殊图.docVIP

第八章 几种特殊的图 本章讨论几类在理论研究和实际应用中都有重要意义的特殊图，它们是二分图、平面图和树。 ? 8.1 二 分 图 ? 8.1.1 二分图的基本概念 定义8.1 无向图G = V，E，(称为二分图（bipartite graph），如果有非空集合X，Y使X∪Y = V，X∩Y = (，且对每一e(E，((e) = (x, y)，x(X，y(Y。此时常用X，E，Y表示二分图G。若对X中任一x及Y中任一y恰有一边e(E，使((e) = (x, y), 则称G为完全二分图（complete bipartite graph）。当(X( = m，(Y( = n时，完全二分图G记为Km,n。 例8.1 图8.1中（a），（b）为二分图，（c）为完全二分图K3,3，(d), (e)不是二分图。 (a) (b) (c) (d) (e) 图8.1 二分图的下列特征性是重要的。 定理8.1 无向图G为二分图的充分必要条件是，G至少有两个顶点,且其所有回路的长度均为偶数。 证 先证必要性。 设G为二分图X，E，Y。由于X，Y非空，故G至少有两个顶点。若C为G中任一回路，令 C = ( v0,v 1,v2,…,v l-1,v l = v0 ) 其中诸vi ( i = 0,1,…,l )必定相间出现于X及Y中，不妨设 {v0,v2,v4,…, v l = v0} ( X {v1,v3,v5,…, v l-1} ( Y 因此l必为偶数，从而C中有偶数条边。 再证充分性。 设G的所有回路具有偶数长度，并设G为连通图（不失一般性，若G不连通，则可对G的各连通分支作下述讨论）。 令G的顶点集为V，边集为E，现构作X，Y，使X，E，Y = G。取v0(V,置 X = {v ( v= v0或v到v0有偶数长度的通路} Y = V-X X显然非空。现需证Y非空，且没有任何边的两个端点都在X中或都在Y中。 由于(V(≥2并且G为一连通图，因此v0必定有相邻顶点，设为v1，那么v1(Y；故Y不空。 设有边(u, v), 使u(X，v(X。那么，v0到u有偶数长度的通路，或u = v0；v0到v有偶数长度的通路，或v = v0。无论何种情况，均有一条从v0到v0的奇数长度的闭路径，因而有从v0到v0的奇数长度的回路（因从闭路径上可能删去的回路长度总为偶数），与题设矛盾。故不可能有边（u, v）使u, v均在X中。 “没有任何边的两个端点全在Y中”的证明可仿上进行，请读者思考。 二分图是十分有用的一种数学模型，许多问题可以用它来刻划。例如“资源分配”、“工作安排”、“人员择偶”等等。但是，利用二分图分析解决这类问题时，还需要有关二分图的另一个概念——匹配。 8.1.2 匹配 定义8.2 设G = X，E，Y为二分图，M(E。称M为G的一个匹配（matching），如果M中任何两条边都没有公共端点。G的所有匹配中边数最多的匹配称为最大匹配（maximal matching）。如果X(Y)中任一顶点均为匹配M中边的端点，那么称M为X(Y)-完全匹配(perfect matching)。若M既是X-完全匹配又是Y-完全匹配，则称M为G的完全匹配。 例8.2 图8.2中各图的粗线表示匹配中的边（简称匹配边）。（b）中匹配是最大的，X-完全的，（c）中匹配是完全的（从而也是最大的）。 ? ? ? ? ? ? （a） （b） （c） 图8.2 注意，最大匹配总是存在但未必唯一。此外，X(Y)-完全匹配及完全匹配必定是最大的，但反之则不然；X(Y)-完全匹配未必存在。 为讨论最大匹配的求法及完全匹配的存在条件，需要下列术语。 定义8.3 设G = X，E，Y，M为G的一个匹配。 （1）M中边的端点称为M-顶点，其它顶点称为非M-顶点。 （2）G中vk到vl的通路P称为交替链，如果P的起点vk和终点vl为非M-顶点，而其边的序列中非匹配边与匹配边交替出现（从而首尾两边必为非匹配边，除顶点vk，vl以外各顶点均为M-顶点）。特别地，当一边（v, v）两端点均为非M-顶点，通路（v, v）亦称为交替链。 以下算法可把G中任一匹配M扩充为最大匹配，此算法是Edmonds于1965年提出的，被称为匈牙利算法，其步骤如下： （1）首先用（*）标记X中所有的非M-顶点，然后