所以，G1、G2、G3至少有两个是同构的。

20、已知n阶无向简单图G有m条边，试求G的补图G的边数m?。

解：m??n(n?1)?m 221、无向图G如下图

(1)求G的全部点割集与边割集，指出其中的割点和桥； (2) 求G的点连通度k(G)与边连通度?(G)。

ae2be3解：点割集: {a,b},(d)

e1de5ee4c

边割集{e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5}

k(G)=?(G)=1

23、求G的点连通度k(G)、边连通度?(G)与最小度数?(G)。

解：k(G)?2、?(G)?3 、?(G)?4

28、设n阶无向简单图为3-正则图，且边数m与n满足2n-3=m问这样的无向图有几种非同构的情况？

?3n?2m解：? 得n=6,m=9.

?2n?3?m 31、设图G和它的部图G的边数分别为m和m，试确定G的阶数。

25

解：m?m?n(n?1)2 得n??1?1?8(m?m)2 45、有向图D如图

(1)求v2到v5长度为1，2，3，4的通路数；

(2)求v5到v5长度为1，2，3，4的回路数； (3)求D中长度为4的通路数； (4)求D中长度小于或等于4的回路数； (5)写出D的可达矩阵。

v1v4v5v2v3

解：有向图D的邻接矩阵为：

??00001??01010?20?10100????00002??20???0202A???00001?，A2??0010?A3??2020??10100???1?002????02?01010???00?20200???02?0000??00004??215??40400???01?52522??A4???00004??? A?A2?A3?A4???21215?

?40400??522???04040???42?25254??(1)v2到v5长度为1，2，3，4的通路数为0,2,0,0； (2)v5到v5长度为1，2，3，4的回路数为0,0,4,0； (3)D中长度为4的通路数为32； (4)D中长度小于或等于4的回路数10；

26

0?0??0?0??4??

?1??1(4)出D的可达矩阵P??1??1?1?1111??1111?1111?

?1111?1111??第十六章部分课后习题参考答案

1、画出所有5阶和7阶非同构的无向树.

2、一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，问T有几个顶点? 解：设3度分支点x个，则

5?1?3?2?3x?2?(5?3?x?1)，解得x?3

T有11个顶点

3、无向树T有8个树叶，2个3度分支点，其余的分支点都是4度顶点，问T有几个4度分支点？根据T的度数列，请至少画出4棵非同构的无向树。

解：设4度分支点x个，则

8?1?2?3?4x?2?(8?2?x?1)，解得x?2

度数列111111113344

4、棵无向树T有ni (i=2，3，…，k)个i度分支点，其余顶点都是树叶，问T应该有几片树叶? 解：设树叶x片，则

27

ni?i?x?1?2?(ni?x?1)，解得x?(i?2)ni?2 评论：2，3，4题都是用了两个结论,一是握手定理，二是m?n?1 5、n(n≥3)阶无向树T的最大度解：2，n-1

6、若n(n≥3)阶无向树T的最大度解：n-1

7、证明：n(n≥2) 阶无向树不是欧拉图. 证明：无向树没有回路，因而不是欧拉图。 8、证明：n(n≥2) 阶无向树不是哈密顿图. 证明：无向树没有回路，因而不是哈密顿图。 9、证明：任何无向树T都是二部图.

证明：无向树没有回路，因而不存在技术长度的圈，是二部图。 10、什么样的无向树T既是欧拉图，又是哈密顿图? 解：一阶无向树

=2，问T中最长的路径长度为几？ 至少为几？最多为几？

14、设e为无向连通图G中的一条边， e在G的任何生成树中，问e应有什么性质?

解：e是桥

15、设e为无向连通图G中的一条边， e不在G的任何生成树中， 问e应有什么性质?

解：e是环

23、已知n阶m条的无向图 G是k(k≥2)棵树组成的森林，证明：m = n-k.；

证明：数学归纳法。k=1时, m = n-1，结论成立；

设k=t-1(t-1?1)时，结论成立，当k=t时, 无向图 G是t棵树组成的森林,任取两棵树，每棵树任取一个顶点，这两个顶点连线。则所得新图有t-1棵树，所以m = n-（k-1）.

所以原图中m = n-k 得证。

24、在图16.6所示2图中，实边所示的生成子图T是该图的生成树.

(1)指出T的弦，及每条弦对应的基本回路和对应T的基本回路系统.

(2) 指出T的所有树枝， 及每条树枝对应的基本割集和对应T的基本割集系统.

28