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

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

Пример

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

Помеченный граф	Матрица Кирхгофа
	$\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}~~ i,j=1...|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 является собственным значением матрицы (соответствующих собственный вектор — все единицы), кратность его равна числу связных компонент графа.
• Остальные собственные значения положительны. Второе по малости значение Фидлер назвал индексом связности графа, его с. вектор — вектор Фиддлера.

Этот раздел не завершён. Вы поможете проекту, исправив и дополнив его.

См. также

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