Докажите, что если для G выполнено условие: $$ 2\| G \| \geq | G |^{2} - 3|G| + 6$$, где ||G|| - это количество ребёр, |G| - количество вершин, то в нем есть гамильтонов цикл. Рассматриваются только простые графы.

задан 8 Ноя 1:12

изменен 8 Ноя 4:23

Надо пояснить, что такое |G|, и что такое ||G||. Это не общепринятые обозначения, то есть их кто-то вводил, и при этом пояснял.

Также надо уточнить, какие графы рассматриваются (только простые, или не обязательно).

(8 Ноя 1:33) falcao

спасибо большое за замечание, исправил

(8 Ноя 3:39) gg_math15

извините, а можно ли вам в личные сообщения написать ?

(8 Ноя 4:18) gg_math15

@gg_math15: а тут на форуме нет службы личных сообщений. Что конкретно Вас интересует?

(8 Ноя 5:01) falcao

извините, наверное так делать нельзя, но я хотел задать вопрос про прошлую задачу, которую вы закрыли 1) почему там всегда инъекция ? 2) какое противоречие исходит, если мы предполагаем, что в G имеются гамильтоновы циклы ?

(8 Ноя 5:23) gg_math15

@gg_math15: так это и надо было там спросить, а не пытаться что-то скрыть или закрыть. Форум ведь и существует для обсуждений.

Если у нас есть цикл, вершины которого v(1), ... , v(n), то при сдвиге вершин на одну (по циклу) разные вершины переходят в разные. Это и означает инъективность. Если есть инъекция из A в B для конечных множеств, то |A|<=|B|. Поэтому наличие гамильтонова цикла влечёт |X|<=|N(X)|, что противоречит условию.

(8 Ноя 5:32) falcao
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
0

Добавим к условию, что графы считаются простыми, и число вершин $%n$% не меньше трёх.

Разница между числом рёбер $%\frac{n(n-1)}2$% полного графа на $%n$% вершинах и числом рёбер рассматриваемого подграфа, которое не меньше $%f(n)=\frac{n^2-3n+6}2$%, составляет не больше $%n-3$%. Поэтому можно считать, что мы из полного графа удаляем $%n-3$% ребра, и надо доказать, что при этом получается гамильтонов граф. Отметим, что оценка является точной, так как удаление $%n-2$% рёбер, исходящих из одной вершины, привела бы уже к негамильтонову графу.

Проводим индукцию по $%n\ge3$%. При $%n=3$% всё очевидно. Пусть $%n > 3$%. Рассмотрим одно удаляемое ребро $%e$%, соединяющее вершины $%v$% и $%w$%. Остальные удаляемые рёбра, инцидентные $%v$%, не инцидентны $%w$%. Вместе их не больше $%n-4$%. Поэтому хотя бы для одной из этих вершин, которую можно считать равной $%v$%, число дополнительно удаляемых рёбер c началом $%v$%, не больше половины от этого числа, то есть $%\frac{n}2-2$%. Значит, остаётся не менее $%\frac{n}2$% рёбер с началом $%v$%, которые войдут в подграф.

Рассмотрим подграф $%G'$% на $%n-1$% вершине, не считая $%v$%. Легко видеть, что $%f(n)-f(n-1)=n-2$%, а удалили мы $%n-3$% ребра. Поэтому в $%G'$% останется более $%f(n-1)$% ребра, и к нему применимо индукционное предположение. Рассмотрим в $%G'$% гамильтонов цикл.

Вершина $%v$% соединена не менее чем с $%\frac{n}2$% вершинами этого цикла. Поэтому среди них найдутся две соседние в этом цикле. Тогда соединяющее их ребро цикла заменяем на два ребра, проходящие через $%v$%, и получаем гамильтонов цикл в $%G$%.

ссылка

отвечен 8 Ноя 11:19

@falcao извините, а по какому поводу вы пишите: Остальные удаляемые рёбра, инцидентные v, не инцидентны w ?

(21 Ноя 15:30) gg_math15

@gg_math15: я бы советовал Вам начинать с того, что проверять каждое утверждение на истинность. У нас граф простой. Вершины v и w соединены ребром. Остальные рёбра или инцидентны v, или инцидентны w, или ни то, ни другое. То есть сказанное является правдой, причём очевидной правдой. Тогда она принимается, и читаем дальше. Если задумываться каждый раз над вопросом "зачем", то трудно будет дочитать до конца. И уже когда всё прочитано и понято, можно перечитывать и задавать вопросы такого уровня. Тогда станет ясно, для чего это говорилось: для вывода, что из v или w выходит мало удаляемых рёбер.

(21 Ноя 16:11) falcao

(продолжение) Назначение той фразы в том, что множество рёбер разделено на непересекающиеся части. Тогда, если в одной из них рёбер много, то в другой мало.

(21 Ноя 16:13) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×576

задан
8 Ноя 1:12

показан
120 раз

обновлен
21 Ноя 16:13

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

по почте:

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

по RSS:

Ответы

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

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