Связность и связные подграфы (клики)
Ошибка.
Попробуйте повторить позже
На окружности отмечены 
точек. Двое по очереди проводят отрезки с концами в отмеченных точках, первый своим ходом
проводит один красный отрезок, второй — 
синих. Один и тот же отрезок запрещено проводить дважды. Первый игрок хочет, чтобы
после нескольких ходов граф, образованный 
отмеченными точками и красными отрезками, был связным. Сможет ли второй ему
помешать?
Первый будет строить остовное дерево и каждым ходом проводить новое его ребро, то есть спустя 
ход игра будет окончена его
победой.
_________________________________________________________________________________________________________________________________________________________________________________
Лемма 1. Если первый успеет разбить вершины на компоненты связности размера не меньше 
— он победил.
Доказательство. Для победы второму нужно отделить некоторое множество из 
вершин от остальных 
на что
требуется 
ребер. За игру он успеет нарисовать всего 
ребер, что меньше 
при ![x∈ [101,n∕2]](/api/latex-service/v1/GetSession/184235/index-c8c946dd464df237ff84e39ab5281a84.svg)
.
Стратегия первого на ход такова: выбирать компоненту 
размера меньше 
из которой наружу идёт больше всего синих ребер и
соединять её с любой другой. Будем говорить, что синие рёбра идущие из 
в этот момент упомянуты.
_________________________________________________________________________________________________________________________________________________________________________________
Лемма 2. Каждое синее ребро упомянуто не больше 
раз.
Доказательство. Каждому упоминанию синего ребра 
соответствует проведение красного ребра из одной из компонент между
которыми оно проходит. Компоненты при этом увеличиваются, каждая из них делает это не больше 
раз. Следовательно, суммарно они
упоминают 
не больше 
раз.
_________________________________________________________________________________________________________________________________________________________________________________
Следствие. Суммарное количество упоминаний за игру не превосходит 
______________________________________________________________________________________________________________________________________________________
Доказательство. Предположим противное — первый не может сделать ход, который предписывает ему стратегия. То есть, некоторая
компонента 
отделена от остальных вершин. Тем самым, сейчас из неё ведет не меньше 
синих ребер. Посмотрим,
что было за 
ходов до. Из вершин 
в остальные вело не меньше 
синих ребер. Вершины 
составляли
максимум 
разных компонент, то есть одна из них содержала минимум 
синих ребер наружу. Следовательно,
некоторая компонента, минимум с таким количеством синих ребер наружу, с чем-то соединялась и упоминала все свои синие
рёбра.
_________________________________________________________________________________________________________________________________________________________________________________
Оценим снизу количество упоминаний как
Это больше чем 
противоречие.
Не сможет
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
