内容发布更新时间 : 2025/11/27 15:14:52星期一 下面是文章的全部内容请认真阅读。
第六章 图的基本概念
P206习题
1．画出具有4个顶点的所有无向图(同构的只算一个)。
11个
2．画出具有3个顶点的所有有向图(同构的只算一个)。
16个
3．画出具有4个、6个、8个顶点的三次图。 略
4．某次宴会上，许多人互相握手。证明：握过奇数次手的人数为偶数(注意，0是偶数)。
把实际问题转化为图论问题，然后用握手定理的推论。
P209习题
1．设u与v是图G的两个不同顶点。若u与v间有两条不同的通道(迹)，则G中是否有圈？
若u与v间有两条不同的通道，G中无圈 若u与v间有两条不同的迹，G中有圈
2．证明：一个连通的(p，q)图中q≥p-1。 数学归纳法
3．设G是一个（p，q）图，且q?(p?1)(p?2)/2，则G是连通的。
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。
下图中任意一对不邻接的顶点u和v，均有：degu+degv≥9。
2．试求Kp中不同的哈密顿圈的个数。
(p-1)!/2
4．完全偶图Km，n为哈密顿图的充分必要条件是什么？
10．证明具有奇数顶点的偶图不是哈密顿图。