Tag Archives: 拉普拉斯矩陣

克希荷夫矩陣─樹定理

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

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

線性代數在圖論的應用 (三):拉普拉斯矩陣

本文的閱讀等級:中級 令 為一個無向圖 (undirected graph),其中 是頂點集合, 稱為圖 的階 (order), 是無向邊集合。若頂點 和 之間存在一邊,記為 ,我們稱 和 鄰接 (adjacent),並稱該邊與二頂點有關聯 (incident)。無向邊不具方向性, 是兩頂點組成的集合,即每一邊可視為一無序頂點對。以下考慮簡單無向圖,意思是不存在自迴路 (self-loop),即 ,且不存在重邊 (multiedge),即任二相異頂點至多僅存在一關聯邊。對應 階圖 ,鄰接矩陣 為一 階矩陣,定義如下: 若 ,否則 (見“線性代數在圖論的應用 (一):鄰接矩陣”)。顯然,, 是一對稱矩陣。表面上,鄰接矩陣是一圖的最自然的表示方式,但它的實用價值卻不大,原因在於鄰接矩陣的特徵值和特徵向量未能揭露圖結構的重要訊息,此外,鄰接矩陣的二次型亦缺乏明確的涵義。本文介紹一種適於建立矩陣譜 (相異特徵值集合,spectrum) 理論的無向圖表示矩陣,稱為拉普拉斯矩陣 (Laplacian)。對於頂點 ,分支度 (度數,degree) 是所有與 有關聯的邊數,即鄰接矩陣 的第 列 (或行) … Continue reading

Posted in 線性代數專欄, 圖論, 應用之道 | Tagged , , , , | 2 Comments