Коды Прюфера — различия между версиями
(→Источники информации) |
(→Алгоритм построения кодов Прюфера) |
||
(не показана 1 промежуточная версия 1 участника) | |||
Строка 6: | Строка 6: | ||
# Вершина <tex>v</tex> и инцидентное ей ребро удаляются из дерева. | # Вершина <tex>v</tex> и инцидентное ей ребро удаляются из дерева. | ||
<br> | <br> | ||
− | Полученная последовательность называется '''кодом Прюфера''' ''(англ. | + | Полученная последовательность называется '''кодом Прюфера''' ''(англ. Prüfer code)'' для заданного дерева. |
{{Лемма | {{Лемма | ||
Строка 14: | Строка 14: | ||
# Вершина с номером <tex>n</tex> не может быть удалена, следовательно на последнем шаге у неё была смежная вершина, и число <tex>n</tex> встретилось в коде. | # Вершина с номером <tex>n</tex> не может быть удалена, следовательно на последнем шаге у неё была смежная вершина, и число <tex>n</tex> встретилось в коде. | ||
# Если вершина не является листом, то у неё на некотором шаге была смежная вершина <tex>-</tex> лист, следовательно номер этой вершины встречается в коде. | # Если вершина не является листом, то у неё на некотором шаге была смежная вершина <tex>-</tex> лист, следовательно номер этой вершины встречается в коде. | ||
− | # Если вершина является листом с номером меньше <tex>n</tex>, то она была удалена до того, как был удален | + | # Если вершина является листом с номером меньше <tex>n</tex>, то она была удалена до того, как был удален её сосед, следовательно её номер не встречается в коде. |
Таким образом, номера всех вершин, не являющихся листьями или имеющих номер <tex>n</tex>, встречаются в коде Прюфера, а остальные <tex>-</tex> нет. | Таким образом, номера всех вершин, не являющихся листьями или имеющих номер <tex>n</tex>, встречаются в коде Прюфера, а остальные <tex>-</tex> нет. |
Версия 08:42, 17 октября 2019
Содержание
Алгоритм построения кодов Прюфера
Кодирование Прюфера переводит помеченные деревья порядка в последовательность чисел от до по алгоритму:
Пока количество вершин больше двух:
- Выбирается лист с минимальным номером.
- В код Прюфера добавляется номер вершины, смежной с .
- Вершина и инцидентное ей ребро удаляются из дерева.
Полученная последовательность называется кодом Прюфера (англ. Prüfer code) для заданного дерева.
Лемма: |
Номер вершины встречается в коде Прюфера тогда и только тогда, когда не является листом, причём встречается этот номер к коде дерева в точности раз. |
Доказательство: |
|
Лемма: |
По любой последовательности длины из чисел от до можно построить помеченное дерево,
для которого эта последовательность является кодом Прюфера. |
Доказательство: |
Доказательство проведем по индукции по числу верно. Индукционный переход: Пусть для числа верно, построим доказательство для :Пусть у нас есть последовательность: Выберем минимальное число не лежащее в . По предыдущей лемме вершина, которую мы удалили первой. Соединим и ребром. Выкинем из последовательности число . Перенумеруем вершины, для всех заменим на . А теперь мы можем применить предположение индукции. |
Теорема: |
Кодирование Прюфера задаёт биекцию между множествами помеченных деревьев порядка и последовательностями длиной из чисел от до |
Доказательство: |
|
Следствием из этой теоремы является формула Кэли.
Пример построения кода Прюфера
Пример декодирования кода Прюфера
См. также
- Связь матрицы Кирхгофа и матрицы инцидентности
- Матрица Кирхгофа
- Количество помеченных деревьев
- Подсчет числа остовных деревьев с помощью матрицы Кирхгофа