Сорри за частичный плагиат, но классическую задачу о кенигсбергских мостах я перепёр на новый лад. Итак, перед вами центр схемы метро СПБ. Вопрос: можно ли проехать все тоннели, обозначенные на схеме, побывав в любом из мест только один раз?
P.S. Ответа я не знаю. Ничего, прорвемся!
Задача из комбинаторики
-
- Сообщения: 525
- Зарегистрирован: 27 июн 2007, 10:35
-
- Сообщения: 212
- Зарегистрирован: 08 мар 2005, 14:44
- Станция метро: Маяковская
- Откуда: Санкт-Петербург
Пардон муа, но это не комбинаторика, а теория графов)))
Здесь ответ - нельзя, т.к. в данном графе количество нечётных вершин больше двух. Нечётная вершина - это та вершина, от которой отходит нечётное количество рёбер, т.е. линий. Граф можно нарисовать одним росчерком, если количество нечётных вершин равняется нулю или двойке.
Вроде, так. ))) Поправьте, если что.
Здесь ответ - нельзя, т.к. в данном графе количество нечётных вершин больше двух. Нечётная вершина - это та вершина, от которой отходит нечётное количество рёбер, т.е. линий. Граф можно нарисовать одним росчерком, если количество нечётных вершин равняется нулю или двойке.
Вроде, так. ))) Поправьте, если что.
Тише едешь - шире морда!
-
- Сообщения: 525
- Зарегистрирован: 27 июн 2007, 10:35
Re: Задача из комбинаторики
Arrs, можно ли проехать ВСЕ тоннели?... Имеется в виду: каждый из перегонов - в двух направлениях. Оборотные тупики, ПТО и ССВ - условно отбрасываем.
-
- Сообщения: 98
- Зарегистрирован: 19 апр 2007, 00:28
Re: Задача из комбинаторики
Гм, задача имеет решения, пока не открыта Звенигородская...
-
- Сообщения: 212
- Зарегистрирован: 08 мар 2005, 14:44
- Станция метро: Маяковская
- Откуда: Санкт-Петербург
А, боже мой.)))) БЕГЕМОТ, спасибо. Вообще теория графов, их виды, задачки разные - это очень занимательная вещь, всё хочу хорошенько её изучить.
По задаче.
Тогда количество рёбер удваивается, а значит, везде всё становится чётным. )))
Но при этом каждая линия обозначает сразу два ребра, причём, направленных, в ту или другую сторону, а значит, всё не так однозначно. )))
По задаче.
Тогда количество рёбер удваивается, а значит, везде всё становится чётным. )))
Но при этом каждая линия обозначает сразу два ребра, причём, направленных, в ту или другую сторону, а значит, всё не так однозначно. )))
Тише едешь - шире морда!
-
- Сообщения: 525
- Зарегистрирован: 27 июн 2007, 10:35
Re: Задача из комбинаторики
Вроде бы Arrs почти разгадал задачку. Конечно, в самой фигуре аж целых пять вершин, где встречается нечетное количество лучей, ну, а если каждый луч требуется нарисовать СДВОЕННЫМ (т.е. проехать туда и обратно), значит, "нечетных" вершин вообще не остается.
Вывод: можно, причем вариантов множество. Респект Arrs`у!
Вывод: можно, причем вариантов множество. Респект Arrs`у!
- Усама ибн Саддам бен Ёрик
- Сообщения: 94
- Зарегистрирован: 15 май 2006, 02:08
- id ВКонтакте: 83372
- Станция метро: Маяковская
Re: Задача из комбинаторики
grayhood @ 20.7.2007, 22:18 писал(а):Гм, задача имеет решения, пока не открыта Звенигородская...
Гениально. Прямо так и представляю вузовский задачник и в конце книги ответ на эту задачу, так и сформулированный
- OREL
- Сообщения: 82
- Зарегистрирован: 06 апр 2007, 13:46
- id ВКонтакте: 5705689
- Станция метро: Улица Дыбенко
- Откуда: Saint P
Re: Задача из комбинаторики
Бегемот @ Пт 20 Июл, 2007 21:52 писал(а): Вопрос: можно ли проехать все тоннели, обозначенные на схеме, побывав в любом из мест только один раз?
P.S. Ответа я не знаю. Ничего, прорвемся!
Проехать вс тоннели невозможно, ведь чтобы проехать 2 му тоннелю надо приехать на на станцию, с которой тъехали в первый тоннель!