Question

【题目】若干台计算机联网，要求：

①任意两台之间最多用一条电缆连接；

②任意三台之间最多用两条电缆连接；

③两台计算机之间如果没有电缆连接，则必须有另一台计算机和它们都连接有电缆．若按此要求最少要用79条电缆．

问：(1)这些计算机的数量是多少台?

(2)这些计算机按要求联网，最多可以连多少条电缆?

Answer 1

【答案】(1)80台 (2)1600条

【解析】将机器当成点，连接电缆当成线，我们就得到一个图，如果从图上一个点出发，可以沿着线跑到图上任一个其它的点，这样的图就称为连通的图，条件③表明图是连通图．

我们看一看几个点的连通图至少有多少条线．可以假定图没有圈(如果有圈，就在圈上去掉一条线)，从一点出发，不能再继续前进，将这一点与连结这点的线去掉．考虑剩下的n-1个点的图，它仍然是连通的．用同样的办法又可去掉一点及一条线．这样继续下去，最后只剩下一个点．因此n个点的连通图至少有n-1条线(如果有圈，线的条数就会增加)，并且从一点A向其他n-1个点各连一条线，这样的图恰好有n-1条线．

因此，(1)的答案是n=79+1=80，并且将一台计算机与其他79台各用一条线相连，就得到符合要求的联网．

下面看看最多连多少条线．

在这80个点(80台计算机)中，设从引出的线最多，有k条，与相连的点是,，…，由于条件，,…，之间没有线相连．

设与不相连的点是，…，，则m+k=80，而，…, 每一点至多引出k条线，图中至多有mk条线，因为≤

所以m×k≤1600，即连线不超过1600条．

另一方面，设80个点分为两组：,…，；，…，第一组的每一点与第二组的每一点各用一条线相连，这样的图符合题目要求，共有40×40=1600条线