Re: [ACM ] 11597-Spanning Subtree
※ 引述《DJWS (...)》之銘言：
: 一個graph的生成樹通常不只一種，會有很多很多種。
: 這問題是在問，這很多很多種的生成樹當中，
: 挑其中幾棵出來，而且這幾棵生成樹沒有一條edge是一樣的，最多可以挑出幾棵？
: suhorng和LPH66都有畫圖舉例了。
: UVA所出的題目，題意往往跟題目標題一點關係都沒有。
: 各位應該也司空見慣了。
: －－－－－－
: 一棵生成樹既然是樹，就一定是n-1條edge。
: n個點的完全圖總共有n(n-1)/2條edge，
: 所以我們可以簡單推測出答案一定不會超過n/2棵。
: 至於答案到底是不是剛剛好n/2？
: 這就是得自己想（或找人討論）的部分了。
: 你大可上傳一支程式直接輸出n/2試試看對不對，
: 但是我覺得這樣做很無聊，就算對了又怎樣，結果還是什麼都不會。
都沒人想過用歸納法證嗎XD
n是偶數，所以我們目標是證每多兩個點，
就可以多找出一個spanning tree跟其他spanning tree edge不重複
base case: 2個node, edge不重複的spanning tree的個數=1, trivial
induction: 假設n個node，有n/2個edge不重複的spanning tree T1 ... T(n/2),
考慮n+2個node，要找(n/2)+1個edge不重複的spanning tree
所以我在原來的圖多加兩個node 叫a, b,
以及多加2n+1條edge (1,a),...,(n,a),(1,b),...,(n,b),(a,b)
現在這個圖是n+2的點的complete graph
我要產生(n/2)+1個edge不重複的spanning tree
前n/2個利用已知的T1,...,T(n/2)來產生
T'1=T1加上(1,a),((n/2)+1,b)這兩條edge,
......
T'i=Ti加上(i,a),((n/2)+i, b)這兩條edge,
......
T'(n/2)=T(n/2)加上((n/2),a), (n,b)這兩條edge
剩下來的edge可以組成一個spanning tree
T'((n/2)+1):由(1,b),...,((n/2),b),((n/2)+1,a),...,(n,a),(a,b)
這n+1條edge組成
簡單的說,就是當每多兩個點的時候，會多2n+1條edge
我讓原來的每個spanning tree各多兩條edge連到a跟連到b，
產生新的圖上的spanning tree，這樣用掉n條edge
然後剩下來的n+1條edge構成一個spanning tree
所以任兩個spanning tree的edge都不重複
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.216.151.69
※ 編輯: jhchou 來自: 61.216.151.69 (04/07 15:10)
推
04/07 15:28, , 1F
04/07 15:28, 1F
推
04/07 15:48, , 2F
04/07 15:48, 2F
※ 編輯: jhchou 來自: 61.216.151.69 (04/07 15:53)
推
04/08 07:00, , 3F
04/08 07:00, 3F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 8 之 8 篇)：