2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Гамильтоновы пути в графе.
Сообщение18.12.2012, 22:27 
Заслуженный участник


02/08/10
629
Дан неориентированный граф без петель.
Мы начинаем свой путь в любой (случайной) вершине графа, и далее движемся в любую из соседних, не посещённых ранее, вершин, пока такие есть.
И нужно ответить на такой вопрос: Верно ли, что все такие наши пути будут гамильтоновыми?

А мой вопрос такой: Как это проверить без прямого перебора всех возможных путей, какой критерий использовать для проверки?)
У меня есть предположение, (upd:)которое я уже опровергнул: граф должен быть связным, и степени всех вершин должны быть равны. Но оно не верное, так как задачу ( по спортивному программированию) сдать не получается.

Буду благодарен за помощь=)

 Профиль  
                  
 
 Re: Гамильтоновы пути в графе.
Сообщение18.12.2012, 22:35 
Заслуженный участник
Аватара пользователя


06/04/10
3152
http://ru.wikipedia.org/wiki/%C3%E0%EC% ... 3%F0%E0%F4

 Профиль  
                  
 
 Re: Гамильтоновы пути в графе.
Сообщение18.12.2012, 22:44 
Заслуженный участник


02/08/10
629
nikvic в сообщении #660417 писал(а):
http://ru.wikipedia.org/wiki/%C3%E0%EC%E8%EB%FC%F2%EE%ED%EE%E2_%E3%F0%E0%F4

Мне нужно не просто проверить, является ли граф гамильтоновым. Мне нужно узнать все ли пути (описанные в 1м посте) в нём являются гамильтоновыми. Простейший пример гамильтонова графа, не удовлетворяющему условий задачи: квадрат с одной диагональю.

зы. Своё предположение я уже опровергнул. Построил контрпример=) Но вопрос остаётся открытым.

 Профиль  
                  
 
 Re: Гамильтоновы пути в графе.
Сообщение19.12.2012, 09:41 
Заслуженный участник


27/06/08
4058
Волгоград
MrDindows в сообщении #660409 писал(а):
Дан неориентированный граф без петель.
Мы начинаем свой путь в любой (случайной) вершине графа, и далее движемся в любую из соседних, не посещённых ранее, вершин, пока такие есть.
И нужно ответить на такой вопрос: Верно ли, что все такие наши пути будут гамильтоновыми?
Какой-то странный вопрос!
Ответ, разумеется, отрицательный.
Во-первых, в графе может вообще не быть гамильтоновых путей.
Но, даже если они есть, столь примитивный алгоритм (начальный этап поиска в глубину), не приведет к их построению. (Хотя может, конечно, и привести, в частном случае, иногда, если повезет.)

 Профиль  
                  
 
 Re: Гамильтоновы пути в графе.
Сообщение19.12.2012, 16:09 
Заслуженный участник


02/08/10
629
VAL в сообщении #660566 писал(а):
MrDindows в сообщении #660409 писал(а):
Дан неориентированный граф без петель.
Мы начинаем свой путь в любой (случайной) вершине графа, и далее движемся в любую из соседних, не посещённых ранее, вершин, пока такие есть.
И нужно ответить на такой вопрос: Верно ли, что все такие наши пути будут гамильтоновыми?
Какой-то странный вопрос!
Ответ, разумеется, отрицательный.
Во-первых, в графе может вообще не быть гамильтоновых путей.
Но, даже если они есть, столь примитивный алгоритм (начальный этап поиска в глубину), не приведет к их построению. (Хотя может, конечно, и привести, в частном случае, иногда, если повезет.)

Мне не нужно ответить на вопрос для всех графов сразу=) И не нужно строить сами гамильтоновы пути.
Возможно,я не достаточно понятно объяснил условие задачи, так что попробую ещё раз=)

Нам дан граф (конкретный граф), заданный количеством вершин( $<10^6$) и описанием всех его рёбер ( $< 2 \cdot 10^6$).
Допустим, в начале в некоторой (случайной) вершине находится мистер Икс. С этой вершины он начинает свой путь, и далее с каждой текущей вершины движется в любую (случайную) соседнюю, не посещённую ранее, пока это возможно.
И вот надо ответить на вопрос: можно ли гарантировать, что путь, пройдённый мистером Икс, будет гамильтоновым?
Ответ "Да", например, очевиден для всех полных графов, для графов, которые являются одним простым циклом,
Ответ "Нет", например, для всех несвязных графов, для графов, в которых есть хотя одна точка сочленения.

Более обще, можно сказать, что если в графе есть цепь, при удалении которой он становится несвязным, то ответ "Нет". Но как это проверять без полного перебора, который невозможен для данного ограничения входных данных, я не знаю.

 Профиль  
                  
 
 Re: Гамильтоновы пути в графе.
Сообщение19.12.2012, 16:40 
Заслуженный участник
Аватара пользователя


06/04/10
3152
MrDindows в сообщении #660662 писал(а):
Но как это проверять без полного перебора, который невозможен для данного ограничения входных данных, я не знаю.

Во всяком случае, задача о существовании цикла Гамильтона из NP-полных.
Однако у Вас фигурирует некая случайность. Верно ли Вы запомнили требование к алгоритму?

 Профиль  
                  
 
 Re: Гамильтоновы пути в графе.
Сообщение19.12.2012, 18:42 
Заслуженный участник


02/08/10
629
nikvic в сообщении #660668 писал(а):
MrDindows в сообщении #660662 писал(а):
Но как это проверять без полного перебора, который невозможен для данного ограничения входных данных, я не знаю.

Во всяком случае, задача о существовании цикла Гамильтона из NP-полных.
Однако у Вас фигурирует некая случайность. Верно ли Вы запомнили требование к алгоритму?

Верно=)
Вот http://www.e-olimp.com/problems/3470, можете почитать исходное условие.

 Профиль  
                  
 
 Re: Гамильтоновы пути в графе.
Сообщение19.12.2012, 18:50 
Заслуженный участник
Аватара пользователя


06/04/10
3152
Ага, так яснее. Лучше ""через наоборот :|

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

Есть ли тупиковый путь?

 Профиль  
                  
 
 Re: Гамильтоновы пути в графе.
Сообщение19.12.2012, 19:04 
Заслуженный участник


27/06/08
4058
Волгоград
MrDindows в сообщении #660662 писал(а):
Нам дан граф (конкретный граф), заданный количеством вершин( $<10^6$) и описанием всех его рёбер ( $< 2 \cdot 10^6$).
Допустим, в начале в некоторой (случайной) вершине находится мистер Икс. С этой вершины он начинает свой путь, и далее с каждой текущей вершины движется в любую (случайную) соседнюю, не посещённую ранее, пока это возможно.
И вот надо ответить на вопрос: можно ли гарантировать, что путь, пройдённый мистером Икс, будет гамильтоновым?
Ответ "Да", например, очевиден для всех полных графов, для графов, которые являются одним простым циклом,
Таких графов крайне мало. Не исключено, что они исчерпываются вышеперечисленными.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Модераторы Математики, Супермодераторы



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

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


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group