Research Space for Linear Algebra & Discrete Mathematics
您好：下面有解釋喔，因為本身就不連通，所以沒有生成樹。以上淺見..
補充：固定右邊那條邊，取與不取，不取的話就沒有生成樹，取的話就有3種生成樹。
還是不清楚= =不好意思...當初這邊就聽不懂可以在說得更清楚一點嗎?謝謝:)
拆邊黏點的過程事實上就是遞迴窮舉出所有的可能然後拆到最後再加總所有小圖的可能即可至於剩下的小圖要如何討論, 比方說看最後一行的第四個圖假設剩下的那三個點從上, 左, 右依序叫x, y, z, 則(1) 假設不把 y 和 z 連起來, 因為 x 連 y 有 2 種, 乘上 x 連 z 有 2 種, 所以spanning tree有 2 * 2 種可能(2) 假設不把 x 和 y 連起來, 因為 x 連 z 有 2 種, 乘上 y 連 z 有 1 種, 則spanning tree有 2 * 1 種可能(3) 假設不把 x 和 z 連起來, 同理所以spanning tree的個數為 2*2 + 2*1 + 2*1
懂了!謝謝你們:)
張貼留言
6 則留言:
您好：下面有解釋喔，因為本身就不連通，所以沒有生成樹。
以上淺見..
補充：固定右邊那條邊，取與不取，不取的話就沒有生成樹，取的話就有3種生成樹。
還是不清楚= =不好意思...
當初這邊就聽不懂
可以在說得更清楚一點嗎?謝謝:)
拆邊黏點的過程事實上就是遞迴窮舉出所有的可能
然後拆到最後再加總所有小圖的可能即可
至於剩下的小圖要如何討論,
比方說看最後一行的第四個圖
假設剩下的那三個點從上, 左, 右依序叫x, y, z, 則
(1) 假設不把 y 和 z 連起來,
因為 x 連 y 有 2 種, 乘上 x 連 z 有 2 種,
所以spanning tree有 2 * 2 種可能
(2) 假設不把 x 和 y 連起來,
因為 x 連 z 有 2 種, 乘上 y 連 z 有 1 種,
則spanning tree有 2 * 1 種可能
(3) 假設不把 x 和 z 連起來, 同理
所以spanning tree的個數為 2*2 + 2*1 + 2*1
懂了!
謝謝你們:)
懂了!
謝謝你們:)
張貼留言