Tag Archives: 圖論

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

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

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

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