《图论》5-8章-习题课.ppt

《《图论》5-8章-习题课.ppt》由会员分享，可在线阅读，更多相关《《图论》5-8章-习题课.ppt（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、11. 平面图 G 的对偶 G* 同构于 G 时，称 G 为自对偶图。证明：G= (V, E) 为自对偶图时，有 m = 2n 2。这里 n=|V|，m = |E|。 图论4-8 章 习题课 第一页，编辑于星期六：八点 分。21. 平面图 G 的对偶 G* 同构于 G 时，称 G 为自对偶图。证明：G= (V, E) 为自对偶图时，有 m = 2n 2。这里 n=|V|，m = |E|。 提示：提示：欧拉公式：n m + d = 2对偶性：d = n*同构性：n* = n 联立解得。图论4-8 章 习题课 第二页，编辑于星期六：八点 分。32. 证明：Perterson 图不是平面图。 图论4

2、-8 章 习题课 第三页，编辑于星期六：八点 分。42. 证明：Perterson 图不是平面图。 图论4-8 章 习题课 证一证一：反证。设其为平面图，则 n m + d = 2。每个面至少有 5条边，则 2m 5d ，或 d 2/5 m。故 n m + 2/5 m 2，即 m 5/3 (n 2)。将 n = 10, m = 15 代入得 15 5/3 8，矛盾。 第四页，编辑于星期六：八点 分。5图论4-8 章 习题课 2. 证明：Perterson 图不是平面图。证二：证二：反证。设其为平面图。由图示，每个面至少有5条边，即 l=5，代入：得： 3m 5(n2)将 n =10, m =1

3、5 代入得 45 40，矛盾。 (2)2nlml第五页，编辑于星期六：八点 分。63. 设 G 是边数 m 小于30的简单平面图，证明 G 中存在节点 v，deg(v)4。 图论4-8 章 习题课 第六页，编辑于星期六：八点 分。73. 设 G 是边数 m 小于30的简单平面图，证明 G 中存在节点 v，deg(v)4。证明：证明：不妨设 G 是连通的。若 G 是一棵树，结论显然成立。设G 中有回路。反证：若 G 中所有结点的度均大于等于5，则 2m 5n。联立 m 3n6 得 m 30，矛盾。 图论4-8 章 习题课 第七页，编辑于星期六：八点 分。84. 设简单平面图 G 中结点数 n =

4、7，边数 m =15。证明 G 是连通的。 图论4-8 章 习题课 第八页，编辑于星期六：八点 分。94. 设简单平面图 G 中结点数 n =7，边数 m =15。证明 G 是连通的。证明：证明：反证。设 G 不连通，有 k 个连通分支 G1, G2, , Gk， Gi对应结点数和边数分别为 ni 和 mi。不存在 1 阶的连通分支，否则 G 只能由平凡图加上 K6 才能构成 m = 15，而 K6是不可平面的。也不存在 2 阶的连通分支 K2，否则 G 最多由 K2 加上 K5 也只能构成 m = 10 15。因此任意连通分支的阶必大于等于3。由 mi 3ni6，对全部连通分支求和得 m3n

5、6k。将 n = 7, m = 15 代入得 k 1。 图论4-8 章 习题课 第九页，编辑于星期六：八点 分。105. 将平面分成 x 个区域，且使得任意两个区域都相邻，问 x 最大是多少？ 图论4-8 章 习题课 第十页，编辑于星期六：八点 分。115. 将平面分成 x 个区域，且使得任意两个区域都相邻，问 x 最大是多少？证明：上述分法得到平面图 G，设其对偶为 G*。可知 G* 的任意两个顶点都邻接，即 G* 是一个完全图。又 G* 是一个平面图，故最多 G* 为 K4。即 x 的最大值是4。 图论4-8 章 习题课 第十一页，编辑于星期六：八点 分。126. 设 G 是连通的平面图，

6、证明：G 为二部图当且仅当 G 的对偶图为欧拉图。 图论4-8 章 习题课 第十二页，编辑于星期六：八点 分。136. 设 G 是连通的平面图，证明：G 为二部图当且仅当 G 的对偶图为欧拉图。证明：设 G 的对偶为 G*，则 G* 是连通的。必要性： G 为二部图，则 G 中无奇数长度回路，故 G* 中无奇数度顶点，因此 G* 是一个欧拉图。充分性：G* 是一个欧拉图，则 G* 中无奇数度顶点，故 G 中无奇数长度回路，因此 G 为一个二部图。 图论4-8 章 习题课 第十三页，编辑于星期六：八点 分。147. 证明：k 色图 G 中至少有 k(k1)/2 条边。图论4-8 章 习题课 第十

7、四页，编辑于星期六：八点 分。157. 证明：k 色图G中至少有 k(k1)/2 条边。证明：按 G 的一个 k 正常着色方案划分 G 的顶点为 k 个集合 V1, V2, , Vk。则任给 i, j，ij，在 Vi 和 Vj 之间必有边相连，否则给 Vi 和 Vj 的顶点染上相同颜色，可以得到 G的一个 k1 正常着色方案，与 G 的色数是 k 矛盾。将 Vi 用一个结点 ui 取代，得到一个 k 阶完全图，其边数恰为 k(k1)/2。 图论4-8 章 习题课 第十五页，编辑于星期六：八点 分。168. 色数的图解求法：如图，求其色数 (G)。 图论4-8 章 习题课 第十六页，编辑于星期六

