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