Tag Archives: 圖論

克希荷夫矩陣─樹定理

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

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

答Xiaoyang Su──關於歐拉多面體公式的線性代數證法

網友Xiaoyang Su留言: 請老師指點歐拉多面體公式:頂點數+面數=邊數+2,和綫性代數中的秩─零化度定理的關係是什麽?

Posted in 答讀者問, 圖論 | Tagged , , , , | 4 Comments

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

本文的閱讀等級:中級 令 為一個無向圖 (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

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

本文的閱讀等級:初級 本文是探討電影《心靈捕手》中數學問題的完結篇。這回麻省理工學院朗博教授和威爾將聯手出擊,他們的目標要破解一道組合數學問題:求3─太陽圖 (3-sun graph) 的色多項式 (chromatic polynomial),其中 的頂點集合是 ,邊集合是 (見圖一)。

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

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

本文的閱讀等級:中級 朗博教授公告在走廊黑板的第二個挑戰問題抄錄於下: (1) How many trees are there with labeled vertices? (2) Draw all the homeomorphically irreducible trees with . 威爾的答案:(1) ,(2) 8 棵樹 (見電影劇照)。這兩個問題屬於組合數學的範疇。廣義的組合數學就是離散數學,狹義的組合數學是圖論、代數結構、數理邏輯等的總稱[1]。為了讀懂朗博教授的問題,我們先要瞭解一些關於樹 (圖論的一個主題) 的基本知識。

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

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

本文的閱讀等級:中級 美國馬里蘭大學馬尼爾‧蘇里 (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

線性代數在圖論的應用 (二):關聯矩陣

本文的閱讀等級:初級 線性代數在圖論的應用建立於圖的矩陣表達。我們曾在“線性代數在圖論的應用 (一):鄰接矩陣”討論了鄰接矩陣 (adjacency matrix),本文將介紹另一個重要的矩陣表達──關聯矩陣 (incidence matrix)。令 為一個有向圖,其中 是頂點集合, 是有向邊集合。我們以 和 分別表示頂點和邊的總數,即 ,。有序對 表示邊 的起始頂點是 ,終止頂點是 ,即 。我們定義關聯矩陣 為一 階矩陣,其中 且 若 ,其餘元為零[1]。見下例: 此圖的關聯矩陣為 。

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

渡河問題

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

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