第六?/p>
图的基本概念
206
P
习题
1
.画出具?/p>
4
个顶点的所有无向图
(
同构的只算一?/p>
)
?/p>
11
?/p>
2
.画出具?/p>
3
个顶点的所有有向图
(
同构的只算一?/p>
)
?/p>
16
?/p>
3
.画出具?/p>
4
个?/p>
6
个?/p>
8
个顶点的三次图?/p>
?/p>
4
.某次宴会上,许多人互相握手。证明:握过奇数次手的人数为偶数
(
注意?/p>
0
是偶?/p>
)
?/p>
把实际问题转化为图论问题,然后用握手定理的推论?/p>
209
P
习题
1
.设
u
?/p>
v
是图
G
的两个不同顶点。若
u
?/p>
v
间有两条不同的通道
(
?/p>
)
,则
G
中是否有圈?
?/p>
u
?/p>
v
间有两条不同的通道?/p>
G
中无?/p>
?/p>
u
?/p>
v
间有两条不同的迹?/p>
G
中有?/p>
2
.证明:一个连通的
(p
?/p>
q)
图中
q
?/p>
p-1
?/p>
数学归纳?/p>
3
.设
G
是一个(
p
?/p>
q
)图,且
2
/
)
2
)(
1
(
?/p>
?/p>
?/p>
p
p
q
,则
G
是连通的?/p>

6
.在一个有
n
个人的宴会上,每个人至少?/p>
m
个朋?/p>
(2
?/p>
m
?/p>
n)
。试证:有不?/p>
?/p>
m+1
个人?/p>
使得他们按某种方法坐在一张圆桌旁?/p>
每人的左?/p>
右均是他的朋友?/p>
证明:把实际问题转化为图论问题,就和下面的题一样了?/p>
8
.设
G
是图。证明:?/p>
δ
(G)
?/p>
2
,则
G
包含长至少是
δ
(G)+1
的圈?/p>
这两个题和这个题一样的证明方法?/p>
