Редактирование: Коды Прюфера
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
| Текущая версия | Ваш текст | ||
| Строка 1: | Строка 1: | ||
| − | == | + | == Коды Прюфера. == |
| − | Кодирование Прюфера переводит | + | Кодирование Прюфера переводит помеченные деревья порядка <tex>n</tex> в последовательность чисел от <tex>1</tex> до <tex>n</tex> по алгоритму: |
| − | Пока количество вершин больше | + | Пока количество вершин больше одной { |
| − | + | 1. Выбирается лист <tex>v</tex> с минимальным номером. | |
| − | + | 2. В код Прюфера добавляется номер вершины, смежной с <tex>v</tex>. | |
| − | + | 3. Вершина <tex>v</tex> и инцидентное ей ребро удаляются из дерева. | |
| − | + | } | |
| − | Полученная последовательность называется '''кодом Прюфера' | + | Полученная последовательность называется '''кодом Прюфера''' для заданного дерева. |
{{Лемма | {{Лемма | ||
|statement= | |statement= | ||
| − | Номер вершины <tex>v</tex> встречается в коде Прюфера тогда и только тогда, когда <tex>v</tex> не является листом | + | Номер вершины <tex>v</tex> встречается в коде Прюфера тогда и только тогда, когда <tex>v</tex> не является листом или <tex>v</tex> имеет номер <tex>n</tex>. |
|proof= | |proof= | ||
# Вершина с номером <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> нет. | ||
| Строка 24: | Строка 24: | ||
для которого эта последовательность является кодом Прюфера. | для которого эта последовательность является кодом Прюфера. | ||
|proof= | |proof= | ||
| − | Доказательство проведем по индукции | + | Доказательство проведем по индукции. <br> |
| − | + | База. <tex>n = 1</tex> <tex>-</tex> верно. | |
| − | + | <br> | |
| − | <tex>n = 1</tex> <tex>-</tex> верно. | + | Переход от <tex>n</tex> к <tex>n + 1</tex>. |
| − | + | <br> | |
| − | < | ||
| − | |||
| − | |||
| − | |||
Пусть у нас есть последовательность: <tex>A = [a_1, a_2, ..., a_{n - 2}].</tex> | Пусть у нас есть последовательность: <tex>A = [a_1, a_2, ..., a_{n - 2}].</tex> | ||
Выберем минимальное число <tex>v</tex> не лежащее в <tex>A</tex>. По предыдущей лемме <tex>v</tex> <tex>-</tex> вершина, которую мы удалили первой. Соединим <tex>v</tex> и <tex>a_1</tex> ребром. Выкинем из последовательности <tex>A</tex> число <tex>a_1</tex>. Перенумеруем вершины, для всех <tex>a_i > v</tex> заменим <tex>a_i</tex> на <tex>a_i - 1</tex>. А теперь мы можем применить предположение индукции. | Выберем минимальное число <tex>v</tex> не лежащее в <tex>A</tex>. По предыдущей лемме <tex>v</tex> <tex>-</tex> вершина, которую мы удалили первой. Соединим <tex>v</tex> и <tex>a_1</tex> ребром. Выкинем из последовательности <tex>A</tex> число <tex>a_1</tex>. Перенумеруем вершины, для всех <tex>a_i > v</tex> заменим <tex>a_i</tex> на <tex>a_i - 1</tex>. А теперь мы можем применить предположение индукции. | ||
| Строка 53: | Строка 49: | ||
[[Файл: backprufer.png|700px]] | [[Файл: backprufer.png|700px]] | ||
| − | + | == Источники == | |
| − | + | [http://www.intuit.ru/department/algorithms/graphsuse/11/2.html Интернет Университет INTUIT | Представление с помощью списка ребер и кода Прюфера] | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | == Источники | ||
| − | |||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Остовные деревья ]] | [[Категория: Остовные деревья ]] | ||
| − | |||
