Подсчёт числа остовных деревьев с помощью матрицы Кирхгофа — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показаны 4 промежуточные версии 3 участников) | |||
Строка 18: | Строка 18: | ||
{{Теорема | {{Теорема | ||
|about= | |about= | ||
− | Формула Бине-Коши<ref>[https://ru.wikipedia.org/wiki/%D0%A4%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D0%B0_%D0%91%D0%B8%D0%BD%D0%B5_%E2%80%94_%D0%9A%D0%BE%D1%88%D0%B8 | + | Формула Бине-Коши<ref>[https://ru.wikipedia.org/wiki/%D0%A4%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D0%B0_%D0%91%D0%B8%D0%BD%D0%B5_%E2%80%94_%D0%9A%D0%BE%D1%88%D0%B8 Формула Бине-Коши] </ref> |
|statement= | |statement= | ||
Определитель матрицы <tex>C</tex> равен сумме всевозможных попарных произведений миноров порядка <tex>s</tex> матрицы <tex>P</tex> на соответствующие миноры матрицы <tex>Q</tex>. | Определитель матрицы <tex>C</tex> равен сумме всевозможных попарных произведений миноров порядка <tex>s</tex> матрицы <tex>P</tex> на соответствующие миноры матрицы <tex>Q</tex>. | ||
Строка 38: | Строка 38: | ||
*[[Количество помеченных деревьев]] | *[[Количество помеченных деревьев]] | ||
*[[Коды Прюфера]] | *[[Коды Прюфера]] | ||
+ | |||
+ | == Примечания == | ||
+ | <references /> | ||
==Источники информации== | ==Источники информации== | ||
− | |||
*Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр. | *Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр. | ||
− | |||
− | |||
− | |||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Остовные деревья ]] | [[Категория: Остовные деревья ]] | ||
[[Категория: Свойства остовных деревьев ]] | [[Категория: Свойства остовных деревьев ]] |
Текущая версия на 19:28, 4 сентября 2022
Лемма: |
Пусть граф, , — матрица инцидентности некоторой его ориентации, — произвольный минор порядка матрицы . Тогда
— обыкновенный —
|
Доказательство: |
Заметим, что смена нумерации вершин и нумерации ребер графа
|
Определение: |
Пусть | и — соответственно — матрица и — матрица, где . Положим . Минор порядка матрицы называется соответствующим минором минору порядка матрицы , если множество номеров строк, составляющих матрицу первого минора, равно множеству номеров столбцов, составляющих матрицу второго минора.
Теорема (Формула Бине-Коши[1]): |
Определитель матрицы равен сумме всевозможных попарных произведений миноров порядка матрицы на соответствующие миноры матрицы . |
Следствие
При определитель произведения двух квадратных матриц порядка равен произведению определителей этих матриц
Теорема (Кирхгоф, 1847): |
Число остовов в связном неодноэлементном обыкновенном графе матрицы Кирхгофа . равно алгебраическому дополнению любого элемента |
Доказательство: |
Пусть лемме выполняется . Пусть — подматрица матрицы , полученная удалением последней строки. Тогда имеем , где — это — матрица. Очевидно, есть алгебраическое дополнение элемента в матрице Кирхгофа . В силу формулы Бине-Коши равно сумме квадратов всех миноров порядка матрицы . Согласно лемме, доказанной выше, каждый такой минор равен , если остовный подграф графа , ребра которого соответствуют столбцам, вошедшим в матрицу минора , является деревом, и равен в другом случае. Следовательно, равно числу остовов графа . Осталось отметить, что по лемме алгебраические дополнения всех элементов матрицы Кирхгофа равны между собой. | — произвольный связный обыкновенный — граф, и — матрица инцидентности какой-либо ориентации графа . Заметим, что в силу связности графа . По
См. также
- Связь матрицы Кирхгофа и матрицы инцидентности
- Матрица Кирхгофа
- Количество помеченных деревьев
- Коды Прюфера
Примечания
Источники информации
- Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.