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

Матрица Кирхгофа — одно из представлений конечного графа с помощью матрицы. Матрица Кирхгофа представляет дискретный оператор Лапласа для графа. Она используется для подсчета остовных деревьев данного графа (матричная теорема о деревьях), а также в спектральной теории графов.

Определение

Дан простой граф [math]\displaystyle{ \ G }[/math] с [math]\displaystyle{ \ |V(G)| = n }[/math] вершинами. Тогда матрица Кирхгофа [math]\displaystyle{ \ K = (k_{i,j})_{n \times n} }[/math] данного графа будет определяться следующим образом:

[math]\displaystyle{ \ k_{i,j}:= \begin{cases} \deg(v_i), & \text{если}\ i = j, \\ -1, & \text{если}\ (v_i,v_j) \in E(G), \\ 0, & \text{иначе}. \end{cases} }[/math]

Также матрицу Кирхгофа можно определить как разность матриц

[math]\displaystyle{ \ K = D - A, }[/math]

где [math]\displaystyle{ \ A }[/math] — это матрица смежности данного графа, а [math]\displaystyle{ \ D = (d_{i,j})_{n \times n} }[/math] — матрица, на главной диагонали которой степени вершин графа, а остальные элементы — нули:

[math]\displaystyle{ \ d_{i,j}:= \begin{cases} \deg(v_i), & \text{если}\ i = j, \\ 0, & \text{иначе}. \end{cases} }[/math]

Если граф является взвешенным, то определение матрицы Кирхгофа обобщается. В этом случае элементами главной диагонали матрицы Кирхгофа будут суммы весов рёбер, инцидентных соответствующей вершине. Для смежных (связанных) вершин [math]\displaystyle{ \ k_{i,j} = -c(v_i,v_j) }[/math], где [math]\displaystyle{ \ c(v_i,v_j) }[/math] — это вес (проводимость) ребра. Для различных не смежных (не связанных) вершин полагается [math]\displaystyle{ \ k_{i,j} = 0 }[/math].

[math]\displaystyle{ \ 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{если}\ i = j, \\ -c(v_i,v_j), & \text{если}\ (v_i,v_j) \in E(G), \\ 0, & \text{иначе}. \end{cases} }[/math]

Для взвешенного графа матрица смежности [math]\displaystyle{ \ A }[/math] записывается с учетом проводимостей ребер, а на главной диагонали матрицы [math]\displaystyle{ \ D }[/math] будут суммы проводимостей ребер инцидентных соответствующим вершинам.

[math]\displaystyle{ \ 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{если}\ i = j, \\ 0, & \text{иначе}. \end{cases} }[/math]

Пример

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

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

Свойства

Сумма элементов каждой строки (столбца) матрицы Кирхгофа равна нулю:
[math]\displaystyle{ \ \sum_{i=1}^{|V(G)|} k_{i,j} = 0 }[/math].

Определитель матрицы Кирхгофа равен нулю:
[math]\displaystyle{ \det K=0 }[/math]

Матрица Кирхгофа простого графа симметрична:
[math]\displaystyle{ \ k_{i,j} = k_{j,i}\quad i,j=1, \ldots, |V(G)| }[/math].

Все алгебраические дополнения [math]\displaystyle{ \ K_{(ij)} }[/math] симметричной матрицы Кирхгофа равны между собой — постоянная матрицы Кирхгофа. Для простого графа значение данной постоянной совпадает с числом всех возможных остовов графа (см. Матричная теорема о деревьях).

Если взвешенный граф представляет собой электрическую сеть, где вес каждого ребра соответствует его проводимости, то миноры матрицы Кирхгофа позволяют вычислить резистивное расстояние [math]\displaystyle{ \ R_{ij} }[/math] между точками [math]\displaystyle{ \ i }[/math] и [math]\displaystyle{ \ j }[/math] данной сети:
[math]\displaystyle{ \ R_{ij} = \frac{K^{(i, j)}}{K_{(ij)}} }[/math], здесь [math]\displaystyle{ \ K_{(ij)} }[/math] — постоянная (алгебраическое дополнение) матрицы Кирхгофа, а [math]\displaystyle{ \ K^{(i, j)} }[/math] — алгебраическое дополнение 2-го порядка, то есть определитель матрицы, получающейся из матрицы Кирхгофа вычеркиванием двух строк и двух столбцов [math]\displaystyle{ \ i, j }[/math].

Существует алгоритм восстановления матрицы Кирхгофа по матрице сопротивлений [math]\displaystyle{ R_{ij} }[/math].
0 является собственным значением матрицы (соответствующий собственный вектор — все единицы), кратность его равна числу связных компонент графа.
Остальные собственные значения положительны. Второе по малости значение Фидлер назвал индексом связности графа, соответствующий собственный вектор — вектор Фидлера (не путать с индексом связности графа Рандича).

См. также