В связном графе n вершин, все степени которых равны 5. Какова наибольшая длина эйлерова пути, который можно построить в таком графе независимо от величины n?

задан 12 Янв 16:15

Каждая внутренняя вершина в эйлеровом пути имеет четную степень. Наибольшее четное число не большее 5 это 4. Крайние вершины имеют нечетную степень. Наибольшее нечетное не большее 5 это 5. Таким образом наибольшее число ребер в нашем пути (4n+2)/2. Остается показать, что такой путь существует. Убрав по ребру у каждой вершины строим эйлеров цикл длины 2n. Добавляя ребро к произвольной вершине получаем эйлеров путь длины 2n+1

(12 Янв 17:01) abc
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×375
×4

задан
12 Янв 16:15

показан
135 раз

обновлен
12 Янв 17:01

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

по почте:

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

по RSS:

Ответы

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

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