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]

Niech G będzie spójnym grafem nieskierowanym o n wierzchołkach . Niech A będzie laplasjanem grafu, czyli macierzą n×n, taką że:

.

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

Przykład[edytuj]

Przykładowy graf
  • Tworzymy laplasjan grafu:
  • Obliczamy dopełnienie algebraiczne dowolnego elementu macierzy, w tym przypadku będzie to A11:
.

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

Bibliografia[edytuj]

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