Материал из Викиконспекты
Помеченное дерево.
| Определение: |
| Помеченное дерево порядка 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] |