8、：八点 分。17图论4-8 章 习题课 (G) = min(K5), (K4), (K3) = (K3) =3 K5 K4 K4 K3第十七页，编辑于星期六：八点 分。189-1.色数多项式的图解求法：加边法。如图，求其色数多项式。图论4-8 章 习题课 第十八页，编辑于星期六：八点 分。19图论4-8 章 习题课 PG(k) = PK4(k)+ 2PK3(k)+ PK2(k) = k(k1)(k2)(k3)+2k(k1)(k2)+k(k1) = k44k3+6k23k第十九页，编辑于星期六：八点 分。209-2. 色数多项式的图解求法：减边法。如图，求其色数多项式。图论4-8 章 习题课 第

9、二十页，编辑于星期六：八点 分。21图论4-8 章 习题课 PG(k) = k43k3+3k2k第二十一页，编辑于星期六：八点 分。2210. 如图是一份PCB 板设计图，孔位 x1 x9, y1 y3 已经确定，联结边（导通）e1 e9。问至少要分成几层板才能实现。 图论4-8 章 习题课 x1x2x3x4x5y1y2y3x6x7x8x9e1e2e3e4e5e6e7e8e9第二十二页，编辑于星期六：八点 分。2310. 解：PCB 要求将设计图P中发生交叉的边分配到不同的层面。若将同层的边染以相同颜色， 问题转化为求最少颜色数。构造图 G 如下：以顶点 vi 标示图 P 的边 ei，G 的两

10、个顶点 vi , vj 邻接当且仅当 P 中的两条边 ei , ej。图论4-8 章 习题课 v1v2v3v4v5v6v7v8v9第二十三页，编辑于星期六：八点 分。2410. 易得G的色数为3，即至少需要3层板。给出G的一种染色方案，相应可以得到P的一种铺板方案。图论4-8 章 习题课 v1v2v3v4v5v6v7v8v9第二十四页，编辑于星期六：八点 分。2510. P的一种3层铺板方案。 图论4-8 章 习题课 x1x2x3x4x5y1y2y3x6x7x8x9e1e2e5e7e9x1x2x3x4x5y1y2y3x6x7x8x9e3e4e8x1x2x3x4x5y1y2y3x6x7x8x9e

11、6第二十五页，编辑于星期六：八点 分。2611. 点独立集与点覆盖的相关关系 。定理定理6-3-2 设图 G = (V, E) 无孤立点，CV，则：C 为 G 的一个点覆盖 V-C 为 G 的一个独立集。推论推论1 G 如上所述，CV，则：C 为 G 的一个极小点覆盖 V-C 是 G 的一个极大独立集。推论推论2 G 如上所述，n =|V|，则 0 + 0 = n 。图论4-8 章 习题课 第二十六页，编辑于星期六：八点 分。2712. 匹配与边覆盖的相关关系 。 定理定理8-1-1 设 M 是 G=(V, E) 的一个匹配，n=|V|，且 G 中无孤立点： (1) 设 M 为 G 的一个最大

12、匹配，对 G 中每一个 M不饱和顶点取一条关联边，组成边集 N，则 W=M N 为 G 的一个最小边覆盖。 (2) 设 W1为 G 的一个最小边覆盖，将 W1中每相邻的边移去一条，设移去的边构成边集 N1，则 M1=W1N1 为 G 的一个最大匹配。 (3) 1(G) + 1(G) = n 。图论4-8 章 习题课 第二十七页，编辑于星期六：八点 分。2813. Hall 婚姻定理。定理定理8-2-2 二部图 G=(X, Y, E)，|X| |Y|，存在完全匹配的充要条件充要条件是：对任意 AX，有 | (A)| |A|。(A) 为 A 在 Y中的像：(A)=y|yYx(xA(x, y)E )

13、。 推论推论 设有二部图 G=(X, Y, E)，若对每个结点 xX，都有deg(x)k；对每个结点 yY，都有 deg(y)k，则 G 中存在从 X 到 Y 的完全匹配。 图论4-8 章 习题课 第二十八页，编辑于星期六：八点 分。2914. 匈牙利算法求二部图的可增广道：如图，设初始匹配 (x2, y2), (x3, y3), (x5, y5)，求其最大匹配。 图论4-8 章 习题课 x1x2x3x4x5y1y2y3y4y5第二十九页，编辑于星期六：八点 分。3014. 解：解：图论4-8 章 习题课 x1x2x3x4x5y1y2y3y4y5 (1) U=x1，V=。 (U)=y2, y3

14、y2(U)V，且有标记：(x2, y2)M。U=x1, x2，V=y2。(U)=y2, y3 , y1 , y4 , y5y1(U)V，且未标记，故存在从 x1 到 y1 的可增广道。找到一条可增广道 P = (x1, y2 , x2 , y1)。将 x1、y1 标记 I。M =(x1, y2), (x2, y1), (x3, y3), (x5, y5)。第三十页，编辑于星期六：八点 分。3115. 流割定理。 定理定理8-5-1 设网络 N 中一个从 z 到 z 的流 f 的流量为 w, (S, S) 为任意一个割切，则 w = f(S, S) f(S, S) 推论推论1 对网络 N中任意流量 w 和割切 (S, S)，有 w c(S, S)。 推论推论2 最大流量不大于最小割切容量，即： wmax minc(S, S)。 定理定理8-6-2 在任何运输网络中，流的最大值等于最小的割切容量，即 wmax = min c(S, S) 图论4-8 章 习题课 第三十一页，编辑于星期六：八点 分。3216. 2F标号法。 求下图所示网络的最大流。图论4-8 章 习题课 容量容量 流量流量abdczz 15, 04, 012, 05, 03, 010, 07, 010, 0第三十二页，编辑于星期六：八点 分。