algorithm - its - size of a graph

Encuentra todos los ciclos sin cuerda en un gráfico no dirigido

Question

¿Cómo encontrar todos los ciclos sin acordes en un gráfico no dirigido?

Por ejemplo, dado el gráfico

0 --- 1
|     | /
|     |  /
4 --- 3 - 2

el algoritmo debería devolver 1-2-3 y 0-1-3-4, pero nunca 0-1-2-3-4.

(Nota: [1] Esta pregunta no es lo mismo que encontrar un ciclo pequeño en un gráfico plano porque el gráfico no es necesariamente plano. [2] He leído el artículo Generación de todos los ciclos, ciclos sin cuerda y ciclos de Hamilton con el principio de exclusión, pero no entiendo lo que están haciendo :). [3] He intentado con CYPATH pero el programa solo proporciona el recuento, el algoritmo EnumChordlessPath en el archivo readme.txt tiene errores ortográficos significativos, y el código C es un desastre. [4] No estoy tratando de encontrar un conjunto arbitrario de ciclos fundamentales . La base del ciclo puede tener acordes).

Answer 1

@aioobe tiene un punto. Solo encuentra todos los ciclos y luego excluye los que no son sin cordón. Esto puede ser demasiado ineficiente, pero el espacio de búsqueda puede reducirse en el camino para reducir las ineficiencias. Aquí hay un algoritmo general:

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);
   }
}

Answer 2

Asigna números a los nodos de 1 a n.

1. Elija el número de nodo 1. Llámalo ''A''.

2. Enumerar pares de enlaces que salen de ''A''.

3. Elegir uno. Llamemos a los nodos adyacentes ''B'' y ''C'' con B menor que C.

4. Si B y C están conectados, entonces envíe el ciclo ABC, vuelva al paso 3 y elija un par diferente.

5. Si B y C no están conectados:

   • Enumere todos los nodos conectados a B. Supongamos que está conectado a D, E y F. Cree una lista de vectores CABD, CABE, CABF. Para cada uno de estos:
   • si el último nodo está conectado a cualquier nodo interno, excepto C y B, descarte el vector
   • si el último nodo está conectado a C, déjalo salir y descarta
   • si no está conectado a ninguno de ellos, cree una nueva lista de vectores, agregando todos los nodos a los que está conectado el último nodo.

   Repite hasta que te quedes sin vectores.

6. Repita los pasos 3-5 con todos los pares.

7. Elimine el nodo 1 y todos los enlaces que lo conducen. Elija el siguiente nodo y regrese al paso 2.

Editar: y puedes eliminar un ciclo anidado.

Esto parece funcionar a primera vista, puede haber errores, pero debes tener la idea:

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);
                }
            }
        }
    }
}

Answer 3

Encuentra todos los ciclos.

La definición de un ciclo sin cuerda es un conjunto de puntos en los que no existe un ciclo de subconjuntos de esos puntos. Entonces, una vez que tiene todos los ciclos, el problema es simplemente eliminar ciclos que sí tienen un ciclo de subconjuntos.

Para la eficiencia, para cada ciclo que encuentre, recorra todos los ciclos existentes y verifique que no sea un subconjunto de otro ciclo o viceversa, y si es así, elimine el ciclo más grande.

Más allá de eso, la única dificultad es descubrir cómo escribir un algoritmo que determine si un conjunto es un subconjunto de otro.

Answer 4

Qué tal esto. Primero, reduzca el problema para encontrar todos los ciclos sin acordes que pasan por un vértice A dado. Una vez que haya encontrado todos esos, puede eliminar A del gráfico y repetir con otro punto hasta que no quede nada.

¿Y cómo encontrar todos los ciclos sin cuerda que pasan por el vértice A? Redúcelo a la búsqueda de todas las rutas sin acordes de B a A, dada una lista de vértices permitidos, y busca ancho primero o primero en profundidad. Tenga en cuenta que al iterar sobre los vértices alcanzables (en un paso) desde B, cuando elija uno de ellos, debe eliminar todos los demás de la lista de vértices permitidos (tenga especial cuidado cuando B = A, para no eliminar tres -edge caminos).

Answer 5

Solo un pensamiento:

Digamos que estás enumerando ciclos en tu gráfico de ejemplo y estás comenzando desde el nodo 0.

Si hace una búsqueda de amplitud para cada borde dado, por ejemplo 0 - 1, llega a una bifurcación en 1. Entonces los ciclos que alcanzan 0 nuevamente primero son sin acordes, y el resto no lo son y pueden eliminarse ... al menos Creo que este es el caso.

¿Podrías usar un enfoque como este? ¿O hay un contraejemplo?