文档文本内容
模块
模块1：
1 某国首都有
条航线连接其他城市，而城只有一条航线与某个城市连接，其他各城市中的每个城市都有
条航线
连接别处．证明：由首都可以飞抵城．
1 一个镇子有
个居民，编号到，任意两个陌生的人，有一个共同的朋友，并且没有人和其他
个人都是朋
友，
表示号居民的朋友数量，
．
，若可以安排一次为人的圆桌聚会，使得相邻两人互相认
识．求的最小值．
2019暑高三数学实验班第
暑高三数学实验班第12讲
连通图
连通图
例题1
21
A
20
A
例题2
n ⩾5
1
n
n −1
ai
i
a
= n −n
i=1
∑
n
i2
2
k ⩾3
k
k
例题3
1 设某国共有
个城市，它们之间有道路网相连，已知即使关闭其中一个城市的所有道路后，都仍然可以由其他城
市中的任一城市沿道路网抵达任何另一城市．证明：可将该国分解为两个主权国家，每个国家
个城市，使得任何一
个国家内部都可以由一个城市沿道路网抵达另一个城市．
1
个学生参加一次考试，试题有
道，已知没有两个学生做对的题目完全相同．证明这
道题目中可以找到一道
试题，将这道试题取消后，任意两个学生做对的题目仍不完全相同．
一个国家的国王打算建个城市和
条道路，使每条道路连接两个城市而不经过其他城市，而且每两个城市都可
以互相到达，这个城市之间的最短距离恰好分别是，，，
，
这些数．问下列情况下，国
王的打算能否实现．
1
．
100
50
例题4
10
10
10
例题5
n
n −1
n
1
2
3
⋯
C
=
n
2
n n −1
2
1
(
)
n = 6
2
．
1 在
座城市之间有两种方式的飞行航线被执行：任意一座城市至少和七座城市有直航；任意两座城市可以通过有
限次直航来连接．求最小的整数，使得无论如何安排满足条件的航线，任意一座城市到任意其他城市最多可以经过
次直航到达．
1 六座城市间有一个铁路网，使得任两座城市间均有直通的铁路，而在星期天的时候，一些铁路将关闭以便修整，
现铁路部门规定：关闭若干段铁路之后，必须保证仍可利用铁路交通往返于任意两座城市之间(不一定直达)问：有多
少种不同的铁路修整方式满足铁路部门的要求？
n = 2004
例题6
80
k
n
例题7
例题8
1 某国有
座城市，它们之间有一些道路相连，使得可以从任意一座城市到达任意一座别的城市．已知若关闭掉
其中任意一条道路，都仍然可以从任意一座城市到达任意一座别的城市．交通部长和内务部长轮流选择一条道路实施
单行车规则(只许朝一个方向行车)，直到所有道路均实施单向行车规则．若某个部长实施其规则之后，发现由某座城
市不能到达另外某座城市，则该部长就引咎辞职．首先由交通部长开始．试问：是否可能有一个部长总能使得对方
(无论怎么做)均落得个辞职的下场？
1 假设是一棵有条边的树，证明：维立方体可以被分割为与同构的树．
2004
例题9
T
k
k
T
