SubwayTalks.ru

Сорри за частичный плагиат, но классическую задачу о кенигсбергских мостах я перепёр на новый лад. Итак, перед вами центр схемы метро СПБ. Вопрос: можно ли проехать все тоннели, обозначенные на схеме, побывав в любом из мест только один раз?
P.S. Ответа я не знаю. Ничего, прорвемся!

Пардон муа, но это не комбинаторика, а теория графов)))

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

Вроде, так. ))) Поправьте, если что.

Arrs, можно ли проехать ВСЕ тоннели?... Имеется в виду: каждый из перегонов - в двух направлениях. Оборотные тупики, ПТО и ССВ - условно отбрасываем.

Гм, задача имеет решения, пока не открыта Звенигородская...

А, боже мой.)))) БЕГЕМОТ, спасибо. Вообще теория графов, их виды, задачки разные - это очень занимательная вещь, всё хочу хорошенько её изучить.

По задаче.
Тогда количество рёбер удваивается, а значит, везде всё становится чётным. )))
Но при этом каждая линия обозначает сразу два ребра, причём, направленных, в ту или другую сторону, а значит, всё не так однозначно. )))

Вроде бы Arrs почти разгадал задачку. Конечно, в самой фигуре аж целых пять вершин, где встречается нечетное количество лучей, ну, а если каждый луч требуется нарисовать СДВОЕННЫМ (т.е. проехать туда и обратно), значит, "нечетных" вершин вообще не остается.
Вывод: можно, причем вариантов множество. Респект Arrs`у!

grayhood @ 20.7.2007, 22:18 писал(а):Гм, задача имеет решения, пока не открыта Звенигородская...

Гениально. Прямо так и представляю вузовский задачник и в конце книги ответ на эту задачу, так и сформулированный

Бегемот @ Пт 20 Июл, 2007 21:52 писал(а): Вопрос: можно ли проехать все тоннели, обозначенные на схеме, побывав в любом из мест только один раз?
P.S. Ответа я не знаю. Ничего, прорвемся!

Проехать вс тоннели невозможно, ведь чтобы проехать 2 му тоннелю надо приехать на на станцию, с которой тъехали в первый тоннель!