Kirchhoffova matice

Kirchhoffova matice je jednou z reprezentací konečného grafu pomocí matice. Kirchhoffova matice představuje diskrétní Laplaceův operátor pro graf. Používá se k počítání kostry daného grafu ( teorém maticového stromu ) a také v teorii spektrálních grafů .

Definice

Daný jednoduchý graf s vrcholy. Poté bude Kirchhoffova matice daného grafu definována takto: $\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})\v E(G),\\0,&{\text{jinak}}.\end{cases}}

Kirchhoffovu matici lze také definovat jako rozdíl matic

\ K=DA,

kde je matice sousednosti daného grafu a je matice, na jejíž hlavní diagonále jsou stupně vrcholů grafu a zbývající prvky jsou nuly: $\A$ ${\displaystyle \ D=(d_{i,j})_{n\times n))$

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

Pokud je graf vážený , pak se definice Kirchhoffovy matice zobecní. V tomto případě budou prvky hlavní úhlopříčky Kirchhoffovy matice součtem vah hran dopadajících na odpovídající vrchol. Pro sousední (spojené) vrcholy , kde je hmotnost (vodivost) hrany. Pro různé nesousedící (nespojené) vrcholy , . $\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})\v E(G),\\0,&{\text{jinak}}.\ end{cases}}

Pro vážený graf je matice sousednosti zapsána s přihlédnutím k vodivosti hran a na hlavní diagonále matice budou součty vodivosti hran dopadajících na odpovídající vrcholy. $\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{jinak}}.\end{cases}}

Příklad

Příklad Kirchhoffovy matice pro jednoduchý graf.

Označený graf	Kirchhoffova matice
	$\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)$

Vlastnosti

Součet prvků každého řádku (sloupce) Kirchhoffovy matice je nula: $\ \sum _{i=1}^{|V(G)|}k_{i,j}=0$ .

Determinant Kirchhoffovy matice je nula: $\det K=0$

Kirchhoffova matice jednoduchého grafu je symetrická : $\ k_{i,j}=k_{j,i}\quad i,j=1,\ldots ,|V(G)|$ .

Všechny algebraické doplňky symetrické Kirchhoffovy matice jsou si navzájem rovny - konstanta Kirchhoffovy matice. Pro jednoduchý graf je hodnota dané konstanty stejná jako počet všech možných koster grafu (viz věta o maticovém stromu ). ${\displaystyle \ K_{(ij)))$

Pokud je váženým grafem elektrická síť, kde váha každé hrany odpovídá její vodivosti , pak nám minority Kirchhoffovy matice umožňují vypočítat odporovou vzdálenost mezi body a dané sítě: $\ R_{ij}$ $\i$ $\j$ ${\displaystyle \ R_{ij}={\frac {K^{(i,j))){K_{(ij)))))$ , zde je konstanta (algebraický doplněk) Kirchhoffovy matice a je algebraický doplněk 2. řádu, tedy determinant matice získaný z Kirchhoffovy matice vymazáním dvou řádků a dvou sloupců . ${\displaystyle \ K_{(ij)))$ ${\displaystyle \ K^{(i,j)))$ $\i,j$

Existuje algoritmus pro obnovu Kirchhoffovy matice z matice odporu . $R_{ij}$
0 je vlastní hodnota matice (odpovídající vlastní vektor jsou všechny jedničky), její násobnost je rovna počtu spojených složek grafu.
Zbytek vlastních čísel je kladný. Fiedler nazval druhou nejmenší hodnotu index konektivity grafu, odpovídajícím vlastním vektorem je Fiedlerův vektor (neplést s indexem konektivity Randicova grafu ).

Kirchhoffova matice

Definice

Příklad

Vlastnosti

Viz také