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

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

Визначення

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

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

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

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

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

$\ k_{i,j}:={\begin{cases}\sum _{\begin{smallmatrix}u\in V(G)\\(v_{i},u)\in E(G)\end{smallmatrix}}^{}c(v_{i},u)&{\mbox{if}}\ i=j,\\-c(v_{i},v_{j})&{\mbox{if}}\ (v_{i},v_{j})\in E(G),\\0&{\mbox{otherwise}}.\end{cases}}$

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

$\ d_{i,j}:={\begin{cases}\sum _{\begin{smallmatrix}u\in V(G)\\(v_{i},u)\in E(G)\end{smallmatrix}}^{}c(v_{i},u)&{\mbox{if}}\ i=j,\\0&{\mbox{otherwise}}.\end{cases}}$

Приклад

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

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

Властивості

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

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

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

  $\det K=0$

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

  $\ k_{i,j}=k_{j,i}\quad i,j=1,\ldots ,|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 є власним значенням матриці (відповідний власний вектор — всі одиниці), кратність його дорівнює числу зв'язних компонент графа.
  • Інші власні значення додатні. Друге за малістю значення Мирослав Фідлер назвав індексом зв'язності графа, відповідний власний вектор — вектор Фідлера.

Див. також

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