Изменения

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

Коды Прюфера

11 байт добавлено, 02:39, 9 октября 2010
Коды Прюфера.
|proof=
1. Вершина <tex>n</tex> не удаляется, так как у неё максимальный номер (в графе с <tex>>1</tex> вершиной - <tex>\geq 2</tex> листа), а, значит, на последнем шаге у неё была смежная вершина. <tex>\Rightarrow</tex> <tex>n</tex> - как минимум один раз встретилось в коде.
 2. Если вершина - не лист, то у неё на каком-то шаге была смежная вершина - лист. А, значит, номер этой вершины был <tex>>1</tex> раза выписан в код. 
3. Так как вершина - лист(с номером не равным <tex>n</tex>), она была только удалена.
Анонимный участник

Навигация