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