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