[其他] 離散-spanning tree 個數

看板Math作者 (ling)時間8年前 (2016/05/31 17:20), 8年前編輯推噓5(5推 0噓 10→)
留言15則, 1人參與, 最新討論串1/1
不好意思打擾各位！ 想請問一下附圖中，此無向圖的spanning tree 個數要怎麼找... 原本想用 matrix tree 方法（儘管陣列會超大...） 但圖中紅色點互連的線有兩條，所以行不通（不是簡單無向圖） 希望有神人可以提點我QQ http://imgur.com/M2457vh.jpg
-- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.160.238.113 ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1464686415.A.35E.html
推
05/31 18:12, , 1F
把兩條邊其中一條 收縮 以及 刪除 就會變簡單圖
05/31 18:12, 1F
→
05/31 18:13, , 2F
(loop直接刪除) 這手法可能會出現在證明裡
05/31 18:13, 2F
推
05/31 18:53, , 3F
另外其實 matrix tree thm 有 multi-edged digraph
05/31 18:53, 3F
→
05/31 18:54, , 4F
版本(可化約到無向圖)，也可以試著自己從原本證明
05/31 18:54, 4F
→
05/31 18:54, , 5F
推廣看看
05/31 18:54, 5F
嗯嗯很感謝你QAQ 我自己推導是以下，不曉得正不正確~ http://i.imgur.com/QQlAhKM.jpg
- http://i.imgur.com/ey8NAA8.jpg
※ 編輯: ling35021 (118.160.236.219), 05/31/2016 19:25:12 ※ 編輯: ling35021 (118.160.236.219), 05/31/2016 19:25:43
推
05/31 19:29, , 6F
你好像搞錯收縮的定義了，但的確沒我說的那麼簡單
05/31 19:29, 6F
→
05/31 19:29, , 7F
要做多次收縮/刪除
05/31 19:29, 7F
→
05/31 19:30, , 8F
也許還是證明推廣版比較實際些
05/31 19:30, 8F
我是用 原圖=取那兩條邊其中一條x2+不取那兩條邊 不過我真的不太瞭解您說的收縮刪除QQ 另外，可以非簡單無向圖的matrix tree thm 我目前還沒找到，可能我還不夠用心找... ※ 編輯: ling35021 (42.72.202.192), 05/31/2016 19:41:13
推
05/31 19:51, , 9F
收縮的關鍵字 Edge contraction
05/31 19:51, 9F
→
05/31 19:52, , 10F
某個matrix tree thm 的證明有用到
05/31 19:52, 10F
→
05/31 19:53, , 11F
τ(G)=τ(G-e)+τ(G‧e) 減號是刪除，dot是收縮
05/31 19:53, 11F
→
05/31 19:53, , 12F
τ是生成樹個數
05/31 19:53, 12F
推
05/31 19:56, , 13F
非簡單無向圖的版本，維基的頁面最後一項有提到
05/31 19:56, 13F
※ 編輯: ling35021 (42.72.202.192), 05/31/2016 19:57:44
→
05/31 19:57, , 14F
證明仿造原版本的
05/31 19:57, 14F
→
05/31 19:58, , 15F
另外也要想想要把無向圖變成怎樣的有向圖
05/31 19:58, 15F
‣ 更多 ling35021 的文章
文章代碼(AID): #1NJLTFDU (Math)