Question

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

①任意兩臺(tái)之間最多用一條電纜連接；

②任意三臺(tái)之間最多用兩條電纜連接；

③兩臺(tái)計(jì)算機(jī)之間如果沒(méi)有電纜連接，則必須有另一臺(tái)計(jì)算機(jī)和它們都連接有電纜．若按此要求最少要用79條電纜．

問(wèn)：(1)這些計(jì)算機(jī)的數(shù)量是多少臺(tái)?

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

Answer 1

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

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

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

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

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

在這80個(gè)點(diǎn)(80臺(tái)計(jì)算機(jī))中，設(shè)從引出的線最多，有k條，與相連的點(diǎn)是,，…，由于條件，,…，之間沒(méi)有線相連．

設(shè)與不相連的點(diǎn)是，…，，則m+k=80，而，…, 每一點(diǎn)至多引出k條線，圖中至多有mk條線，因?yàn)?/span>≤

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

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