== Некоторые свойства ==
* '''1.''' Сумма элементов каждой строки (столбца) матрицы Кирхгофа равна нулю:
: <tex>\ \sum_{i=1}^{|V|} k_{i,j} = 0</tex>.
* '''2.''' Определитель матрицы Кирхгофа равен нулю:
: <tex>\det K=0</tex>
* Доказательство: <tex> \det K = \begin{vmatrix}k_{1, 1} & k_{1, 2} & \cdots & k_{1, |V|} \\k_{2, 1} & k_{2, 2} & \cdots & k_{2, |V|} \\ \vdots & \vdots & \ddots & \vdots \\k_{|V|, 1} & k_{|V|, 2} & \cdots & k_{|V|, |V|}\end{vmatrix}</tex> Прибавим к первой строке все остальные строки(это не изменит значение определителя): <tex>\begin{vmatrix}k_{1, 1} + k_{2, 1} + \cdots + k_{|V|, 1} & k_{1, 2} + k_{2, 2} + \cdots + k_{|V|, 2} & \cdots & k_{1, |V|} + k_{2, |V|} + \cdots + k_{|V|, |V|} \\k_{2, 1} & k_{2, 2} & \cdots & k_{2, |V|} \\ \vdots & \vdots & \ddots & \vdots \\k_{|V|, 1} & k_{|V|, 2} & \cdots & k_{|V|, |V|}\end{vmatrix}</tex> Так как сумма элементов каждого столбца равна <tex>0</tex>, получим: <tex>\det K = \begin{vmatrix}0 & 0 & \cdots & 0 \\k_{2, 1} & k_{2, 2} & \cdots & k_{2, |V|} \\ \vdots & \vdots & \ddots & \vdots \\k_{|V|, 1} & k_{|V|, 2} & \cdots & k_{|V|, |V|}\end{vmatrix} = 0</tex> '''3.''' Матрица Кирхгофа простого графа симметрична:
: <tex>\ k_{i,j} = k_{j,i}\quad i,j=1, \ldots, |V|</tex>.
*'''4.''' Связь с [[Матрица смежности графа|матрицей смежности]]:
:<tex> K =
\begin{pmatrix}
\mathrm{deg}(v_1) & 0 & \cdots & 0 \\0 & \mathrm{deg}(v_2) & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & \mathrm{deg}(v_n)
\end{pmatrix} - A,
</tex>
где <tex>A</tex> — матрица смежности графа <tex>G</tex>.
*'''5.''' [[Связь матрицы Кирхгофа и матрицы инцидентности|Связь с матрицей инцидентности]]:
:<tex> K = I \cdot I^T, </tex> где <tex>I</tex> — матрица инцидентности некоторой ориентации графа.
*'''6.''' <tex>0</tex> является собственным значением матрицы. Доказательство: Собственным значением матрицы называют значения <tex>\lambda</tex>, которые удовлетворяют уравнению: <tex>\begin{vmatrix}k_{1, 1} - \lambda &k_{1, 2} & \cdots & k_{1, |V|} \\k_{2, 1} & k_{2, 2} - \lambda & \cdots & k_{2, |V|} \\ \vdots & \vdots & \ddots & \vdots \\k_{|V|, 1} & k_{|V|, 2} & \cdots & k_{|V|, |V| - \lambda}\end{vmatrix} = 0</tex> Прибавим к первой строке все остальные строки(это не изменит значение определителя): <tex>\begin{vmatrix}k_{1, 1} + k_{2, 1} + \cdots + k_{|V|, 1} - \lambda & k_{1, 2} + k_{2, 2} + \cdots + k_{|V|, кратность его 2} - \lambda & \cdots & k_{1, |V|} + k_{2, |V|} + \cdots + k_{|V|, |V|} - \lambda \\k_{2, 1} & k_{2, 2} & \cdots & k_{2, |V|} \\ \vdots & \vdots & \ddots & \vdots \\k_{|V|, 1} & k_{|V|, 2} & \cdots & k_{|V|, |V|}\end{vmatrix}</tex> Так как сумма элементов каждого столбца равна числу компонент связности графа<tex>0</tex>, получим: <tex>\begin{vmatrix} - \lambda &-\lambda & \cdots & - \lambda \\k_{2, 1} & k_{2, 2} - \lambda & \cdots & k_{2, |V|} \\ \vdots & \vdots & \ddots & \vdots \\k_{|V|, 1} & k_{|V|, 2} & \cdots & k_{|V|, |V|} - \lambda\end{vmatrix} = 0</tex> <tex>- \lambda\begin{vmatrix} 1 & 1 & \cdots & 1 \\k_{2, 1} & k_{2, 2} - \lambda & \cdots & k_{2, |V|} \\ \vdots & \vdots & \ddots & \vdots \\k_{|V|, 1} & k_{|V|, 2} & \cdots & k_{|V|, |V|} - \lambda\end{vmatrix}= 0.</tex>
Следовательно, <tex>0</tex> является собственным значением
==См. также==
*[[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
==Источникиинформации==
*Асанов М., Баранский В., Расин В.: Дискретная математика: Графы, матроиды, алгоритмы. стр. 18
*[http://ru.wikipedia.org/wiki/%CC%E0%F2%F0%E8%F6%E0_%CA%E8%F0%F5%E3%EE%F4%E0 Википедия, Матрица Кирхгофа]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]]
