В неориентированном графе на 100 вершинах любой подграф из 40 вершин связен. Верно ли что обязательно существует а) эйлеров цикл, б) гамильтонов цикл в графе?

задан 19 Ноя 15:19

а) Это вопрос явно "провокационного" типа, потому что даже в полном графе все степени вершин будут нечётны, и от эйлерова он крайне далёк. При этом все подграфы там связны. За этим вопросом скрывается нехитрая мысль выяснить, знает ли отвечающий критерий эйлеровости :)

б) Любая вершина имеет степень > 60, так как в противном случае она не соединена с 39, которые вместе с ней дадут несвязный подграф. Для гамильтоновости достаточно степеней вершин >=50 по теореме Дирака.

(19 Ноя 15:33) falcao

@falcao: спасибо. Извиняюсь за оффтоп, а Вы знаете свое число Эрдеша?

(20 Ноя 2:20) Konon

@Konon: да, знаю. У меня есть очень много работ с коллегой, который имеет совместную статью с соавтором Эрдёша, то есть оно равно 3.

(20 Ноя 2:47) falcao

@falcao: ого, очень близко к легенде :D

(20 Ноя 2:50) Konon
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×1,550
×182

задан
19 Ноя 15:19

показан
42 раза

обновлен
20 Ноя 2:50

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

по почте:

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

по RSS:

Ответы

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

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