ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 79244
Темы:    [ Принцип крайнего (прочее) ]
[ Связность и разложение на связные компоненты ]
[ Деревья ]
Сложность: 3+
Классы: 10
В корзину
Прислать комментарий

Условие

В городе N с каждой станции метро на любую другую можно проехать. Доказать, что одну из станций можно закрыть на ремонт без права проезда через неё так, чтобы с любой из оставшихся станций можно было по-прежнему проехать на любую другую.


Также доступны документы в формате TeX

Решение

Первый способ. Пусть S – какая-то станция метро, T – самая далекая от S станция, то есть такая, что кратчайший путь из S на T ведёт через большее (или, по крайней мере, не меньшее) число станций, чем кратчайший путь от S до любой другой станции. Закроем теперь станцию T. При этом из S мы по-прежнему сможем проехать на любую другую (не закрытую) станцию U, ибо кратчайший путь из S в U никак не может вести через T – иначе станция V была бы расположена дальше от S, чем станция T. Поэтому, если U и V – две какие угодно отличные от T станции метро, то с одной из них мы заведомо сможем проехать на другую, минуя T (если U и V отличны от S, проедем с U на S, а оттуда – на V.

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


Также доступны документы в формате TeX

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Номер 36
Год 1973
вариант
Класс 9
Тур 1
задача
Номер 4

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .