题目内容
【题目】若干台计算机联网，要求：
①任意两台之间最多用一条电缆连接；
②任意三台之间最多用两条电缆连接；
③两台计算机之间如果没有电缆连接，则必须有另一台计算机和它们都连接有电缆．若按此要求最少要用79条电缆．
问：(1)这些计算机的数量是多少台?
(2)这些计算机按要求联网，最多可以连多少条电缆?
【答案】(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条线
练习册系列答案
相关题目
