Twierdzenie Kirchhoffa

Twierdzenie Kirchhoffa (twierdzenie macierzowe o drzewach) to 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, \ldots, v_n$. Niech A będzie laplasjanem grafu, czyli macierzą n×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

Przykładowy graf

• Tworzymy laplasjan grafu:

$A = \left[\begin{array}{rrrrrr} 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}{rrrrr} 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).