图论习题课件.ppt

1、图论习题考研习题与经典习题2004-5n一、握手定理的应用n二、平面图、欧拉公式的应用n三、图的基本概念与应用n四、欧拉图和哈密顿图n五、图的着色一、握手定理的应用n1. 已知具有n个度数都为3的结点的简单图G有e条边，n（1）若e=3n-6，证明G在同构意义下唯一，并求e，n。n（2）若n=6，证明G在同构意义下不唯一。n提示：握手定理（北师大2000考研）n解：n（1）由握手定理，3n=2e; 因为e=3n-6，所以n=4，e=6。这样的图是完全图K4，所以在同构的意义下唯一。n（2）由握手定理，3*6=2e；e=9。在同构的意义下不唯一。n2. 无向图G有21条边，12个结点度数为3，其

2、余结点度数为2，求G的顶点数。n提示：握手定理（北大2001考研）n解：1()222142123(12)24215niidev vennn3. 已知n个结点的简单图G有e条边，各结点度数为3，2n=e+3。试画出满足条件的所有不同构的G。n提示：握手定理（西南交大2000考研/北京大学1990考研）n参考1(2)n解：由握手定理，e=(3n/2)；由已知，e=2n-2；所以n=6，e=9。n在同构意义下G不是唯一的。n4. 设树T有17条边，12片树叶，4个4度内结点，1个3度内结点，求T的树根的度数。n（提示：握手定理。北大1997考研）n解：结点数为17+1=18由握手定理，12*1+4*

