Как определить, есть ли в данном графе цикл, содержащий все его узлы? Есть ли в предложенном алгоритме недостатки?

Question

Как определить, есть ли в данном графе цикл, содержащий все его узлы? Есть ли в предложенном алгоритме недостатки?

У меня есть связанный, ненаправленный граф с N узлами и 2N-3 ребрами. Вы можете рассмотреть график так, как он построен на существующем начальном графе, который имеет 3 узла и 3 ребра. Каждый узел добавляется на график и имеет 2 соединения с существующими узлами на графике. Когда все узлы добавляются к графу (всего N-3 узлов), создается окончательный граф.

Первоначально меня спрашивали, какое максимальное количество узлов в этом графе можно посетить ровно один раз (кроме начального узла), т. Е. Каково максимальное количество узлов, содержащихся в наибольшем гамильтоновом пути данного графа? (Хорошо, говоря, что самый большой гамильтонов путь не является допустимой фразой, но, учитывая природу вопроса, мне нужно найти максимальное количество узлов, которые посещаются один раз, и поездка заканчивается на начальном узле. Я думал, что это можно рассматривать как подграф, который является гамильтоновым и состоит из максимального числа узлов, таким образом, наибольшего возможного гамильтонова пути).

Так как меня не просят найти путь, я должен сначала проверить, существует ли гамильтонов путь для данного числа узлов. Я знаю, что планарные графы и циклический граф s (C_n) являются гамильтоновыми графами (я также знаю теорему Оре для гамильтоновых графов, но граф, над которым я буду работать, не будет плотным графом с большой вероятностью, что делает теорему Оре довольно симпатичной много бесполезного в моем случае). Поэтому мне нужно найти алгоритм для проверки, является ли граф графом цикла, т.е. существует ли цикл, который содержит все узлы данного графа.

Поскольку DFS используется для обнаружения циклов, я подумал, что некоторые незначительные манипуляции с DFS могут помочь мне обнаружить то, что я ищу, например, для отслеживания исследуемых узлов и, наконец, проверки, имеет ли последний посещенный узел соединение с начальным узлом. К сожалению, я не смог добиться успеха с таким подходом.

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

Я в значительной степени застрял здесь. Можете ли вы помочь мне придумать другой алгоритм, чтобы сказать, является ли график циклическим?

редактировать

Я понял с помощью комментария (спасибо за это, нм):

Граф цикла состоит из одного цикла и имеет N ребер и N вершин. Если существует цикл, который содержит все узлы данного графа, это гамильтонов цикл. - нм

что я на самом деле ищу гамильтонов путь, который я не собирался делать:) Во-вторых, я думаю, что проверка гамильтонова свойства графа при его построении будет более эффективной, что я также ищу: эффективность времени.

Подумав, я подумал, каким бы ни было количество узлов, график кажется гамильтоновым из-за критериев добавления узлов. Проблема в том, что я не уверен и не могу доказать это. Изменяет ли добавление узлов таким способом, то есть добавление новых узлов с 2 ребрами, которые соединяют добавленный узел с существующими узлами, изменение гамильтонова свойства графа? Если это не меняет гамильтоново свойство, как так? Если это изменится, опять же, как так? Благодарю.

РЕДАКТИРОВАТЬ № 2

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

эти входные данные говорят, что 4-й узел подключен к узлу 1 и узлу 3, 5-й к узлу 2 и узлу 3 .,,

4-й и 7-й узлы подключены к одним и тем же узлам, что позволяет уменьшить максимальное число узлов, которые могут быть посещены ровно один раз, на 1. Если я обнаруживаю эти коллизии (НЕ включая вход, такой как 3 3, который является примером, который вы предложили Так как проблема утверждает, что вновь добавленные ребра связаны с 2 другими узлами) и уменьшают максимальное количество узлов, начиная с N, я считаю, что могу получить правильный результат.

Видишь, я не выбираю связи, они мне даны и я должен найти макс. количество узлов.

Я думаю, что подсчет одинаковых соединений при построении графика и вычитание количества одинаковых соединений из N даст правильный результат? Можете ли вы подтвердить это или есть недостаток в этом алгоритме?

9

algorithm graph language-agnostic hamiltonian-cycle cyclic-graph

Источник

user2034041 06 апр '13 в 19:44

3 ответа

Решение

Что у нас есть в этой проблеме connected, non-directed граф с N узлами и 2N-3 ребрами. Рассмотрим график, приведенный ниже,

Граф не имеет гамильтонова цикла. Но график построен в соответствии с вашими правилами добавления узлов. Поэтому поиск гамильтонова цикла может не дать вам решения. Более того, даже если это возможно, обнаружение гамильтонова цикла является NP-полной задачей со сложностью O (2^N). Так что подход не может быть идеальным.

Я предлагаю использовать модифицированную версию Floyd's Cycle Finding algorithm (Также называется Tortoise and Hare Алгоритм).

