Подсчёт числа остовных деревьев с помощью матрицы Кирхгофа

Лемма:

Пусть [math]H[/math] — обыкновенный [math](n, n - 1)[/math] — граф, [math]n \geqslant 2 [/math], [math]I[/math] — матрица инцидентности некоторой его ориентации, [math]M[/math] — произвольный минор порядка [math]n - 1[/math] матрицы [math]I[/math]. Тогда если [math]H[/math] не является деревом, то [math]M = 0[/math]; если [math]H[/math] — дерево, то [math]M = \pm 1[/math].

Доказательство:

[math]\triangleright[/math]

Заметим, что смена нумерации вершин и нумерации ребер графа [math]H[/math] приводит к перестановке строк и перестановке столбцов матрицы [math]I[/math]. Рассматриваемый минор при этом может сменить лишь знак. Пусть [math]v[/math] — вершина, соответствующая строке матрицы [math]I[/math], не вошедшей в матрицу минора [math]M[/math]. Пусть [math]H[/math] не является деревом. Тогда граф [math]H[/math] несвязен. Пусть [math]v_1, ..., v_t[/math] — множество вершин некоторой компоненты связности [math]H_1[/math] графа [math]H[/math], не содержащей [math]v[/math]. Если [math]t = 1[/math], то [math]v_1[/math] — изолированная вершина и в матрице минора [math]M[/math] имеется нулевая строка, поэтому [math]M = 0[/math]. Пусть [math]t \gt 1[/math]. С помощью подходящей перенумерации вершин и ребер из [math]H[/math] матрицу [math]I[/math] приведем к клеточному виду [math]\begin{pmatrix} I_1 & 0\\0 & I_2 \end{pmatrix}[/math], где [math]I_1[/math] — матрица инцидентности ориентации компоненты [math]H_1[/math], а вершине [math]v[/math] отвечает строка, проходящая через [math]I_2[/math]. Каждый столбец, проходящий через [math]I_1[/math], содержит точно одну единицу и точно одну [math]-1[/math] (остальные элементы равны нулю). Следовательно, сумма первых [math]t[/math] строк равна [math]0[/math]. Так как первые [math]t[/math] строк входят в матрицу минора [math]M[/math], имеем [math]M = 0[/math]. Пусть [math]H[/math] является деревом. Заново перенумеруем вершины и ребра графа [math]H[/math] с помощью следующей процедуры. В качестве [math]v_1[/math] возьмем одну из висячих вершин дерева [math]H[/math], отличную от [math]v[/math]. Через [math]e_1[/math] обозначим инцидентное ей висячее ребро. Рассмотрим дерево [math]H_1 = H - v_1[/math]. Если его порядок [math]\geqslant 2[/math], то через [math]v_2[/math] обозначим одну из висячих вершин, отличных от [math]v[/math], а через [math]e_2[/math] — инцидентное ей висячее ребро. Положим [math]H_2 = H_1 - e_2[/math]. Продолжаем этот процесс до тех пор, пока не получим одноэлементное дерево [math]H_{n-1}[/math], единственной вершиной которого обязательно будет вершина [math]v[/math]. Получим нумерацию вершин [math]v_1, ..., v_n = v[/math] и нумерацию ребер [math]e_1, ..., e_{n-1}[/math]. В новой нумерации матрица [math]I[/math] приведется к виду [math]\begin{pmatrix} \pm 1 & 0 &\cdots &0\\* & \pm 1 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ * & * & \cdots & \pm 1\\ * & * & \cdots & * \end{pmatrix}[/math], причем вершине [math]v[/math] отвечает последняя строка (здесь каждый диагональный элемент равен [math]1[/math] или [math]-1[/math], а через [math]*[/math] обозначены элементы матрицы, значения которых не вписаны в явном виде). Таким образом, матрица минора имеет треугольный вид и [math]M = \pm1[/math].

[math]\triangleleft[/math]

Определение:

Пусть [math]P[/math] и [math]Q[/math] — соответственно [math](s \times t)[/math] — матрица и [math](t \times s)[/math] — матрица, где [math]s \leqslant t[/math]. Положим [math]C = PQ[/math]. Минор порядка [math]s[/math] матрицы [math]Q[/math] называется соответствующим минором минору порядка [math]s[/math] матрицы [math]P[/math], если множество номеров строк, составляющих матрицу первого минора, равно множеству номеров столбцов, составляющих матрицу второго минора.

Теорема (Формула Бине-Коши):

Определитель матрицы [math]C[/math] равен сумме всевозможных попарных произведений миноров порядка [math]s[/math] матрицы [math]P[/math] на соответствующие миноры матрицы [math]Q[/math].

Следствие
При [math]s = t[/math] определитель произведения двух квадратных матриц порядка [math]s[/math] равен произведению определителей этих матриц

Теорема (Кирхгоф, 1847):

Число остовов в связном неодноэлементном обыкновенном графе [math]G[/math] равно алгебраическому дополнению любого элемента матрицы Кирхгофа [math]B(G)[/math].

Доказательство:

[math]\triangleright[/math]

Пусть [math]G[/math] — произвольный связный обыкновенный [math](n, m)[/math] — граф, [math]n \geqslant 2[/math] и [math]I[/math] — матрица инцидентности какой-либо ориентации графа [math]G[/math]. Заметим, что [math]m \geqslant n - 1[/math] в силу связности графа [math]G[/math]. По лемме выполняется [math]B = B(G) = I \cdot I^T[/math]. Пусть [math]B'[/math] — подматрица матрицы [math]B[/math], полученная удалением последней строки. Тогда имеем [math]B' = JJ^T[/math], где [math]J[/math] — это [math]((n - 1) \times m)[/math] — матрица. Очевидно, [math]B_{nn} = \det B'[/math] есть алгебраическое дополнение элемента [math]\beta_{nn}[/math] в матрице Кирхгофа [math]B[/math]. В силу формулы Бине-Коши [math]B_{nn}[/math] равно сумме квадратов всех миноров порядка [math](n - 1)[/math] матрицы [math]J[/math]. Согласно лемме, доказанной выше, каждый такой минор [math]M[/math] равен [math]\pm 1[/math], если остовный подграф графа [math]G[/math], ребра которого соответствуют столбцам, вошедшим в матрицу минора [math]M[/math], является деревом, и равен [math]0[/math] в другом случае. Следовательно, [math]B_{nn}[/math] равно числу остовов графа [math]G[/math]. Осталось отметить, что по лемме алгебраические дополнения всех элементов матрицы Кирхгофа равны между собой.

[math]\triangleleft[/math]

См. также

• Связь матрицы Кирхгофа и матрицы инцидентности
• Матрица Кирхгофа
• Количество помеченных деревьев
• Коды Прюфера

Источники информации

• Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.