|
в некотором царстве есть n городов.каждые два соеденены дорогой, на всех дорогах введено одностороннее движение.Докажите что найдётся такой город в который можно попасть из любого другого города по пути проезжая не более одного промежуточного города. задан 8 Июл '13 17:49 
денис |
|
Рассмотри город, в который входит наибольшее число дорог. Пусть $%x_1,..,x_k$% - города, из которых в него идут дороги, а $%y_1,..,y_m$% - города, в которые из него иду дороги. Из первой группы можно доехать до данного города без промежуточных городов. Если у из некоторого города $%y_i$% до данного нельзя доехать искомым образом, то в него ведут дороги из данного города и из всех $%y_1,...,y_m$% и число входящих дорого у него больше чем у данного. Противоречие, ч. и т. д. отвечен 8 Июл '13 18:51 
dmg3 Тут, судя по всему, имелось в виду, что в город $%y_i$% ведут все дороги из данного города и из всех $%x_1$%, ..., $%x_k$%.
(8 Июл '13 23:35)
falcao
|