Каким деревьям соответствует код прюфера, в которых все числа различны?

задан 25 Май '17 15:24

Что означает последнее странное буквосочетание в заголовке?

(25 Май '17 16:59) falcao

Это случайно получилось)

(25 Май '17 17:38) Spl35

@Spl35: а как такое могло получиться случайно? :)

(25 Май '17 17:48) falcao
10|600 символов нужно символов осталось
0

Известно, что номер вершины встречается в коде Прюфера ровно k-1 раз, где k -- степень вершины размеченного дерева. Все числа кода будут различными тогда и только тогда, когда нет вершин степени 3 и более. Это значит, что дерево является линейными графом, что легко проверяется индукцией по числу вершин.

ссылка

отвечен 25 Май '17 16:58

А можете написать проверку индукцией

(25 Май '17 17:31) Spl35

@Spl35: в каждом дереве, у которого более одной вершины, есть "висячая" вершина (степени 1). Её можно временно удалить вместе с ребром. Получится дерево, в котором вершин степени >=3 нет. Тогда это линейный граф по предположению индукции. Теперь вернём удалённое ребро на место. Оно к какой-то вершине подсоединится. Если к концевой, то это даст линейный граф. Если не к концевой, то возникнет вершина степени 3 -- противоречие.

(25 Май '17 17:47) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,475

задан
25 Май '17 15:24

показан
864 раза

обновлен
25 Май '17 17:48

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru