: ※ 發信站: 批踢踢實業坊(ptt.cc)
: ◆ From: 122.123.246.222
: 推 ledia:你確定生成一棵樹之後, 不會讓其他樹生不出來嗎? :p 04/06 19:06
: → lagerway:我也有相同的疑問 04/06 20:32
: → netsphere:在每個spanning tree都是一條線的時候 就會是n/2個了 04/06 22:08
: 推 pichubaby:不會 因為每個點的邊數都會同時減少 04/07 08:33
在每個spanning tree都是一條線的時候，會不會是n/2個。
這個問題就是之前我的文章討論的問題。
討論的假設是
"給定偶數N個點所組成的degree <= 2的spanning tree，經過點與點的交換位置，
可以產生n/2個spanning tree且這n/2個spanning tree並沒有相同邊。"
我無法證明，所以我寫了個程式來測試。
程式碼︰http://nopaste.csie.org/6ae78
程式結果︰http://nopaste.csie.org/6b3e4
即使有了這個程式，我還是無法證明。
在20點之前的測資都可以正確無誤，且輸出在人類感受不會太久的情況。
但在22個點時，需要時間大約3分鐘，答案也的確是11(22 / 2)。
由於時間過久，我無法證明N很大的時候是否正確。
這個程式所有spanning tree的端點使用我所提到的端點對稱性質。
即10個點會是(頭，尾) = (1,10)(2,9)(3,8)(4,7)(5,6)
且每個點只會當端點一次。
而這個程式的回溯只設定在只能找到n / 2 - 1個spanning tree的時候
如果在n / 2 - 1之前就必須回溯的話，
我在程式碼裡安插一個字串"haha"然後跳出迴圈。
代表程式可能有寫錯的地方。
我應該不再維護這個程式，也不確定這個程式一定沒寫錯。
有興趣的人就自行測試了。
Bleed
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.32.177.97