矩陣樹定理
佇圖論內底，基爾霍夫定理（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 : 十 . 九十七分之一千空一十六嬸三千一百六十五 ( 七十八 ) 九九四空六十七孵五