Простой путь, Гамильтонов путь, Гамильтонов цикл
Ошибка.
Попробуйте повторить позже
Пусть в графе 
с 
вершинами максимальное число попарно несмежных вершин равно 
При этом при удалении любых 
вершин граф остается связным. Докажите, что если 
то в графе существует гамильтонов цикл.
Подсказка 0
Введем обозначения. Пусть α(G) — наибольшее количество вершин во всех возможных подграфах G' таких, что никакие две вершины G' не соединены ребром, k(G) — наименьшее количество вершин графа G, удаление которых приводит к потери связности G. Так, исходная задача может быть переформулировано в следующем виде:
Подсказка 1
Рассмотрите 2 случая: граф - дерево, и в графе есть циклы. Разберите сначала случай дерева, он проще. Обратите внимание на висячие вершины.
Подсказка 2
Рассмотрим случай, когда в графе есть цикл. Хочется рассмотреть какую-то операцию над графом, которая что-то говорит про не смежность вершин и связана с циклами. Предлагается удалить из графа цикл наибольшей длины и посмотреть на получившиеся компоненты связности. Подумайте сколько их могло оказаться? Как они устроены?
Подсказка 3
Рассмотрите множество вершин цикла, связанных с какой-либо компонентой связности. Найдите связь количества всех таких вершин с интересующим нас значением k(G). Осталось оценить как-то α(G). Как можно к нему подобраться?
Подсказка 4
Рассмотрите множество соседей в цикле, рассматриваемых выше. Нужно сравнить количество элементов в этом множестве с чему-нибудь. Сравните с k(G), α(G). Как это можно сделать? Для этого достаточно понять, что это множество независимо.
Введем обозначения. Пусть 
— наибольшее количество вершин во всех возможных подграфах 
таких, что никакие две вершины
не соединены ребром, 
— наименьшее количество вершин графа 
удаление которых приводит к потери связности
Так, исходная задача может быть переформулировано в следующем виде:
Пусть 
— граф, такой, что 
и 
Тогда 
— гамильтонов.
Перейдем к доказательству. Положим 
Предположим сначала, что в 
нет циклов. Поскольку 
и
граф связный, а, значит, 
— это дерево. Т.к. 
то в 
есть хотя бы две несвязные висячие вершины, а,
значит,
откуда в 
есть хотя бы один цикл. Пусть 
— самый длинный простой цикл в 
причем 
Удалим из 
все вершины, лежащие в 
и обозначим за 
любую связную компоненту в оставшемся графе. Определим
Сразу ясно, что 
(действительно, связность могла нарушиться только из-за
удаления ребер в 
Более того, 
не содержит 
для любого 
из множества 
(положим 
иначе в
есть цикл, длиннее 
Все вышесказанное означает, что 
и 
а, значит, 
поскольку при
удалении 
множество 
уже образует отдельную компоненту связности.
.png)
Рис. 1: цикл длиннее, чем 
в первом случае
Определим 
— соседи всех 
из 
например, против часовой стрелки. Из рисунка выше
следует, что 
пусто 
Заметим теперь, что 
независимое множество, иначе в 
опять-таки,
есть цикл длиннее 
а, значит, 
откуда 
.png)
Рис. 2: цикл длиннее, чем 
во втором случае
Рассмотрим произвольную вершину 
и множество 
Поскольку 
то 
— тоже независимое
множество, а, значит, 
— противоречие.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
