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

задан 8 Июл '13 17:49

10|600 символов нужно символов осталось
1

Рассмотри город, в который входит наибольшее число дорог. Пусть $%x_1,..,x_k$% - города, из которых в него идут дороги, а $%y_1,..,y_m$% - города, в которые из него иду дороги. Из первой группы можно доехать до данного города без промежуточных городов. Если у из некоторого города $%y_i$% до данного нельзя доехать искомым образом, то в него ведут дороги из данного города и из всех $%y_1,...,y_m$% и число входящих дорого у него больше чем у данного. Противоречие, ч. и т. д.

ссылка

отвечен 8 Июл '13 18:51

Тут, судя по всему, имелось в виду, что в город $%y_i$% ведут все дороги из данного города и из всех $%x_1$%, ..., $%x_k$%.

(8 Июл '13 23:35) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×794

задан
8 Июл '13 17:49

показан
328 раз

обновлен
8 Июл '13 23:35

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru