Связь матрицы Кирхгофа и матрицы инцидентности
Версия от 23:58, 22 января 2011; Kirelagin (обсуждение | вклад) (Матрица, транспонированная данной…)
Определение: |
Пусть орграф на том же самом множестве вершин будем называть ориентацией графа . | - произвольный граф. Превратим каждое его ребро в дугу, придав ребру одно из двух возможных направлений. Полученный
Лемма: |
Пусть - матрица Кирхгофа графа , - матрица инцидентности с некоторой ориентацией. Тогда
|
Доказательство: |
При умножении | -й строки исходной матрицы на -й столбец транспонированной матрицы перемножаются i-я и j-я строки исходной матрицы. При умножении -й строки на саму себя на диагонали полученной матрицы получится сумма квадратов элементов -й строки, которая равна, очевидно, . Пусть теперь . Если , то существует ровно одно ребро, соединяющее и , следовательно результат перемножения -й и -й строк равен -1, в противном случае он равен 0 в силу отсутствия ребра, инцидентного обеим вершинам. Определенная данными условиями матрица и является матрицей Кирхгофа.
См. также
Подсчет числа остовных деревьев с помощью матрицы Кирхгофа
Источники
Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.