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


File translated from TEX by TTH, version 3.64.
On 03 Apr 2005, 08:56.