Задача из комбинаторики

[Бегемот]

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

[Arrs]

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

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

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

[Бегемот]

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

[grayhood]

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

[Arrs]

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

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

[Бегемот]

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

[Усама ибн Саддам бен Ёрик]

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

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

[OREL]

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

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