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條線