《复旦大学计算机科学与工程系吴永辉离散数学图论习题》由会员分享,可在线阅读,更多相关《复旦大学计算机科学与工程系吴永辉离散数学图论习题(70页珍藏版)》请在金锄头文库上搜索。
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解:n3. 已知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*4+1*3+1*l=34, l=3.n5. 设无向树T有3个3度
3、,2个2度结点,其余结点都是树叶,问T有几片树叶?n握手定理n6. 证明:在任何两个或两个以上人的组内,存在两个人在组内有相同个数的朋友。n/*等价于:至少有两个顶点的简单图有两个相同度数的顶点n/*中国科学院自动化所1998考研二、平面图、欧拉公式的应用n1,关于平面图的不等式的证明欧拉公式及其推论的运用n2,非平面图的判定应用库拉托斯基定理n1. 设G是n个结点的连通简单平面图,若n3,则G中必有一个结点度数不超过5。n提示:涉及度数,握手定理;连通平面图,欧拉公式;简单平面图,若n3,欧拉公式的推论n(西南交大1999考研)n证明:握手定理:dev(vi)=2e; 反证:设每个结点的度数
4、超过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, 从而e30。所以矛盾。n4. 证明在简单平面图G中, f 和n分别表示
5、该图的面数和结点数,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是由n个结点,e条边,(2)个连通分支的平面图,G的每个面至少由k(
6、k3)条边围成,则n n证明:设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, v2, , vs,ij,1i,jn,Ek表示完全图的边集。n任取V中两个结点,
7、分两种情况讨论: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)证明: 一个图是自补图, 其对应的完全图的边数必是偶数;n3)是否有3个结点或者6个结点的自补图.n2)证明:如果一个图是自
8、补图,设该图的边数为e,则该图的自补图的边数也为e,所以对应的完全图的边数是2e,为偶数。n3)解:3个结点或者6个结点的完全图的边数分别为3和15,是奇数;所以不存在3个结点或者6个结点的自补图。连通性n证明连通的两种方法: 直接证明/反证法.n证明连通的直接证明方法:任取图中两点,寻找这两点间必定存在路。n证明连通的反证法: 首先假设图不连通,则它具有多个连通分支,然后根据题目条件推出矛盾。推矛盾的过程,通常是将具有多个连通分支的图的边数放到最大的过程(放缩法),即使每个连通分支都是完全图,然后推出边仍然不满足条件。n1. n个结点的简单图G,n2且n奇数,G和G补图中度数为奇数的结点个数
9、是否相等?请证明或给出反例。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为简单图,且 ,则G是连通的。其中m和n分别为该图的边数和顶点数。n/*中国科学院自动化所
10、1998考研n证明方法: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是连通的。n4. 设G=(V, E)是连通简单图,但不是完全图,则存在3个结点u、v和w, 使(u, v), (v, w)E,但(u, w)E。n/*中国科学院计算所1993考研n证明方法:n1)反证法n2)数学归纳法n5. 设G为非平凡有向图,V为G的结点集合,若对V的任一非空子集S,G中起始结点在S中
11、,终止结点在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, u1至少有一条有向边(u, u2)或(u1, u2)。无论哪种情况都有从u到u2的有向道路,因为G中
12、结点数有限,所以通过如上递归地求解,一定有从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考研n9. 能否画一个简单无向连通图,使各结点的度数与下面给出的序列一致?如可能,则画出符合条件的图,所画图是二分图?如不能,则说明原因。n(1)1,2,3,2,
13、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 设图G有n个结点,r个连通分支,则图G的路径矩阵的秩为n-r。n证明:设图G的r个连通分支为G1, G2, , Gr
14、。得分块路径矩阵如下:n因为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线性无关线性无关。 n2 2 向量组的秩向量组的秩n 如果向量组1, 2, ., s中存在r个线性无关的向量,且其中任一个向量可由这r个线性无关的向量线性表示,则数r称为向量组的秩向量组的秩,记作1, 2,
15、 ., 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,导致矛盾。n:设e不是G的割集,若有G的生成树T,则T+e包含回路。则删去e后连通,则与e是G的割集的假设矛盾。n15. 具有(2)棵树的森林,恰巧加多少新边能使森林变树?nn个结点, (
16、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是竞赛图,所以设(u, v)E, 在G中存在顶点w,使得(v, w)E, (u, w)E。所以,根据竞赛图的性质, (w, u)E。则构成有向回路u, v, w, u。导致矛盾。所以命题成立。n证明欧拉
17、图:按照充要条件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