Ciclo euleriano

En la teoría de grafos, un camino euleriano es un camino que pasa por cada arista una y solo una vez. Un ciclo o circuito euleriano es un camino cerrado que recorre cada arista exactamente una vez. El problema de encontrar dichos caminos fue discutido por primera vez por Leonhard Euler, en el famoso problema de los puentes de Königsberg.

Ciclos eulerianos

Dibujar un sobre abierto, como el de la imagen, sin levantar el lápiz del papel ni pasar dos veces por el mismo sitio, es posible. En cambio, dibujar el sobre cerrado (prescindiendo del punto 5 y sus líneas adyacentes) es imposible.

En la imagen, $C=\{1,2,3,4,6,3,5,4,1\}\,$ es un ciclo euleriano, luego es un grafo euleriano.

Un grafo es una representación, un modelo, compuesto por un número determinado de vértices (nodos) y un número de arcos (aristas) que los relacionan, cada arista o arco tiene la capacidad de relacionar dos nodos. La palabra ciclo se emplea en teoría de grafos para indicar un camino cerrado en un grafo, es decir, en que el nodo de inicio y el nodo final son el mismo, como contrapartida un camino hamiltoniano es un camino que recorre todos los vértices de un grafo sin pasar dos veces por el mismo vértice. Si el camino es cerrado se dice un ciclo hamiltoniano.

Si un grafo admite un ciclo euleriano, se denomina grafo euleriano.

Características

Se elige para iniciar el trazo cualquier punto impar y se terminará en el otro punto o vértice impar.

Historia

El origen de la teoría de los ciclos eulerianos fue planteado y resuelto por el propio Leonhard Euler en 1736 en un problema que tiene el nombre de Siete puentes de la ciudad de Königsberg (Prusia oriental en el siglo XVIII y actualmente, Kaliningrado, provincia rusa) dando origen a la Teoría de los grafos.

El problema se enuncia de la siguiente forma: Dos islas en el río Pregel, en Königsberg se unen entre ellas y con la tierra firme mediante siete puentes. ¿Es posible dar un paseo empezando por una cualquiera de las cuatro partes de tierra firme, cruzando cada puente una sola vez y volviendo al punto de partida?

Euler enfocó el problema representando cada parte de tierra por un punto y cada puente, por una línea, uniendo los puntos que se corresponden. Entonces, el problema anterior se puede trasladar a la siguiente pregunta: ¿se puede recorrer el dibujo sin repetir las líneas?

Euler demostró que no era posible puesto que el número de líneas que inciden en cada punto no es par (condición necesaria para entrar y salir de cada punto, y para regresar al punto de partida, por caminos distintos en todo momento).

Casos

Dado un grafo conexo (no existen nodos aislados) y no dirigido $G=(V,E\,)$, si $G\,$ tiene exactamente dos vértices de grado impar, entonces $G\,$ tiene un camino euleriano no cerrado. En caso de que todos los vértices tengan grado par, $G\,$ tiene un ciclo euleriano.

Teorema

Dado $G(V,E\,)$ no orientado y conexo; si tiene $2k\,$ nodos de grado impar, entonces $G\,$ puede ser escrito como unión de $k\,$ caminos (simples) distintos sobre los arcos. Las siguientes expresiones son equivalentes:

1) $G\,$ es euleriano;

2) $\forall v\in \ V$ con grado $(v)\geq 2$ y par.

3) $G=\coprod _{i=1}^{n}C_{i}$ todos disjuntos (caminos distintos) en los arcos,

es decir $C_{i}^{E}\cap \;C_{j}^{E}=\emptyset \;$ con ${i\not \neq \;j}$ va de un nodo de grado impar a un nodo de grado impar.

Un grafo admite un camino euleriano, pero no un ciclo euleriano, cuando tiene exactamente dos nodos de grado impar (conexos a los caminos).

Propiedades

