Теорема. При n > 1 число остовов в полном графе Kn равно nn-2.
Доказательство.
Матрица Кирхгофа графа Kn имеет вид
Рассмотрим алгебраическое дополнение A11 элемента матрицы. Очевидно оно
имеет тот же вид, но размер матрицы будет n-1×n-1. Преобразуем определитель,
добавив к первой строке последовательно все остальные n-2 строки. Для
первого столбца имеем n-1+(n-2)(-1)=1. То же получится и для других
элементов первой строки. В результате определитель примет простой вид
Добавим первую строку (из единиц) ко всем строкам определителя
Литература.
Емеличев В.А., Мельников О.И., Сарванов В.И.,
Тышкевич Р.И. Лекции по теории графов.- М.:Наука, 1990.- 384 с.
|