Изменения
Новая страница: «{{Определение |definition= Рассмотрим неориентированный граф <math>G=(V, E)</math>. Ориентируем каждое и…»
{{Определение
|definition=
Рассмотрим неориентированный граф <math>G=(V, E)</math>. Ориентируем каждое из ребер в произвольном направлении и построим для полученного графа матрицу инцидентности как для ориентированного графа. Полученную матрицу назовем '''матрицей инцидентности с произвольной ориентацией'''.}}
{{Лемма
|statement=
Пусть <math>K</math>- матрица Кирхгофа графа <math>G</math>, <math>I</math>- матрица инцидентности с некоторой ориентацией. Тогда
<math>K = I \cdot I^T.</math>
|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 в силу отсутствия ребра, инцидентного обеим вершинам. Определенная данными условиями матрица и является матрицей Кирхгофа.
}}
|definition=
Рассмотрим неориентированный граф <math>G=(V, E)</math>. Ориентируем каждое из ребер в произвольном направлении и построим для полученного графа матрицу инцидентности как для ориентированного графа. Полученную матрицу назовем '''матрицей инцидентности с произвольной ориентацией'''.}}
{{Лемма
|statement=
Пусть <math>K</math>- матрица Кирхгофа графа <math>G</math>, <math>I</math>- матрица инцидентности с некоторой ориентацией. Тогда
<math>K = I \cdot I^T.</math>
|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 в силу отсутствия ребра, инцидентного обеим вершинам. Определенная данными условиями матрица и является матрицей Кирхгофа.
}}
