Kirchhoff matrix

Kirchhoff -matricen er en af repræsentationerne af en endelig graf ved hjælp af en matrix. Kirchhoff-matricen repræsenterer den diskrete Laplace-operator for en graf. Det bruges til at tælle spændingstræerne i en given graf ( matrixtræsætning ), og også i spektralgrafteori .

Definition

Givet en simpel graf med toppunkter. Så vil Kirchhoff-matricen for den givne graf blive defineret som følger: $\G$ $\ |V(G)|=n$ ${\displaystyle \ K=(k_{i,j})_{n\ gange 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{ellers}}.\end{cases}}

Kirchhoff-matricen kan også defineres som forskellen mellem matricer

\ K=DA,

hvor er nabomatrixen for den givne graf, og er matrixen, på hvis hoveddiagonal er graderne af grafens hjørner, og de resterende elementer er nuller: $\EN$ ${\displaystyle \ D=(d_{i,j})_{n\ gange n))$

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

Hvis grafen er vægtet , så generaliseres definitionen af Kirchhoff-matricen. I dette tilfælde vil elementerne i Kirchhoff-matricens hoveddiagonal være summen af vægtene af kanterne, der falder ind på det tilsvarende toppunkt. For tilstødende (forbundne) hjørner , hvor er vægten (ledningsevnen) af kanten. For forskellige ikke-tilstødende (ikke-forbundne) hjørner , . $\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{lillematrix}}\!\!\!\!\!\!c(v_{i},u),&{\text{if}}\ i=j,\\-c(v_{ i},v_{j}),&{\text{if}}\ (v_{i},v_{j})\i E(G),\\0,&{\text{ellers}}.\ slut{cases}}

For en vægtet graf skrives tilstødende matrix under hensyntagen til kanternes ledningsevne, og på matrixens hoveddiagonal vil der være summen af ledningsevnerne af kanterne, der falder ind på de tilsvarende toppunkter. $\EN$ $\D$

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

Eksempel

Et eksempel på en Kirchhoff-matrix til en simpel graf.

Mærket graf	Kirchhoff matrix
	$\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)$

Egenskaber

Summen af elementerne i hver række (søjle) i Kirchhoff-matricen er nul: $\ \sum _{i=1}^{|V(G)|}k_{i,j}=0$ .

Determinanten for Kirchhoff-matricen er nul: $\det K=0$

Kirchhoff-matricen af en simpel graf er symmetrisk : $\ k_{i,j}=k_{j,i}\quad i,j=1,\ldots ,|V(G)|$ .

Alle algebraiske komplementer af den symmetriske Kirchhoff-matrix er lig med hinanden - konstanten af Kirchhoff-matricen. For en simpel graf er værdien af en given konstant den samme som antallet af alle mulige skeletter i grafen (se Matrix-træsætning ). ${\displaystyle \ K_{(ij)))$

Hvis den vægtede graf er et elektrisk netværk, hvor vægten af hver kant svarer til dens ledningsevne , så tillader minorerne i Kirchhoff-matricen os at beregne den resistive afstand mellem punkterne og af det givne netværk: $\ R_{ij}$ $\jeg$ $\j$ ${\displaystyle \ R_{ij}={\frac {K^{(i,j))){K_{(ij)))))$ , her er konstanten (algebraisk komplement) af Kirchhoff-matricen, og er det algebraiske komplement af 2. orden, det vil sige determinanten for matricen opnået fra Kirchhoff-matricen ved at slette to rækker og to kolonner . ${\displaystyle \ K_{(ij)))$ ${\displaystyle \ K^{(i,j)))$ $\i,j$

Der er en algoritme til at gendanne Kirchhoff-matricen fra modstandsmatrixen . $R_{ij}$
0 er en egenværdi af matricen (den tilsvarende egenvektor er alle enere), dens multiplicitet er lig med antallet af forbundne komponenter i grafen.
Resten af egenværdierne er positive. Fiedler kaldte den næstmindste værdi for grafforbindelsesindekset, den tilsvarende egenvektor er Fiedler-vektoren (ikke at forveksle med forbindelsesindekset for den randiske graf ).

Kirchhoff matrix

Definition

Eksempel

Egenskaber

Se også