3622
правки
Изменения
м
[[Матрица Кирхгофа]]*Асанов М., Баранский В., Расин В. {{---}} Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.
→Источники информации
{{Определение
|definition=
Пусть <tex>G</tex> — произвольный граф. Превратим каждое его ребро в дугу, придав ребру одно из двух возможных направлений. Полученный [[Основные определения теории графов#Ориентированные графы|орграф]] на том же самом множестве вершин будем называть '''ориентацией''' графа <tex>G</tex>.
}}
{{Лемма
|statement=
Пусть <tex>K</tex>- — [[Матрица Кирхгофа| матрица Кирхгофа ]] графа <tex>G</tex>, <tex>I</tex>- — [[Матрица инцидентности графа| матрица инцидентности ]] <tex>G</tex> с некоторой ориентацией. Тогда
<tex>K = I \cdot I^T.</tex>
|proof=
При умножении <tex>i</tex>-й строки исходной матрицы <tex>I</tex> на <tex>j</tex>-й столбец трансонированной ей транспонированной матрицы <tex>I^T </tex> перемножаются <tex>i</tex>-я и <tex>j</tex>-я строки исходной матрицы. При умножении <tex>i</tex>-й строки на саму на себя на диагонали полученной матрицы будет получится сумма квадратов элементов <tex>i</tex>-й строки, которая равна, очевидно, <tex>\deg(v_i)</tex>. Пусть теперь <tex>i \ne j</tex>. Если <tex> (v_i, v_j) \in E </tex>, то существует ровно одно ребро, соединяющее <tex> v_i </tex> и <tex> v_j </tex>, следовательно результат перемножения <tex>i</tex>-й и <tex>j</tex>-й строк равен <tex>-1</tex>, в противном случае он равен <tex>0 </tex> в силу отсутствия ребра, инцидентного обеим вершинам. Определенная данными условиями матрица и является матрицей Кирхгофа.
}}
{|class="wikitable"
!Граф
!Матрица Кирхгофа
!Матрица инцидентности
|-
|[[Файл:Link_kirhgof_matrix_1.png|200px]]
|<tex>\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)</tex>
|<tex>\begin{pmatrix}
1 & 0 & 0 & 0 & 1 & 0 & 0\\
1 & 1 & 0 & 0 & 0 & 1 & 0\\
0 & 1 & 1 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 1 & 0 & 0 & 1\\
0 & 0 & 0 & 1 & 1 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 1\\
\end{pmatrix}</tex>
|}
==См. также==
*[[Матрица Кирхгофа]]
*[[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
*[[Количество помеченных деревьев]]
*[[Коды Прюфера]]
== См. также Источники информации==[[Матрица инцидентности графа]]
[[Подсчет числа Категория: Алгоритмы и структуры данных]][[Категория: Остовные деревья ]][[Категория: Свойства остовных деревьев с помощью матрицы Кирхгофа]]
