Изменения

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

Коды Прюфера

8 байт добавлено, 02:29, 9 октября 2010
Коды Прюфера.
{{Лемма
|statement=
Номера всех вершин, которые не являются листьями или с имеют номером <tex>n</tex>, встречаются в коде Прюфера. А те, которые не входят - являются листьями.
|proof=
1. Вершина <tex>n</tex> не удаляется, так как у неё максимальный номер (в графе с <tex>>1</tex> вершиной - <tex>\leq 2</tex> листа), а, значит, на последнем шаге у неё была смежная вершина. <tex>\Rightarrow</tex> n - как минимум один раз встретилось в коде.
Анонимный участник

Навигация