Tag Archives: 最小生成樹

本文的閱讀等級：高級 令 為一無向圖，其中 是頂點 (vertex) 集合， 是邊 (edge) 集合，頂點數 稱為圖 的階 (order)。每一條無向邊 (以下簡稱邊) 有兩個頂點為其端點 (endpoint)。因此，一邊 定義為 中兩頂點 和 組成的集合或無序對，記為 ，我們稱頂點 和 鄰接 (adjacent)，並稱頂點 和 與邊 有關聯 (incident)。以下考慮簡單圖，意思是不存在自環 (self-loop)，即一邊的兩端點為同一頂點，並且不存在重邊 (multiedge)，即任意兩相異頂點至多僅存在一連接邊。若一圖的任兩頂點之間存在一序列鄰接頂點構成的連通路徑 (path)，則稱為連通圖 (connected graph)。若 且 ，我們說 是圖 的一個子圖 (subgraph)。圖 的一個連通元件是指子圖 為一連通圖，但任意 和 … Continue reading →