有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