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

Определение матрицы Кирхгофа

Определение:

Матрицей Кирхгофа простого графа [math]G = (V,E) [/math] называется матрица [math] K (|V| \times |V|) = \parallel k_{i,j} \parallel [/math], элементы которой определяются равенством: [math] k_{i,j} = \begin{cases} \deg(v_i), \ i = j \\ -1, \ (v_i,v_j) \in E \\ 0, \mbox{ else}. \end{cases} [/math]

Иными словами, на главной диагонали матрицы Кирхгофа находятся степени вершин, а на пересечении i-й строки и j-го столбца ([math]i \ne j[/math]) стоит -1, если вершины с номерами i и j смежны, и 0 в противном случае.

Пример матрицы Кирхгофа

Пример матрицы Кирхгофа простого графа.

Помеченный граф	Матрица Кирхгофа
175px	[math]\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)[/math]

Некоторые свойства

1) Матрица Кирхгофа является симметрической (т.е. симметрична относительно главной диагонали).

2) Связь с матрицей смежности:

[math] K = \begin{pmatrix} deg(v_1) & 0 & \cdots & 0 \\ 0 & deg(v_2) & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & deg(v_n) \end{pmatrix} - A, [/math]

где [math]A[/math] - матрица смежности графа [math]G[/math].

3) Связь с матрицей инцидентности: [math] K = I \cdot I^T, [/math] где [math]I[/math] - матрица инцидентности с некоторой ориентацией.

Источники

Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.