Kirchhoff matriisi

Kirchhoff -matriisi on yksi matriisia käyttävän äärellisen graafin esityksistä . Kirchhoff-matriisi edustaa graafin diskreettiä Laplace-operaattoria . Sitä käytetään tietyn graafin virittävien puiden laskemiseen ( matriisipuulause ) ja myös spektrigraafiteoriassa .

Määritelmä

Annettu yksinkertainen graafi , jossa on pisteitä. Sitten annetun graafin Kirchhoff-matriisi määritellään seuraavasti: $\G$ $\ |V(G)|=n$ ${\displaystyle \ K=(k_{i,j})_{n\times n))$

\ k_{i,j}:={\begin{cases}\deg(v_{i}),&{\text{if}}\ i=j,\\-1,&{\text{ if}}\ (v_{i},v_{j})\in E(G),\\0,&{\teksti{muutoin}}.\end{cases}}

Myös Kirchhoff-matriisi voidaan määritellä matriisien erotukseksi

{\näyttötyyli \ K=DA,}

missä on annetun graafin vierekkäisyysmatriisi ja on matriisi, jonka päädiagonaalissa ovat graafin kärkien asteet ja loput alkiot ovat nollia: $\A$ ${\displaystyle \ D=(d_{i,j})_{n\times n))$

\ d_{i,j}:={\begin{cases}\deg(v_{i}),&{\text{if}}\ i=j,\\0,&{\text{muuten }}.\end{cases}}

Jos kuvaaja on painotettu , Kirchhoff-matriisin määritelmä yleistetään. Tässä tapauksessa Kirchhoff-matriisin päädiagonaalin alkiot ovat vastaavaan kärkeen osuvien reunojen painojen summa. Vierekkäisille (liitetyille) kärkipisteille , missä on reunan paino (johtavuus). Erilaisille ei-viereisille (ei-liittyneille) kärkeille , . $\k_{i,j}=-c(v_{i},v_{j})$ $\ c(v_{i},v_{j})$ $\k_{i,j}=0$

\ k_{i,j}:={\begin{cases}\sum \limits _{\begin{smallmatrix}u\in V(G)\\(v_{i},u)\in E( G)\end{smallmatrix}}\!\!\!\!\!\!c(v_{i},u),&{\text{if}}\ i=j,\\-c(v_{ i},v_{j}),&{\text{if}}\ (v_{i},v_{j})\in E(G),\\0,&{\teksti{muutoin}}.\ lopeta{tapaukset}}

Painotetussa graafissa viereisyysmatriisi kirjoitetaan ottaen huomioon reunojen johtavuudet, ja matriisin päädiagonaalissa on vastaaviin kärkikohtiin osuvien reunojen johtavuuksien summat. $\A$ $\D$

\ d_{i,j}:={\begin{cases}\sum \limits _{\begin{smallmatrix}u\in V(G)\\(v_{i},u)\in E( G)\end{smallmatrix}}\!\!\!\!\!\!c(v_{i},u),&{\text{if}}\ i=j,\\0,&{\ teksti{muuten}}.\end{cases}}

Esimerkki

Esimerkki Kirchhoff-matriisista yksinkertaiselle graafille.

Merkitty kaavio	Kirchhoff matriisi
	$\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)$

Ominaisuudet

Kirchhoff-matriisin jokaisen rivin (sarakkeen) elementtien summa on nolla: $\ \sum _{i=1}^{|V(G)|}k_{i,j}=0$ .

Kirchhoff-matriisin determinantti on nolla: $\det K=0$

Yksinkertaisen graafin Kirchhoff-matriisi on symmetrinen : $\ k_{i,j}=k_{j,i}\quad i,j=1,\ldots ,|V(G)|$ .

Kaikki symmetrisen Kirchhoff-matriisin algebralliset komplementit ovat keskenään yhtä suuret - Kirchhoff-matriisin vakio . Yksinkertaisessa graafissa tietyn vakion arvo on sama kuin graafin kaikkien mahdollisten runkojen lukumäärä (katso Matriisipuulause ). ${\näyttötyyli \ K_{(ij)))$

Jos painotettu graafi on sähköverkko, jossa kunkin reunan paino vastaa sen johtavuutta , niin Kirchhoff-matriisin minorit mahdollistavat pisteiden ja annetun verkon välisen resistiivisen etäisyyden laskemisen: ${\displaystyle \ R_{ij))$ $\i$ ${\näyttötyyli \j}$ ${\displaystyle \ R_{ij}={\frac {K^{(i,j))){K_{(ij)))))$ , tässä on Kirchhoff-matriisin vakio (algebrallinen komplementti), ja se on 2. kertaluvun algebrallinen komplementti, eli matriisin determinantti, joka saadaan Kirchhoff-matriisista poistamalla kaksi riviä ja kaksi saraketta . ${\näyttötyyli \ K_{(ij)))$ ${\näyttötyyli \ K^{(i,j)))$ ${\näyttötyyli \i,j}$

Kirchhoff-matriisin palauttamiseksi resistanssimatriisista on olemassa algoritmi . $R_{ij}$
0 on matriisin ominaisarvo (vastaava ominaisvektori on kaikki ykköset), sen monikertaisuus on yhtä suuri kuin graafin yhdistettyjen komponenttien lukumäärä.
Loput ominaisarvot ovat positiivisia. Fiedler kutsui toiseksi pienintä arvoa graafin yhteysindeksiksi, vastaava ominaisvektori on Fiedler-vektori (ei pidä sekoittaa Randic-graafin yhteysindeksiin ).

Kirchhoff matriisi

Määritelmä

Esimerkki

Ominaisuudet

Katso myös