Коды Прюфера — различия между версиями
(→Алгоритм построения кодов Прюфера) |
м (rollbackEdits.php mass rollback) |
||
(не показано 8 промежуточных версий 6 участников) | |||
Строка 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> нет. | ||
Строка 24: | Строка 24: | ||
для которого эта последовательность является кодом Прюфера. | для которого эта последовательность является кодом Прюфера. | ||
|proof= | |proof= | ||
− | Доказательство проведем по индукции | + | Доказательство проведем по индукции по числу <tex>n</tex><br> |
− | База | + | <u>''База индукции:''</u> |
− | < | + | |
− | + | <tex>n = 1</tex> <tex>-</tex> верно. | |
− | + | ||
+ | <u>''Индукционный переход:''</u> | ||
+ | |||
+ | Пусть для числа <tex>n</tex> верно, построим доказательство для <tex>n+1</tex>: | ||
+ | |||
Пусть у нас есть последовательность: <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>. А теперь мы можем применить предположение индукции. | ||
Строка 45: | Строка 49: | ||
== Пример построения кода Прюфера == | == Пример построения кода Прюфера == | ||
[[Файл: Prufer.png|500px]] | [[Файл: Prufer.png|500px]] | ||
+ | |||
+ | == Алгоритм декодирования кодa Прюфера == | ||
+ | |||
+ | В массиве вершин исходного дерева <tex>V</tex> найдём вершину <tex>v_{min}</tex> с минимальным номером, не содержащуюся в массиве с кодом Прюфера <tex>P</tex>, т.е. такую, что она является листом или концом уже добавленного в граф ребра, т.е. она стала листом в процессе построения кода Прюфера (по первому пункту построения). Вершина <tex>p_1</tex> была добавлена в код Прюфера как инцидентная листу с минимальным номером (по второму пункту построения), поэтому в исходном дереве существует ребро {<tex>p_1</tex>, <tex>v_{min}</tex>}, добавим его в список ребер. Удалим первый элемент из массива <tex>Р</tex>, а вершину <tex>v_{min}</tex> - из массива <tex>V</tex> т.к. она больше не может являться листом (по третьему пункту построения). Будем выполнять вышеуказанные действия, пока массив <tex>P</tex> не станет пустым. В конце работы алгоритма в массиве <tex>V</tex> останутся две вершины, составляющие последнее ребро дерева (это следует из построения). | ||
+ | |||
+ | === Реализация === | ||
+ | # P - код Прюфера | ||
+ | # V - вершины | ||
+ | '''function''' buildTree(P, V): | ||
+ | '''while'' '''not'' P.empty(): | ||
+ | u = P[0] | ||
+ | v = min(x '''<tex>\in</tex>''' V: P.count(x) == 0) | ||
+ | G.push({u, v}) | ||
+ | P.erase(0) | ||
+ | V.erase(indexOf(v)) | ||
+ | G.push({v[0], v[1]}) | ||
+ | '''return''' G | ||
+ | |||
== Пример декодирования кода Прюфера == | == Пример декодирования кода Прюфера == | ||
Строка 50: | Строка 72: | ||
==См. также== | ==См. также== | ||
− | * [[Матрица Кирхгофа]] | + | *[[Связь матрицы Кирхгофа и матрицы инцидентности]] |
+ | *[[Матрица Кирхгофа]] | ||
+ | *[[Количество помеченных деревьев]] | ||
+ | *[[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]] | ||
+ | |||
== Источники информации == | == Источники информации == | ||
− | * [http://www.intuit.ru/department/algorithms/graphsuse/11/2.html | + | * [http://www.intuit.ru/department/algorithms/graphsuse/11/2.html Университет INTUIT | Представление с помощью списка ребер и кода Прюфера] |
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Остовные деревья ]] | [[Категория: Остовные деревья ]] | ||
[[Категория: Свойства остовных деревьев ]] | [[Категория: Свойства остовных деревьев ]] |
Текущая версия на 19:06, 4 сентября 2022
Содержание
Алгоритм построения кодов Прюфера
Кодирование Прюфера переводит помеченные деревья порядка в последовательность чисел от до по алгоритму:
Пока количество вершин больше двух:
- Выбирается лист с минимальным номером.
- В код Прюфера добавляется номер вершины, смежной с .
- Вершина и инцидентное ей ребро удаляются из дерева.
Полученная последовательность называется кодом Прюфера (англ. Prüfer code) для заданного дерева.
Лемма: |
Номер вершины встречается в коде Прюфера тогда и только тогда, когда не является листом, причём встречается этот номер к коде дерева в точности раз. |
Доказательство: |
|
Лемма: |
По любой последовательности длины из чисел от до можно построить помеченное дерево,
для которого эта последовательность является кодом Прюфера. |
Доказательство: |
Доказательство проведем по индукции по числу верно. Индукционный переход: Пусть для числа верно, построим доказательство для :Пусть у нас есть последовательность: Выберем минимальное число не лежащее в . По предыдущей лемме вершина, которую мы удалили первой. Соединим и ребром. Выкинем из последовательности число . Перенумеруем вершины, для всех заменим на . А теперь мы можем применить предположение индукции. |
Теорема: |
Кодирование Прюфера задаёт биекцию между множествами помеченных деревьев порядка и последовательностями длиной из чисел от до |
Доказательство: |
|
Следствием из этой теоремы является формула Кэли.
Пример построения кода Прюфера
Алгоритм декодирования кодa Прюфера
В массиве вершин исходного дерева
найдём вершину с минимальным номером, не содержащуюся в массиве с кодом Прюфера , т.е. такую, что она является листом или концом уже добавленного в граф ребра, т.е. она стала листом в процессе построения кода Прюфера (по первому пункту построения). Вершина была добавлена в код Прюфера как инцидентная листу с минимальным номером (по второму пункту построения), поэтому в исходном дереве существует ребро { , }, добавим его в список ребер. Удалим первый элемент из массива , а вершину - из массива т.к. она больше не может являться листом (по третьему пункту построения). Будем выполнять вышеуказанные действия, пока массив не станет пустым. В конце работы алгоритма в массиве останутся две вершины, составляющие последнее ребро дерева (это следует из построения).Реализация
# P - код Прюфера
# V - вершины
function buildTree(P, V):
while not P.empty():
u = P[0]
v = min(x
V: P.count(x) == 0)
G.push({u, v})
P.erase(0)
V.erase(indexOf(v))
G.push({v[0], v[1]})
return G
Пример декодирования кода Прюфера
См. также
- Связь матрицы Кирхгофа и матрицы инцидентности
- Матрица Кирхгофа
- Количество помеченных деревьев
- Подсчет числа остовных деревьев с помощью матрицы Кирхгофа