Докажите, что если для G выполнено условие: $$ 2\| G \| \geq | G |^{2} - 3|G| + 6$$, где ||G|| - это количество ребёр, |G| - количество вершин, то в нем есть гамильтонов цикл. Рассматриваются только простые графы. задан 8 Ноя '20 1:12 gg_math15
показано 5 из 6
показать еще 1
|
Добавим к условию, что графы считаются простыми, и число вершин $%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 Ноя '20 11:19 falcao @falcao извините, а по какому поводу вы пишите: Остальные удаляемые рёбра, инцидентные v, не инцидентны w ?
(21 Ноя '20 15:30)
gg_math15
@gg_math15: я бы советовал Вам начинать с того, что проверять каждое утверждение на истинность. У нас граф простой. Вершины v и w соединены ребром. Остальные рёбра или инцидентны v, или инцидентны w, или ни то, ни другое. То есть сказанное является правдой, причём очевидной правдой. Тогда она принимается, и читаем дальше. Если задумываться каждый раз над вопросом "зачем", то трудно будет дочитать до конца. И уже когда всё прочитано и понято, можно перечитывать и задавать вопросы такого уровня. Тогда станет ясно, для чего это говорилось: для вывода, что из v или w выходит мало удаляемых рёбер.
(21 Ноя '20 16:11)
falcao
(продолжение) Назначение той фразы в том, что множество рёбер разделено на непересекающиеся части. Тогда, если в одной из них рёбер много, то в другой мало.
(21 Ноя '20 16:13)
falcao
|
Надо пояснить, что такое |G|, и что такое ||G||. Это не общепринятые обозначения, то есть их кто-то вводил, и при этом пояснял.
Также надо уточнить, какие графы рассматриваются (только простые, или не обязательно).
спасибо большое за замечание, исправил
извините, а можно ли вам в личные сообщения написать ?
@gg_math15: а тут на форуме нет службы личных сообщений. Что конкретно Вас интересует?
извините, наверное так делать нельзя, но я хотел задать вопрос про прошлую задачу, которую вы закрыли 1) почему там всегда инъекция ? 2) какое противоречие исходит, если мы предполагаем, что в G имеются гамильтоновы циклы ?
@gg_math15: так это и надо было там спросить, а не пытаться что-то скрыть или закрыть. Форум ведь и существует для обсуждений.
Если у нас есть цикл, вершины которого v(1), ... , v(n), то при сдвиге вершин на одну (по циклу) разные вершины переходят в разные. Это и означает инъективность. Если есть инъекция из A в B для конечных множеств, то |A|<=|B|. Поэтому наличие гамильтонова цикла влечёт |X|<=|N(X)|, что противоречит условию.