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