复旦大学：《离散数学》课程教学讲义（图论）图论习题——考研习题与经典习题

图论习题 考研习题与经典习题 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考研）

解: ∑dev(v,)=2e=2×21=42 12×3+(n-12)×2=42 n=15

 解： 1 ( ) 2 2 21 42 12 3 ( 12) 2 42 1 5 n i i dev v e n n          

3.已知m个结点的简单图G有e条边,各结 点度数为3,2n=e+3。试画出满足条件的 所有不同构的G ■提示:握手定理(西南交大2000考研/北京 大学1990考研) 参考1(2)

 3. 已知n个结点的简单图G有e条边，各结 点度数为3，2n=e+3。试画出满足条件的 所有不同构的G。  提示：握手定理（西南交大2000考研/北京 大学1990考研）  参考1(2)

■解:由握手定理,e=(3n/2);由已知, e=2n2;所以n=6,e=9。 在同构意义下G不是唯一的

 解：由握手定理，e=(3n/2)；由已知， e=2n-2；所以n=6 ，e=9 。  在同构意义下 G不是唯一的

4.设树T有17条边,12片树叶,4个4度 内结点,1个3度内结点,求T的树根的度 数 (提示:握手定理。北大1997考研)

 4. 设树T有17条边，12片树叶，4个4度 内结点，1个3度内结点，求T的树根的度 数。  （提示：握手定理。北大1997考研）

■解:结点数为17+1=18 由握手定理,12*1+4*4+1*3+1*=34

 解：结点数为17+1=18 由握手定理，12*1+4*4+1*3+1* l=34, l=3