Подсчёт числа остовных деревьев с помощью матрицы Кирхгофа — различия между версиями
Строка 18: | Строка 18: | ||
{{Теорема | {{Теорема | ||
|about= | |about= | ||
− | Формула Бине-Коши | + | [[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 |Формула Бине-Коши]] |
|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>. | ||
Строка 32: | Строка 32: | ||
Пусть <tex>G</tex> — произвольный связный обыкновенный <tex>(n, m)</tex>-граф, <tex>n \ge 2</tex> и <tex>I</tex> — матрица инцидентности какой-либо ориентации графа <tex>G</tex>. Заметим, что <tex>m \ge n - 1</tex> в силу связности графа <tex>G</tex>. По [[Связь матрицы Кирхгофа и матрицы инцидентности|лемме]] выполняется <tex>B = B(G) = I \cdot I^T</tex>. Пусть <tex>B'</tex> — подматрица матрицы <tex>B</tex>, полученная удалением последней строки. Тогда имеем <tex>B' = JJ^T</tex>, где <tex>J</tex> — это <tex>((n - 1) \times m)</tex> - матрица. Очевидно, <tex>B_{nn} = det B'</tex> есть алгебраическое дополнение элемента <tex>\beta_{nn}</tex> в матрице Кирхгофа <tex>B</tex>. В силу формулы Бине-Коши <tex>B_{nn}</tex> равно сумме квадратов всех миноров порядка <tex>(n - 1)</tex> матрицы <tex>J</tex>. Согласно лемме, доказанной выше, каждый такой минор <tex>M</tex> равен <tex>\pm 1</tex>, если остовный подграф графа <tex>G</tex>, ребра которого соответствуют столбцам, вошедшим в матрицу минора <tex>M</tex>, является деревом, и равен <tex>0</tex> в другом случае. Следовательно, <tex>B_{nn}</tex> равно числу остовов графа <tex>G</tex>. Осталось отметить, что по лемме алгебраические дополнения всех элементов матрицы Кирхгофа равны между собой. | Пусть <tex>G</tex> — произвольный связный обыкновенный <tex>(n, m)</tex>-граф, <tex>n \ge 2</tex> и <tex>I</tex> — матрица инцидентности какой-либо ориентации графа <tex>G</tex>. Заметим, что <tex>m \ge n - 1</tex> в силу связности графа <tex>G</tex>. По [[Связь матрицы Кирхгофа и матрицы инцидентности|лемме]] выполняется <tex>B = B(G) = I \cdot I^T</tex>. Пусть <tex>B'</tex> — подматрица матрицы <tex>B</tex>, полученная удалением последней строки. Тогда имеем <tex>B' = JJ^T</tex>, где <tex>J</tex> — это <tex>((n - 1) \times m)</tex> - матрица. Очевидно, <tex>B_{nn} = det B'</tex> есть алгебраическое дополнение элемента <tex>\beta_{nn}</tex> в матрице Кирхгофа <tex>B</tex>. В силу формулы Бине-Коши <tex>B_{nn}</tex> равно сумме квадратов всех миноров порядка <tex>(n - 1)</tex> матрицы <tex>J</tex>. Согласно лемме, доказанной выше, каждый такой минор <tex>M</tex> равен <tex>\pm 1</tex>, если остовный подграф графа <tex>G</tex>, ребра которого соответствуют столбцам, вошедшим в матрицу минора <tex>M</tex>, является деревом, и равен <tex>0</tex> в другом случае. Следовательно, <tex>B_{nn}</tex> равно числу остовов графа <tex>G</tex>. Осталось отметить, что по лемме алгебраические дополнения всех элементов матрицы Кирхгофа равны между собой. | ||
}} | }} | ||
− | |||
− | Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр. | + | |
+ | ==См. также== | ||
+ | *[[Связь матрицы Кирхгофа и матрицы инцидентности]] | ||
+ | *[[Матрица Кирхгофа]] | ||
+ | |||
+ | ==Источники информации== | ||
+ | |||
+ | #Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр. | ||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Остовные деревья ]] | [[Категория: Остовные деревья ]] | ||
+ | [[Категория: Свойства остовных деревьев ]] |
Версия 17:49, 29 декабря 2015
Лемма: |
Пусть граф, , — матрица инцидентности некоторой его ориентации, — произвольный минор порядка матрицы . Тогда
— обыкновенный -
|
Доказательство: |
Заметим, что смена нумерации вершин и нумерации ребер графа
|
Определение: |
Пусть | и — соответственно — матрица и — матрица, где . Положим . Минор порядка матрицы называется соответствующим минором минору порядка матрицы , если множество номеров строк, составляющих матрицу первого минора, равно множеству номеров столбцов, составляющих матрицу второго минора.
Теорема ([|Формула Бине-Коши]): |
Определитель матрицы равен сумме всевозможных попарных произведений миноров порядка матрицы на соответствующие миноры матрицы . |
Следствие
При определитель произведения двух квадратных матриц порядка равен произведению определителей этих матриц
Теорема (Кирхгоф, 1847): |
Число остовов в связном неодноэлементном обыкновенном графе матрицы Кирхгофа . равно алгебраическому дополнению любого элемента |
Доказательство: |
Пусть лемме выполняется . Пусть — подматрица матрицы , полученная удалением последней строки. Тогда имеем , где — это - матрица. Очевидно, есть алгебраическое дополнение элемента в матрице Кирхгофа . В силу формулы Бине-Коши равно сумме квадратов всех миноров порядка матрицы . Согласно лемме, доказанной выше, каждый такой минор равен , если остовный подграф графа , ребра которого соответствуют столбцам, вошедшим в матрицу минора , является деревом, и равен в другом случае. Следовательно, равно числу остовов графа . Осталось отметить, что по лемме алгебраические дополнения всех элементов матрицы Кирхгофа равны между собой. | — произвольный связный обыкновенный -граф, и — матрица инцидентности какой-либо ориентации графа . Заметим, что в силу связности графа . По
См. также
Источники информации
- Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.