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