Twierdzenie Kirchhoffa

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.

Graf pełny jest grafem prostym, w którym dla każdej pary węzłów istnieje krawędź je łącząca. Graf pełny o n {displaystyle n} wierzchołkach oznacza się następująco: K n {displaystyle K_{n}} .Twierdzenie to sformalizowana wypowiedź sądu, stosowana we wszystkich naukach ścisłych, składająca się z dwóch zbiorów zdań, które łączy relacja implikacji. Pierwszy zbiór zdań określa ściśle warunki dla których dane twierdzenie jest spełnione i nazywa się założeniem twierdzenia, a drugi zbiór zdań jest właściwym sądem, będącym istotną treścią wypowiadanego twierdzenia i zwany jest tezą twierdzenia.

Treść twierdzenia[ | edytuj kod]

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

Operator Laplace’a (laplasjan) – operator różniczkowy drugiego rzędu, szczególnie ważny element klasy operatorów eliptycznych. Jego nazwa pochodzi od nazwiska Pierre’a Simona de Laplace’a.Drzewem rozpinającym (ang. Spanning Tree) grafu G nazywamy drzewo, które zawiera wszystkie wierzchołki grafu G, zaś zbiór krawędzi drzewa jest podzbiorem zbioru krawędzi grafu.

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

Macierz – w matematyce układ liczb, symboli lub wyrażeń zapisanych w postaci prostokątnej tablicy. Choć słowo „macierz” oznacza najczęściej macierz dwuwskaźnikową, to możliwe jest rozpatrywanie macierzy wielowskaźnikowych (zob. notacja wielowskaźnikowa). Macierze jednowskaźnikowe nazywa się często wektorami wierszowymi lub kolumnowymi, co wynika z zastosowań macierzy w algebrze liniowej. W informatyce macierze modeluje się zwykle za pomocą (najczęściej dwuwymiarowych) tablic.Gustav Robert Kirchhoff (ur. 12 marca 1824 Królewiec, zm. 17 października 1887 Berlin) – niemiecki fizyk, twórca prawa promieniowania cieplnego dotyczącego zależności między zdolnością emisyjną i absorpcyjną, oraz praw dotyczących obwodów elektrycznych (pierwsze i drugie prawo Kirchhoffa). Razem z Robertem W. Bunsenem odkryli cez i rubid, wynaleźli spektroskop, a także opracowali metody analizy spektralnej.

Przykład[ | edytuj kod]

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.

    Matematyka (z łac. mathematicus, od gr. μαθηματικός mathēmatikós, od μαθηματ-, μαθημα mathēmat-, mathēma, „nauka, lekcja, poznanie”, od μανθάνειν manthánein, „uczyć się, dowiedzieć”; prawd. spokr. z goc. mundon, „baczyć, uważać”) – nauka dostarczająca narzędzi do otrzymywania ścisłych wniosków z przyjętych założeń, zatem dotycząca prawidłowości rozumowania. Ponieważ ścisłe założenia mogą dotyczyć najróżniejszych dziedzin myśli ludzkiej, a muszą być czynione w naukach ścisłych, technice a nawet w naukach humanistycznych, zakres matematyki jest szeroki i stale się powiększa.

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




  • Reklama