Форум программистов, компьютерный форум, киберфорум
Дискретная математика
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.71/7: Рейтинг темы: голосов - 7, средняя оценка - 4.71
25 / 25 / 26
Регистрация: 06.06.2012
Сообщений: 92
1

Задача по Графам

18.03.2013, 18:01. Просмотров 1376. Ответов 4
Метки нет (Все метки)

Столкнулся с задачей на графы... Вот условие:

Составьте все возможные планы маршрута путешествия по историческим местам, если автотуристам надо проехать из пункта M в пункт N, осмотрев все памятники архитектуры не более одного раза. Как называется такой маршрут?

Название: sshot-1.png
Просмотров: 224

Размер: 11.4 Кб

Я так понимаю этот маршрут называется гамильтоновым путём. Но найти этот маршрут я не могу. Помогите пожалуйста.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
18.03.2013, 18:01
Ответы с готовыми решениями:

задача по графам
перечитал кучу книжек везде нахожу только с каким-то условиями, у меня же с задаче просто...

Задачка по графам
Здравствуйте уважаемые знатоки! Необходима помощь по графам. Написал прогу, но не могу...

Задание по графам
Проверить достижимость в графе одной вершины из другой. Граф задан списком ребер. Примеры: в...

алгоритм по графам
Всем привет! Занимаюсь изучением динамического программирования при решении задач для графов. У...

4
2527 / 1624 / 146
Регистрация: 05.06.2011
Сообщений: 4,553
21.03.2013, 10:46 2
Да, гамильтонов путь. NP-полная задача. Решается, по сути, полным перебором. Ищи.
1
Модератор
Эксперт Python
26751 / 13973 / 2667
Регистрация: 12.02.2012
Сообщений: 22,905
Записей в блоге: 2
21.03.2013, 16:53 3
Привет, земляк! Есть такая вещь - "Перебор с возвратом". Выкладываю презентацию на эту тему. Может, поможет...
1
Вложения
Тип файла: zip backtrack.zip (586.8 Кб, 18 просмотров)
Модератор
Эксперт Python
26751 / 13973 / 2667
Регистрация: 12.02.2012
Сообщений: 22,905
Записей в блоге: 2
21.03.2013, 19:23 4
Такое впечатление, что у этого графа нет гамильтонова цикла...
0
2527 / 1624 / 146
Регистрация: 05.06.2011
Сообщений: 4,553
22.03.2013, 02:37 5
Собственно, даже проще.
Какие есть варианты начала? Идём по ним, стирая вершины:
MAB -- и C остаётся висячей: если туда зайдём, идти будет некогда. Разве что ею продолжить, но тогда только в N и на выход.
MB -- ну, тут вообще понятно: после стирания граф становится несвязным.
MD -- A остаётся висячей.
Вот и всё.
2
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
22.03.2013, 02:37

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

FAQ по графам
Иногда на форуме появляются просьбы решить задачу на теорию графов. На теории такие задачи решаются...

книги по графам
Подскажите, какие учебники лучше всего подходят для изучения графов в турбо паскале?? в интернете я...

Книги по графам
Подскажите пожалуйста, по какой книге лучше всего начать изучение графов в с++ с нуля? и если...

Теоретические задачи по графам
Здравствуйте. Прошу помощи в решении следующих двух задач: 1. Дан невзвешенный неориентированный...

Задачи по графам Haskell
Помогите пожалуйста решить лабораторную Вот условия задачи 1. Функция longWay gr a b, которая...

2 задачи по графам и доказательство.
Помогите в решении данных задач, нужен не только ответ, но и расписать почему. 1)Всегда ли...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.