(书后作业)集合论与图论

2.在图6.5.5所示的图中,找一条欧拉迹。

3.某展览馆共有36个展室,布置如图6.5.6所示。有阴影的展室陈列实物,没有阴影的展室陈列图片。邻室之间都有门可以通行。有人希望每个展室都参观一次且仅一次,请你替他设计一条参观路线。

P228习题

1.给出一个10个顶点的非哈密顿图的例子,使得每一对不邻接的顶点u和v,均有:degu+degv≥9。

2.试求Kp中不同的哈密顿圈的个数。

3.试证:图6.6.6中的图不是哈密顿图。

4.完全偶图Km,n为哈密顿图的充分必要条件是什么?

5.设G是一个p(p≥3)个顶点的图。u和v是G的两个不邻接的顶点,并且

degu+degv≥p

26

证明:G是哈密顿图当且仅当G+uv是哈密顿图。

10.证明具有奇数顶点的偶图不是哈密顿图。

第七章 树和割集

P243习题

1.分别画出具有4、5、6个顶点的所有树(同构的只算一个)。

2.证明:每个非平凡树是偶图。

3.设G是一棵树且Δ(G)≥k,证明:G中至少有k个度为1的顶点。

27

4.令G是一个有p个顶点,k个支的森林,证明:G有p-k条边。 6.设树T中有2n个度为1的顶点,有3n个度为2的顶点,有n个度为3的顶点,则这棵树有多少个顶点和多少条边?

7一棵树T有n2个度为2的顶点,n3个度为3的顶点,?,nk个度为k的顶点,则T有多少个度为1的顶点?

P252习题

1.设G是一个连通图。试证:G的子图G1是G的某个生成树的子图,当且仅当G1没有圈。

2.证明:连通图的任一条边必是它的某个生成树的一条边。

28

P257习题

1.P个顶点的图中,最多有多少个割点?

2.证明:恰有两个顶点不是割点的连通图是一条路。

3.证明:有一座桥的三次图中至少有10个顶点。

4.设v是图G的一个割点,证明v不是G的补图Gc的割点。

7.有割点的连通图是否一定不是欧拉图?是否一定不是哈密顿图?有桥的连通图是否一定不是欧拉图和哈密顿图。

第八章 联通度和匹配

P264习题

1.设G是一个有p个顶点的图,δ(G)≥((p+k)-1)/2,试证:G是k-连通的。

29

2.若(p,q)图G是k-边连通的,试证:q≥kp/2。

7.设r≥2,G是r正则图且χ(G)=1。证明:λ(G)≥[r/2]。

8.构造一个图G,使得χ(G)=3,λ(G)=4,δ(G)=5。

第九章 平面图和图的着色

P281习题

1.设G?(p,q)是一个具有f个面,k个分支的平面图,则p?q?f?k?1。

30

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4