討論串[ACM ] 11597-Spanning Subtree
共 8 篇文章
內容預覽:
都沒人想過用歸納法證嗎XD. n是偶數，所以我們目標是證每多兩個點，. 就可以多找出一個spanning tree跟其他spanning tree edge不重複. base case: 2個node, edge不重複的spanning tree的個數=1, trivial. induction:
(還有861個字)
內容預覽:
一個graph的生成樹通常不只一種，會有很多很多種。. 這問題是在問，這很多很多種的生成樹當中，. 挑其中幾棵出來，而且這幾棵生成樹沒有一條edge是一樣的，最多可以挑出幾棵？. suhorng和LPH66都有畫圖舉例了。. UVA所出的題目，題意往往跟題目標題一點關係都沒有。. 各位應該也司空見慣
(還有204個字)
內容預覽:
在每個spanning tree都是一條線的時候，會不會是n/2個。. 這個問題就是之前我的文章討論的問題。. 討論的假設是. "給定偶數N個點所組成的degree <= 2的spanning tree，經過點與點的交換位置，. 可以產生n/2個spanning tree且這n/2個spanning
(還有375個字)
內容預覽:
試著說明看看，有錯還請指正 ^^". 照原題，n 為偶數. 取 n-1 條 edge 組成 path , 各邊不重覆取. 可以生成 n/2 個生成樹，欲證明 n/2 為最多，. 且這些生成樹都是 path. 假如有 n/2 + 1 個生成樹且無重覆邊. 則總共邊數為. (n/2 + 1)(n-1)
(還有131個字)