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

有向無環圖與 (0,1) 矩陣的特徵值

本文的閱讀等級:中級 若一個矩陣 的每一元 為 或 ,我們稱之為 (0,1) 矩陣。2003年任職 Wolfram 研究中心的韋斯坦 (Eric W. Weisstein) 在計算 階 (0,1) 矩陣,,的特徵值時,發現所有特徵值皆為正實數[1]的 (0,1) 矩陣總數為下列序列: 在圖論中,若一個有向圖無法從某個頂點出發經過若干條邊回到該點,則稱之為有向無環圖 (directed acyclic graph,簡稱DAG)。韋斯坦得到的序列恰巧與包含 個標記頂點的有向無環圖數的前五項相等[2]: 自然地,韋斯坦猜想這兩個數列完全相同。圖一顯示 的所有標記有向無環圖。2004年麥凱 (Brendan D. McKay) 等人證明了韋斯坦猜想:包含 個標記頂點的有向無環圖與特徵值皆為正實數的 階 矩陣存在一對一的關係[3]。底下介紹一個精巧的證明。

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

電影《心靈捕手》的數學問題 (一)

本文的閱讀等級:中級 美國馬里蘭大學馬尼爾‧蘇里 (Manil Suri) 教授說[1]: 在新聞媒體或文化領域,很少會出現數學這個主題。很多時候,當數學出現在一部小說或電影中時,我就會想起契訶夫諺語中的槍:如果一個數學家不發瘋,就別讓他出場。對數學的焦慮感,像厚厚的陰霾一樣籠罩着萬事萬物。   我知道關於「數學與人物」的電影法則包括 如果你是一個正常人,那麼你應當害怕或討厭數學。 如果你解開別人解不出的數學問題,那麼你不是書呆子就是精神異常者。 如果你的數學本來其爛無比,有一天卻突然擁有超強的特異能力,那麼你可能被外星人附體或腦部受到不明來源的輻射汙染。   在電影《心靈捕手》(Good Will Hunting),麻省理工學院的朗博教授 (Gerald Lambeau) 為激勵學生上進,他在走廊黑板公布數學難題並保證答對者將可名利雙收。清潔工威爾 (Will Hunting) 擁有過人的天賦,性格叛逆亟需心理治療,但尚未惡化到發瘋的地步[2]。朗博教授和威爾同在一棟大樓工作,不過兩人沒有任何交集。本文討論朗博教授張貼的第一個問題。下面是電影片段 (字幕見[3])。

Posted in 圖論 | Tagged , , , , , , | 5 Comments

特殊矩陣 (20):可約矩陣

本文的閱讀等級:中級 令 為一 階矩陣。如果存在一排列矩陣 (permutation matrix) 使得 , 其中 是 階,, 是 階,我們稱 為可約矩陣 (reducible matrix),否則稱之為不可約矩陣 (irreducible matrix)。排列矩陣滿足 ,可知 相似於 。因為 以相同方式交換 的行與列, 也稱為 的一個對稱排列 (symmetric permutation)。設想 的 元代表變數 與變數 的關聯性,對稱排列 的作用即在重新命名變數 (見“矩陣視覺化”)。可約矩陣的名稱由來係因其對稱排列具有分塊上三角形式,使得線性方程的求解工作變得較為簡單。若 和 以分塊表示為 和 ,則 可化約為兩個較小型的子系統: 當線性方程是一致時,採用反向代回法,先從 解出 … Continue reading

Posted in 特殊矩陣, 線性代數專欄 | Tagged , , , , , , | 12 Comments

Hermitian 矩陣與實對稱矩陣的一些實例

本文的閱讀等級:初級 令 為一個 階矩陣。若 ,其中 ,即 ,我們稱 為 Hermitian 矩陣 (見“特殊矩陣 (9):Hermitian 矩陣”)。若所有 都是實數,則 ,實 Hermitian 矩陣即為實對稱矩陣。Hermitian 矩陣和實對稱矩陣是目前應用最廣的特殊矩陣,原因有二:它們具備許多美好的特徵分析性質 (見“實對稱矩陣可正交對角化的證明”,“Hermitian 矩陣特徵值的變化界定”),以及它們「天生地」出現在多樣應用場合。下面列舉一些實例,包括 Hessian 矩陣、共變異數矩陣、鄰接矩陣、二次型和雙線性形式。

Posted in 線性代數專欄, 二次型 | Tagged , , , , , , , , | Leave a comment

渡河問題

本文的閱讀等級:初級 傳教士與食人族問題 (Missionaries and cannibals problem) 是一個典型的渡河問題,簡述如下: 三個傳教士和三個食人族土著一起渡河,小船一次僅能載二人。不論此岸或彼岸,如果土著人數多於傳教士人數,土人便會吃掉傳教士。當然,小船來回都必須有人操作。問路程最短的安全渡河法?又共有多少種方式? 本文介紹如何利用圖論方法建立分析模型,並以矩陣運算求得解答。閱讀前,讀者可於下列網站線上作答:http://www.plastelina.net/examples/games/game2.html

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

線性代數在圖論的應用 (一):鄰接矩陣

本文的閱讀等級:初級 針對給定的一個有限集合,集合裡的元素之間常存在某種關係。例如,一個國家中城市之間的飛航路線,產業聚落中公司之間的產品供應鏈,以及社交網路服務網站,如 Facebook,MySpace 的社群人際關係。圖論 (graph theory) 是一門描述集合裡元素彼此關係的數學領域,上述這些問題都可架構於圖論模型以利分析。

Posted in 線性代數專欄, 圖論, 應用之道 | Tagged , , , , , , , | Leave a comment