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試試看對不對，
但是我覺得這樣做很無聊，就算對了又怎樣，結果還是什麼都不會。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.115.153.231
※ 編輯: DJWS            來自: 59.115.153.231       (04/07 13:03)
推 ledia:用模擬的方式 把各組解列出來 對證明是有幫助的
→ ledia:我猜測這題組合的題目, 解法應該用 construction 就可以了
→ ledia:construct 的方式, 應該可以參考之前討論所提到端點的分布
→ ledia:第一組是 1-2 2-3 3-4 5-6 7-8, 其他用代換
→ ledia:只要能證明端點置換的結果不會讓邊重複即可
→ ledia:至於會不會有其他形狀的 disjoint spanning tree
→ ledia:對 construction 解法來說不是很重要
→ ledia:第一感覺得應該跟拉丁方陣有關
→ DJWS:前面有人說到生成樹都是一條線  所以我想到了這個
→ DJWS:http://ppt.cc/sxY2
推 ledia:eular circuit uses every edge of G
→ ledia:slightly different
→ DJWS:是不太一樣。假設現在有個奇數個點的完全圖的euler circuit，
→ DJWS:然後從完全圖上拿掉一個點，這樣就產生n/2段路徑。    　
※ 編輯: DJWS            來自: 59.115.153.231       (04/07 13:47)
推 ledia:http://0rz.tw/qYyS4  I found something from your hint
→ ledia:hamilton circuit might be more useful than eular circuit
→ DJWS:然後證明這n/2條路段可以是n/2種不同的hamilton path即可
→ DJWS:證明過程...就是ledia貼的文章  哈哈