小蓝书 17.4 题解

传送门：小蓝书 17.4

第一部分 例题

例4

由于书上例1,2,3都是基础概念，所以直接从例4开始讲。

某 $15$ 座城市，他们之间的航线分数三家航空公司。一直无论哪家航空公司停飞，旅客总还能从任意城市飞往其他任何城市（允许转机），那么至少需要多少条航线。

解：

记三家航空公司的航线数分别为 $a,b,c$ ，显然有

$$a + b \ge 14 \,\land\, a + c \ge 14 \,\land\, b + c\ge 14$$

合并一下就是

$$a + b + c \ge 21$$

因此需要至少 $21$ 条航线。容易构造出几个例子，如下

其实也容易证明，上图的构造方式具有一般性，对于 $n > 2$ 。

例5

咕咕咕。。

---

第二部分 习题

咕咕咕。。