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

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

ОпределениеПравить

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

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

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

$K=D-<!--\; -\; -->A,$$\ K=D-A,$ 

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

$\ d_{i,j}:={\begin{cases}\deg(v_{i}),&{\text{если}}\ i=j,\\0,&{\text{иначе}}.\end{cases}}$ 

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

$\ 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}}$ 

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

$\ 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}}$ 

ПримерПравить

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

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

СвойстваПравить

• Сумма элементов каждой строки (столбца) матрицы Кирхгофа равна нулю:

  $\underset{i=1}{\overset{|V(G)|}{\sum <!--\; \sum \; -->}}{k}_{i,j}=0$$\ \sum _{i=1}^{|V(G)|}k_{i,j}=0$ .

• Определитель матрицы Кирхгофа равен нулю:

  $detK=0$$\det K=0$ 

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

  $k_{i,j}=k_{j,i}i,j=1,\dots <!--\; \dots \; -->,|V(G)|$$\ k_{i,j}=k_{j,i}\quad i,j=1,\ldots ,|V(G)|$ .

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

• Если взвешенный граф представляет собой электрическую сеть, где вес каждого ребра соответствует его проводимости, то миноры матрицы Кирхгофа позволяют вычислить резистивное расстояние $R_{ij}$$\ R_{ij}$  между точками $i$$\ i$  и $j$$\ j$  данной сети:

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

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

См. такжеПравить

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