Encontrar el camino euleriano en
Un camino euleriano (Eulerian path) es un camino en un grafo que pasa por todas sus aristas exactamente una vez. Un ciclo euleriano (Eulerian cycle) es un camino euleriano que es un ciclo.
El problema es encontrar el camino euleriano en un multigrafo no dirigido con bucles.
Algoritmo
Primero podemos comprobar si existe un camino euleriano. Podemos usar el siguiente teorema. Un ciclo euleriano existe si y solo si los grados de todos los vértices son pares. Y un camino euleriano existe si y solo si el número de vértices con grado impar es dos (o cero, en el caso de la existencia de un ciclo euleriano). Además, por supuesto, el grafo debe estar suficientemente conexo (es decir, si se quitan todos los vértices aislados, se debe obtener un grafo conexo).
Para encontrar el camino euleriano / ciclo euleriano podemos usar la siguiente estrategia: Encontramos todos los ciclos simples y los combinamos en uno: este será el ciclo euleriano. Si el grafo es tal que el camino euleriano no es un ciclo, entonces agregamos la arista que falta, encontramos el ciclo euleriano y luego quitamos la arista extra.
Buscar todos los ciclos y combinarlos se puede hacer con un procedimiento recursivo simple:
procedure FindEulerPath(V)
1. iterate through all the edges outgoing from vertex V;
remove this edge from the graph,
and call FindEulerPath from the second end of this edge;
2. add vertex V to the answer.La complejidad de este algoritmo es obviamente lineal respecto del número de aristas.
Pero podemos escribir el mismo algoritmo en la versión no recursiva:
stack St;
put start vertex in St;
until St is empty
let V be the value at the top of St;
if degree(V) = 0, then
add V to the answer;
remove V from the top of St;
otherwise
find any edge coming out of V;
remove it from the graph;
put the second end of this edge in St;Es fácil comprobar la equivalencia de estas dos formas del algoritmo. Sin embargo, la segunda forma es obviamente más rápida, y el código será mucho más eficiente.
El problema del dominó
Damos aquí un problema clásico de ciclo euleriano: el problema del dominó.
Hay fichas de dominó; como se sabe, en ambos extremos del dominó está escrito un número (usualmente de 1 a 6, pero en nuestro caso no es importante). Se quiere poner todas las fichas en una fila de modo que los números de cualesquiera dos fichas adyacentes, escritos en su lado común, coincidan. Se permite girar las fichas.
Reformulemos el problema. Sean los números escritos en los extremos los vértices del grafo, y las fichas las aristas de este grafo (cada ficha con números son las aristas y ). Entonces nuestro problema se reduce al problema de encontrar el camino euleriano en este grafo.
Implementación
El programa de abajo busca e imprime un ciclo o camino euleriano en un grafo, o imprime si no existe.
Primero, el programa comprueba el grado de los vértices: si no hay vértices con grado impar, entonces el grafo tiene un ciclo euleriano; si hay vértices con grado impar, entonces en el grafo solo hay un camino euleriano (pero no un ciclo euleriano); si hay más de de tales vértices, entonces en el grafo no hay ciclo euleriano ni camino euleriano. Para encontrar el camino euleriano (no un ciclo), hagamos esto: si y son dos vértices de grado impar, entonces simplemente agregamos una arista , en el grafo resultante encontramos el ciclo euleriano (obviamente existirá), y luego quitamos la arista “ficticia” de la respuesta. Buscaremos el ciclo euleriano exactamente como se describió arriba (versión no recursiva), y al mismo tiempo al final de este algoritmo comprobaremos si el grafo estaba conexo o no (si el grafo no estaba conexo, entonces al final del algoritmo quedarán algunas aristas en el grafo, y en este caso hay que imprimir ). Finalmente, el programa tiene en cuenta que puede haber vértices aislados en el grafo.
Nótese que usamos una matriz de adyacencia en este problema. También esta implementación maneja encontrar la siguiente arista con fuerza bruta, lo que requiere iterar sobre la fila completa de la matriz una y otra vez. Una forma mejor sería guardar el grafo como una lista de adyacencia, y quitar aristas en y marcar las aristas inversas en una lista separada. De esta forma podemos alcanzar un algoritmo .
int main() {
int n;
vector<vector<int>> g(n, vector<int>(n));
// reading the graph in the adjacency matrix
vector<int> deg(n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j)
deg[i] += g[i][j];
}
int first = 0;
while (first < n && !deg[first])
++first;
if (first == n) {
cout << -1;
return 0;
}
int v1 = -1, v2 = -1;
bool bad = false;
for (int i = 0; i < n; ++i) {
if (deg[i] & 1) {
if (v1 == -1)
v1 = i;
else if (v2 == -1)
v2 = i;
else
bad = true;
}
}
if (v1 != -1)
++g[v1][v2], ++g[v2][v1];
stack<int> st;
st.push(first);
vector<int> res;
while (!st.empty()) {
int v = st.top();
int i;
for (i = 0; i < n; ++i)
if (g[v][i])
break;
if (i == n) {
res.push_back(v);
st.pop();
} else {
--g[v][i];
--g[i][v];
st.push(i);
}
}
if (v1 != -1) {
for (size_t i = 0; i + 1 < res.size(); ++i) {
if ((res[i] == v1 && res[i + 1] == v2) ||
(res[i] == v2 && res[i + 1] == v1)) {
vector<int> res2;
for (size_t j = i + 1; j < res.size(); ++j)
res2.push_back(res[j]);
for (size_t j = 1; j <= i; ++j)
res2.push_back(res[j]);
res = res2;
break;
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (g[i][j])
bad = true;
}
}
if (bad) {
cout << -1;
} else {
for (int x : res)
cout << x << " ";
}
}