Матриця Кірхгофа

Матриця Кірхгофа (Шаблон:Lang-en) — один з методів подання графа за допомогою матриці. Матриця Кірхгофа використовується для підрахунку кістякових дерев графа, а також у спектральній теорії графів.

Визначення

Дано простий граф$G$ з $|V(G)|=n$ вершинами. Тоді матриця Кірхгофа $K=(k_{i,j}{)}_{n\times n}$ цього графа буде визначатися так:

$k_{i,j}:=\{\begin{array}{cc}\mathrm{deg}(v_i)& \text{if}i=j,\\ -1& \text{if}(v_i,v_j)\in E(G),\\ 0& \text{otherwise}.\end{array}$

Також матрицю Кірхгофа можна визначити як різницю матриць $K=D-A,$ де $A$ — це матриця суміжності цього графа, а $D=(d_{i,j}{)}_{n\times n}$ — матриця, на головній діагоналі якої степені вершин графа, а решта елементів — нулі:

$d_{i,j}:=\{\begin{array}{cc}\mathrm{deg}(v_i)& \text{if}i=j,\\ 0& \text{otherwise}.\end{array}$

Якщо граф є зваженим, то визначення матриці Кірхгофа узагальнюється. У цьому випадку елементами головної діагоналі матриці Кірхгофа будуть суми ваг ребер, інцидентних відповідній вершині. Для суміжних (пов'язаних) вершин $k_{i,j}=-c(v_i,v_j)$, де $c(v_i,v_j)$ — це вага (провідність) ребра. Для різних не суміжних (не пов'язаних) вершин покладається $k_{i,j}=0$.

$k_{i,j}:=\{\begin{array}{cc}\sum _{\begin{array}{c}u\in V(G)\\ (v_i,u)\in E(G)\end{array}}^{}c(v_i,u)& \text{if}i=j,\\ -c(v_i,v_j)& \text{if}(v_i,v_j)\in E(G),\\ 0& \text{otherwise}.\end{array}$

Для зваженого графа матриця суміжності $A$ записується з урахуванням провідностей ребер, а на головній діагоналі матриці $D$ будуть суми провідностей ребер, інцидентних відповідним вершинам.

$d_{i,j}:=\{\begin{array}{cc}\sum _{\begin{array}{c}u\in V(G)\\ (v_i,u)\in E(G)\end{array}}^{}c(v_i,u)& \text{if}i=j,\\ 0& \text{otherwise}.\end{array}$

Приклад

Приклад матриці Кірхгофа простого графа.

Розмічений граф	Матриця Кірхгофа
	$\left(\begin{array}{cccccc}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)$

Властивості

• Сума елементів кожного рядка (стовпця) матриці Кірхгофа дорівнює нулю:

  $\sum _{i=1}^{|V(G)|}{k}_{i,j}=0$.

• Визначник матриці Кірхгофа дорівнює нулю:

  $\det K=0$

• Матриця Кірхгофа простого графа симетрична:

  $k_{i,j}=k_{j,i}i,j=1,\dots ,|V(G)|$.

• Всі алгебраїчні доповнення $K_{(ij)}$ симетричної матриці Кірхгофа рівні між собою — стала матриці Кірхгофа. Для простого графа значення цієї сталої збігається з числом всіх можливих кістяків графа.

• Якщо зважений граф являє собою електричну мережу, де вага кожного ребра відповідає його провідності, то мінори матриці Кірхгофа дозволяють обчислити резистивні відстані $R_{ij}$ між точками $i$ і $j$ даної мережі:

  $R_{ij}=\frac{K^{(i,j)}}{K_{(ij)}}$,

тут $K_{(ij)}$ — стала (алгебраїчне доповнення) матриці Кірхгофа, а $K^{(i,j)}$ — алгебраїчне доповнення 2-го порядку, тобто визначник матриці, отримуваної з матриці Кірхгофа викреслюванням двох рядків і двох стовпців$i,j$.

• Існує алгоритм відновлення матриці Кірхгофа за матрицею опорів $R_{ij}$.
  • 0 є власним значенням матриці (відповідний власний вектор — всі одиниці), кратність його дорівнює числу зв'язних компонент графа.
  • Інші власні значення додатні. Друге за малістю значення Шаблон:Нп назвав індексом зв'язності графа, відповідний власний вектор — вектор Фідлера.

Див. також

• Матрична теорема про дерева
• Матриця суміжності
• Степенева матриця
• Матриця інцидентності
• Дискретна математика
• Алгебрична_зв'язність
• Провідність графа