Связь матрицы Кирхгофа и матрицы инцидентности — различия между версиями
Shersh (обсуждение | вклад) м (→Источники информации) |
м (rollbackEdits.php mass rollback) |
(не показана 1 промежуточная версия 1 участника) | |
(нет различий)
|
Текущая версия на 19:25, 4 сентября 2022
Определение: |
Пусть орграф на том же самом множестве вершин будем называть ориентацией графа . | — произвольный граф. Превратим каждое его ребро в дугу, придав ребру одно из двух возможных направлений. Полученный
Лемма: |
Пусть матрица Кирхгофа графа , — матрица инцидентности с некоторой ориентацией. Тогда
— |
Доказательство: |
При умножении | -й строки исходной матрицы на -й столбец транспонированной матрицы перемножаются -я и -я строки исходной матрицы. При умножении -й строки на саму себя на диагонали полученной матрицы получится сумма квадратов элементов -й строки, которая равна, очевидно, . Пусть теперь . Если , то существует ровно одно ребро, соединяющее и , следовательно результат перемножения -й и -й строк равен , в противном случае он равен в силу отсутствия ребра, инцидентного обеим вершинам. Определенная данными условиями матрица и является матрицей Кирхгофа.
Граф | Матрица Кирхгофа | Матрица инцидентности |
---|---|---|
См. также
- Матрица Кирхгофа
- Подсчет числа остовных деревьев с помощью матрицы Кирхгофа
- Количество помеченных деревьев
- Коды Прюфера
Источники информации
- Асанов М., Баранский В., Расин В. — Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.