3、4+1*3+1*l=34, l=3.n5. 设无向树T有3个3度，2个2度结点，其余结点都是树叶，问T有几片树叶？n握手定理n6. 证明：在任何两个或两个以上人的组内，存在两个人在组内有相同个数的朋友。n/*等价于：至少有两个顶点的简单图有两个相同度数的顶点n/*中国科学院自动化所1998考研二、平面图、欧拉公式的应用n1，关于平面图的不等式的证明欧拉公式及其推论的运用n2，非平面图的判定应用库拉托斯基定理n1. 设G是n个结点的连通简单平面图，若n3，则G中必有一个结点度数不超过5。n提示：涉及度数，握手定理；连通平面图，欧拉公式；简单平面图，若n3，欧拉公式的推论n（西南交大1999考研）

4、n证明：握手定理：dev(vi)=2e; 反证：设每个结点的度数超过5，即dev(vi)6，则2e=dev(vi)6n, 所以e3n.由欧拉公式的推论，e3n-6。所以矛盾。n2. 证明彼得森图是非平面图。n提示：要证明一个图不是平面图，首先考虑应用库拉托斯基定理。即在要判别的图中，找出一个K5或K3,3的剖分。n（西安交通大学1997考研）n3. 证明小于30条边的简单平面图G中，至少有一个度数小于等于4的结点。n证明：不妨设G是连通图。 因为e3n-6，假设所有顶点度数大于等于5；由握手定理，dev(vi)=2e; 所以2e5n，则有n2e/5。 代入e3n-6，则e6e/5-6, 从而e

5、30。所以矛盾。n4. 证明在简单平面图G中， f 和n分别表示该图的面数和结点数，n(1) 如果n3，则f 2n-4。n(2) G中结点最小的度(G)=4，则G中至少有6个结点的度数小于等于5。n（西安交通大学1996考研）n（1）证明：假设图中的边数为e。由于简单图的每个面至少由3条边围成，因此3f 2e。由欧拉公式n-e+f=2，得e=n+f-2；代入3f 2e得到3f 2(n+f-2)，得f 2n-4。n（2）证明：（反证法）n 假设G中至多有5个结点的度数小于等于5。因为(G)=4，则d(v)54+6(n-5)。因为d(v)=2e，则e3n-5。由(1)，e3n-6。n5. 设G是由

6、n个结点，e条边，(2)个连通分支的平面图，G的每个面至少由k（k3）条边围成，则n (1)2k nekn证明：设G的面数为f，各面的度数之和为T，T=2e。因为G的每个面至少由k条边围成，所以k*fT=2e。由欧拉公式的推广，f=+1+e-n, k*( +1+e-n)2e. n所以命题成立。三、图的基本概念与应用n1. 补图n2. 连通性补图n1. 证明无向图G是不连通的，则它的补图是连通的。n提示：分而治之（西南交大1999考研）n证明连通的两种方法：直接证明，反证法n证明：设G=(V, E), 根据连通分支将V划分为V1, V2, , Vn，并设Vi=u1, u2, , ur，Vj=v1

7、, v2, , vs，ij，1i,jn，Ek表示完全图的边集。n任取V中两个结点，分两种情况讨论：n（1）设uiVi, vjVj. (ui, vj)E, 则(ui, vj) Ek E. 所以ui, vj是连通的。即在不同连通分支中的两个结点在补图中是连通的。n（2）设ui, ujVi, vjVj. 由(1)，(ui, vj) Ek E, (uj, vj) Ek E. 所以ui, uj通过vj连通。即在相同连通分支中的两个结点在补图中是连通的。n所以，命题成立。n2. 一个图如果同构于它的补图, 则该图称为自补图.n1)试给出一个5个结点的自补图;n2)证明: 一个图是自补图, 其对应的完全图的

8、边数必是偶数;n3)是否有3个结点或者6个结点的自补图.n2)证明：如果一个图是自补图，设该图的边数为e，则该图的自补图的边数也为e，所以对应的完全图的边数是2e，为偶数。n3)解：3个结点或者6个结点的完全图的边数分别为3和15，是奇数；所以不存在3个结点或者6个结点的自补图。连通性n证明连通的两种方法: 直接证明/反证法.n证明连通的直接证明方法：任取图中两点，寻找这两点间必定存在路。n证明连通的反证法: 首先假设图不连通，则它具有多个连通分支，然后根据题目条件推出矛盾。推矛盾的过程，通常是将具有多个连通分支的图的边数放到最大的过程（放缩法），即使每个连通分支都是完全图，然后推出边仍然不满

9、足条件。n1. n个结点的简单图G，n2且n奇数，G和G补图中度数为奇数的结点个数是否相等？请证明或给出反例。n（西南交大2001考研）n解：一定相等。n因为n2且n奇数，则对于奇数个结点的完全图，每个结点的度数必为偶数。若G中度数为奇数的结点个数是m，则G的补图中m个结点的度数为（偶数-奇数）=奇数。 G中度数为偶数的结点，在G的补图中这些结点的度数仍为（偶数-偶数）=偶数。n所以命题成立。n2. 设无向图G有n个结点，n2。证明：n1）当(G)n/2时，G是连通图；n2）当(G)(1/2)(n+k-1)时，G是k-连通图，其中1 k n-1。n(北京大学1994年考研)n3. 若G为简单图

10、，且 ，则G是连通的。其中m和n分别为该图的边数和顶点数。n/*中国科学院自动化所1998考研21nmCn证明方法：n1）反证法（简捷）n2）数学归纳法：对顶点数进行数学归纳n反证法：n证明：假设G不是连通的，则G至少存在两个连通分支。设G有两个连通分支C1和C2，则G的最大可能的边数m=x(x-1)/2+(n-x)(n-x-1)/2，其中1xn-1；所以m的最大 所以导致矛盾，则G是连通的。21nCn4. 设G=(V, E)是连通简单图，但不是完全图，则存在3个结点u、v和w, 使(u, v), (v, w)E，但(u, w)E。n/*中国科学院计算所1993考研n证明方法：n1）反证法n2

11、）数学归纳法n5. 设G为非平凡有向图，V为G的结点集合，若对V的任一非空子集S，G中起始结点在S中，终止结点在V-S中的有向边至少有k条，则称G是k边连通的。n证明：非平凡有向图是强连通的充要条件为它是一边连通的。n/*中国科学院计算所1999考研n证明：n/*必要性证明*/n因为设G为强连通的，假设从S到V-S没有有向边，则S中的任一顶点u到V-S中的任一顶点v均没有有向道路，从而与G为强连通的相矛盾。所以从S到V-S至少有一条有向边，即G为一边连通的。n/*充分性证明*/n设G为一边连通的，对任意的u, vV, 则u到V(G-u)至少有一条边，设为(u, u1)，而u, u1到V-u,

12、u1至少有一条有向边(u, u2)或(u1, u2)。无论哪种情况都有从u到u2的有向道路，因为G中结点数有限，所以通过如上递归地求解，一定有从u到v的有向道路。所以G为强连通的。n6. 设简单平面图G中顶点数n=7，边数e=15，证明G是连通的。n提示：反证n7.简单图G由图H和两个孤立点组成，图H不含孤立点，为平面图，证明H为连通图。n（中国科学院软件所1994考研）n8. 若G为简单图, 且 , 则G是连通的. 其中m和n分别为该图的边数和顶点数. 给出一个有n个结点而不连通的简单图,其边数恰好为 .n/*华中科技大学2000考研21nmC21nCn9. 能否画一个简单无向连通图，使各结

13、点的度数与下面给出的序列一致？如可能，则画出符合条件的图，所画图是二分图？如不能，则说明原因。n（1）1，2，3，2，1，1n（2）1，1，2，3，2，2n（3）1，2，3，4，5，5n（4）2，2，2，3，3，4n（西南交大1995考研）n(1) V1=a, c, e, V2=b, d, f.n(2) 不可能画出图。(顶点度数之和为偶数)n(3) 不可能画出图和二分图。由于有两个结点的度数为5，则该两个结点的度数必与其余5个结点有边相连（因为是简单图），所以其余4个结点度数至少为2，但有一个结点的度数为1。n(4) (1, 6, 4, 5, 6, 1)，回路长度为奇数，所以不是二分图。n10

14、 设图G有n个结点，r个连通分支，则图G的路径矩阵的秩为n-r。n证明：设图G的r个连通分支为G1, G2, , Gr。得分块路径矩阵如下：12()0.00() .0( ).000.()rP GP GP GP Gn因为Gi是连通图，Gi的秩是连通分支Gi的结点个数-1，所以rank(G)=rank(Gi)=n-r。n本题背景：本题背景：n1 线性相关线性相关/线性无关线性无关 n 如果对m个向量1, 2, ., mFm，有m个不全为零的数k1, k2, ., kmF，使k11+k22 +.+kmm=0n成立，则称1, 2, ., m线性相关线性相关；否则，称1, 2, ., m线性无关线性无关

15、。 n2 2 向量组的秩向量组的秩n 如果向量组1, 2, ., s中存在r个线性无关的向量，且其中任一个向量可由这r个线性无关的向量线性表示，则数r称为向量组的秩向量组的秩，记作1, 2, ., s =r。 n9. 若图G=(V, E)是连通图，且eE，证明：n(1)e属于每一棵生成树的充要条件是e为G的割集；n(2)e不属于G的任何一棵生成树的充要条件是e为G中的环。n提示：反证n分析：n(1) e属于每一棵生成树, 要证G删去e后必不连通，否则矛盾。n(2)n证明：（1）n： e属于每一棵生成树, 若e不是G的割集，G-e连通，则G-e中必存在生成树T，因为T也是G的生成树，但T不包含e

16、，导致矛盾。n：设e不是G的割集，若有G的生成树T，则T+e包含回路。则删去e后连通，则与e是G的割集的假设矛盾。n15. 具有(2)棵树的森林，恰巧加多少新边能使森林变树？nn个结点， (2)棵树，n-条边nn个结点的树，n-1条边n（n-1）-（n-）=-1n16. 已知n个结点（n2）的简单无向图G具有n-1条边，G是树吗？n提示：定义7.1 定理7.1四、欧拉图和哈密顿图n1 证明：在无有向回路的竞赛图G=(V, E)中，对任意的u,vV, d+(u)d+(v)。n/*中国科学院软件所*/n/*反证*/n证明：假设G中存在两个顶点u, v， d+(u) =d+(v)。因为G是竞赛图，所

17、以设(u, v)E, 在G中存在顶点w，使得(v, w)E, (u, w)E。所以，根据竞赛图的性质， (w, u)E。则构成有向回路u, v, w, u。导致矛盾。所以命题成立。n证明欧拉图：按照充要条件n证明哈密顿图：抽象图，充分条件或必要条件；具体图，比较困难五、图的着色n四色猜想和五色定理相对平面图而言n上海交通大学4次考到五色定理的证明n顶点着色n1 图G(V, E)称为k色临界图是指，对任意vV，均有 (G-v) (G)=k。n证明：在k色临界图中，(G)k-1，其中(G)=mind(v)|vV。n中国科学院软件所1995n证明：/*反证法*/n 若在图G中存在v0V，d(v0)k-2。因为G是k色临界图，所以对G-v0可作k-1正常着色。又因为在G中与v0邻接的结点个数k-2，所以在G-v0中对这些邻接点至多用k-2种颜色，即至少还有k-1种颜色中的一种未使用。在G中用这种颜色对v0着色，其他结点着色与G-v0相同，所以得到G的k-1正常着色，与 (G)=k矛盾。n2 对于图G， (G)=k，则G中至少有k(k-1)/2条边。n中国科学院计算所1998