Изменения

Перейти к: навигация, поиск
Нет описания правки
{{Определение
|definition=
Рассмотрим неориентированный граф <math>G=(V, E)</math>. Ориентируем каждое из ребер в произвольном направлении и построим для полученного графа матрицу инцидентности как для ориентированного графа. Полученную матрицу назовем '''матрицей инцидентности с произвольной ориентацией'''.}}
 
{{Лемма
|statement=
Пусть <mathtex>K</mathtex>- матрица Кирхгофа графа <mathtex>G</mathtex>, <mathtex>I</mathtex>- матрица инцидентности с некоторой ориентацией. Тогда <mathtex>K = I \cdot I^T.</mathtex>
|proof=
При умножении i-й строки исходной матрицы <mathtex>I</mathtex> на j-й столбец трансонированной ей матрицы <mathtex>I^T </mathtex> перемножаются i-я и j-я строки исходной матрицы. При умножении i-й строки саму на себя на диагонали полученной матрицы будет сумма квадратов элементов i-й строки, которая равна, очевидно, <mathtex>deg(v_i)</mathtex>. Пусть теперь <mathtex>i \ne j</mathtex>. Если <mathtex> (v_i, v_j) \in E </mathtex>, то существует ровно одно ребро, соединяющее <mathtex> v_i </mathtex> и <mathtex> v_j </mathtex>, следовательно результат перемножения i-й и j-й строк равен -1, в противном случае он равен 0 в силу отсутствия ребра, инцидентного обеим вершинам. Определенная данными условиями матрица и является матрицей Кирхгофа.
}}
Анонимный участник

Навигация