Tag Archives: 克希荷夫矩陣─樹定理

克希荷夫矩陣─樹定理

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

Posted in 圖論 | Tagged , , , , , , , | Leave a comment