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

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

Определение

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

$k_{i,j}:=\{\begin{array}{cc}\mathrm{deg}(v_i),& \text{если}i=j,\\ -1,& \text{если}(v_i,v_j)\in E(G),\\ 0& \text{иначе}.\end{array}$

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

$K=D-A,$

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

$d_{i,j}:=\{\begin{array}{cc}\mathrm{deg}(v_i),& \text{если}i=j,\\ 0& \text{иначе}.\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{если}i=j,\\ -c(v_i,v_j),& \text{если}(v_i,v_j)\in E(G),\\ 0& \text{иначе}.\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{если}i=j,\\ 0& \text{иначе}.\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 является собственным значением матрицы (соответствующий собственный вектор — все единицы), кратность его равна числу связных компонент графа.
• Остальные собственные значения положительны. Второе по малости значение Шаблон:Iw назвал индексом связности графа, соответствующий собственный вектор — вектор Фидлера (не путать с индексом связности графа Рандича).

См. также

• Матричная теорема о деревьях
• Оператор Лапласа