[其他] 離散-spanning tree 個數

[ling35021 (ling)]

不好意思打擾各位！
想請問一下附圖中，此無向圖的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
推 arthurduh1  : 把兩條邊其中一條 收縮 以及 刪除 就會變簡單圖
→ arthurduh1  : (loop直接刪除)  這手法可能會出現在證明裡
推 arthurduh1  : 另外其實 matrix tree thm 有 multi-edged digraph
→ arthurduh1  : 版本(可化約到無向圖)，也可以試著自己從原本證明
→ arthurduh1  : 推廣看看
嗯嗯很感謝你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
推 arthurduh1  : 你好像搞錯收縮的定義了，但的確沒我說的那麼簡單
→ arthurduh1  : 要做多次收縮/刪除
→ arthurduh1  : 也許還是證明推廣版比較實際些
我是用
原圖=取那兩條邊其中一條x2+不取那兩條邊

不過我真的不太瞭解您說的收縮刪除QQ
另外，可以非簡單無向圖的matrix tree thm
我目前還沒找到，可能我還不夠用心找...
※ 編輯: ling35021 (42.72.202.192), 05/31/2016 19:41:13
推 arthurduh1  : 收縮的關鍵字 Edge contraction
→ arthurduh1  : 某個matrix tree thm 的證明有用到
→ arthurduh1  : τ(G)=τ(G-e)+τ(G‧e)  減號是刪除，dot是收縮
→ arthurduh1  : τ是生成樹個數
推 arthurduh1  : 非簡單無向圖的版本，維基的頁面最後一項有提到
※ 編輯: ling35021 (42.72.202.192), 05/31/2016 19:57:44
→ arthurduh1  : 證明仿造原版本的
→ arthurduh1  : 另外也要想想要把無向圖變成怎樣的有向圖