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