PPT《图论习题》

图论习题 考研习题与经典习题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.这样的图是完全图K4,所以在同构的意义下唯一.(2)由握手定理,3*6=2e;

e=9.在同构的意义下不唯一. 2. 无向图G有21条边,12个结点度数为3,其余结点度数为2,求G的顶点数.提示:握手定理(北大2001考研) 解: 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(vi)=2e;

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

由握手定理,?dev(vi)=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)条边围成,则 证明:设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划分为{V1, V2, ……, Vn},并设Vi={u1, u2, …, ur},Vj={v1, v2, …, vs},i?j,1?i,j?n,Ek表示完全图的边集.任取V中两个结点,分两种情况讨论:(1)设ui?Vi, vj?Vj. (ui, vj)?E, 则(ui, vj)? Ek CE. 所以ui, vj是连通的.即在不同连通分支中的两个结点在补图中是连通的.(2)设ui, uj?Vi, vj?Vj. 由(1),(ui, vj)? Ek CE, (uj, vj)? Ek CE. 所以ui, uj通过vj连通.即在相同连通分支中的两个结点在补图中是连通的.所以,命题成立. 2. 一个图如果同构于它的补图, 则该图称为自补图.1)试给出一个5个结点的自补图;