图论习题 考研习题与经典习题 2004-5
图论习题 考研习题与经典习题 2004-5
、握手定理的应用 平面图、欧拉公式的应用 ■三、图的基本概念与应用 四、欧拉图和哈密顿图 五、图的着色
一、握手定理的应用 二、平面图、欧拉公式的应用 三、图的基本概念与应用 四、欧拉图和哈密顿图 五、图的着色
握手定理的应用 1.已知具有n个度数都为3的结点的简单 图G有e条边, (1)若e=3n-6,证明G在同构意义下唯 ,并求e,n (2)若η=6,证明G在同构意义下不唯 ■提示:握手定理(北师大2000考研)
一、握手定理的应用 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。在同 构的意义下不唯
解： （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考研)
2. 无向图G有21条边，12个结点度数为 3，其余结点度数为2，求G的顶点数。 提示：握手定理（北大2001考研）