Re: [ACM ] 11597-Spanning Subtree

看板C_and_CPP作者 (...)時間15年前 (2010/04/07 12:42), 編輯推噓3(3推 0噓 15→)
留言18則, 2人參與, 最新討論串7/8 (看更多)
一個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)
推
04/07 13:29, , 1F
用模擬的方式 把各組解列出來 對證明是有幫助的
04/07 13:29, 1F
→
04/07 13:30, , 2F
我猜測這題組合的題目, 解法應該用 construction 就可以了
04/07 13:30, 2F
→
04/07 13:31, , 3F
construct 的方式, 應該可以參考之前討論所提到端點的分布
04/07 13:31, 3F
→
04/07 13:32, , 4F
第一組是 1-2 2-3 3-4 5-6 7-8, 其他用代換
04/07 13:32, 4F
→
04/07 13:32, , 5F
只要能證明端點置換的結果不會讓邊重複即可
04/07 13:32, 5F
→
04/07 13:33, , 6F
至於會不會有其他形狀的 disjoint spanning tree
04/07 13:33, 6F
→
04/07 13:33, , 7F
對 construction 解法來說不是很重要
04/07 13:33, 7F
→
04/07 13:34, , 8F
第一感覺得應該跟拉丁方陣有關
04/07 13:34, 8F
→
04/07 13:36, , 9F
前面有人說到生成樹都是一條線 所以我想到了這個
04/07 13:36, 9F
→
04/07 13:37, , 10F
04/07 13:37, 10F
推
04/07 13:39, , 11F
eular circuit uses every edge of G
04/07 13:39, 11F
→
04/07 13:40, , 12F
slightly different
04/07 13:40, 12F
→
04/07 13:46, , 13F
是不太一樣。假設現在有個奇數個點的完全圖的euler circuit，
04/07 13:46, 13F
→
04/07 13:46, , 14F
然後從完全圖上拿掉一個點，這樣就產生n/2段路徑。 　
04/07 13:46, 14F
※ 編輯: DJWS 來自: 59.115.153.231 (04/07 13:47)
推
04/07 13:50, , 15F
http://0rz.tw/qYyS4 I found something from your hint
04/07 13:50, 15F
→
04/07 13:51, , 16F
hamilton circuit might be more useful than eular circuit
04/07 13:51, 16F
→
04/07 14:24, , 17F
然後證明這n/2條路段可以是n/2種不同的hamilton path即可
04/07 14:24, 17F
→
04/07 14:30, , 18F
證明過程...就是ledia貼的文章 哈哈
04/07 14:30, 18F
‣ 更多 DJWS 的文章
文章代碼(AID): #1Bl0r74B (C_and_CPP)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 7 之 8 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共8篇)
‣ 更多 DJWS 的文章
文章代碼(AID): #1Bl0r74B (C_and_CPP)