檢視矩陣樹定理的原始碼

佇圖論內底，'''基爾霍夫定理（Kirchhoff theorem）'''抑是'''矩陣樹定理（matrix tree theorem）'''是指圖的生做樹數量等於調佮矩陣的行列式（所以需要時間多項式計算）。

若是 _ G _ 有 _ n _ 頂點，_ λ _ 一 ,   _ λ _ 二 ,   . . . ,   _ λn _ 鋪一是拉普拉斯矩陣的非零特徵值，著


: $ t ( G )={ \ frac { 一 } { n } } \ lambda _ { 一 } \ lambda _ { 二 } \ cdots \ lambda _ { n 影一 } . $

這个定理以基爾霍夫名號名。這嘛是凱萊公式的推廣（若圖是完全圖）。

==舉例==


: $ Q=\ left [{ \ begin { array } { rrrr } 二 & 影一 & 影一 & 零 \ \ 影一 & 三 & 影一 & 影一 \ \ 影一 & 影一 & 三 & 影一 \ \ 零 & 影一 & 影一 & 二 \ end { array } } \ right] . $

刪除任何一个行佮一个列，比如講第一行佮第一列：


: $ Q ^ { \ ast }=\ left [{ \ begin { array } { rrr } 三 & 影一 & 影一 \ \ 影一 & 三 & 影一 \ \ 影一 & 影一 & 二 \ end { array } } \ right] . $

著

$ $
\ det ( Q ^ { * } )=八=t ( G )
$ $

接續矩陣是

$ $
K={ \ begin { bmatrix } 一 & 一 & 零 & 零 & 零 \ \ 影一 & 零 & 一 & 一 & 零 \ \ 零 & 影一 & 影一 & 零 & 一 \ \ 零 & 零 & 零 & 影一 & 影一 \ \ \ end { bmatrix } } .
$ $

===凱萊公式===

完全圖 _ Kn _ 伊的調佮矩陣是


: $ { \ begin { bmatrix } n 影一 & 影一 & \ cdots & 影一 \ \ 影一 & n 影一 & \ cdots & 影一 \ \ \ vdots & \ vdots & \ ddots & \ vdots \ \ 影一 & 影一 & \ cdots & n 影一 \ \ \ end { bmatrix } } . $

任何餘因子的行列式是 _ nn-_ 二。閣再講 L 的所有特徵值是 n，而且 L 只有 n 糊一个特徵向量。所以成樹仔的總數閣是 _ nn-_ 二。

==證明大綱==

拉氏矩陣有這个屬性：任何行抑是列的元素總佮等於零。所以乎，無論刪除啥物行抑列，$ \ det ( L ^ { * } ) $ 攏是不變的。抑是講 L 的任何餘因為有仝款的行列式。

若是 K 是接續矩陣，_ L _=KKT。佇矩陣 K 中，刪除任何一條行抑是列得著矩陣 F。設 _ FF _ T=_ M 十一 _。

用柯西奈式


: $ \ det \ left ( M _ { 十一 } \ right )=\ sum _ { S } \ det \ left ( F _ { S } \ right ) \ det \ left ( F _ { S } ^ { T } \ right )=\ sum _ { S } \ det \ left ( F _ { S } \ right ) ^ { 二 } $

會當表示這个行列式予生做樹仔的數量。

==參見==

* 普呂舒序列
* 細漢生做樹仔

==閱讀==

* Harris , John M . ; Hirst , Jeffry L . ; Mossinghoff , Michael J . , Combinatorics and Graph Theory , Undergraduate Texts in Mathematics 二 nd , Springer , 兩千空八
* Maurer , Stephen B . , Matrix generalizations of some theorems on trees , cycles and cocycles in graphs , SIAM Journal on Applied Mathematics , 一千九百七十六 ,'''三十'''( 一 ) : 一百四十三–一百四十八 , MR  三十九石兩千六百三十五 , doi : 十 . 十三抹空一十七分之一千一百三十七   .
* Tutte , W . T . , Graph Theory , Cambridge University Press : 一百三十八 , 兩千空一 , ISBN  九百七十八追空抹五百二十一孵七鋪九千四百八十九鼻三   .
* Chaiken , S . ; Kleitman , D . , Matrix Tree Theorems , Journal of Combinatorial Theory , Series A , 一千九百七十八 ,'''二十四'''( 三 ) : 三百七十七–三百八十一 , ISSN  九十七孵三千一百六十五 , doi : 十 . 九十七分之一千空一十六嬸三千一百六十五 ( 七十八 ) 九九四空六十七孵五

==參考文獻==

[[分類: 待校正]]