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