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