Редактирование: Коды Прюфера

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 6: Строка 6:
 
# Вершина <tex>v</tex> и инцидентное ей ребро удаляются из дерева.
 
# Вершина <tex>v</tex> и инцидентное ей ребро удаляются из дерева.
 
<br>
 
<br>
Полученная последовательность называется '''кодом Прюфера''' ''(англ. Prüfer code)'' для заданного дерева.
+
Полученная последовательность называется '''кодом Прюфера''' ''(англ. Codes Priifer)'' для заданного дерева.
  
 
{{Лемма
 
{{Лемма
Строка 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> нет.
Строка 28: Строка 28:
  
 
<tex>n = 1</tex> <tex>-</tex> верно.
 
<tex>n = 1</tex> <tex>-</tex> верно.
 
+
<br>
<u>''Индукционный переход:''</u>
+
<u>''Индукционный переход:</u>
 
+
<br>
Пусть для числа <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>. А теперь мы можем применить предположение индукции.
Строка 54: Строка 52:
  
 
==См. также==
 
==См. также==
*[[Связь матрицы Кирхгофа и матрицы инцидентности]]
+
* [[Матрица Кирхгофа]]
*[[Матрица Кирхгофа]]
 
*[[Количество помеченных деревьев]]
 
*[[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
 
 
 
  
 
== Источники информации ==
 
== Источники информации ==
* [http://www.intuit.ru/department/algorithms/graphsuse/11/2.html Университет INTUIT | Представление с помощью списка ребер и кода Прюфера]
+
* [http://www.intuit.ru/department/algorithms/graphsuse/11/2.html Интернет Университет INTUIT | Представление с помощью списка ребер и кода Прюфера]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Остовные деревья ]]
 
[[Категория: Остовные деревья ]]
 
[[Категория: Свойства остовных деревьев ]]
 
[[Категория: Свойства остовных деревьев ]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: