Коды Прюфера — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 52 промежуточные версии 11 участников)
Строка 1: Строка 1:
== Коды Прюфера. ==
+
== Алгоритм построения кодов Прюфера ==
Кодирование Прюфера переводит помеченные деревья порядка n в последовательность чисел от 1 до n по алгоритму:
+
Кодирование Прюфера переводит [[Количество помеченных деревьев#Помеченное дерево|помеченные деревья порядка <tex>n</tex>]] в последовательность чисел от <tex>1</tex> до <tex>n</tex> по алгоритму:<br>
  Пока количество вершин <math>>1</math>{
+
Пока количество вершин больше двух:
    1. Выбирается лист с минимальным номером.
+
# Выбирается лист <tex>v</tex> с минимальным номером.
    2. В последовательность Прюфера добавляется номер смежной вершины.
+
# В код Прюфера добавляется номер вершины, смежной с <tex>v</tex>.
    3. Лист и инцидентное ребро удаляются из дерева.
+
# Вершина <tex>v</tex> и инцидентное ей ребро удаляются из дерева.
  }
+
<br>
Полученная последовательность и есть '''код Прюфера'''.
+
Полученная последовательность называется '''кодом Прюфера''' ''(англ. Prüfer code)'' для заданного дерева.
 +
 
 +
{{Лемма
 +
|statement=
 +
Номер вершины <tex>v</tex> встречается в коде Прюфера тогда и только тогда, когда <tex>v</tex> не является листом, причём встречается этот номер к коде дерева в точности <math>\deg v - 1</math> раз.
 +
|proof=
 +
# Вершина с номером <tex>n</tex> не может быть удалена, следовательно на последнем шаге у неё была смежная вершина, и число <tex>n</tex> встретилось в коде.
 +
# Если вершина не является листом, то у неё на некотором шаге была смежная вершина <tex>-</tex> лист, следовательно номер этой вершины встречается в коде.
 +
# Если вершина является листом с номером меньше <tex>n</tex>, то она была удалена до того, как был удален её сосед, следовательно её номер не встречается в коде.
 +
 
 +
Таким образом, номера всех вершин, не являющихся листьями или имеющих номер <tex>n</tex>, встречаются в коде Прюфера, а остальные <tex>-</tex> нет.
 +
}}
  
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
По любой последовательности длиной <math>n - 2</math> из чисел от <math>1</math> до <math>n</math> можно построить помеченное дерево.
+
По любой последовательности длины <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex> можно построить помеченное дерево,
 +
для которого эта последовательность является кодом Прюфера.
 
|proof=
 
|proof=
Доказательство по индукции.
+
Доказательство проведем по индукции по числу <tex>n</tex><br>
База. <math>n = 1</math> - верно.
+
<u>''База индукции:''</u>
<br>
+
 
Переход <math>n \rightarrow n + 1</math>.
+
<tex>n = 1</tex> <tex>-</tex> верно.
<br>
+
 
Пусть у нас есть последовательность: <math>A = [a_1, a_2, ..., a_{n - 2}].</math>
+
<u>''Индукционный переход:''</u>
Выберем минимальное число <math>v</math> не лежащее в A. Это означает, что <math>v</math> - вершина, которую мы удалили первой, а, значит, это лист. Соединяем <math>v</math> и <math>a_1</math> ребром. Т.к. <math>v</math> - лист - он нам больше не помешает. Выкинем из последовательности <math>A</math> - <math>a_1</math> и применим предположение индукции.
+
 
 +
Пусть для числа <tex>n</tex> верно, построим доказательство для <tex>n+1</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>. А теперь мы можем применить предположение индукции.
 
}}
 
}}
  
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Кодирование Прюфера задаёт биекцию между множествами помеченных деревьев порядка <math>n</math> и последовательностями длиной <math>n - 2</math> из чисел от <math>1</math> до <math>n</math>  
+
Кодирование Прюфера задаёт биекцию между множествами помеченных деревьев порядка <math>n</math> и последовательностями длиной <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex>
 
|proof=
 
|proof=
1. Каждому помеченному дереву соотвествует последовательность и только одна - Верно по построению кода.
+
# Каждому помеченному дереву приведенный алгоритм сопоставляет последовательность.
<br>
+
# Каждой последовательности, как следует из предыдущей леммы, соотвествует помеченное дерево.
2. Каждой последовательности соотвествует помеченное дерево и только одно - Верно по предыдущей лемме, т.к. восстанавливали мы однозначно.  
 
 
}}
 
}}
  
''Следствие:''
+
Следствием из этой теоремы является [[Количество помеченных деревьев|формула Кэли]].
Количество различных помеченных деревьев порядка <math>n - n^{n - 2}</math>.
+
 
 +
== Пример построения кода Прюфера ==
 +
