矩陣樹定理

圖論中,矩陣樹定理(matrix tree theorem)或基爾霍夫定理(Kirchhoff theorem)是指生成樹數量等於調和矩陣餘子式(所以需要時間多項式計算)。

Gn頂點λ1λ2, ..., λn-1拉普拉斯矩陣的非零特徵值,則

這個定理以古斯塔夫·基爾霍夫名字命名。 這也是凱萊公式的推廣(若圖是完全圖)。

舉例

 
L是這個鑽石圖的拉氏矩陣
 

刪除任何一個行和一個列,比方說第一行和第一列:

 

 

接續矩陣

 

完全圖 Kn 的調和矩陣是

 

任何餘因子的行列式是 nn-2 。再說L的所有特徵值是n,而且L只有n-1個特徵向量。所以生成樹的總數又是 nn-2

證明大綱

拉氏矩陣有這個屬性:任何行或列的元素總和等於0。所以,無論刪除什麼行或列, 都是不變的。或者說L的任何餘因子有同樣的行列式。

若K是接續矩陣L = KKT。在矩陣K中,刪除任何一個行或列得到矩陣F。設 FFT = M11

使用柯西奈式[1]

 

可以表示這個行列式給予生成樹的數量。

參見

閱讀

參考文獻

  1. ^ Graphs, Matrices, Isomorphism. math.fau.edu. [2020-02-14]. (原始內容存檔於2009-03-04).