第三章 图论

一、判断题

（1）n阶完全图的任意两个不同结点的距离都为1. （ 对 ） （2）图G的两个不同结点vi,vj连接时一定邻接. （ 错 ） （3）图G中连接结点vi,vj的初级通路为vi,vj之间的短程. （ 错 ） （4）在有向图中，结点vi到结点vj的有向短程即为vj到vi的有向短程． （ 错 ） （5）强连通有向图一定是单向连通的． （ 对 ） （6）不论无向图或有向图，初级回路一定是简单回路． （ 对 ） （7）设图G是连通的，则任意指定G的各边方向后所得的有向图是弱连通的．

（ 对 ）

（8）有生成树的无向图是连通的． （对） （9）下图所示的图是欧拉图. （ 错 ）

（10）下图所示的图有哈密尔顿回路. （ 对 ）

二、单项选择题

（1）仅由孤立点组成的图称为 （ A ） A. 零图； B．平凡图； C. 完全图； D. 多重图.

（2）仅由一个孤立点组成的图称为 （ B ） A. 零图； B．平凡图； C.多重图； D. 子图.

（3）在任何图G中必有偶数个 （ B ） A. 度数为偶数的结点； B．度数为奇数的结点； C. 入度为奇数的结点； D. 出度为奇数的结点.

（4）设G为有n个结点的无向完全图，则G的边数为 （ C ） A. n(n?1) B．n(n?1) C. n(n?1)2 D. (n?1)2

（5）在有n个结点的连通图G中，其边数 （ B ） A. 最多n?1条； B．至少n?1条；

9

C. 最多n条； D. 至少n条.

（6）任何无向图G中结点间的连通关系是 （ B ） A. 偏序关系； B．等价关系；

C. 既是偏序关系又是等价关系； D. 既不是偏序关系也不是等价关系.

（7）对于无向图，下列说法中正确的是. （ B ） A．不含平行边及环的图称为完全图

B．任何两个不同结点都有边相连且无平行边及环的图称为完全图 C．具有经过每条边一次且仅一次回路的图称为哈密尔顿图 D．具有经过每个结点一次且仅一次回路的图称为欧拉图

（8）设D是有向图，则D强连通的充分必要条件为. ( C ) A．略去D中各边方向后所得到的无向图是连通的

B．D是单向连通图，且改变它的各边方向后所得到的有向图也是单向连通图 C．D的任意两个不同的结点都可以相互到达 D．D是完全图

（9）对于无向图G，以下结论中不正确的是. （ A ） A．如果G的两个不同结点是连接的，则这两个结点之间有初级回路 B．如果G的两个不同结点是连接的，则这两个结点之间至少有一条短程 C．如果G是树，则任何两个不同结点之间有且仅有一条初级通路

D．如果G是欧拉图，则G有欧拉回路

三、填空题

1. 设树T中有7片树叶，3个3度结点，其余都是4度结点，则T中有 个4度结点. 解 用握手定理和树的性质列出方程求解，设有x个4度结点，

7?9?4x?2(7?3?x?1)，x?1

2.设T??V,E?为树，T中有4度，3度，2度分支点各1个，问T中有 片树叶。 解 与上题解法相同，设有x片树叶，4?3?2?x?2(3?x?1)，x?5 3.n阶完全图的任意两个不同结点的距离都为 ．1 4.图G为n阶无向完全图，则G共有 条边。n(n?1)/2 5.设G为(n,m)图，则图中结点度数的总和为 。2m

6. 图G为欧拉图的充分必要条件是_____________________. G为无奇度结点的连通图 四、解答题

1. 对下图所示的图G，求 （1）G的邻接矩阵A；

（2）G的结点v1,v3之间长度为3的通路； （3）G的连接矩阵C； （4）G的关联矩阵M。

10

v1v2v3v4v5v1?01110?解 （1） A=

v?2?10101??v3?1011?v?14?10100?. ?v5??01100??（2） 因为

??31212???7??13221????????? A2=??22411?, 3

????12121? A=???????????21112????????所以，结点v1,v3之间长度为3的通路共有7条，它们是

v1v3v1v3,v1v2v5v3,v1v2v1v3,v1v4v1v3,v1v3v5v3,v1v3v2v3,v1v3v

4v3.（3）由于图G是连通的，所以

v1v2v3v4v5

v1?11111?v?2?11111?? C=v?311111?. v?4?11111??v5??11111??（4） e1e2e3e4e5e6e7

v1?1011000?v?2?1100001?? M=v?110110?v3?04?0001100?. ?v5??0000011??2. 在下面的有向图D中，回答下列问题

11

???????,??????

（1）写出图D的邻接矩阵A；

（2）写出结点v1到结点v3的长度为3的所有有向通路； （3）写出结点v5到自身的长度为3的所有有向回路；

?0??1解：（1）A??0??0?0??0??02（2）A??0??0?1?0001??0100?0110?

?0001?1010??1010??10??0111??010111? A3??01??1010??10?010101???101??121?121?

?101?121??所以结点v1到结点v3的长度为3的所有有向通路只有一条: v1v5v2v3

（3）结点v5到自身的长度为3的所有有向回路只有一条：v5v2v1v5

3.在下面的无向图G中，回答下列问题

a e

d

b c

（1）写出a,d之间的所有初级通路； （2）写出a,d之间的所有短程，并求d(a,d)； （3）判断无向图G是否为欧拉图并说明理由。 解（1）a,d之间的所有初级通路共有7条，分别为

aed，aecd，aebcd，abed，abcd，abecd，abced （2）a,d之间的长度最短的通路只有1条，即aed，因而它是a,d之间

唯一的短程，d(a,d)?2 （3）由于无向图G中有两个奇度顶点deg(b)?3,deg(c)?3，所以无向图G没有欧

12