Модифицированный алгоритм

1. Initialize a List CYC_LIST to ∅.

2. Add the root node to the list CYC_LIST and set it as unvisited. 

3. Call the function Floyd() twice with the unvisited node in the list CYC_LIST for each of the two edges. Mark the node as visited.

4. Add all the previously unvisited vertices traversed by the Tortoise pointer to the list CYC_LIST.

5. Repeat steps 3 and 4 until no more unvisited nodes remains in the list.

6. If the list CYC_LIST contains N nodes, then the Graph contains a Cycle involving all the nodes.

Алгоритм называет алгоритм нахождения цикла Флойда максимум 2N раз. Алгоритм нахождения цикла Флойда занимает линейное время ( O(N)). Таким образом, сложность модифицированного алгоритма составляет O (N²), что намного лучше, чем экспоненциальное время, используемое подходом, основанным на гамильтоновом цикле.

Одна из возможных проблем с этим подходом состоит в том, что он обнаружит closed paths наряду с циклами, если не применяются более строгие критерии проверки.

Ответить на правку № 2

Рассмотрим график, приведенный ниже,

            A------------\
           / \            \
          B _ C            \
          |\ /|             \
          | D |             F
          \   /            /
           \ /            / 
            E------------/

Согласно вашему алгоритму этот граф не имеет цикла, содержащего все узлы. Но в этом графе есть цикл, содержащий все узлы.

A-B-D-C-E-F-A

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

1

Источник

user2105110 07 апр '13 в 03:55

Ниже я добавил три дополнительных узла (3,4,5) в исходный граф, и кажется, что я могу продолжать добавлять новые узлы бесконечно, сохраняя свойство гамильтонова цикла. Для приведенного ниже графика цикл будет 0-1-3-5-4-2-0

  1---3---5
 / \ / \ /
0---2---4

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

0

Источник

user183695 07 апр '13 в 06:09

Другие вопросы по тегам algorithm graph language-agnostic hamiltonian-cycle cyclic-graph

user1086871 06 апр '13 в 20:30 2013-04-06 20:30 · Accepted Answer · 2013-04-06 20:30

Чтобы добавить некоторое пояснение к этой теме: нахождение гамильтонова цикла является NP-полным, что подразумевает, что нахождение самого длинного цикла также является NP-полным, потому что если мы можем найти самый длинный цикл в любом графе, мы можем найти гамильтоновый цикл подграфа. индуцируется вершинами, которые лежат на этом цикле. (Смотрите также, например, этот документ, касающийся самой длинной проблемы цикла)

Мы не можем использовать критерий Дирака здесь: Дирак только говорит нам minimum degree >= n/2 -> Hamiltonian Cycle, это означает, что нам нужно противоположное направление. Обратный путь определенно не верен: возьмите на себя цикл n вершины, каждая вершина в ней имеет ровно степень 2, независимо от размера круга, но она имеет (есть) HC. Что вы можете сказать из Дирака, так это то, что no Hamiltonian Cycle -> minimum degree < n/2, который здесь бесполезен, так как мы не знаем, имеет ли наш граф HC или нет, поэтому мы не можем использовать импликацию (тем не менее, каждый граф, который мы строим в соответствии с описанным OP, будет иметь вершину степени 2а именно последняя вершина, добавленная в граф, поэтому для произвольной nу нас минимальная степень 2).

Проблема в том, что вы можете построить как графики произвольного размера, имеющие HC, так и графики произвольного размера, не имеющие HC. Для первой части: если исходный треугольник A,B,C и добавленные вершины пронумерованы от 1 до k, то соедините 1-ю добавленную вершину с A и C, а k+1-ую вершину с A и k-м вершина для всех k >= 1. Цикл A,B,C,1,2,...,k,A, Для второй части соедините обе вершины 1 и 2 с A и B; этот график не имеет HC.

Также важно отметить, что свойство наличия HC может изменяться от одной вершины к другой во время построения. Вы можете создавать и уничтожать свойство HC при добавлении вершины, поэтому вам придется проверять его каждый раз при добавлении вершины. Простой пример: возьмите график после добавления 1-й вершины и добавьте вторую вершину вместе с ребрами к тем же двум вершинам треугольника, с которыми была связана 1-я вершина. Это строит из графа с HC граф без HC. Обратный путь: добавьте третью вершину и соедините ее с 1 и 2; это строит из графа без HC граф с HC.
Storing the last known HC during construction doesn't really help you because it may change completely. You could have an HC after the 20th vertex was added, then not have one for k in [21,2000], and have one again for the 2001st vertex added. Most likely the HC you had on 23 vertices will not help you a lot.

If you want to figure out how to solve this problem efficiently, you'll have to find criteria that work for all your graphs that can be checked for efficiently. Otherwise, your problem doesn't appear to me to be simpler than the Hamiltonian Cycle problem is in the general case, so you might be able to adjust one of the algorithms used for that problem to your variant of it.