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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Матрица Кирхгофа (англ. 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}

Пример[править | править вики-текст]

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

Помеченный граф Матрица Кирхгофа
6n-graf.svg \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)} симметричной матрицы Кирхгофа равны между собой — постоянная матрицы Кирхгофа. Для простого графа значение данной постоянной совпадает с числом всех возможных остовов графа (см. Матричная теорема о деревьях).
  • Если взвешенный граф представляет собой электрическую сеть, то миноры матрицы Кирхгофа позволяют вычислить резистивное расстояние (resistance distance) \ R_{ij} между точками \ i и \ j данной сети:

\ R_{ij} = \frac{K^{(i, j)}}{K_{(ij)}},

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

Существует алгоритм восстановления матрицы Кирхгофа по матрице сопротивлений \ R_{ij}.

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


См. также[править | править вики-текст]