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