文档文本内容
模块
模块1：
1 一个小组有个人，每两个人要么是仇人，要么是朋友，要么是相互不认识，且任意三个人中，有且只有两种关
系，证明：
．
1 在
，
时，
．
并且在
与
都是偶数时，成立严格不等式．
1 当
，
时，
．
2019暑高三数学实验班第
暑高三数学实验班第14讲
欧拉图与汉密尔顿图
欧拉图与汉密尔顿图
例题1
n
n ⩽12
例题2
p ⩾2
q ⩾2
r p, q ⩽
(
)
r p, q −1 +
(
)
r p + 1, q
(
)
r p, q −1
(
)
r p −1, q
(
)
例题3
p ⩾2
q ⩾2
r p, q ⩽
(
)
C
p+q−2
p−1
1 如图所示，图有个顶点，条边，它们都在同一平面上，这个平面被条边分成个区域Ⅰ，Ⅱ，Ⅲ，Ⅳ，称这些区
域为面．设有两个点
，
在这些面中，证明平面上不存在一条连接
与
的线同时满足：
截每条边
恰好一次
；
不过任一顶点
．
1 在由
个小正方形组成的图形中，试设计一条从点出发的路径，走过所有小正方形的边，最后回到点，并且使
得路径最短．
例题4
G
4
6
6
4
Q1
Q2
Q1
Q2
μ
1 μ
( )
e
i
i = 1, 2, ⋯, 6
(
)
2 μ
( )
v
j = 1, 2, 3, 4
j (
)
例题5
25
A
A
1 设是
阶简单图，且对每一对顶点
，
有
，
求证：图有哈密顿链．
1 是
阶简单图，且对每一对不相邻的顶点
、
有
，
那么图有哈密顿圈．
1 个人参加一次会议，在会议期间，每天都要在一张圆桌上共进晚餐．如果要求每次晚餐就座时，每个人相邻就座
者都不相同，问这样的晚餐最多能进行多少次？
例题6
G
n n ⩾3
(
)
(v
v )′
d v +
( )
d v
⩾
( ′)
n −1
G
例题7
G
n n ⩾3
(
)
(v
v )′
d v +
( )
d v
⩾
( ′)
n
G
例题8
n
1 若
为一个正
边形，连接它的所有对角线，这样得到一个图．证明：图的每个哈密顿圈
都必定包含两条边，它们在图中是平行线．
1 平面上个点和若干条边所成的图不是哈密顿图，但若任意去掉一点及与之相连的边，则剩下的图为哈密顿图．求
的最小值．
例题9
A
A
A
⋯A
0
1
2
2n−1
2n
G
G
例题10
n
n
