Связь матрицы Кирхгофа и матрицы инцидентности — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показаны 4 промежуточные версии 3 участников) | |||
Строка 10: | Строка 10: | ||
|proof= | |proof= | ||
− | При умножении <tex>i</tex>-й строки исходной матрицы <tex>I</tex> на <tex>j</tex>-й столбец транспонированной матрицы <tex>I^T </tex> перемножаются <tex>i</tex>-я и <tex>j</tex>-я строки исходной матрицы. При умножении <tex>i</tex>-й строки на саму себя на диагонали полученной матрицы получится сумма квадратов элементов <tex>i</tex>-й строки, которая равна, очевидно, <tex>deg(v_i)</tex>. Пусть теперь <tex>i \ne j</tex>. Если <tex> (v_i, v_j) \in E </tex>, то существует ровно одно ребро, соединяющее <tex> v_i </tex> и <tex> v_j </tex>, следовательно результат перемножения <tex>i</tex>-й и <tex>j</tex>-й строк равен <tex>-1</tex>, в противном случае он равен <tex>0</tex> в силу отсутствия ребра, инцидентного обеим вершинам. Определенная данными условиями матрица и является матрицей Кирхгофа. | + | При умножении <tex>i</tex>-й строки исходной матрицы <tex>I</tex> на <tex>j</tex>-й столбец транспонированной матрицы <tex>I^T </tex> перемножаются <tex>i</tex>-я и <tex>j</tex>-я строки исходной матрицы. При умножении <tex>i</tex>-й строки на саму себя на диагонали полученной матрицы получится сумма квадратов элементов <tex>i</tex>-й строки, которая равна, очевидно, <tex>\deg(v_i)</tex>. Пусть теперь <tex>i \ne j</tex>. Если <tex> (v_i, v_j) \in E </tex>, то существует ровно одно ребро, соединяющее <tex> v_i </tex> и <tex> v_j </tex>, следовательно результат перемножения <tex>i</tex>-й и <tex>j</tex>-й строк равен <tex>-1</tex>, в противном случае он равен <tex>0</tex> в силу отсутствия ребра, инцидентного обеим вершинам. Определенная данными условиями матрица и является матрицей Кирхгофа. |
}} | }} | ||
{|class="wikitable" | {|class="wikitable" | ||
Строка 39: | Строка 39: | ||
*[[Матрица Кирхгофа]] | *[[Матрица Кирхгофа]] | ||
*[[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]] | *[[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]] | ||
+ | *[[Количество помеченных деревьев]] | ||
+ | *[[Коды Прюфера]] | ||
==Источники информации== | ==Источники информации== | ||
− | + | *Асанов М., Баранский В., Расин В. {{---}} Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр. | |
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Остовные деревья ]] | [[Категория: Остовные деревья ]] | ||
[[Категория: Свойства остовных деревьев ]] | [[Категория: Свойства остовных деревьев ]] |
Текущая версия на 19:25, 4 сентября 2022
Определение: |
Пусть орграф на том же самом множестве вершин будем называть ориентацией графа . | — произвольный граф. Превратим каждое его ребро в дугу, придав ребру одно из двух возможных направлений. Полученный
Лемма: |
Пусть матрица Кирхгофа графа , — матрица инцидентности с некоторой ориентацией. Тогда
— |
Доказательство: |
При умножении | -й строки исходной матрицы на -й столбец транспонированной матрицы перемножаются -я и -я строки исходной матрицы. При умножении -й строки на саму себя на диагонали полученной матрицы получится сумма квадратов элементов -й строки, которая равна, очевидно, . Пусть теперь . Если , то существует ровно одно ребро, соединяющее и , следовательно результат перемножения -й и -й строк равен , в противном случае он равен в силу отсутствия ребра, инцидентного обеим вершинам. Определенная данными условиями матрица и является матрицей Кирхгофа.
Граф | Матрица Кирхгофа | Матрица инцидентности |
---|---|---|
![]() |
См. также
Источники информации
- Асанов М., Баранский В., Расин В. — Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.