内容发布更新时间 : 2024/12/23 17:38:00星期一 下面是文章的全部内容请认真阅读。
6.在一个有n个人的宴会上,每个人至少有m个朋友(2≤m≤n)。试证:有不少于m+1个人,使得他们按某种方法坐在一张圆桌旁,每人的左、右均是他的朋友。
8.设G是图。证明:若δ(G)≥2,则G包含长至少是δ(G)+1的圈。
P216习题
1.证明:若图G不是连通图,则Gc 是连通图。
2.证明:每一个自补图有4n或4n+1个顶点。
P228习题
1.给出一个10个顶点的非哈密顿图的例子,使得每一对不邻接的顶点u和v,均有:degu+degv≥9。
2.试求Kp中不同的哈密顿圈的个数。
4.完全偶图Km,n为哈密顿图的充分必要条件是什么?
10.证明具有奇数顶点的偶图不是哈密顿图。
16
第七章 树和割集
P243习题
1.分别画出具有4、5、6个顶点的所有树(同构的只算一个)。
2.证明:每个非平凡树是偶图。
3.设G是一棵树且Δ(G)≥k,证明:G中至少有k个度为1的顶点。
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的顶点?
P257习题
1. P个顶点的图中,最多有多少个割点?
3.证明:有一座桥的三次图中至少有10个顶点。
4.设v是图G的一个割点,证明v不是G的补图Gc的割点。
7.有割点的连通图是否一定不是欧拉图?是否一定不是哈密顿图?有桥的连通图是否一定不是欧拉图和哈密顿图。
17
第八章 连通度和匹配
P264习题
1. 设G是一个有p个顶点的图,?(G)?(p?k?1)/2p?2。试证:G是k?连通的,
其中k?p。
6. G是一个三次正则图,试证:k(G) = ?(G)。
r7. 设r?2, G是r-正则图且k(G)=1。试证:?(G)?[]。
2
第九章 平面图和图的着色
P281习题
1.设G?(p,q)是一个具有f个面,k个分支的平面图,则p?q?f?k?1。
18
2. 若G是顶点数p≥11的平面图,试证Gc不是平面图。
4.证明:不存在7条棱的凸多面体。
P294习题
1.设G是一个没有三角形的平面图。应用欧拉公式证明G中有一个顶点v,使得degv ≤3。
2.设G是一个没有三角形的平面图。应用数学归纳法证明G是4-可着色的。
第十章 有向图
P301习题
2.画出具有三个顶点的所有互不同构的有向图的图解。
19
3.具有p个顶点的完全有向图中有多少条弧?
P307习题
1.设D是一个有p个顶点q条弧的有向图。若D是连通的,证明:p-1≤q≤p(p-1)。
2.设D是一个有p个顶点q条弧的强连通的有向图,则q至少是多大?
P307习题
2.有向图D的图解如图10.4.3所示
(1)写出D的邻接矩阵及可达矩阵;(2)写出D关联矩阵。
3.设D为图10.4.4中的有向图,试求v2到其余每个顶点的长≤4的所有通道的条数。
P321习题
1.设T是一个正则m元有序树,它有n0个叶子,T有多有多少条弧?
20