洪帆《离散数学基础》(第三版)课后习题答案 下载本文

有S与T至少有一条公共边,

9、试作出一个连通图G,使之满足等式K(G)??(G)??(G)。 解:

上图中由定义可得K(G)??(G)??(G)?2

10、设图G中各结点的度都是3,且结点数n与边数m间有如下关系 2n?3?m 问(1) G中结点数与边数各为多少? (2) 在同构的意义下G是唯一的吗?

解:(1) 由题知该图的总度数为3n,由握手定理知边数与度数的关系为2m?3n,又由2n?3?m,可以解出边数m?9,结点数n?6。

(2) 在同构的意义下图G不唯一,见第一节的例8中图(b)和图(c)。

11、若图G的补图同构于G,则称G为自补图。试证明下图所示的图是自补图。你能否找到其他5结点的自补图。

证明:上图的补图为

图G与其补图的结点集合之间可以建立一一对应关系,因此两个图是同构的。

45

12、已知关于人员a,b,c,d,e,f,g的下述事实:

a说英语;b说英语和西班牙语;c说英语、意大利语和俄语;d说日语和西班

牙语;e说德语和意大利语;f说法语、日语和俄语;g说法语和德语,试问上述7人中是否任意两个人都能交谈?如有必要,可由其余5人中所组成的译员链帮忙?

解:设7个人为7个结点,将两个懂同一种语言的人之间连成一条边,即表示他们能直接交谈。这样就得到一个简单图G,问题就转化为G是否连通,G如下图所示,因为G中任意两个结点是连接的,所以G是连通图。因此,上述7个人中任意两个能交谈。

13、试从下图中找出一条欧拉回路:

解:agbhiljklfejcdecba

14、试在下图中找出一条欧拉路:

解:haghbgfecdfcbah。

15、判断下面4个图哪个是欧拉图,哪个是哈密顿图,在各适当情况下指出欧拉回路和哈密顿环。

46

(a)

解:图(a)是欧拉图,存在一条欧拉回路为abfcbgcdhgfea;图(a)是哈密顿图,存在一个哈密顿环abcdhgfea。

(b)

解:图(b)是欧拉图,具有一条欧拉回路abecfbdca,不是哈密顿图。

(c)

解:图(c)不是欧拉图,是哈密顿图,存在一个哈密顿环abcdhgfea。

(d)

解:图(d)不是欧拉图,也不是哈密顿图。

16、 构造下图中图G的闭包,并判断G是否为哈密顿图?如果不用观察的方法,你能说出你判别的根据嘛?

47

解:先求图G的闭包n=6。因为deg(v5)?deg(v6)?6;deg(v2)?deg(v3)?6,所以连接v5与v6,v2与v3得图G1:

deg(v2)?deg(v4)?6,

因此,连接v2与v4,v1与v5,v4与v6,v1与

在图G1中,因为

deg(v1)?deg(v5)?6,deg(v4)?deg(v6)?6,deg(v1)?deg(v3)?6,v3的图G2:

在图G2 中,因为deg(v1)?deg(v4)?8,因此连接v1与v4得图G3:

且G3是G的闭包,因此G是哈密顿图。

17、某流动售货员居住在a城,打算走销b,c,d城后返回a城。若该四城间的距

48