若干台计算机联网，要求：（1）任意两台之间最多用一台电缆连接；（2）任意三台之间最多用两条电缆连接；（3）两台计算机之间如果没有连接电缆，则必须有另一台计算机和它们都连接

Question

若干台计算机联网，要求：（1）任意两台之间最多用一台电缆连接；（2）任意三台之间最多用两条电缆连接；（3）两台计算机之间如果没有连接电缆，则必须有另一台计算机和它们都连接有电缆．若按此要求最少要连79条，问：
（1）这些计算机的数量是多少？
（2）这些计算机按要求联网，最多可以连多少条电缆？

Answer 1

将机器当成点，连结的电缆当成线，我们就得到一个图．如果从图上一个点出发，可以沿着线跑到图上任一个其它的点，这样的图就称为连通的图，条件③表明图是连通图．
（1）我们看一看几个点的连通图至少有多少条线可以假定图没有圈（如果有圈，就在圈上去掉一条线），从一点出发．沿线前进，已走过的点不再重复，那么走若干步后，必然走到一个点，不能再继续前进，将这一点与连结这点的线去掉．考虑剩下的n-1个点的图，它仍然是连通的．用同样的办法又可去掉一个点及一条线．这样继续下去，最后只剩下一个点．因此n个点的连通图至少有n-1条线（如果有圈，线的条数就会增加），并且从一点A向其它n-1个点各连一条线，这样的图恰好有n-1条线
因此，n=79+1=80，并且将一台计算机与其它79台各用一条线相连，就得到符合要求的联网．

（2）下面看看最多连多少条线．
在这80个点（80台计算机）中，设从A．引出的线最多，有K条，与A₁相连的点是B₁，B₂，…，B_K，由于条件②，B₁，B₂，…，B_K之间没有线相连．
设与A₁不相连的点是A₂，A₃，…，A_m，则m+k=80
而A₂，A₃，…，A_m每一点至多引出K条线，图中至多有mK条线，因为4×m×k=（m+k）²-（m-k）²≤（m+k）²=6400．所以m×k≤1600 即连线不超过1600条．
另一方面，设80个点分为两组：A₁，A₂…，A₄₀；B₁，B₂，…，B₄₀，第一组的每一点与第二组的每一点各用一条线相连，这样的图符合题目要求，共有 40×40=1600条线，因此，最多可连1600条线．
注：我们只用到图是连通的，而没有利用强得多的条件③，因此结论更有一般性．