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

Чтобы добавить некоторые пояснения к этой теме: поиск гамильтонова цикла является 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.
Сохранение последнего известного HC во время построения вам не поможет, потому что оно может полностью измениться. У вас может быть HC после добавления 20-й вершины, а затем не иметь его для k в [21,2000] и снова иметь один для добавленной вершины 2001-го. Скорее всего, HC, который у вас был на 23 вершинах, вам не сильно поможет.

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

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

            A
           / \
          B _ C
         ( )  
          D 

График не имеет гамильтонова цикла. Но График построен в соответствии с вашими правилами добавления узлов. Поэтому поиск гамильтонова цикла может не дать вам решения. Более того, даже если это возможно, обнаружение гамильтонова цикла является проблемой NP-Complete со сложностью 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).

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

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

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