Али Чепанов и "сорок разбойников"

Necroman · Сообщение **Necroman** » Сб май 19, 2007 10:06 pm

А можно ли проехать по всем автомобильным дорогам Сарова последовательно, не проезжая дважды ни один участок (перекрестки не в счет)?

Сообщение **Mortal** » Вс май 20, 2007 9:04 am

Necroman писал(а):Цитата(Necroman @ 19.05.2007 - 22:06) А можно ли проехать по всем автомобильным дорогам Сарова последовательно, не проезжая дважды ни один участок (перекрестки не в счет)?

Теория графов поможет тебе разрешить этот вопрос

Necroman · Сообщение **Necroman** » Вс май 20, 2007 4:08 pm

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

А вот случай, когда встречка считается другой дорогой, гораздо сложнее.

Necroman · Сообщение **Necroman** » Пн май 21, 2007 12:03 pm

Ответ: никакой город невозможно объехать, не проезжая одну и ту же дорогу дважды, если в городе больше двух тупиков. С одним-двумя тупиками ещё как-то можно разобраться, начав путь из одного и закончив в другом.

А в Сарове минимум 3 тупика: КПП-1, КПП-3 и КПП-5