3622
правки
Изменения
м
== Определение матрицы Кирхгофа ==
Пример матрицы Кирхгофа простого графа.
2) Связь с матрицей смежности{{Утверждение|statement=Матрица Кирхгофа простого графа симметрична: : <tex>\ k_{i,j} = k_{j,i}\quad i,j=1, \ldots, |V|</tex>.}}
где <tex>A</tex> - матрица смежности графа <tex>G</tex>==См.также==
3) *[[Связь матрицы Кирхгофа и матрицы инцидентности|Связь ]]*[[Подсчет числа остовных деревьев с матрицей инцидентностипомощью матрицы Кирхгофа]]: <tex> K = I \cdot I^T, </tex> где <tex>I</tex> - матрица инцидентности с некоторой ориентацией.
→Источники информации
{{Определение
|definition=
'''Матрицей Кирхгофа''' [[Основные определения теории графов#def_simple_graph|простого графа ]] <tex>G = (V,E) </tex> называется матрица <tex> K (|V| \times |V|) = \parallel k_{i,j} \parallel </tex>, элементы которой определяются равенством: <tex>
k_{i,j} =
\begin{cases}
\deg(v_i), \ i = j \\
-1, \ (v_i,v_j) \in E \\
0, \mbox{ elseotherwise}.
\end{cases}
</tex>
}}
Иными словами, на главной диагонали матрицы Кирхгофа находятся степени вершин, а на пересечении <tex>i</tex>-й строки и <tex>j</tex>-го столбца (<tex>i \ne j</tex>) стоит <tex>-1</tex>, если вершины с номерами <tex>i </tex> и <tex>j </tex> смежны, и <tex>0 </tex> в противном случае.
== Пример матрицы Кирхгофа==
{|class="wikitable"
![[Помеченный граф]]Граф
!Матрица Кирхгофа
|-
|[[imageФайл:6n-grafKirhgof_matrix_1.svgpng|175px200px]]|<mathtex>\left(\begin{array}{rrrrrr}
2 & -1 & 0 & 0 & -1 & 0\\
-1 & 3 & -1 & 0 & -1 & 0\\
-1 & -1 & 0 & -1 & 3 & 0\\
0 & 0 & 0 & -1 & 0 & 1\\
\end{array}\right)</mathtex>
|}
== Некоторые свойства ==
{{Утверждение
|statement=Сумма элементов каждой строки (столбца) матрицы Кирхгофа равна нулю:
: <tex>\ \sum_{i=1}^{|V|} k_{i,j} = 0</tex>.
}}
{{Утверждение|statement=Определитель матрицы Кирхгофа равен нулю:: <tex>\det K= Некоторые свойства 0</tex>|proof=<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>}}
{{Утверждение|statement=Связь с [[Матрица смежности графа|матрицей смежности]]: :<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>.
}}
{{Утверждение
|statement=[[Связь матрицы Кирхгофа и матрицы инцидентности|Связь с матрицей инцидентности]]:
:<tex> K = I \cdot I^T, </tex> где <tex>I</tex> — матрица инцидентности некоторой ориентации графа.
}}
{{Утверждение
|statement=<tex>0</tex> является [[Собственные векторы и собственные значения|собственным значением]] матрицы, кратность его равна числу [[Отношение связности, компоненты связности|компонент связности]] графа.
|proof=Собственным значением матрицы называют значения <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} - \lambda & \cdots & k_{2, |V|} \\
\vdots & \vdots & \ddots & \vdots \\
k_{|V|, 1} & k_{|V|, 2} & \cdots & k_{|V|, |V|} - \lambda
\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> является собственным значением.
'''Доказательство кратности:'''
Пусть дан граф <tex>G</tex> c <tex>n</tex> компонентами связности. Перенумеруем его вершины так, чтобы сначала шли вершины первой компоненты связности, затем второй и т.д. Тогда матрица Кирхгофа примет блочно-диагональный вид, и <tex>i</tex>-тый блок этой матрицы будет являтся матрицей Кирхгофа для <tex>i</tex>-той компоненты связности.
Из свойства блочно-диагональной матрицы <tex>\det K = \det K_{1} \cdot \det K_{2} \cdot \ldots \cdot \det K_{n}</tex>, где <tex>K_{i}</tex> — матрица Кирхгофа для <tex>i</tex>-той компоненты связности, и свойства, доказанного выше,
<tex>\det K_{i} = - \lambda \cdot det X_{i} \quad \Rightarrow \quad \det K = (-1)^{n} \cdot \lambda^{n} \cdot \det X_{1} \cdot \det X_{2} \cdot \ldots \cdot \det X_{n}</tex>
}}
==Источникиинформации==
*Асанов М., Баранский В., Расин В. - : Дискретная математика: Графы, матроиды, алгоритмы — Ижевск. стр. 18*[http: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр//ru.wikipedia.org/wiki/%CC%E0%F2%F0%E8%F6%E0_%CA%E8%F0%F5%E3%EE%F4%E0 Википедия — Матрица Кирхгофа]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]][[Категория: Свойства остовных деревьев ]]
