Top.Mail.Ru

Часто ищут

Разделы

Бесплатно

Тема . Графы и турниры

Деревья и остовные деревья

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела графы и турниры
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#81407

В некоторой стране есть 100  городов, которые связаны такой сетью дорог, что из любого города в любой другой можно проехать только одним способом без разворотов. Схема сети дорог известна, развилки и перекрестки сети необязательно являются городами, всякая тупиковая ветвь сети обязательно заканчивается городом. Навигатор может измерить длину пути по этой сети между любыми двумя городами. Можно ли за 100  таких измерений гарантированно определить длину всей сети дорог?

Источники: ММО - 2021, первый день, 11.4 (см. mmo.mccme.ru)

Подсказки к задаче

Подсказка 1

Города и дороги сразу же намекают нам о том, что над задачей стоит думать в формате графа. Но что это за граф такой, в котором из любой вершины в любую другую можно попасть только одним единственным способом?

Подсказка 2

Наш граф является деревом, так как он связный и в нём не может быть циклов. Заметьте, что нам доступно не более 100 измерений. А чего в дереве из ста вершин будет менее сотни?

Подсказка 3

В дереве на ста вершинах всегда будет меньше ста листов. Подумайте над обходом, который обходит последовательно все листья и позволяет нам посчитать количество всех ребер в дереве.

Подсказка 4

Подвесим наше дерево за одну из вершин, не являющуюся листом, это будет корень. Рассмотрим вариант обхода. Выбираем случайный лист и ищем следующий для него, всегда будем идти по самому правому, еще не посещенному, ведущему вниз ребру, если таких нет, то поднимаемся на уровень выше, движемся таким образом, пока не окажемся в листе.

Подсказка 5

Повторяем данный алгоритм последовательно, пока не вернемся в изначальный лист. Сколько раз в результате такого обхода будет посещено каждое ребро?

Сообщить об ошибке
Подсказки
Ответ и решение
Сообщить об ошибке

Специальные программы

Все специальные программы

Программа
лояльности вер. 2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к твоему аккаунту.

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас важно быть полезными учителям по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!