Количество помеченных деревьев — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Количество помеченных деревьев.)
(Количество помеченных деревьев.)
Строка 11: Строка 11:
 
|statement=Число помеченных деревьев порядка <tex>n</tex> равно <tex>n^{n - 2}</tex>.
 
|statement=Число помеченных деревьев порядка <tex>n</tex> равно <tex>n^{n - 2}</tex>.
 
|proof=
 
|proof=
''Доказательство 1.'' Так как между помеченными деревьями порядка <tex>n</tex> и последовательностями длины <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex> существует биекция, <tex>|</tex>множество помеченных деревьев<tex>|</tex> = <tex>|</tex>множество последовательностей длины <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex><tex>|</tex> = <tex>n^{n - 2}</tex>. С помощью [[Коды Прюфера|кодов Прюфера]].
+
''Доказательство 1.'' Так как между помеченными деревьями порядка <tex>n</tex> и последовательностями длины <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex> существует биекция, <br> то <tex>|</tex>множество помеченных деревьев<tex>|</tex> = <tex>|</tex>множество последовательностей длины <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex><tex>|</tex> = <tex>n^{n - 2}</tex>. (Также смотри [[Коды Прюфера|кодов Прюфера]].)
 
<br>
 
<br>
 
''Доказательство 2.'' С помощью [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа |матрицы Кирхгофа]] для полного графа на <tex>n</tex> на вершинах.
 
''Доказательство 2.'' С помощью [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа |матрицы Кирхгофа]] для полного графа на <tex>n</tex> на вершинах.
 
}}
 
}}

Версия 22:29, 8 октября 2010

Помеченное дерево.

Определение:
Помеченное дерево порядка n - дерево порядка [math]n[/math], вершинам которого взаимно однозначно соответствуют числа от 1 до n.


Количество помеченных деревьев.

Теорема (Формула Кэли):
Число помеченных деревьев порядка [math]n[/math] равно [math]n^{n - 2}[/math].
Доказательство:
[math]\triangleright[/math]

Доказательство 1. Так как между помеченными деревьями порядка [math]n[/math] и последовательностями длины [math]n - 2[/math] из чисел от [math]1[/math] до [math]n[/math] существует биекция,
то [math]|[/math]множество помеченных деревьев[math]|[/math] = [math]|[/math]множество последовательностей длины [math]n - 2[/math] из чисел от [math]1[/math] до [math]n[/math][math]|[/math] = [math]n^{n - 2}[/math]. (Также смотри кодов Прюфера.)

Доказательство 2. С помощью матрицы Кирхгофа для полного графа на [math]n[/math] на вершинах.
[math]\triangleleft[/math]