• Un grafo conexo y no dirigido se dice que es euleriano si cada vértice tiene un grado par.
• Un grafo no dirigido es euleriano si es conexo y si se puede descomponer en uno con los vértices disjuntos.
• Si un grafo no dirigido G es euleriano entonces su gráfo-línea L(G) se dice que es también euleriano.
• Un grafo dirigido es euleriano si es conexo y cada vértice tiene grados internos iguales a los externos.
• Un grafo no dirigido se dice que es susceptible de ser recorrido (en inglés: traversable) si es conexo y dos vértices en el grafo tienen grado impar.

Construcción de trayectos y circuitos

Algoritmo de Fleury

El algoritmo de Fleury es un algoritmo elegante pero ineficiente cuyo origen se remonta al año 1883. Considerando un grafo del que sabemos que todas las líneas en la misma componente y al menos dos vértices de ángulo impar. El algoritmo comienza en el vértice del ángulo impar. En cada paso se elige el siguiente lado que queda unido al punto anterior por una sola línea. Finalmente nos movemos al lado que queda en el vértice sobrante. Al concluir el algoritmo, no quedan lados sin recorrer, y la secuencia que queda sigue un ciclo Euleriano sin vértices de ángulos impares. También puede quedar un trayecto Euleriano si hay exactamente dos vértices de ángulo impar. La complejidad correspondiente a este algoritmo es O(n^2), aunque hace unos años, esta fue mejorada hasta alcanzar una complejidad $O(|E|(\log |E|)^{3}\log \log |E|)$ pero sigue siendo todavía un recorrido más lento que otros algoritmos.

Implementación en C++ del algoritmo de Fleury

// Implemetación en c++
#include <iostream>
#include <string.h>
#include <algorithm>
#include <list>
using namespace std;
 
// Clase para representar el grafo
class Graph
{
  private:
    int V;    // Número de vértices
    list<int> *adj;    // Vector dinámico
  public:
    // Constructor y destructor
    Graph(int V)  { this->V = V;  adj = new list<int>[V];  }
    ~Graph()      { delete [] adj;  }
 
    void addEdge(int u, int v) {  adj[u].push_back(v); adj[v].push_back(u); }
    void rmvEdge(int u, int v);
 
    void printEulerTour();
    void printEulerUtil(int s);
 
    int DFSCount(int v, bool visited[]);

    bool isValidNextEdge(int u, int v);
};
 

void Graph::printEulerTour()
{
  int u = 0;
  for (int i = 0; i < V; i++)
      if (adj[i].size() & 1)
        {   u = i; break;  }
 
  printEulerUtil(u);
  cout << endl;
}

void Graph::printEulerUtil(int u)
{

  list<int>::iterator i;
  for (i = adj[u].begin(); i != adj[u].end(); ++i)
  {
      int v = *i;

      if (v != -1 && isValidNextEdge(u, v))
      {
          cout << u << "-" << v << "  ";
          rmvEdge(u, v);
          printEulerUtil(v);
      }
  }
}
 

bool Graph::isValidNextEdge(int u, int v)
{
  int count = 0;  
  list<int>::iterator i;
  for (i = adj[u].begin(); i != adj[u].end(); ++i)
     if (*i != -1)
        count++;
  if (count == 1)
    return true;
 
 
  bool visited[V];
  memset(visited, false, V);
  int count1 = DFSCount(u, visited);
 
  rmvEdge(u, v);
  memset(visited, false, V);
  int count2 = DFSCount(u, visited);

  addEdge(u, v);

  return (count1 > count2)? false: true;
}
 

void Graph::rmvEdge(int u, int v)
{
  list<int>::iterator iv = find(adj[u].begin(), adj[u].end(), v);
  *iv = -1;

  list<int>::iterator iu = find(adj[v].begin(), adj[v].end(), u);
  *iu = -1;
}
 
int Graph::DFSCount(int v, bool visited[])
{
  // Marcamos el actual
  visited[v] = true;
  int count = 1;
 
  // Método recursivo
  list<int>::iterator i;
  for (i = adj[v].begin(); i != adj[v].end(); ++i)
      if (*i != -1 && !visited[*i])
          count += DFSCount(*i, visited);
 
  return count;
}
 
