Изменения

Рассмотрим неориентированный граф Пусть <mathtex>G=(V, E)</mathtex>— произвольный граф. Ориентируем Превратим каждое его ребро в дугу, придав ребру одно из ребер в произвольном направлении и построим для полученного графа матрицу инцидентности как для ориентированного графадвух возможных направлений. Полученную матрицу назовем Полученный [[Основные определения теории графов#Ориентированные графы|орграф]] на том же самом множестве вершин будем называть '''матрицей инцидентности с произвольной ориентацией'''графа <tex>G</tex>.}}

Пусть <mathtex>K</mathtex>- — [[Матрица Кирхгофа| матрица Кирхгофа ]] графа <mathtex>G</mathtex>, <mathtex>I</mathtex>- — [[Матрица инцидентности графа| матрица инцидентности ]] <tex>G</tex> с некоторой ориентацией. Тогда <mathtex>K = I \cdot I^T.</mathtex>

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