SubwayTalks.ru • Просмотр темы - Задача из комбинаторики

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

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

Сообщение Бегемот » 20 июл 2007, 22:52

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

 
Сообщения: 525
Зарегистрирован: 27 июн 2007, 11:35
Пункты репутации: 1
Добавить пункт репутацииВычесть пункт репутации

Сообщение Arrs » 20 июл 2007, 23:05

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

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

Вроде, так. ))) Поправьте, если что.
Тише едешь - шире морда!
Arrs

 
Сообщения: 212
Зарегистрирован: 08 мар 2005, 16:44
Откуда: Санкт-Петербург
id ВКонтакте: 0
Станция метро: Маяковская
Пункты репутации: 4
Добавить пункт репутацииВычесть пункт репутации

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

Сообщение Бегемот » 20 июл 2007, 23:14

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

 
Сообщения: 525
Зарегистрирован: 27 июн 2007, 11:35
Пункты репутации: 1
Добавить пункт репутацииВычесть пункт репутации

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

Сообщение grayhood » 20 июл 2007, 23:18

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

 
Сообщения: 98
Зарегистрирован: 19 апр 2007, 01:28
Пункты репутации: 0
Добавить пункт репутацииВычесть пункт репутации

Сообщение Arrs » 20 июл 2007, 23:23

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

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

 
Сообщения: 212
Зарегистрирован: 08 мар 2005, 16:44
Откуда: Санкт-Петербург
id ВКонтакте: 0
Станция метро: Маяковская
Пункты репутации: 4
Добавить пункт репутацииВычесть пункт репутации

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

Сообщение Бегемот » 24 июл 2007, 14:25

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

 
Сообщения: 525
Зарегистрирован: 27 июн 2007, 11:35
Пункты репутации: 1
Добавить пункт репутацииВычесть пункт репутации

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

Сообщение Усама ибн Саддам бен Ёрик » 02 авг 2007, 22:11

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

Гениально. Прямо так и представляю вузовский задачник и в конце книги ответ на эту задачу, так и сформулированный :lol: :lol: :lol:
Изображение
Изображение
Аватара пользователя
Усама ибн Саддам бен Ёрик

 
Сообщения: 94
Зарегистрирован: 15 май 2006, 03:08
id ВКонтакте: 83372
Станция метро: Маяковская
Пункты репутации: 0
Добавить пункт репутацииВычесть пункт репутации

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

Сообщение OREL » 31 окт 2007, 16:32

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


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

 
Сообщения: 82
Зарегистрирован: 06 апр 2007, 14:46
Откуда: Leningrad
id ВКонтакте: 5705689
Станция метро: Обводный Канал-2
Пункты репутации: 1
Добавить пункт репутацииВычесть пункт репутации


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

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

Rambler's Top100 Яндекс.Метрика