Найти все хордычные циклы в неориентированном графе

Ответ 1

Назначить номера узлам от 1 до n.

• Выберите номер node 1. Назовите его "A".

• Перечислить пары ссылок, выходящих из "A".

• Выберите один. Пусть вызываются соседние узлы "B" и "C", а B меньше C.

• Если B и C подключены, выведите цикл ABC, вернитесь к шагу 3 и выберите другую пару.

• Если B и C не связаны:

  • Перечислите все узлы, подключенные к B. Предположим, что он подключен к D, E и F. Создайте список векторов CABD, CABE, CABF. Для каждого из них:
  • если последний node подключен к любому внутреннему node, кроме C и B, отбрасывает вектор
  • если последний node подключен к C, выводит и отбрасывает
  • Если он не подключен к другому, создайте новый список векторов, добавив все узлы, к которым подключен последний node.

  Повторяйте до тех пор, пока не закончите векторы.

• Повторите шаги 3-5 со всеми парами.

• Удалите node 1 и все ссылки, которые приводят к нему. Выберите следующий node и вернитесь к шагу 2.

Изменить: и вы можете покончить с одним вложенным циклом.

Это, кажется, работает с первого взгляда, могут быть ошибки, но вы должны понять:

void chordless_cycles(int* adjacency, int dim)
{
    for(int i=0; i<dim-2; i++)
    {
        for(int j=i+1; j<dim-1; j++)
        {
            if(!adjacency[i+j*dim])
                continue;
            list<vector<int> > candidates;
            for(int k=j+1; k<dim; k++)
            {
                if(!adjacency[i+k*dim])
                    continue;
                if(adjacency[j+k*dim])
                {
                    cout << i+1 << " " << j+1 << " " << k+1 << endl;
                    continue;
                }
                vector<int> v;
                v.resize(3);
                v[0]=j;
                v[1]=i;
                v[2]=k;
                candidates.push_back(v);
            }
            while(!candidates.empty())
            {
                vector<int> v = candidates.front();
                candidates.pop_front();
                int k = v.back();
                for(int m=i+1; m<dim; m++)
                {
                    if(find(v.begin(), v.end(), m) != v.end())
                        continue;
                    if(!adjacency[m+k*dim])
                        continue;
                    bool chord = false;
                    int n;
                    for(n=1; n<v.size()-1; n++)
                        if(adjacency[m+v[n]*dim])
                            chord = true;
                    if(chord)
                        continue;
                    if(adjacency[m+j*dim])
                    {
                        for(n=0; n<v.size(); n++)
                            cout<<v[n]+1<<" ";
                        cout<<m+1<<endl;
                        continue;
                    }
                    vector<int> w = v;
                    w.push_back(m);
                    candidates.push_back(w);
                }
            }
        }
    }
}

Ответ 2

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

void printChordlessCycles( ChordlessCycle path) {

  System.out.println( path.toString() );
  for( Node n : path.lastNode().neighbors() ) {

    if( path.canAdd( n) ) {

      path.add( n);
      printChordlessCycles( path);
      path.remove( n);
    }
  }
}

Graph g = loadGraph(...);
ChordlessCycle p = new ChordlessCycle();
for( Node n : g.getNodes()) {
  p.add(n);
  printChordlessCycles( p);
  p.remove( n);
}

class ChordlessCycle {
   private CountedSet<Node> connected_nodes;
   private List<Node> path;

   ...

   public void add( Node n) {
     for( Node neighbor : n.getNeighbors() ) {
       connected_nodes.increment( neighbor);
     }
     path.add( n);
   }

   public void remove( Node n) {
     for( Node neighbor : n.getNeighbors() ) {
       connected_nodes.decrement( neighbor);
     }
     path.remove( n);
   }

   public boolean canAdd( Node n) {
     return (connected_nodes.getCount( n) == 0);
   }
}

Ответ 3

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

И как найти все хордовые последовательности, проходящие через вершину А? Уменьшите это, чтобы найти все хордальные пути от B до A, учитывая список разрешенных вершин и поиск по ширине или по глубине. Обратите внимание, что при итерации по вершинам, достижимым (в один шаг) из B, когда вы выбираете один из них, вы должны удалить все остальные из списка разрешенных вершин (обратите особое внимание, когда B = A, чтобы не исключать три -edge).

Ответ 4

Просто мысль:

Скажем, вы перечисляете циклы на вашем примерном графике и начинаете с node 0.

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

Не могли бы вы использовать такой подход? Или есть контрпример?

Ответ 5

Найти все циклы.

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

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

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