→ springman :for m = 1,...,n 這裡應該是 for m = 1,...,n-1 12/29 16:48
→ hchuang :阿對 哈哈 打很快 12/30 13:42
※ 編輯: hchuang 來自: 211.74.111.98 (12/30 13:42)
推 jimmy055263 :謝謝您的回覆，非常的詳細! 12/30 16:14
※ 引述《jimmy055263 (御痕星語)》之銘言：
: 在寫作業上遇到了一些問題
: PO上來看看有沒有高人可以解答
: 問題:
: n個城市之間，有k高速公路，每條公路連接兩個城市，
: 兩個城市之間只有一條直接相連的高速公路。試證明
: 當K > (n-1)(n-2)/2 時，任意兩個城市之間的交通，
: 必定可以完全經由高速公路。
假設 K > (n-1)(n-2)/2 為 disconnected graph
則 graph 至少可以分成兩個不相連的子圖 G1 and G2
假設 |V(G1)| = m , |V(G2)| = n-m
則在 G1 中 至多有 C(m,2) 條邊
G2 中 至多有 C(n-m,2) 條邊
然而 C(m,2) + C(n-m,2) < (n-1)(n-2)/2 , for m = 1,...,n-1
表示 G1 和 G2 中一定有邊相連 ---><---
故為 connected graph
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 211.74.111.29