图论习题 考研习题与经典习题 2004-5
一 握手定理的应用 二 平面图 欧拉公式的应用 三 图的基本概念与应用 四 欧拉图和哈密顿图 五 图的着色
一 握手定理的应用 1. 已知具有 n 个度数都为 3 的结点的简单图 G 有 e 条边, (1) 若 e=3n-6, 证明 G 在同构意义下唯一, 并求 e,n (2) 若 n=6, 证明 G 在同构意义下不唯一 提示 : 握手定理 ( 北师大 2000 考研 )
解 : (1) 由握手定理,3n=2e; 因为 e=3n-6, 所以 n=4,e=6 这样的图是完全图 K 4, 所以在同构的意义下唯一 (2) 由握手定理,3*6=2e;e=9 在同构的意义下不唯一
2. 无向图 G 有 21 条边,12 个结点度数为 3, 其余结点度数为 2, 求 G 的顶点数 提示 : 握手定理 ( 北大 2001 考研 )
解 : n i 1 dev( v ) 2e 2 21 42 i 12 3 ( n 12) 2 42 n 15
3. 已知 n 个结点的简单图 G 有 e 条边, 各结点度数为 3,2n=e+3 试画出满足条件的所有不同构的 G 提示 : 握手定理 ( 西南交大 2000 考研 / 北京大学 1990 考研 ) 参考 1(2)
解 : 由握手定理,e=(3n/2); 由已知, e=2n-2; 所以 n=6,e=9 在同构意义下 G 不是唯一的
4. 设树 T 有 17 条边,12 片树叶,4 个 4 度内结点,1 个 3 度内结点, 求 T 的树根的度数 ( 提示 : 握手定理 北大 1997 考研 )
解 : 结点数为 17+1=18 由握手定理,12*1+4*4+1*3+1*l=34, l=3.
5. 设无向树 T 有 3 个 3 度,2 个 2 度结点, 其余结点都是树叶, 问 T 有几片树叶? 握手定理
6. 证明 : 在任何两个或两个以上人的组内, 存在两个人在组内有相同个数的朋友 /* 等价于 : 至少有两个顶点的简单图有两个相同度数的顶点 /* 中国科学院自动化所 1998 考研
二 平面图 欧拉公式的应用 1, 关于平面图的不等式的证明欧拉公式及其推论的运用 2, 非平面图的判定应用库拉托斯基定理
1. 设 G 是 n 个结点的连通简单平面图, 若 n 3, 则 G 中必有一个结点度数不超过 5 提示 : 涉及度数, 握手定理 ; 连通平面图, 欧拉公式 ; 简单平面图, 若 n 3, 欧拉公式的推论 ( 西南交大 1999 考研 )
证明 : 握手定理 : dev(v i )=2e; 反证 : 设每个结点的度数超过 5, 即 dev(v i ) 6, 则 2e= dev(v i ) 6n, 所以 e 3n. 由欧拉公式的推论,e 3n-6 所以矛盾
2. 证明彼得森图是非平面图 提示 : 要证明一个图不是平面图, 首先考虑应用库拉托斯基定理 即在要判别的图中, 找出一个 K 5 或 K 3,3 的剖分 ( 西安交通大学 1997 考研 )
3. 证明小于 30 条边的简单平面图 G 中, 至少有一个度数小于等于 4 的结点
证明 : 不妨设 G 是连通图 因为 e 3n-6, 假设所有顶点度数大于等于 5; 由握手定理, dev(v i )=2e; 所以 2e 5n, 则有 n 2e/5 代入 e 3n-6, 则 e 6e/5-6, 从而 e 30 所以矛盾
4. 证明在简单平面图 G 中, f 和 n 分别表示该图的面数和结点数, (1) 如果 n 3, 则 f 2n-4 (2) G 中结点最小的度 (G)=4, 则 G 中至少有 6 个结点的度数小于等于 5 ( 西安交通大学 1996 考研 )
(1) 证明 : 假设图中的边数为 e 由于简单图的每个面至少由 3 条边围成, 因此 3f 2e 由欧拉公式 n- e+f=2, 得 e=n+f-2; 代入 3f 2e 得到 3f 2(n+f-2), 得 f 2n-4
(2) 证明 :( 反证法 ) 假设 G 中至多有 5 个结点的度数小于等于 5 因为 (G)=4, 则 d(v) 5 4+6(n-5) 因为 d(v)=2e, 则 e 3n-5 由 (1),e 3n-6
5. 设 G 是由 n 个结点,e 条边, ( 2) 个连通分支的平面图,G 的每个面至少由 k(k 3) 条边围成, 则 k ( n 1) e k 2
证明 : 设 G 的面数为 f, 各面的度数之和为 T,T=2e 因为 G 的每个面至少由 k 条边围成, 所以 k*f T=2e 由欧拉公式的推广,f= +1+e-n, k*( +1+e-n) 2e. 所以命题成立
三 图的基本概念与应用 1. 补图 2. 连通性
补图 1. 证明无向图 G 是不连通的, 则它的补图是连通的 提示 : 分而治之 ( 西南交大 1999 考研 ) 证明连通的两种方法 : 直接证明, 反证法
证明 : 设 G=(V, E), 根据连通分支将 V 划分为 {V 1, V 2,, V n }, 并设 V i ={u 1, u 2,, u r },V j ={v 1, v 2,, v s },i j,1 i,j n,e k 表示完全图的边集 任取 V 中两个结点, 分两种情况讨论 : (1) 设 u i V i, v j V j. (u i, v j ) E, 则 (u i, v j ) E k E. 所以 u i, v j 是连通的 即在不同连通分支中的两个结点在补图中是连通的 (2) 设 u i, u j V i, v j V j. 由 (1),(u i, v j ) E k E, (u j, v j ) E k E. 所以 u i, u j 通过 v j 连通 即在相同连通分支中的两个结点在补图中是连通的 所以, 命题成立
2. 一个图如果同构于它的补图, 则该图称为自补图. 1) 试给出一个 5 个结点的自补图 ; 2) 证明 : 一个图是自补图, 其对应的完全图的边数必是偶数 ; 3) 是否有 3 个结点或者 6 个结点的自补图.
2) 证明 : 如果一个图是自补图, 设该图的边数为 e, 则该图的自补图的边数也为 e, 所以对应的完全图的边数是 2e, 为偶数
3) 解 :3 个结点或者 6 个结点的完全图的边数分别为 3 和 15, 是奇数 ; 所以不存在 3 个结点或者 6 个结点的自补图
连通性 证明连通的两种方法 : 直接证明 / 反证法. 证明连通的直接证明方法 : 任取图中两点, 寻找这两点间必定存在路 证明连通的反证法 : 首先假设图不连通, 则它具有多个连通分支, 然后根据题目条件推出矛盾 推矛盾的过程, 通常是将具有多个连通分支的图的边数放到最大的过程 ( 放缩法 ), 即使每个连通分支都是完全图, 然后推出边仍然不满足条件
1. n 个结点的简单图 G,n>2 且 n 奇数,G 和 G 补图中度数为奇数的结点个数是否相等? 请证明或给出反例 ( 西南交大 2001 考研 )
解 : 一定相等 因为 n>2 且 n 奇数, 则对于奇数个结点的完全图, 每个结点的度数必为偶数 若 G 中度数为奇数的结点个数是 m, 则 G 的补图中 m 个结点的度数为 ( 偶数 - 奇数 )= 奇数 G 中度数为偶数的结点, 在 G 的补图中这些结点的度数仍为 ( 偶数 - 偶数 )= 偶数 所以命题成立
2. 设无向图 G 有 n 个结点,n 2 证明 : 1) 当 (G) n/2 时,G 是连通图 ; 2) 当 (G) (1/2)(n+k-1) 时,G 是 k- 连通图, 其中 1 k n-1 ( 北京大学 1994 年考研 )
2 3. 若 G 为简单图, 且 m Cn 1, 则 G 是连通的 其中 m 和 n 分别为该图的边数和顶点数 /* 中国科学院自动化所 1998 考研
证明方法 : 1) 反证法 ( 简捷 ) 2) 数学归纳法 : 对顶点数进行数学归纳
反证法 : 证明 : 假设 G 不是连通的, 则 G 至少存在两个连通分支 设 G 有两个连通分支 C 1 和 C 2, 则 G 的最大可能的边数 m=x(x- 1)/2+(n-x)(n-x-1)/2, 其中 1 x n-1; 所 2 以 m 的最大 C n 1 所以导致矛盾, 则 G 是连通的
4. 设 G=(V, E) 是连通简单图, 但不是完全图, 则存在 3 个结点 u v 和 w, 使 (u, v), (v, w) E, 但 (u, w) E /* 中国科学院计算所 1993 考研
证明方法 : 1) 反证法 2) 数学归纳法
5. 设 G 为非平凡有向图,V 为 G 的结点集合, 若对 V 的任一非空子集 S,G 中起始结点在 S 中, 终止结点在 V-S 中的有向边至少有 k 条, 则称 G 是 k 边连通的 证明 : 非平凡有向图是强连通的充要条件为它是一边连通的 /* 中国科学院计算所 1999 考研
证明 : /* 必要性证明 */ 因为设 G 为强连通的, 假设从 S 到 V-S 没有有向边, 则 S 中的任一顶点 u 到 V-S 中的任一顶点 v 均没有有向道路, 从而与 G 为强连通的相矛盾 所以从 S 到 V-S 至少有一条有向边, 即 G 为一边连通的
/* 充分性证明 */ 设 G 为一边连通的, 对任意的 u, v V, 则 {u} 到 V(G-u) 至少有一条边, 设为 (u, u 1 ), 而 {u, u 1 } 到 V-{u, u 1 } 至少有一条有向边 (u, u 2 ) 或 (u 1, u 2 ) 无论哪种情况都有从 u 到 u 2 的有向道路, 因为 G 中结点数有限, 所以通过如上递归地求解, 一定有从 u 到 v 的有向道路 所以 G 为强连通的
6. 设简单平面图 G 中顶点数 n=7, 边数 e=15, 证明 G 是连通的 提示 : 反证
7. 简单图 G 由图 H 和两个孤立点组成, 图 H 不含孤立点,Ğ 为平面图, 证明 H 为连通图 ( 中国科学院软件所 1994 考研 )
2 8. 若 G 为简单图, 且 m Cn 1, 则 G 是连通的. 其中 m 和 n 分别为该图的边数和顶点数. 给出一个有 n 个结点而不连通的简单图, 2 其边数恰好为 C. n 1 /* 华中科技大学 2000 考研
9. 能否画一个简单无向连通图, 使各结点的度数与下面给出的序列一致? 如可能, 则画出符合条件的图, 所画图是二分图? 如不能, 则说明原因 (1)1,2,3,2,1,1 (2)1,1,2,3,2,2 (3)1,2,3,4,5,5 (4)2,2,2,3,3,4 ( 西南交大 1995 考研 )
(1) V 1 ={a, c, e}, V 2 ={b, d, f}. (2) 不可能画出图 ( 顶点度数之和为偶数 ) (3) 不可能画出图和二分图 由于有两个结点的度数为 5, 则该两个结点的度数必与其余 5 个结点有边相连 ( 因为是简单图 ), 所以其余 4 个结点度数至少为 2, 但有一个结点的度数为 1 (4) (1, 6, 4, 5, 6, 1), 回路长度为奇数, 所以不是二分图
10 设图 G 有 n 个结点,r 个连通分支, 则图 G 的路径矩阵的秩为 n-r
证明 : 设图 G 的 r 个连通分支为 G 1, G 2,, G r 得分块路径矩阵如下 : PG ( ) PG ( ) 0... 0 1 0 PG ( )... 0 2......... 0 0 0... PG ( ) r
因为 G i 是连通图,G i 的秩是连通分支 G i 的结点个数 -1, 所以 rank(g)= rank(g i )=n-r
本题背景 : 1 线性相关 / 线性无关 如果对 m 个向量 1, 2,., m F m, 有 m 个不全为零的数 k 1, k 2,., k m F, 使 k 1 1 +k 2 2 +.+k m m =0 n 成立, 则称 1, 2,., m 线性相关 ; 否则, 称 1, 2,., m 线性无关
2 向量组的秩 如果向量组 1, 2,., s 中存在 r 个线性无关的向量, 且其中任一个向量可由这 r 个线性无关的向量线性表示, 则数 r 称为向量组的秩, 记作 { 1, 2,., s }=r
9. 若图 G=(V, E) 是连通图, 且 e E, 证明 : (1)e 属于每一棵生成树的充要条件是 {e} 为 G 的割集 ; (2)e 不属于 G 的任何一棵生成树的充要条件是 e 为 G 中的环 提示 : 反证
分析 : (1) e 属于每一棵生成树, 要证 G 删去 e 后必不连通, 否则矛盾 (2)
证明 :(1) : e 属于每一棵生成树, 若 {e} 不是 G 的割集,G-e 连通, 则 G-e 中必存在生成树 T, 因为 T 也是 G 的生成树, 但 T 不包含 e, 导致矛盾 : 设 {e} 不是 G 的割集, 若有 G 的生成树 T, 则 T+e 包含回路 则删去 e 后连通, 则与 {e} 是 G 的割集的假设矛盾
15. 具有 ( 2) 棵树的森林, 恰巧加多少新边能使森林变树?
n 个结点, ( 2) 棵树,n- 条边 n 个结点的树,n-1 条边 (n-1)-(n- )= -1
16. 已知 n 个结点 (n 2) 的简单无向图 G 具有 n-1 条边,G 是树吗? 提示 : 定义 7.1 定理 7.1
四 欧拉图和哈密顿图 1 证明 : 在无有向回路的竞赛图 G=(V, E) 中, 对任意的 u,v V, d + (u) d + (v) /* 中国科学院软件所 */ /* 反证 */
证明 : 假设 G 中存在两个顶点 u, v, d + (u) =d + (v) 因为 G 是竞赛图, 所以设 (u, v) E, 在 G 中存在顶点 w, 使得 (v, w) E, (u, w) E 所以, 根据竞赛图的性质, (w, u) E 则构成有向回路 u, v, w, u 导致矛盾 所以命题成立
证明欧拉图 : 按照充要条件
证明哈密顿图 : 抽象图, 充分条件或必要条件 ; 具体图, 比较困难
五 图的着色 四色猜想和五色定理相对平面图而言 上海交通大学 4 次考到五色定理的证明 顶点着色
1 图 G(V, E) 称为 k 色临界图是指, 对任意 v V, 均有 (G-v)< (G)=k 证明 : 在 k 色临界图中, (G) k-1, 其中 (G)=min{d(v) v V} 中国科学院软件所 1995
证明 :/* 反证法 */ 若在图 G 中存在 v 0 V,d(v 0 ) k-2 因为 G 是 k 色临界图, 所以对 G-v 0 可作 k-1 正常着色 又因为在 G 中与 v 0 邻接的结点个数 k-2, 所以在 G-v 0 中对这些邻接点至多用 k-2 种颜色, 即至少还有 k-1 种颜色中的一种未使用 在 G 中用这种颜色对 v 0 着色, 其他结点着色与 G-v 0 相同, 所以得到 G 的 k-1 正常着色, 与 (G)=k 矛盾
2 对于图 G, (G)=k, 则 G 中至少有 k(k- 1)/2 条边 中国科学院计算所 1998