图论习题考研习题与经典习题

《图论习题考研习题与经典习题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、图论习题考研习题与经典习题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、。在同构的意义下不唯一。2.无向图G有21条边，12个结点度数为3，其余结点度数为2，求G的顶点数。提示：握手定理（北大2001考研）解：ndevv()222142iei1123(n12)242n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.设树

3、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，关于平面图的不等式的证明欧拉公式及

4、其推论的运用2，非平面图的判定应用库拉托斯基定理1.设G是n个结点的连通简单平面图，若n3，则G中必有一个结点度数不超过5。提示：涉及度数，握手定理；连通平面图，欧拉公式；简单平面图，若n3，欧拉公式的推论（西南交大1999考研）证明：握手定理：dev(v)=2e;i反证：设每个结点的度数超过5，即dev(v)6，则2e=dev(v)6n,所以iie3n.由欧拉公式的推论，e3n-6。所以矛盾。2.证明彼得森图是非平面图。提示：要证明一个图不是平面图，首先考虑应用库拉托斯基定理。即在要判

5、别的图中，找出一个K或K的剖分。53,3（西安交通大学1997考研）3.证明小于30条边的简单平面图G中，至少有一个度数小于等于4的结点。证明：不妨设G是连通图。因为e3n-6，假设所有顶点度数大于等于5；由握手定理，dev(v)=2e;i所以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。

6、（西安交通大学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）条边围成，则kn(1)e

7、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划分为{V1,V,……,V}，并设V={u,u,…,u}，V={v,2ni12rj1v,…,v}，ij

8、，1i,jn，E表示完全图的边集。2sk任取V中两个结点，分两种情况讨论：（1）设uiVi,vjVj.(ui,vj)E,则(ui,vj)Ek–E.所以u,v是连通的。即在不同连通分支中的两个ij结点在补图中是连通的。（2）设ui,ujVi,vjVj.由(1)，(ui,vj)Ek–E,(u,v)E–E.所以u,u通过v连