Связь матрицы Кирхгофа и матрицы инцидентности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 18: Строка 18:
 
|-
 
|-
 
|[[Файл:Kirhgof.png|175px]]
 
|[[Файл:Kirhgof.png|175px]]
|<math>\left(\begin{array}{rrrrrr}
+
|<tex>\left(\begin{array}{rrrrrr}
 
  2 & -1 &  0 &  0 & -1 &  0\\
 
  2 & -1 &  0 &  0 & -1 &  0\\
 
-1 &  3 & -1 &  0 & -1 &  0\\
 
-1 &  3 & -1 &  0 & -1 &  0\\
Строка 25: Строка 25:
 
-1 & -1 &  0 & -1 &  3 &  0\\
 
-1 & -1 &  0 & -1 &  3 &  0\\
 
  0 &  0 &  0 & -1 &  0 &  1\\
 
  0 &  0 &  0 & -1 &  0 &  1\\
\end{array}\right)</math>
+
\end{array}\right)</tex>
|<math>\begin{pmatrix}
+
|<tex>\begin{pmatrix}
 
1 & 0 & 0 & 0 & 1 & 0 & 0\\
 
1 & 0 & 0 & 0 & 1 & 0 & 0\\
 
1 & 1 & 0 & 0 & 0 & 1 & 0\\
 
1 & 1 & 0 & 0 & 0 & 1 & 0\\
Строка 33: Строка 33:
 
0 & 0 & 0 & 1 & 1 & 1 & 0\\
 
0 & 0 & 0 & 1 & 1 & 1 & 0\\
 
0 & 0 & 0 & 0 & 0 & 0 & 1\\
 
0 & 0 & 0 & 0 & 0 & 0 & 1\\
\end{pmatrix}</math>
+
\end{pmatrix}</tex>
 
|}
 
|}
  

Версия 14:34, 29 ноября 2011

Определение:
Пусть [math]G[/math] - произвольный граф. Превратим каждое его ребро в дугу, придав ребру одно из двух возможных направлений. Полученный орграф на том же самом множестве вершин будем называть ориентацией графа [math]G[/math].


Лемма:
Пусть [math]K[/math]- матрица Кирхгофа графа [math]G[/math], [math]I[/math]- матрица инцидентности [math]G[/math] с некоторой ориентацией. Тогда [math]K = I \cdot I^T.[/math]
Доказательство:
[math]\triangleright[/math]
При умножении [math]i[/math]-й строки исходной матрицы [math]I[/math] на [math]j[/math]-й столбец транспонированной матрицы [math]I^T [/math] перемножаются [math]i[/math]-я и [math]j[/math]-я строки исходной матрицы. При умножении [math]i[/math]-й строки на саму себя на диагонали полученной матрицы получится сумма квадратов элементов [math]i[/math]-й строки, которая равна, очевидно, [math]deg(v_i)[/math]. Пусть теперь [math]i \ne j[/math]. Если [math] (v_i, v_j) \in E [/math], то существует ровно одно ребро, соединяющее [math] v_i [/math] и [math] v_j [/math], следовательно результат перемножения [math]i[/math]-й и [math]j[/math]-й строк равен -1, в противном случае он равен 0 в силу отсутствия ребра, инцидентного обеим вершинам. Определенная данными условиями матрица и является матрицей Кирхгофа.
[math]\triangleleft[/math]
Граф Матрица Кирхгофа Матрица инцидентности
Kirhgof.png [math]\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)[/math] [math]\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}[/math]

См. также

Матрица инцидентности графа

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

Подсчет числа остовных деревьев с помощью матрицы Кирхгофа

Источники

Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.