Re: [ACM ] 11597-Spanning Subtree
試著說明看看，有錯還請指正 ^^"
照原題，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
推
04/07 01:40, , 1F
04/07 01:40, 1F
→
04/07 01:41, , 2F
04/07 01:41, 2F
→
04/07 01:42, , 3F
04/07 01:42, 3F
→
04/07 01:50, , 4F
04/07 01:50, 4F
推
04/07 01:53, , 5F
04/07 01:53, 5F
推
04/07 02:05, , 6F
04/07 02:05, 6F
→
04/07 10:44, , 7F
04/07 10:44, 7F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 5 之 8 篇)：