离散数学一些特殊的图.ppt

1 第8章 一些特殊的图 8.1 二部图 8.2 欧拉图 8.3 哈密顿图 8.4 平面图 2 8.1 二部图 二部图 完全二部图 匹配 极大匹配 最大匹配 匹配数 完备匹配 3 二部图 定义 设无向图 G=, 若能将V 分成V1 和 V2 (V1V2=V, V1V2=), 使得G中的每条边的两个端 点都一个属于V1, 另一个属于V2, 则称G为二部图(二分图), 记为, 称V1和V2为互补顶点子集. 又若G 是简单图, 且V1中每个顶点均与V2中每个顶点都相 邻, 则称G为完全二部图, 记为Kr,s, 其中r=|V1|, s=|V2|. (a)(b) 以上两个图都是二部图，其中(b)图是完全二部图。 4 例 完全二分图Km, n=(V1,V2,E)共有 多少条边? 解 因为V1中每个顶点都与V2 中每个顶点相邻接, 所以V1 中每个顶点关联 |V2| = n 条边; 而V1 中有m个顶点, 所以Km, n共有mn条边。 5 二部图的判别法 定理 无向图G=是二部图当且仅当G中 无奇圈 。即G中的每一条回路都是由偶 数条边组成。 证明：当G(V1,V2)是二部图时，G中的任 意一条回路的各边必须往返于V1,V2之间 ，因此其回路必由偶数条边组成。 6 例：判断下图是否为二部图。 解：图中的每一条回路都是由偶数条边组成。 所以此图为二部图。 7 匹配 设G = (V, E)是具有互补顶点子集V1和V2的二 分图, M E, 若M中任意两条边都不相邻, 则称 M为G中的匹配(对集)。 l如果M是G的匹配, 且M中再加入任何一条边就 都是不匹配了, 则称M为极大匹配。 最大匹配: 边数最多的匹配 匹配数: 最大匹配中的边数, 记为1。 8 如在下图中，如果用a1,a2,a3,a4表示4位教师， b1,b2,b3表示三门待开的课程。当某位教师能开某门 课程时，则把它们的对应顶点用边连接起来。如果 规定一个教师只能担任一门课程，那么匹配M就表 示了一种排课方案。为了使排课方案能最大限度地 作到“各尽其能”，这就是最大匹配的概念。 9 匹配 (续) 设M为G中一个匹配 ai与bj被M匹配: (ai,bj)M ai为M饱和点: M中有边与ai关联 ai为M非饱和点: M中没有边与ai关联 M为完美匹配: G的每个顶点都是M饱和点 10 定义 设G=为二部图, |V1|V2|, M是G中最 大匹配, 若V1中顶点全是M饱和点, 则称M为G中V1 到V2的完备匹配. 当|V1|=|V2|时, 完备匹配变成完美 匹配. (1)(2)(3) 图中红边组成各图的一个匹配，(1)为完备的, 但不是完 美的; (2)不是完备的, 其实(2)中无完备匹配; (3) 是完美的. 匹配 (续) 例：如图 11 M1M2 例 求下图的饱和点，并判断哪个图是 完美匹配？ 解：关于M1, a,b,e,d是饱和点f,c是非饱和点 M1不是完美匹配 M2是完美匹配，所以M2中 a,b,c,d,e,f都是饱和点。 12 设G=V1,V2,E是二部图，M是G的一个匹配 ，如果对G的任意匹配M，都有|M|M|，则M 为G的最大匹配 为了寻求二部图的最大匹配，以下引进交替通 路和增长通路两个概念。 定义 设G=V1,V2,E是二部图，M是G的匹配 ，P是G中的一条路，如果P是由G中属于M的边 和不属于M的边交替组成，则称P为G的M交替通 路。如果交替通路的始点和终点都是M的非饱和 点，则称为G的M增长通路。 13 例如，在图中匹配M=(a1,b2), (a2,b3), (a3,b5)， 路 L1：a1b2a2b3a3， L2：a2b3a3b5a4， L3：b1a3b5a4， L4：b1a1b2a2b3a3b5a4 都是M的交替通路，其中后两条交替通路L3和L4的始 点和终点都是M的非饱和点，所以这两条路是M增长 通路。 14 设G=V1,V2,E是二部图，M是G的一个匹配 ，P是G中的一条M增长通路。把P中所有属于M的 边从M中去掉，而把P中所有不属于M的边添加到 M中，得到一个新的边集M，则M也是一个匹配 ，其所含边数比匹配M所含的边数多1。 15 例如在图中，把M增长通路L3：b1a3b5a4中属于 M的边(a3,b5) 从M中去掉，而把L3中不属于M的边 (a3,b1)和(a4,b5) 添加到M中，得到一个新的边集 M=(a1,b2),(a2,b3),(a3,b1), (a4,b5)，显然M也是匹 配且M的边数比M的边数多l，即|M|M|+1。 16 由此可见，利用增长通路可以增加匹配所含的边数 。不断地寻求G的增长通路，直到再也找不到新的增长 通路，就可得到一个最大匹配。将这个结论写成下列的 定理。 定理 设G=V1,V2,E是二部图，M为G的最大匹配的 充分必要条件是G中不存在M增长通路。 证明：设M为G的最大匹配，下证G中不存在M可扩路 。 如果G中存在一条M可扩路，则可以得到比M的边数 多1的匹配，所以M不是最大匹配，矛盾。所以G中不存 在M可扩路。 设G中不存在M可扩路，下证M为G的最大匹配。 设M1是最大匹配，证明|M|=|M1|。 考察属于M而不属于M1和属于M1而不属于M中的边， 由这些边连同它们的端点一起构成G的子图H。 17 在子图H中，任一顶点至多与M中的一条边关联 且与M1中一条边关联。因而任一顶点的度数是1或2 。故H的连通分支是一条路，或者是一个回路。 如果H的连通分支是一条路P，则它是M交替路 ，也是M1交替路。如果P的两个端点均与M中的边 关联，则P是M1可扩路。由假设知，M1是最大匹配 ，所以，不存在M1可扩路，得到矛盾。如果P的两 个端点均与M1的边关联，那么P是一条M可扩路与 题设矛盾。故P只能是一个端点与M中的边关联， 另一个端点与M1中的边关联，这样P中属于M的边 数与属于M1的边数相等。 18 如果H的连通分支是一个回路，回路中的 边交替地属于M和M1，因而属于M的边数与 属于M1的边数相等。 从上面可以看到，H中属于M的边与属 于M1的边的数目相等。再加上既属于M又属 于M1的边，可以得出：M中的边数与M1中的 边数相等。所以M是最大匹配。 19 有了上面的准备以后，就可以进一步讨 论如何在二部图中求最大匹配的问题。 设G=V1,V2,E是二部图，通常先作G的 一个匹配M，再看V1中有没有M的非饱和点 。如果没有，那么M肯定是最大匹配；如果 有，就从这些点出发找M增长通路。由M增 长通路作出一个更大的匹配。所以，在G中 求最大匹配的关键是寻找M增长通路。 20 寻找增长通路的一个有效方法是标记法，其基本思 想如下： 设G=V1,V2,E是二部图，在G中作一个匹配M ，用(*)标记V1中所有M的非饱和点，然后交替地进 行以下和两步： 选一个V2的新标记过的顶点，比如说bi，用 (bi)标记通过M中的边与bi邻接且尚未标记过的V1的所 有顶点。对V2所有新标记过的顶点重复这一过程。 选一个V1的新标记过的顶点，比如说ai，用(ai) 标记不通过M中的边与ai邻接且尚未标记过的V2的所 有顶点。对V1所有新标记过的顶点重复这一过程。 21 直至标记到一个V2中的M的非饱和点。从 该顶点倒向追踪到标记有(*)的顶点，就得到 了一个M增长通路。把M增长通路中所有属于 M的边从M中去掉，而把M可扩路中所有不属 于M的边添加到M中，得到一个新的匹配M且 其所含边数比匹配M所含的边数多1。对M重 复上述过程，直到G中已不存在增长通 路，此时的匹配就是最大匹配。 22 【例】如图是二部图，求其最大匹配。 a1 a2 a3 a4 b1 b2 b3 b4 b5 23 【例】如图是二部图，求其最大匹配。 24 解：取二部图的一个匹配M= (a3,b1), (a5,b2)。用(*)标记V1中所有M的非饱和点a1, a2, a4。 选V1的新标记过的顶点a1，用(a1)标记不 通过M的边与a1邻接且尚未标记过的V2的顶点b1 ；类似地用(a2)标记b2。 选V2的新标记过的顶点b1，用(b1)标记通 过M的边与b1邻接且尚未标记过的V1的顶点a3； 类似地用(b2)标记a5。 25 选V1的新标记过的顶点a3，因为不存在不通 过M的边与a3邻接的V2的顶点，所以不用(a3)标 记V2的顶点；用(a5)标记b3或b4，假定用(a5)标 记b3。如图所示。 b3是M的非饱和点，标记结束。 从b3倒向追踪到标记有(*)的顶点，就得到 了M增长通路：a4b2a5b3或a2b2a5b3，取后者。把 M增长通路a2b2a5b3中的边(a5,b2)从M中去掉， 而把(a2,b2)和(a5,b3)添加到M中得到新的匹配 M=(a3,b1), (a2,b2), (a5,b3)，如图9.61所示。 26 27 对匹配M= (a3,b1), (a2,b2), (a5,b3) 再用标记法： 用(*)标记V1中所有M的非饱和点a1和 a4。 选V1的新标记过的顶点a1，用(a1)标记不通过M 的边与a1邻接且尚未标记过的V2的所有顶点b1；再用(a4) 标记b2。 选V2的新标记过的顶点b1，用(b1)标记通过M的 边与b1邻接且尚未标记过的V1的所有顶点a3；再用(b2)标 记a2。 选V1的新标记过的顶点a2和a3，V2中已无可标记 的顶点。 图中已不存在增长通路，所以M就是最大匹配。 28 【例】求下图的最大匹配。 29 解：取二部图图9.62的一个匹配 M=(a2,b2), (a3,b3), (a5,b5)。用(*)标记V1中所有M的非饱和点a1, a4。 选V1的新标记过的顶点a1，用(a1)标记b2和b3。 选V2的新标记过的顶点b2和b3，用(b2)标记a2，用 (b3)标记a3。 选V1的新标记过的顶点a2，用(a2)标记b1, b4和b5。 由于b1和b4都是M的非饱和点，说明找到了M可扩路 。 它们是：a1b2a2b4和a1b2a2b1。选前者，把边(a2,b2)从 M中去掉，而把(a1,b2)和(a2,b4)添加到M中，得到新的匹 配M=(a1,b2),(a2,b4),(a3,b3), (a5,b5)，如图9.63所示。 对于匹配M= (a1,b2),(a2,b4),(a3,b3), (a5,b5)重复上述过 程，已找不到M可扩路。所以M就是最大匹配。 30 31 Hall定理 定理(Hall定理) 设二部图G=中， |V1|V2|. G中存 在从V1到V2的完备匹配当且仅当V1中任意k 个顶 点至少与V2 中的k个顶点相邻(k=1,2,|V1|). 由Hall定理不难证明, 上一页图(2)没有完备匹配. Hall定理中的条件称为“相异性条件” 32 定理 设二部图G=中, 如果存在t1, 使得(1)V1中每 个顶点至少关联 t 条边, (2)而V2中每个顶点至多关联t条 边，则G中存在V1到V2的完备匹配. (充分条件) 证明 如果(1)成立, 则与V1中k (1k|V1|)个顶点相关联的边 的总数, 至少是kt条。根据(2)这些边至少要与V2中k个顶 点相关联。 l这就得出V1中每k (1k|V1|)个顶点, 至少邻接到到V2中k 个顶点。 定理中的条件称为 t 条件. 满足 t 条件的二部图一定满足相 异性条件. 33 因此，当给出一个二分图后。 判断G中存在 从V1到V2的完备匹配方法: 先找出V中的每个结点的度数，令r minvV1d(v)。再找出V中的每个结点的度数， 令RmaxvV2 d(v)。若rR，则问题有解，取 t为r即可。但这只是充分条件，若不满足，则还 要用充要条件来判断。 34 图9.64中的二部图满足t的条件。其中t=3。因此在 图9.64中存在V1到V2的完备匹配。 35 一个应用实例 例 某课题组要从a, b, c, d, e 5人中派3人分别到上海、广州 、香港去开会. 已知a只想去上海，b只想去广州，c, d, e 都表示想去广州或香港. 问该课题组在满足个人要求的 条件下，共有几种派遣方案？ 解 令G=, 其中V1=s, g, x, V2=a, b, c, d, e, E=(u,v) | uV1, vV2, v想去u, 其中s, g, x分别表示上海、广州和香港. G如图所示. G 满足相异性条件，因而可给 出派遣方案，共有9种派遣方案 (请给出这9种方案). 36 练习： 1.某单位按编制有7个空缺：p1, p2, p7.有10个申请者： a1, a2, a10.他们合格的工作岗位依次为：, p1,p5,p6,p2,