int main()
{
  // Ejemplos
  Graph g1(4);
  g1.addEdge(0, 1);
  g1.addEdge(0, 2);
  g1.addEdge(1, 2);
  g1.addEdge(2, 3);
  g1.printEulerTour();
 
  Graph g2(3);
  g2.addEdge(0, 1);
  g2.addEdge(1, 2);
  g2.addEdge(2, 0);
  g2.printEulerTour();
 
  Graph g3(5);
  g3.addEdge(1, 0);
  g3.addEdge(0, 2);
  g3.addEdge(2, 1);
  g3.addEdge(0, 3);
  g3.addEdge(3, 4);
  g3.addEdge(3, 2);
  g3.addEdge(3, 1);
  g3.addEdge(2, 4);
  g3.printEulerTour();
 
  return 0;
}

Algoritmo de Hierholzer

El documento recogido en 1873 procedente de Hierholzer, proporciona un método diferente a la hora de recorrer los ciclos eulerianos de una forma más eficiente que los algoritmos de Fleury. A continuación se mostraran los pasos necesarios para este algoritmo:

• Elegir cualquier vértice v para empezar, y seguir el recorrido de una línea hasta llegar de nuevo a v. No es posible dejar de avanzar en cualquier vértice que no sea v, ya que incluso el grado de todos los vértices asegura que cuando se realiza una traza, deben usarse todas las líneas excepto una, dejando un vértice w. El recorrido formado, puede no cubrir todos los vértices y lados en un grafo o traza inicial.

• Mientras que exista un vértice u que pertenezca al actual recorrido pero que tenga lados adyacentes no pertenecientes a la traza, se comienza de nuevo desde u, siguiendo los lados no usados hasta regresar a u, y unir el recorrido formado durante esta traza a la anterior.

Usando estas estructuras de datos como doblemente unidas para mantener un conjunto de lados incidentes no usados en cada vértice, una lista de vértices del recorrido actual y mantener el recorrido en sí mismo es necesario buscar un nuevo vértice para el recorrido, y conectar ambos al mismo vértice, de manera que la ejecución de ambos pueda llevarse a cabo de manera conjunta y la complejidad final del algoritmo sea lineal (O(E)) sobre la cantidad de aristas.

Contando circuitos eulerianos en dígrafos

El número de circuitos eulerianos en los dígrafos puede ser calculado mediante el teorema denominado en Inglés: BEST-theorem, procedente de los nombres de sus fundadores: de Bruijn, van Aardenne-Ehrenfest, Smith y Tutte.

En dicho teorema se menciona que dado un dígrafo euleriano G := (V, E), el número ciclos eulerianos no-equivalentes en el grafo es

$C\prod _{v\in V}(\deg ^{+}(v)-1)!$

o equivalentemente

$C\prod _{v\in V}(\deg ^{-}(v)-1)!$

siendo C cualquier cofactor de la matriz laplaciana de G.

Véase también

• Problema de los puentes de Königsberg
• Ciclo hamiltoniano
• Problema del cartero chino
• Glosario en teoría de grafos

Referencias

• "Solutio problematis ad geometriam situs pertinentis", Euler, L.,Comment. Academiae Sci. I. Petropolitanae 8 (1736), 128-140.
• "Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechnung zu umfahren", Hierholzer, C. Mathematische Annalen 6 (1873), 30-32.
• Récréations Mathématiques IV, Lucas, E., Paris, 1921.
• "Deux problemes de geometrie de situation", Fleury, Journal de mathematiques elementaires (1883), 257-261.
• "Discrete Mathematics with Applications", Susanna Epp, Fourth Edition
• "Discreta Mathematics and its application"", Rosen 7.ª edición
• https://en.wikipedia.org/wiki/Eulerian_path

• Datos: Q11691793