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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Добавлены источник и определение ориентации)
Строка 6: Строка 6:
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
Пусть <tex>K</tex>- матрица Кирхгофа графа <tex>G</tex>, <tex>I</tex>- матрица инцидентности с некоторой ориентацией. Тогда  
+
Пусть <tex>K</tex>- матрица Кирхгофа графа <tex>G</tex>, <tex>I</tex>- матрица инцидентности <tex>G</tex> с некоторой ориентацией. Тогда  
 
  <tex>K = I \cdot I^T.</tex>
 
  <tex>K = I \cdot I^T.</tex>
  

Версия 05:49, 14 октября 2010

Определение:
Пусть [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]
При умножении i-й строки исходной матрицы [math]I[/math] на j-й столбец трансонированной ей матрицы [math]I^T [/math] перемножаются i-я и j-я строки исходной матрицы. При умножении i-й строки саму на себя на диагонали полученной матрицы будет сумма квадратов элементов i-й строки, которая равна, очевидно, [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], следовательно результат перемножения i-й и j-й строк равен -1, в противном случае он равен 0 в силу отсутствия ребра, инцидентного обеим вершинам. Определенная данными условиями матрица и является матрицей Кирхгофа.
[math]\triangleleft[/math]

См. также

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

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

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

Источники

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