Изменения

{{Теорема

|about=

|statement=

Определитель матрицы <tex>C</tex> равен сумме всевозможных попарных произведений миноров порядка <tex>s</tex> матрицы <tex>P</tex> на соответствующие миноры матрицы <tex>Q</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>. Осталось отметить, что по лемме алгебраические дополнения всех элементов матрицы Кирхгофа равны между собой.

}}

[[Категория: Алгоритмы и структуры данных]]

[[Категория: Остовные деревья ]]