Re: [離散]電腦配線問題

[hcsoso (索索)]

※ 引述《MOONY135 (柳生劍影)》之銘言：
: 假設有10台電腦 跟五台印表機
: 為了不要互擠
: 那麼最少需要裝幾條線呢?
: 應該最少是5+5*5=30條
: 那麼低於30條為什麼不行呢
: 例 29條線..請問這個要怎樣解釋..

我猜這題想說的是這樣:

有 n 台電腦與 m 台印表機, (n >= m)
我們需要將電腦和印表機之間連線, (所以線是接在電腦與印表機間)
使得任一時刻, 若有 m 台以內的電腦需要使用印表機,
則一定會有足夠的印表機可以使用.
請問最多只需要多少線就可以達到目的?

這其實是圖論上的 bipartite matching 問題,
只是作了個變形: 現在變成了 extremal graph 的問題了.
我們需要一個邊數最少的圖 G, 使得 perfect matching 一定存在.
當然提到 perfect matching, 就不能忘記重要的 Hall's condition:

設 X, Y 為電腦跟印表機的集合, 則 (X,Y) 之間有 perfect matching iff
|S| <= |N(S)| for all S \subset X.

當然現在 |X| >= |Y|, 所以我們只需要 |S| <= |Y| 的子集成立就好了.
所以我們就可以證明底下這個定理:

Theorem. 設 G = (X,Y) 是邊數最少滿足以上條件的圖. 則 |E(G)| = m(n-m+1).

proof.
假設 G 是違反邊數限制的最小(w.r.t.點)圖, 即 |E(G)| > m(n-m+1).
先讓 X = {x_1, ..., x_n} 與 Y = {y_1, ..., y_m},
因為 Hall's condition 成立,
在 X' = {x_1, ..., x_m} 與 Y' = {y_1, ..., y_m} 之間有一組 perfect matching,
不失一般性假設是 {(x_i,y_i)}_i.
又因為 G 是最小, 將 {x_{m+1}, ..., x_n} 從 G 中拔掉後,
剩下圖裡的邊應該只有上面所寫的這組 matching.
這時我們看底下這組 X 的子集 X_{i,j} = X' - {x_i} + {x_j},
我們有 |X_{i,j}| = |X'| = m, 所以它也要滿足 Hall's condition.
看 X_{1,m+1}, 我們發現因為 (x_2,y_2) 到 (x_m,y_m) 都沒有變,
所以 x_{m+1} 必須接到 y_1;
再看 X_{2,m+1}, ..., X_{m,m+1}, 我們發現 x_{m+1} 必須接到所有 y_i.
同樣的去看所有 X_{i,j} for 1 <= i <= m 與 m+1 <= j <= n,
我們會發現這裡會有 m * (n-m) 條邊.
加上之前的 m 條, 一共 m(n-m+1) 條.
這時 Hall's condition 滿足, G 有 perfect matching for every S s.t. |S| <= m,
與上面假設矛盾,
故我們有 extremal graph G 使得 |E(G)| = m(n-m+1).               Q.E.D.

在這裡讓 n = 10, m = 5,
就會有 5*(10-5+1) = 30 了!!

--

不曉得有沒有證錯... 結果誤導人!?
差一點證不出來 > <
請幫忙 verify... 謝謝 XD

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.133.15.15
→ hcsoso      :oops... 好像有點小漏洞, 不過希望題意是對的!
→ hcsoso      :有高手可以示範一下證明或是給反例嗎？
推 doom8199    :應該是差不多的題意 ,　明確點是:
→ doom8199    :若有 m台電腦要使用印表機 , 則可以確保有 m台
→ doom8199    :印表機可供使用。 可用 pigeonhole principle 證明
→ hcsoso      :yes... 用鴿籠原理容易多了...!!
推 MOONY135    :對耶..老師上課很快的就跳過去了..
→ MOONY135    :我想請問不失一般性是什麼意思..
→ hcsoso      :哈哈不要看這個錯誤的證明啦...
→ MOONY135    :另外請問鴿籠原理要怎樣證明
→ hcsoso      :看一下 hsos 說的 #1BQ3EaTt 吧!