Twierdzenie Kirchhoffa

Twierdzenie Kirchhoffa (twierdzenie macierzowe o drzewach) – twierdzenie matematyczne z teorii grafów nazwane na cześć Gustava Kirchhoffa, mówiące o liczbie drzew rozpinających w grafie. Jest ono uogólnieniem wzoru Cayleya o liczbie drzew rozpinających w grafie pełnym.

Treść twierdzenia

Niech $G$ będzie spójnym grafem nieskierowanym o $n$ wierzchołkach $v_1,v_2,\dots ,v_n.$ Niech $A$ będzie laplasjanem grafu, czyli macierzą $n\times n,$ taką że:

$a_{ij}=\{\begin{array}{cc}\mathrm{deg}(v_i)& \text{dla}i=j\\ -1& \text{dla}i\ne j\text{ oraz }{v}_i\text{ sasiaduje z }{v}_j\\ 0& \text{w pozostalych przypadkach}\end{array}.$

Wtedy liczba wszystkich drzew rozpinających grafu $G$ będzie równa dopełnieniu algebraicznemu dowolnego wyrazu macierzy $A.$

Przykład

Przykładowy graf

• Tworzymy laplasjan grafu:

$A=\left[\begin{array}{cccccc}2& -1& 0& 0& -1& 0\\ -1& 3& -1& 0& -1& 0\\ 0& -1& 2& -1& 0& 0\\ 0& 0& -1& 3& -1& -1\\ -1& -1& 0& -1& 3& 0\\ 0& 0& 0& -1& 0& 1\end{array}\right].$

• Obliczamy dopełnienie algebraiczne dowolnego elementu macierzy, w tym przypadku będzie to A₁₁:

$A_{11}=(-1{)}^{1+1}\cdot \left|\begin{array}{ccccc}3& -1& 0& -1& 0\\ -1& 2& -1& 0& 0\\ 0& -1& 3& -1& -1\\ -1& 0& -1& 3& 0\\ 0& 0& -1& 0& 1\end{array}\right|=11.$

Dla przykładowego grafu możemy uzyskać 11 drzew rozpinających.

Bibliografia

• Szablon:Cytuj książkę