Twierdzenie Kirchhoffa


Twierdzenie Kirchhoffa w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

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

Niech G {\displaystyle G} będzie spójnym grafem nieskierowanym o n {\displaystyle n} wierzchołkach v 1 , v 2 , , v n . {\displaystyle v_{1},v_{2},\dots ,v_{n}.} Niech A {\displaystyle A} będzie laplasjanem grafu, czyli macierzą n × n , {\displaystyle n\times n,} taką że:

a i j = { deg ( v i ) dla   i = j 1 dla   i j    oraz  v i  sasiaduje z  v j 0 w pozostalych przypadkach . {\displaystyle 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 {\displaystyle G} będzie równa dopełnieniu algebraicznemu dowolnego wyrazu macierzy A . {\displaystyle A.}

Przykład | edytuj kod

Przykładowy graf
  • Tworzymy laplasjan grafu:
A = 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 . {\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 A11:
A 11 = ( 1 ) 1 + 1 | 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 | = 11. {\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 | 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).
Na podstawie artykułu: "Twierdzenie Kirchhoffa" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy