Kirchhoff matris

Kirchhoff- matrisen är en av representationerna av en finit graf som använder en matris. Kirchhoff-matrisen representerar den diskreta Laplace-operatorn för en graf. Det används för att räkna spännträden i en given graf ( matristrädssatsen ), och även i spektralgrafteori .

Definition

Givet en enkel graf med hörn. Då kommer Kirchhoff-matrisen för den givna grafen att definieras enligt följande: $\G$ $\ |V(G)|=n$ ${\displaystyle \ K=(k_{i,j})_{n\ gånger n))$

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

Kirchhoff-matrisen kan också definieras som skillnaden mellan matriser

\ K=DA,

var är närliggande matris för den givna grafen, och är matrisen, på vars huvuddiagonal är graderna av grafens hörn, och de återstående elementen är nollor: $\A$ ${\displaystyle \ D=(d_{i,j})_{n\ gånger n))$

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

Om grafen är viktad , är definitionen av Kirchhoff-matrisen generaliserad. I detta fall kommer elementen i Kirchhoff-matrisens huvuddiagonal att vara summan av vikterna av kanterna som faller in mot motsvarande vertex. För intilliggande (anslutna) hörn , var är vikten (ledningsförmågan) av kanten. För olika icke-angränsande (icke-anslutna) hörn , . $\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})\i E(G),\\0,&{\text{annars}}.\ slut{cases}}

För en viktad graf skrivs närliggande matris med hänsyn till kanternas ledningsförmåga, och på matrisens huvuddiagonal kommer det att finnas summan av konduktiviteterna för kanterna som faller mot motsvarande hörn. $\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,&{\ text{annat}}.\end{case}}

Exempel

Ett exempel på en Kirchhoff-matris för en enkel graf.

Märkt graf	Kirchhoff matris
	$\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)$

Egenskaper

Summan av elementen i varje rad (kolumn) i Kirchhoff-matrisen är noll: $\ \sum _{i=1}^{|V(G)|}k_{i,j}=0$ .

Determinanten för Kirchhoff-matrisen är noll: $\det K=0$

Kirchhoff-matrisen för en enkel graf är symmetrisk : $\ k_{i,j}=k_{j,i}\quad i,j=1,\ldots ,|V(G)|$ .

Alla algebraiska komplement av den symmetriska Kirchhoff-matrisen är lika med varandra - konstanten för Kirchhoff-matrisen. För en enkel graf är värdet på en given konstant detsamma som antalet av alla möjliga skelett i grafen (se Matristrädsatsen ). ${\displaystyle \ K_{(ij)))$

Om den viktade grafen är ett elektriskt nätverk, där vikten av varje kant motsvarar dess ledningsförmåga , tillåter de mindre i Kirchhoff-matrisen oss att beräkna det resistiva avståndet mellan punkterna och det givna nätverket: $\ R_{ij}$ $\i$ $\j$ ${\displaystyle \ R_{ij}={\frac {K^{(i,j))){K_{(ij)))))$ , här är konstanten (algebraiskt komplement) för Kirchhoff-matrisen, och är det algebraiska komplementet av 2:a ordningen, det vill säga determinanten för matrisen som erhålls från Kirchhoff-matrisen genom att ta bort två rader och två kolumner . ${\displaystyle \ K_{(ij)))$ ${\displaystyle \ K^{(i,j)))$ $\i,j$

Det finns en algoritm för att återställa Kirchhoff-matrisen från resistansmatrisen . $R_{ij}$
0 är ett egenvärde för matrisen (motsvarande egenvektor är alla ettor), dess multiplicitet är lika med antalet sammankopplade komponenter i grafen.
Resten av egenvärdena är positiva. Fiedler kallade det näst minsta värdet för grafens anslutningsindex, motsvarande egenvektor är Fiedler-vektorn (inte att förväxla med anslutningsindexet för den randiska grafen ).

Kirchhoff matris

Definition

Exempel

Egenskaper

Se även