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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
−
{{Определение
 
−
|definition=
 
−
Рассмотрим неориентированный граф <math>G=(V, E)</math>. Ориентируем каждое из ребер в произвольном направлении и построим для полученного графа матрицу инцидентности как для ориентированного графа. Полученную матрицу назовем '''матрицей инцидентности с произвольной ориентацией'''.}}
 
−
 
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
−
Пусть <math>K</math>- матрица Кирхгофа графа <math>G</math>, <math>I</math>- матрица инцидентности с некоторой ориентацией. Тогда  
+
Пусть <tex>K</tex>- матрица Кирхгофа графа <tex>G</tex>, <tex>I</tex>- матрица инцидентности с некоторой ориентацией. Тогда  
−
  <math>K = I \cdot I^T.</math>
+
  <tex>K = I \cdot I^T.</tex>
  
 
|proof=
 
|proof=
−
При умножении 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 в силу отсутствия ребра, инцидентного обеим вершинам. Определенная данными условиями матрица и является матрицей Кирхгофа.
+
При умножении i-й строки исходной матрицы <tex>I</tex> на j-й столбец трансонированной ей матрицы <tex>I^T </tex> перемножаются i-я и j-я строки исходной матрицы. При умножении i-й строки саму на себя на диагонали полученной матрицы будет сумма квадратов элементов i-й строки, которая равна, очевидно, <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>, следовательно результат перемножения i-й и j-й строк равен -1, в противном случае он равен 0 в силу отсутствия ребра, инцидентного обеим вершинам. Определенная данными условиями матрица и является матрицей Кирхгофа.
 
}}
 
}}
  

Версия 23:44, 13 октября 2010

Лемма:
Пусть [math]K[/math]- матрица Кирхгофа графа [math]G[/math], [math]I[/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]

См. также

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

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

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Связь_матрицы_Кирхгофа_и_матрицы_инцидентности&oldid=3863»