第六章 特殊图论

6.1 二部图（含补充的欧拉图与哈密尔顿图） 一、单项选择题

1．下列说法不对的是（ ）

A．欧拉图可以一笔画成，图要一笔画成则一定要是欧拉图 B．欧拉路经过每条边一次且仅有一次，经过的节点可多次 C．汉密尔顿路经过每个节点一次且仅一次，经过的边可多次 D．当且仅当简单图的闭包是汉密顿图时，这个简单图是汉密顿图 2．下列说法不对的是（ ）

A．无向图为欧拉路则其奇数度节点可以是一个 B．一个图是欧拉图当且仅当它连通且均为偶数度节点

C．当一个图每一对节点的度数之和都大于或等于节点数减一，就有汉密尔顿路 D．若一个图G??V,E?,S?V,S??，G含有汉密尔顿路，则W?G?S??S

3．下列为欧拉图的是( )

4．在下列关于图论的命题中，为真的命题是( ) A．完全二部图Kn, m (n ?1, m ?1)是欧拉图 B．欧拉图一定是哈密尔顿图 C．无向完全图Kn（n?3）都是欧拉图 D．无向完全图Kn（n?3）都是哈密尔顿图

5．在下列关于图论的命题中，为假的命题是( ) A．完全二部图Kn, m (n , m为非零正偶数)是欧拉图 B．哈密尔顿图一定是欧拉图 C．有向完全图Kn（n?2）都是欧拉图

D．无向完全图Kn（n?3且为奇数）都是欧拉图 6．在下列关于图论的命题中，为假的命题是( ) A．n =m且大于1时，完全二部图Kn, m 是哈密尔顿图

B．强连通的有向图都是哈密尔顿图

C．完全二部图Kn, m (n , m为非零正偶数)的欧拉回路含mn条边 D．无向完全图K2n（n?2）至少加n条边才能成为欧拉图

6.2 平面图 一、单项选择题

1．下列说法不对的是（ ）

A．一个有限平面图的次数之和等于边数的两倍

B．平面图G的节点数为v，面数为r，边数为e，则有v-e+r=2 C．G是一个v个节点，e条边的连通简单平面图，则v?3?e?3v?6

D．一个图是平面图，当且仅当他不含有与K3,3或K5在2度节点内同构子图 2．下列各图为平面图的是（ ）

3．设G为任意的连通的平面图，且G有n个顶点，m条边，r个面，则平面图的欧拉公式为( ) A．n – m + r = 2 B．m – n + r = 2 C．n + m – r =2 D．r + n + m = 2

6.3 树与有向树 一、单项选择题

1．下列不能作为一棵树的度数列的一组数是( ) A．1,1,2,2,3,3,4,4 B．1,1,1,1,2,2,3,3 C．1,1,1,2,2,2,2,3 D．1,1,1,1,2,2,2,3,3 2．在下列关于图论的命题中，为假的命题是( ) A．6阶连通无向图至少有6棵生成树

B．n阶m条边的无向连通图，对应它的生成树，至少有m-n+1条基本回路 C．高为h的正则二叉树至少有h+1片树叶

D．波兰符号法的运算规则是每个运算符与它前面紧邻的两个数进行运算 3．下列四个图中与其余三个图不同构的图是( )