Twierdzenie Kirchhoffa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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 A11:
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[edytuj | edytuj kod]

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