Question

【題目】若干臺計算機聯(lián)網(wǎng)，要求：

①任意兩臺之間最多用一條電纜連接；

②任意三臺之間最多用兩條電纜連接；

③兩臺計算機之間如果沒有電纜連接，則必須有另一臺計算機和它們都連接有電纜．若按此要求最少要用79條電纜．

問：(1)這些計算機的數(shù)量是多少臺?

(2)這些計算機按要求聯(lián)網(wǎng)，最多可以連多少條電纜?

Answer 1

【答案】(1)80臺 (2)1600條

【解析】將機器當(dāng)成點，連接電纜當(dāng)成線，我們就得到一個圖，如果從圖上一個點出發(fā)，可以沿著線跑到圖上任一個其它的點，這樣的圖就稱為連通的圖，條件③表明圖是連通圖．

我們看一看幾個點的連通圖至少有多少條線．可以假定圖沒有圈(如果有圈，就在圈上去掉一條線)，從一點出發(fā)，不能再繼續(xù)前進，將這一點與連結(jié)這點的線去掉．考慮剩下的n-1個點的圖，它仍然是連通的．用同樣的辦法又可去掉一點及一條線．這樣繼續(xù)下去，最后只剩下一個點．因此n個點的連通圖至少有n-1條線(如果有圈，線的條數(shù)就會增加)，并且從一點A向其他n-1個點各連一條線，這樣的圖恰好有n-1條線．

因此，(1)的答案是n=79+1=80，并且將一臺計算機與其他79臺各用一條線相連，就得到符合要求的聯(lián)網(wǎng)．

下面看看最多連多少條線．

在這80個點(80臺計算機)中，設(shè)從引出的線最多，有k條，與相連的點是,，…，由于條件，,…，之間沒有線相連．

設(shè)與不相連的點是，…，，則m+k=80，而，…, 每一點至多引出k條線，圖中至多有mk條線，因為≤

所以m×k≤1600，即連線不超過1600條．

另一方面，設(shè)80個點分為兩組：,…，；，…，第一組的每一點與第二組的每一點各用一條線相連，這樣的圖符合題目要求，共有40×40=1600條線