香魂女
去百度文库,查看完整内容>内容来自用户:真燕无畏图论习题考研习题与经典习题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考研)解:dev(v)2e22142i1in123(n12)242n153.已知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