Дано дерево на семи вершинах. Известно, что в этом дереве по меньшей мере три вершины имеют степень 1, и как минимум две вершины имеют степень 3. Найдите последовательность степеней вершин этого графа.

задан 26 Окт '15 11:37

10|600 символов нужно символов осталось
1

У этого дерева 6 рёбер, поэтому сумма степеней вершин равна 12. У нас уже есть 1+1+1+3+3 для пяти вершин, поэтому оставшиеся две вершины в сумме должны иметь степень 3, то есть их степени равны 1 и 2. То есть получается 1, 1, 1, 1, 2, 3, 3.

Пример дерева с таким свойством нетрудно нарисовать. С точностью до изоморфизма, таких деревьев имеется два -- в зависимости от того, соединены ли между собой вершины степени 3.

ссылка

отвечен 26 Окт '15 12:35

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×540
×525
×173
×130
×7

задан
26 Окт '15 11:37

показан
2002 раза

обновлен
26 Окт '15 12:35

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

по почте:

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

по RSS:

Ответы

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

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