211
правок
Изменения
Нет описания правки
{{Лемма
|statement=
Пусть <tex>H</tex> - обыкновенный <tex>(n, n - 1)</tex>-[[Основные определения теории графов|граф]], <tex>n \ge 2 </tex>, <tex>I</tex> - [[Матрица инцидентности графа|матрица инцидентности ]] некоторой его ориентации, <tex>M</tex> - произвольный минор порядка <tex>n - 1</tex> матрицы <tex>I</tex>. Тогда# если <tex>H</tex> не является [[Дерево, эквивалентные определения|деревом]], то <tex>M = 0</tex>;
# если <tex>H</tex> - дерево, то <tex>M = \pm 1</tex>.
|proof=
Заметим, что смена нумерации вершин и нумерации ребер графа <tex>H</tex> приводит к перестановке строк и перестановке столбцов матрицы <tex>I</tex>. Рассматриваемый минор при этом может сменить лишь знак.<br/>
Пусть <tex>v</tex> - вершина, соответствующая строке матрицы <tex>I</tex>, не вошедшей в матрицу минора <tex>M</tex>.
# Пусть <tex>H</tex> не является деревом. Тогда граф <tex>H</tex> несвязен. Пусть <tex>v_1, ..., v_i</tex> - множество вершин некоторой [[Отношение связности, компоненты связности|компоненты связности ]] <tex>H_1</tex> графа <tex>H</tex>, не содержащей <tex>v</tex>.
## Если <tex>t = 1</tex>, то <tex>v_1</tex> - изолированная вершина и в матрице минора <tex>M</tex> имеется нулевая строка, поэтому <tex>M = 0</tex>.
## Пусть <tex>t > 1</tex>. С помощью подходящей перенумерации вершин и ребер из <tex>H</tex> матрицу <tex>I</tex> приведем к клеточному виду <br/> <center><tex>\begin{pmatrix} I_1 & 0\\0 & I_2 \end{pmatrix}</tex>, </center><br/>где <tex>I_1</tex> - матрица инцидентности ориентации компоненты <tex>H_1</tex>, а вершине <tex>v</tex> отвечает строка, проходящая через <tex>I_2</tex>. Каждый столбец, проходящий через <tex>I_1</tex>, содержит точно одну единицу и точно одну <tex>-1</tex> (остальные элементы равны нулю). Следовательно, сумма первых <tex>t</tex> строк равна <tex>0</tex>. Так как первые <tex>t</tex> строк входят в матрицу минора <tex>M</tex>, имеем <tex>M = 0</tex>.
{{Определение
|definition=
Пусть <tex>P</tex> и <tex>Q</tex> - соответственно <tex>(s \times t)</tex>-матрица и <tex>(t \times s)</tex>-матрица, где <tex>s \le t</tex>. Положим <tex>C = PQ</tex>. Минор порядка <tex>s</tex> матрицы <tex>Q</tex> называется '''соответствующим минором минору порядка <tex>s</tex> матрицы <tex>P</tex>''', если множество номеров строк, составляющих матрицу первого минора, равно множеству номеров столбцов, составляющих матрицу второго минора.
}}
{{Теорема
Кирхгоф, 1847
|statement=
Число остовов в связном неодноэлементном обыкновенном графе <tex>G</tex> равно алгебраическому дополнению любого элемента [[Матрица Кирхгофа|матрицы Кирхгофа ]] <tex>B(G)</tex>.
|proof=
Пусть <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 * I^T</tex>. Пусть <tex>B'</tex> - подматрица матрицы <tex>B</tex>, полученная удалением последней строки. Тогда имеем <tex>B' = J * J^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>. Осталось отметить, что по лемме алгебраические дополнения всех элементов матрицы Кирхгофа равны между собой.
