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 ${\displaystyle G}$ będzie spójnym grafem nieskierowanym o ${\displaystyle n}$ wierzchołkach ${\displaystyle v_{1},v_{2},\dots ,v_{n}.}$ Niech ${\displaystyle A}$ będzie laplasjanem grafu, czyli macierzą ${\displaystyle n\times n,}$ taką że:

${\displaystyle a_{ij}={\begin{cases}\deg(v_{i})&{\mbox{dla}}\ i=j\\-1&{\mbox{dla}}\ i\neq j\ {\mbox{ oraz }}v_{i}{\text{ sąsiaduje z }}v_{j}\\0&{\text{w pozostałych przypadkach}}\end{cases}}.}$

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

Przykład

• Tworzymy laplasjan grafu:

${\displaystyle A=\left[{\begin{array}{r}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₁₁:

${\displaystyle A_{11}=(-1)^{1+1}\cdot \left|{\begin{array}{r}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

• Donald Ervin Knuth: Sztuka programowania. T. 1. Algorytmy podstawowe. z angielskiego przełożył Grzegorz Jakacki. Warszawa: Wydawnictwa Naukowo-Techniczne, 2002. ISBN 83-204-2540-9 (t. 1).