Re: [ACM ] 11597-Spanning Subtree

[Qlife (Qlife)]

試著說明看看，有錯還請指正 ^^"

照原題，n 為偶數

取 n-1 條 edge 組成 path , 各邊不重覆取
可以生成 n/2 個生成樹，欲證明 n/2 為最多，
且這些生成樹都是 path

假如有 n/2 + 1 個生成樹且無重覆邊
則總共邊數為
   (n/2 + 1)(n-1) > C(n,2)
超過 K_n 的邊數，故矛盾

所以最多是 n/2 個

假如這 n/2 個生成樹中有一個不是 path
也就是，假設這 n/2 個生成樹中有一樹 T
上面有一個點 u , 在 T 中的 degree 為 x 且 x > 2

則把 n/2 個生成樹中，u 的 degree 加總起來

degree u = (n/2 -1) * 2 + x > n

則與原圖中的 degree 不符，矛盾

所以 n/2 個生成樹應該是最多了吧?


※ 引述《andyisman (andychen)》之銘言：
: : 題號：11597
: : 遇到的問題：題目看不懂? 不知道實際上那樹長什麼樣子
: : 附上中文題目跟英文題目的連結
: : 中文：http://zerojudge.tw/ShowProblem?problemid=d656
: : 英文：
: : http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2644
: 你生成一棵樹要用掉 n-1 條邊 因為不能重複
: 所以生成一棵樹就會砍掉 n-條邊
: 又因為完全圖有 n(n-1)/2 條邊
: 所以可以生成幾棵就自己算吧 >.^

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.113.235.154
推 AstralBrain:1. deg(u)=(n/2-1)*2+x 就算x=2也是錯的喔
→ AstralBrain:2. 你只證明生成樹不能超過n/2個
→ AstralBrain:  並沒有說明n/2的時候有沒有解
→ Qlife:確實這兩點都有問題，謝謝樓上，我再想想看!
推 AstralBrain:還有不要太堅持一定要用path 這樣只是把條件變嚴格
推 AstralBrain:給個不用path的例子:http://0rz.tw/oE5yL
→ Qlife:哦哦!有這個反例真好 ~