41
правка
Изменения
м
Нет описания правки
|proof=
# Вершина с номером <tex>n</tex> не может быть удалена, следовательно на последнем шаге у неё была смежная вершина, и число <tex>n</tex> встретилось в коде.
# Если вершина не является листом, то у неё на некотором шаге была смежная вершина <tex>- </tex> лист, следовательно номер этой вершины встречается в коде.
# Если вершина является листом с номером меньше <tex>n</tex>, то она была удалена до того, как был удален ее сосед, следовательно ее номер не встречается в коде.
Таким образом, номера всех вершин, не являющихся листьями или имеющих номер <tex>n</tex>, встречаются в коде Прюфера, а остальные <tex>- </tex> нет.
}}
|proof=
Доказательство проведем по индукции.
База. <tex>n = 1</tex> <tex> - </tex> верно.
<br>
Переход от <tex>n</tex> к <tex>n + 1</tex>.
<br>
Пусть у нас есть последовательность: <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>. А теперь мы можем применить предположение индукции.
}}
== Источники ==
[http://www.intuit.ru/department/algorithms/graphsuse/11/2.html Интернет Университет INTUIT | Представление с помощью списка ребер и кода Прюфера]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]]