[[Файл: 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
 +
 
 +
 
 +
== Пример декодирования кода Прюфера ==
 +
[[Файл: backprufer.png|700px]]
 +
 
 +
==См. также==
 +
*[[Связь матрицы Кирхгофа и матрицы инцидентности]]
 +
*[[Матрица Кирхгофа]]
 +
*[[Количество помеченных деревьев]]
 +
*[[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
 +
 
 +
 
 +
== Источники информации ==
 +
* [http://www.intuit.ru/department/algorithms/graphsuse/11/2.html Университет INTUIT | Представление с помощью списка ребер и кода Прюфера]
 +
 
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Остовные деревья ]]
 +
[[Категория: Свойства остовных деревьев ]]

Текущая версия на 19:06, 4 сентября 2022

Алгоритм построения кодов Прюфера

Кодирование Прюфера переводит помеченные деревья порядка [math]n[/math] в последовательность чисел от [math]1[/math] до [math]n[/math] по алгоритму:
Пока количество вершин больше двух:

  1. Выбирается лист [math]v[/math] с минимальным номером.
  2. В код Прюфера добавляется номер вершины, смежной с [math]v[/math].
  3. Вершина [math]v[/math] и инцидентное ей ребро удаляются из дерева.


Полученная последовательность называется кодом Прюфера (англ. Prüfer code) для заданного дерева.

Лемма:
Номер вершины [math]v[/math] встречается в коде Прюфера тогда и только тогда, когда [math]v[/math] не является листом, причём встречается этот номер к коде дерева в точности [math]\deg v - 1[/math] раз.
Доказательство:
[math]\triangleright[/math]
  1. Вершина с номером [math]n[/math] не может быть удалена, следовательно на последнем шаге у неё была смежная вершина, и число [math]n[/math] встретилось в коде.
  2. Если вершина не является листом, то у неё на некотором шаге была смежная вершина [math]-[/math] лист, следовательно номер этой вершины встречается в коде.
  3. Если вершина является листом с номером меньше [math]n[/math], то она была удалена до того, как был удален её сосед, следовательно её номер не встречается в коде.
Таким образом, номера всех вершин, не являющихся листьями или имеющих номер [math]n[/math], встречаются в коде Прюфера, а остальные [math]-[/math] нет.
[math]\triangleleft[/math]
Лемма:
По любой последовательности длины [math]n - 2[/math] из чисел от [math]1[/math] до [math]n[/math] можно построить помеченное дерево, для которого эта последовательность является кодом Прюфера.
Доказательство:
[math]\triangleright[/math]

Доказательство проведем по индукции по числу [math]n[/math]
База индукции:

[math]n = 1[/math] [math]-[/math] верно.

Индукционный переход:

Пусть для числа [math]n[/math] верно, построим доказательство для [math]n+1[/math]:

Пусть у нас есть последовательность: [math]A = [a_1, a_2, ..., a_{n - 2}].[/math]

Выберем минимальное число [math]v[/math] не лежащее в [math]A[/math]. По предыдущей лемме [math]v[/math] [math]-[/math] вершина, которую мы удалили первой. Соединим [math]v[/math] и [math]a_1[/math] ребром. Выкинем из последовательности [math]A[/math] число [math]a_1[/math]. Перенумеруем вершины, для всех [math]a_i \gt v[/math] заменим [math]a_i[/math] на [math]a_i - 1[/math]. А теперь мы можем применить предположение индукции.
[math]\triangleleft[/math]
Теорема:
Кодирование Прюфера задаёт биекцию между множествами помеченных деревьев порядка [math]n[/math] и последовательностями длиной [math]n - 2[/math] из чисел от [math]1[/math] до [math]n[/math]
Доказательство:
[math]\triangleright[/math]
  1. Каждому помеченному дереву приведенный алгоритм сопоставляет последовательность.
  2. Каждой последовательности, как следует из предыдущей леммы, соотвествует помеченное дерево.
[math]\triangleleft[/math]

Следствием из этой теоремы является формула Кэли.

Пример построения кода Прюфера

Prufer.png

Алгоритм декодирования кодa Прюфера

В массиве вершин исходного дерева [math]V[/math] найдём вершину [math]v_{min}[/math] с минимальным номером, не содержащуюся в массиве с кодом Прюфера [math]P[/math], т.е. такую, что она является листом или концом уже добавленного в граф ребра, т.е. она стала листом в процессе построения кода Прюфера (по первому пункту построения). Вершина [math]p_1[/math] была добавлена в код Прюфера как инцидентная листу с минимальным номером (по второму пункту построения), поэтому в исходном дереве существует ребро {[math]p_1[/math], [math]v_{min}[/math]}, добавим его в список ребер. Удалим первый элемент из массива [math]Р[/math], а вершину [math]v_{min}[/math] - из массива [math]V[/math] т.к. она больше не может являться листом (по третьему пункту построения). Будем выполнять вышеуказанные действия, пока массив [math]P[/math] не станет пустым. В конце работы алгоритма в массиве [math]V[/math] останутся две вершины, составляющие последнее ребро дерева (это следует из построения).

Реализация

# P - код Прюфера
# V - вершины
function buildTree(P, V):
   while not P.empty():
      u = P[0]
      v = min(x [math]\in[/math] V: P.count(x) == 0)
      G.push({u, v})
      P.erase(0)
      V.erase(indexOf(v))
   G.push({v[0], v[1]})
   return G


Пример декодирования кода Прюфера

Backprufer.png

См. также


Источники информации