Matriisipuulause

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 2.6.2020 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Matriisipuulause tai Kirchhoffin lause - antaa lausekkeen graafin virittävien puiden lukumäärälle tietyn matriisin determinantin kautta .

Todisti Gustav Kirchhoff vuonna 1847; Tämän lauseen motiivina olivat sähköpiirien laskelmat . [yksi]

Sanamuoto

Olkoon yhdistetty merkitty graafi Kirchhoff -matriisin kanssa . Kaikki Kirchhoff-matriisin algebralliset komplementit ovat keskenään yhtä suuria ja niiden kokonaisarvo on yhtä suuri kuin graafin virittävien puiden lukumäärä . $G$ $M$ $M$ $G$

Esimerkki

kaavio	3 sen ylittäviä puita
${\begin{matrix}1&&4\\\mid &\smallsetminus &\mid \\2&-&3\end{matrix))$	${\begin{matrix}1&&4\\\mid &&\mid \\2&-&3\end{matrix}}$	${\begin{matrix}1&&4\\\mid &\smallsetminus &\mid \\2&&3\end{matrix))$	${\begin{matrix}1&&4\\&\smallsetminus &\mid \\2&-&3\end{matrix))$

Graafille G, jonka viereisyysmatriisi , saamme: . $A={\begin{bmatrix}0&1&1&0\\1&0&1&0\\1&1&0&1\\0&0&1&0\end{bmatrix}}$ $M={\begin{bmatrix}2&-1&-1&0\\-1&2&-1&0\\-1&-1&3&-1\\0&0&-1&1\end{bmatrix))$

Esimerkiksi alkion M 1, 2 algebrallinen komplementti on , joka on sama kuin virittävien puiden lukumäärä. $(-1)^{(1+2)}{\begin{vmatrix}-1&-1&0\\-1&3&-1\\0&-1&1\end{vmatrix}}=3$

Seuraukset

Matriisilauseesta se seuraa

Cayleyn kaava - kokonaisen graafin virittävien puiden lukumäärä on . $K_n$ $n^{{n-2}}$
Täydellisen kaksiosaisen graafin virittävien puiden lukumäärä on . $K_{{m,n}}$ $m^{{n-1}}\cdot n^{{m-1}}$

Yleistykset

Lause on yleistetty monigraafien ja painotettujen graafien tapaukseen. Painotetussa graafissa Kirchhoff-matriisin alkioiden algebralliset komplementit ovat yhtä suuria kuin kaikkien virittävien puiden kaikkien reunojen painojen tulojen summa. Erikoistapaus saadaan, jos otamme painot yhtä suuret kuin 1: luurankojen painojen tulojen summa on yhtä suuri kuin luurankojen lukumäärä.

Muistiinpanot

↑ Kirchhoff, Gustav. Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird (saksa) // Annalen der Physik. - 1847. - Bd. 148 , nro. 12 . - S. 497-508 .

Linkit

Kirchhoffin lause