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{cases}\deg(v_{i})&{\mbox{dla}}\ i=j\\-1&{\mbox{dla}}\ i\neq j\ {\mbox{ oraz }}v_{i}{\text{ sasiaduje z }}v_{j}\\0&{\text{w pozostalych przypadkach}}\end{cases}}.

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

Przykład

Tworzymy laplasjan grafu:

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₁₁:

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).