Гамильтоновы пути в графе.

[MrDindows]

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

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

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

[nikvic]

http://ru.wikipedia.org/wiki/%C3%E0%EC% ... 3%F0%E0%F4

[MrDindows]

nikvic в сообщении #660417 писал(а):

http://ru.wikipedia.org/wiki/%C3%E0%EC%E8%EB%FC%F2%EE%ED%EE%E2_%E3%F0%E0%F4

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

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

[VAL]

MrDindows в сообщении #660409 писал(а):

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

Какой-то странный вопрос!
Ответ, разумеется, отрицательный.
Во-первых, в графе может вообще не быть гамильтоновых путей.
Но, даже если они есть, столь примитивный алгоритм (начальный этап поиска в глубину), не приведет к их построению. (Хотя может, конечно, и привести, в частном случае, иногда, если повезет.)

[MrDindows]

VAL в сообщении #660566 писал(а):

MrDindows в сообщении #660409 писал(а):

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

Какой-то странный вопрос!
Ответ, разумеется, отрицательный.
Во-первых, в графе может вообще не быть гамильтоновых путей.
Но, даже если они есть, столь примитивный алгоритм (начальный этап поиска в глубину), не приведет к их построению. (Хотя может, конечно, и привести, в частном случае, иногда, если повезет.)

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

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

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

[nikvic]

MrDindows в сообщении #660662 писал(а):

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

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

[MrDindows]

nikvic в сообщении #660668 писал(а):

MrDindows в сообщении #660662 писал(а):

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

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

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

[nikvic]

Ага, так яснее. Лучше ""через наоборот

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

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

[VAL]

MrDindows в сообщении #660662 писал(а):

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

Таких графов крайне мало. Не исключено, что они исчерпываются вышеперечисленными.