Простой путь, Гамильтонов путь, Гамильтонов цикл
Ошибка.
Попробуйте повторить позже
нельзя переставить так, чтобы соседние числа отличались либо на 3, либо на
5.
Пункт а), подсказка 1
Мы понимаем, какие у каждого числа могут быть соседи. Такие связи намекают нам на то, что здесь пригодится нарисовать граф) Как теперь переформулировать задачу?
Пункт а), подсказка 2
Теперь если числа - это вершины, а возможные соседи - ребра, то нам надо доказать, что нет простого пути на всех вершинах. Попробуйте рассмотреть для начала вершинки, в которых самая маленькая степень и порисовать путь на всех вершинах...
Пункта а), подсказка 3
Можно заметить, что если вы проходите через одну из маленьких по степени вершин, то в другую вы больше не придете. Разбейте так эти вершинки с маленькой степенью на пары и строго опишите это!
Пункт б), подсказка 1
Теперь также сделайте граф и посмотрите на отличие от предыдущего, вдруг теперь можно построить пример)
.png)
(a) Начертим граф возможных соседей. Рассмотрим три пары вершин в четырехугольниках на графе (они отмечены жирными точками), а именно: (2, 10), (1, 9) и (3, 11) – это вершины с наименьшей степенью (количеством соседей), равной 2. Предположим, от противного, что есть простой путь на графе (т.е. без повторения вершин), проходящий через все вершины. Тогда найдется такая пара вершин среди трех указанных пар, что путь не начинается и не кончается в вершинах из этой пары (такая пара есть, т.к. концов у пути – два, а пар – три). Таким образом, обе вершины этой пары – “проходны”, но если впервые будет пройдена одна вершина из этой пары, то вторая вершина станет изолированной («отрезанной»: в неё нельзя будет попасть потом). Противоречие.
(b) Пример перестановки: 2, 5, 10, 7, 12, 9, 4, 1, 6, 3, 8, 11. Граф (см. рисунок) помогает построить подобный пример.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
