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

Определение:

Рассмотрим неориентированный граф [math]G=(V, E)[/math]. Ориентируем каждое из ребер в произвольном направлении и построим для полученного графа матрицу инцидентности как для ориентированного графа. Полученную матрицу назовем матрицей инцидентности с произвольной ориентацией.

Лемма:

Пусть [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]

См. также

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

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

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