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

Ответить
Бегемот
Сообщения: 525
Зарегистрирован: 27 июн 2007, 10:35

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

Сообщение Бегемот »

Сорри за частичный плагиат, но классическую задачу о кенигсбергских мостах я перепёр на новый лад. Итак, перед вами центр схемы метро СПБ. Вопрос: можно ли проехать все тоннели, обозначенные на схеме, побывав в любом из мест только один раз?
P.S. Ответа я не знаю. Ничего, прорвемся! :good:
Вложения
ЗАГАДКА.JPG
Arrs
Сообщения: 212
Зарегистрирован: 08 мар 2005, 14:44
Станция метро: Маяковская
Откуда: Санкт-Петербург

Сообщение Arrs »

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

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

Вроде, так. ))) Поправьте, если что.
Тише едешь - шире морда!
Бегемот
Сообщения: 525
Зарегистрирован: 27 июн 2007, 10:35

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

Сообщение Бегемот »

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

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

Сообщение grayhood »

Гм, задача имеет решения, пока не открыта Звенигородская...
Arrs
Сообщения: 212
Зарегистрирован: 08 мар 2005, 14:44
Станция метро: Маяковская
Откуда: Санкт-Петербург

Сообщение Arrs »

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

По задаче.
Тогда количество рёбер удваивается, а значит, везде всё становится чётным. )))
Но при этом каждая линия обозначает сразу два ребра, причём, направленных, в ту или другую сторону, а значит, всё не так однозначно. )))
Тише едешь - шире морда!
Бегемот
Сообщения: 525
Зарегистрирован: 27 июн 2007, 10:35

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

Сообщение Бегемот »

Вроде бы Arrs почти разгадал задачку. Конечно, в самой фигуре аж целых пять вершин, где встречается нечетное количество лучей, ну, а если каждый луч требуется нарисовать СДВОЕННЫМ (т.е. проехать туда и обратно), значит, "нечетных" вершин вообще не остается.
Вывод: можно, причем вариантов множество. Респект Arrs`у! :Rose: :Yahoo!: :Bravo:
Аватара пользователя
Усама ибн Саддам бен Ёрик
Сообщения: 94
Зарегистрирован: 15 май 2006, 02:08
id ВКонтакте: 83372
Станция метро: Маяковская

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

Сообщение Усама ибн Саддам бен Ёрик »

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

Гениально. Прямо так и представляю вузовский задачник и в конце книги ответ на эту задачу, так и сформулированный :lol: :lol: :lol:
Изображение
Изображение
Аватара пользователя
OREL
Сообщения: 82
Зарегистрирован: 06 апр 2007, 13:46
id ВКонтакте: 5705689
Станция метро: Улица Дыбенко
Откуда: Saint P

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

Сообщение OREL »

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


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

Вернуться в «Конкурсы и загадки»