Encontrar camino Hamiltoniano findHamiltonianPath()

En la sección de acciones de Grafos SVG ejecutamos algoritmos sobre un grafo. Uno de ellos es encontrar un camino Hamiltoniano entre dos nodos del grafo, que será un camino que debe recorrer todos los nodos del grafo una única vez. En la Figura vemos un camino Hamiltoniano en el grafo de Petersen 5,2 mostrando un camino entre los nodos "0" y "7" que recorre todos los nodos.

En la Figura vemos la sección de acciones con ese algoritmo findHamiltonianPath(), que como todos los algoritmos, recibe una matriz de adyacencia como estructura de datos del grafo. Pasamos los argumentos primer índice nodo y último índice nodo. El argumento encontrar todos está desactivado, pues como entre dos nodos puede haber cero o más caminos, en caso de que haya caminos devolverá el primero que encuentra. De estar activado devolvería todos los que existan, como veremos después.

La opción color camino se aplica después de ejecutarse el algoritmo, con objeto de resaltar ese camino en el grafo que está en pantalla.

El resultado obtenido es un Array con, a su vez, uno o más Arrays, donde cada uno es un camino en el grafo, que viene a ser una lista de nodos dispuesta de tal forma que entre dos nodos consecutivos existe una arista.

Time: 0 ms

Encontrar camino Hamiltoniano: [[0,1,2,3,4,9,6,8,5,7]]

Puede importar el ejemplo con este JSON.

{"nodes":[
    {"index":0,"nodeOffset":"2.5","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":"65.54 2.64","parent":[{"index":0}]},
    {"index":2,"nodeOffset":"51.01 22.36","parent":[{"index":1}]},
    {"index":3,"nodeOffset":"-4.34 -2.64","parent":[{"index":2}]},
    {"index":4,"nodeOffset":"-35.54 2.64","parent":[{"index":0},{"index":3}]},
    {"index":5,"nodeOffset":"-22.5 -5","parent":[{"index":0}]},
    {"index":6,"nodeOffset":"21.52 -16.18","parent":[{"index":1}]},
    {"index":7,"nodeOffset":"-2.41 -18.82","parent":[{"index":2},{"index":5}]},
    {"index":8,"nodeOffset":"-9.26 -43.82","parent":[{"index":3},{"index":5},{"index":6}]},
    {"index":9,"nodeOffset":"-41.52 -16.18","parent":[{"index":4},{"index":6},{"index":7}]}
],
"config":{
    "algorithm":"Find Hamiltonian path",
    "lastIndex":7
}}

Si marcamos la opción encontrar todos que vemos en la Figura, encontraremos todos los caminos Hamiltonianos entre los nodos "0" y "7". Se obtienen 4 caminos que podemos visualizar con los botones de navegación que se ubican en la parte superior derecha del área del SVG. En la Figura componemos esos grafos en una imagen.

El resultado obtenido son los 4 Arrays que vemos a continuación.

Time: 1 ms

Encontrar camino Hamiltoniano: [[0,1,2,3,4,9,6,8,5,7],[0,4,9,6,1,2,3,8,5,7],
[0,5,8,3,4,9,6,1,2,7],[0,5,8,6,1,2,3,4,9,7]]

En la Figura se muestra el grafo obtenido en Wolfram aplicando la función FindHamiltonianPath[g ,1, 8] para encontrar un camino Hamiltoniano entre los nodos "1" y "8", PathGraph[%] para obtener el subgrafo de ese camino y HighlightGraph[g, s] para resaltar ese subgrafo en el grafo inicial aplicando un estilo al camino con color rojo.

Puede ver más información en Hamiltonian Path en Wolfram MathWorld.

La presentación que ofrece Wolfram no es como la más usada para el grafo de Petersen en forma de dos círculos concéntricos con 5 nodos en cada círculo, pero se trata del mismo grafo. El camino encontrado "0, 5, 8, 3, 4, 9, 6, 1, 2, 7" es el mismo que el del tercer grafo de la Figura.

g = AdjacencyGraph[{{0,1,0,0,1,1,0,0,0,0},{1,0,1,0,0,0,1,0,0,0},{0,1,0,1,0,0,0,1,0,0},{0,0,1,0,1,0,0,0,1,0},{1,0,0,1,0,0,0,0,0,1},
{1,0,0,0,0,0,0,1,1,0},{0,1,0,0,0,0,0,0,1,1},{0,0,1,0,0,1,0,0,0,1},{0,0,0,1,0,1,1,0,0,0},{0,0,0,0,1,0,1,1,0,0}}, ImageSize->243, 
VertexSize->{"Scaled", 0.13}, VertexLabels->{1->Placed[0,Center], 2->Placed[1,Center], 3->Placed[2,Center], 4->Placed[3,Center], 
5->Placed[4,Center], 6->Placed[5,Center], 7->Placed[6,Center], 8->Placed[7,Center], 9->Placed[8,Center], 10->Placed[9,Center]}, 
VertexLabelStyle->Directive[Black,17.5], EdgeLabelStyle->Directive[Black,17.5,Bold], VertexStyle->White, EdgeStyle->{{Black,Thickness[0.005]}}];
FindHamiltonianPath[g, 1, 8];
PathGraph[%];
HighlightGraph[g, {Style[EdgeList[%], Red, Thick], Annotation[EdgeList[%], EdgeLabelStyle->Directive[Blue,17.5,Bold]]}]

Si generamos el grafo de Petersen directamente en Wolfram con PetersenGraph[5, 2, s] antes de aplicar FindHamiltonianPath[g ,1, 8] para encontrar un camino Hamiltoniano entre los nodos "1" y "8", obtenemos la presentación clásica del grafo de Petersen que vemos en la Figura.

s = {ImageSize->250, VertexSize->{"Scaled", 0.13}, VertexLabels ->Placed["Name", Center], VertexLabelStyle->Directive[Black, 17.5], 
VertexStyle->White, EdgeStyle->{{Black,Thickness[0.005]}}};
g = PetersenGraph[5, 2, s];
FindHamiltonianPath[g, 1, 8];
PathGraph[%];
HighlightGraph[g, {Style[EdgeList[%], Red, Thick], Annotation[EdgeList[%], EdgeLabelStyle->Directive[Blue,17.5,Bold]]}]

Si en nuestra aplicación generamos el grafo de Petersen con n=5, k=2 luego hacemos el ajuste visual para reflejar a la derecha y por último aplicamos valor nodo auto con el valor index+1 para que el valor de los nodos se inicie en "1" en lugar de "0", obtenemos el resultado de la Figura con la misma disposición de nodos y del camino Hamiltoniano que obtuvimos en Wolfram antes.

Con el JSON siguiente se puede importar este grafo.

{"nodes":[
    {"index":0,"nodeOffset":"38.19 33.82","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":"-2.41 56.18","parent":[{"index":-1}]},
    {"index":2,"nodeOffset":"24.07 31.18","parent":[{"index":0}]},
    {"index":3,"nodeOffset":"0.15 8.82","parent":[{"index":0},{"index":1}]},
    {"index":4,"nodeOffset":"2.5 -5","parent":[{"index":1},{"index":2}]},
    {"index":5,"nodeOffset":"23.87 2.64","parent":[{"index":0}]},
    {"index":6,"nodeOffset":"-7.32 47.36","parent":[{"index":1},{"index":5}]},
    {"index":7,"nodeOffset":"3.99 22.36","parent":[{"index":2},{"index":6}]},
    {"index":8,"nodeOffset":"-35.54 -22.36","parent":[{"index":3},{"index":7}]},
    {"index":9,"nodeOffset":"-22.5 -50","parent":[{"index":4},{"index":5},{"index":8}]}
],
"config":{
    "nodeValueAuto":"index+1",
    "algorithm":"Find Hamiltonian path",
    "lastIndex":7,
    "findAll":true
}}

En la Figura vemos un camino Hamiltoniano en un grafo dirigido entre nodos "D" y "A". En la aplicación obtenemos el siguiente resultado. Cuando los nodos tienen valores diferentes a sus índices se presenta adicionalmente el camino con los valores de los nodos.

Time: 0 ms

Encontrar camino Hamiltoniano: [[3,4,2,1,0]]

Valores de nodos de camino ⇒ 
["D","E","C","B","A"]

Aunque es posible definir el concepto de camino Hamiltoniano para grafos dirigidos, como así se expone en Wikipedia, no veo que Wolfram lo contemple, pues FindHamiltonianPath[g, 1, 4] devuelve el objeto vacío {} para este grafo.

Con este JSON puede importar el grafo de la Figura.

{"nodes":[
    {"index":0,"value":"A","parent":[{"index":-1}]},
    {"index":1,"value":"B","parent":[{"index":0,"value":10}]},
    {"index":2,"value":"C","parent":[{"index":0,"value":20},{"index":1,"value":30}]},
    {"index":3,"value":"D","parent":[{"index":1,"value":40},{"index":4,"value":"X"}]},
    {"index":4,"value":"E","parent":[{"index":1,"value":50},{"index":2,"value":60}]}
],
"config":{
    "markerEnd":"arrow",
    "algorithm":"Find Hamiltonian path",
    "firstIndex":3
}}

El código de la función findHamiltonianPath() para encontrar un camino Hamiltoniano se expone a continuacion. Se trata de un algoritmo recursivo que va agregando nodos al camino con path.push(firstIndex), de tal forma que cuando se complete un camino con n nodos se devuelve ese camino. En otro caso se quita el último nodo agregado con path.pop() y se prueba con el siguiente. Por lo visto la única forma de encontrar un camino Hamiltoniano entre dos nodos es probar todos los caminos posibles. Y eso es lo que se hace con el recursivo.

Se usa el algoritmo getParents() para obtener los padres de un nodo. El argumento findAll es el que vimos en la aplicación encontrar todos, devolviendo solo el primer camino encontrado o todos los que existen entre dos nodos con índices firstIndex y lastIndex. Se incluye el control de iteraciones máximas con la variable global iter.

function findHamiltonianPath({matrix=[], firstIndex=0, lastIndex=0, findAll=false, path=[], result=[]}) {
    if (iter++, iter>maxIter) return `Maximum iterations ${maxIter} reached`;
    try {
        let n = matrix.length;
        path.push(firstIndex);
        if (firstIndex===lastIndex && path.length===n) {
            result.push(path);
        } else {
            let parents = getParents({matrix, index:firstIndex});
            for (let parent of parents){
                if (parent!==firstIndex) {
                    if (!path.includes(parent)) {
                        let res = findHamiltonianPath({matrix, firstIndex:parent, lastIndex, findAll, path:[...path], result});
                        if (typeof res==="string") {
                            result.warning = res;
                            return result;
                        }
                        if (!findAll && result.length>0) return result;
                    }
                }
            }
            if (path.length<n || path[path.length-1]!==lastIndex) path.pop();
        }
    } catch(e){result = e.message}
    return result;
}

Encontrar todos los caminos Hamiltonianos findHamiltonianPathAll()

Encontrar todos los caminos Hamiltonianos en un grafo supone buscar todas las combinaciones entre dos nodos comprobando si entre ellos hay caminos Hamiltonianos, devolviéndose el primero encontrado para cada una de esas combinaciones.

En la Figura vemos un grafo no dirigido ponderado, con un camino Hamiltoniano entre los nodos "B" y "A". En la aplicación obtenemos el resultado siguiente con 13 caminos encontrados, pudiendo acceder a los grafos de cada uno con los botones que encontrará en la parte superior derecha por encima del área del SVG.

Cuando los nodos tienen valores diferentes de sus índices, se ofrece también los caminos con esos valores, como el primero resaltado B,A" → [["B", "C", "E", "G", "F", "D", "A"]] que se presenta en la Figura.

Time: 1 ms

Encontrar caminos Hamiltonianos todos: {
"1,0":[[1,2,4,6,5,3,0]], "2,0":[[2,1,4,6,5,3,0]], "2,1":[[2,4,6,5,3,0,1]],
"3,0":[[3,5,6,4,2,1,0]], "4,2":[[4,6,5,3,0,1,2]], "5,0":[[5,6,4,2,1,3,0]],
"5,2":[[5,6,4,3,0,1,2]], "5,3":[[5,6,4,2,1,0,3]], "6,0":[[6,5,3,4,2,1,0]],
"6,2":[[6,4,5,3,0,1,2]], "6,3":[[6,5,4,2,1,0,3]], "6,4":[[6,5,3,0,1,2,4]],
"6,5":[[6,4,2,1,0,3,5]]}

Valores de nodos de camino ⇒
"B,A"→[["B","C","E","G","F","D","A"]], "C,A"→[["C","B","E","G","F","D","A"]],
"C,B"→[["C","E","G","F","D","A","B"]], "D,A"→[["D","F","G","E","C","B","A"]],
"E,C"→[["E","G","F","D","A","B","C"]], "F,A"→[["F","G","E","C","B","D","A"]],
"F,C"→[["F","G","E","D","A","B","C"]], "F,D"→[["F","G","E","C","B","A","D"]],
"G,A"→[["G","F","D","E","C","B","A"]], "G,C"→[["G","E","F","D","A","B","C"]],
"G,D"→[["G","F","E","C","B","A","D"]], "G,E"→[["G","F","D","A","B","C","E"]],
"G,F"→[["G","E","C","B","A","D","F"]]

En la Figura vemos la sección de acciones con el algoritmo findHamiltonianPathAll() para encontrar todos los caminos Hamiltonianos del grafo.

Puede importar el ejemplo anterior con el siguiente JSON.

{"nodes":[
    {"index":0,"parent":[{"index":-1}]},
    {"index":1,"parent":[{"index":0,"value":7}]},
    {"index":2,"parent":[{"index":1,"value":8}]},
    {"index":3,"parent":[{"index":0,"value":5},{"index":1,"value":9}]},
    {"index":4,"parent":[{"index":1,"value":7},{"index":2,"value":5},{"index":3,"value":15}]},
    {"index":5,"parent":[{"index":3,"value":6},{"index":4,"value":8}]},
    {"index":6,"parent":[{"index":4,"value":9},{"index":5,"value":11}]}
],
"config":{
    "nodeValueAuto":"alphabetic-upper",
    "algorithm":"Find Hamiltonian path all"
}}

En la Figura vemos como Wolfram presenta todos los caminos Hamiltonianos. Usa la función FindHamiltonianPath[g, i, j] para encontrar un camino Hamiltoniano entre nodos "i" y "j". El código Wolfram siguiente se establece para iterar por todos las combinaciones de nodos del grafo, lo que obtenemos con la función Subsets[l,{2}] que nos devuelve los subconjuntos combinaciones entre dos nodos del grafo {{1,2}, {1,3}, ...}.

La lista "l" la obtenemos con Range[n] siendo "n" el número de nodos del grafo que se obtiene con VertexCount[g].

Usamos Table[] para construir una lista de resultados, donde el primer argumento es FindHamiltonianPath entre cada dos nodos de cada una de la combinaciones obtenidas en la variable "s".

Obtenemos los caminos con PathGraph y filtramos aquellos que no tengan caminos con Select y VertexCount. Por último resaltamos en color rojo los caminos con HighlightGraph.

g = AdjacencyGraph[{{0,1,0,1,0,0,0},{1,0,1,1,1,0,0},{0,1,0,0,1,0,0},{1,1,0,0,1,1,0},{0,1,1,1,0,1,1},{0,0,0,1,1,0,1},{0,0,0,0,1,1,0}}, 
ImageSize->250, VertexSize->{"Scaled", 0.13}, VertexLabels->{1->Placed["A",Center], 2->Placed["B",Center], 
3->Placed["c",Center], 4->Placed["D",Center], 5->Placed["E",Center], 6->Placed["F",Center], 7->Placed["G",Center]}, 
VertexLabelStyle->Directive[Black,17.5], EdgeLabelStyle->Directive[Black,17.5,Bold], 
EdgeLabels->{(2->1)->7, (3->2)->8, (4->1)->5, (4->2)->9, (5->2)->7, (5->3)->5, (5->4)->15, (6->4)->6, (6->5)->8, (7->5)->9, (7->6)->11}, 
VertexStyle->White, EdgeStyle->{{Black,Thickness[0.005]}}];
n = VertexCount[g];
l = Range[n];
s = Subsets[l,{2}];
t = Table[FindHamiltonianPath[g, Part[i,1], Part[i,2]], {i, s}];
q = Table[PathGraph[i], {i, t}];
p = Select[q, VertexCount[#]>0 &];
Table[HighlightGraph[g, {Style[EdgeList[i], Red, Thick], Annotation[EdgeList[i], EdgeLabelStyle->Directive[Blue,17.5,Bold]]}], {i,p}]

Con la opción encontrar todos que vemos en la Figura encontraremos todos los caminos posibles entre dos nodos. Por ejemplo, para los nodos "C" y "A", antes sólo exponía el primer camino encontrado, ahora vemos que aparecen dos, como se muestra en el resultado obtenido en la aplicación, donde seleccionamos los dos grafos de lo señalado en amarillo y lo componemos en la Figura.

"B,A"→[["B","C","E","G","F","D","A"]],
"C,A"→[["C","B","E","G","F","D","A"], ["C","E","G","F","D","B","A"]],
"C,B"→[["C","E","G","F","D","A","B"]],
"D,A"→[["D","F","G","E","C","B","A"]],
"E,C"→[["E","G","F","D","A","B","C"]],
"F,A"→[["F","G","E","C","B","D","A"]],
"F,C"→[["F","G","E","D","A","B","C"]],
"F,D"→[["F","G","E","C","B","A","D"]],
"G,A"→[["G","F","D","E","C","B","A"], ["G","F","E","C","B","D","A"]],
"G,C"→[["G","E","F","D","A","B","C"], ["G","F","D","A","B","E","C"], ["G","F","E","D","A","B","C"]],
"G,D"→[["G","F","E","C","B","A","D"]],
"G,E"→[["G","F","D","A","B","C","E"]],
"G,F"→[["G","E","C","B","A","D","F"]]

El primero ["C","B","E","G","F","D","A"] con suma de valores 8+7+9+11+6+5=46. El segundo ["C","E","G","F","D","B","A"] con suma de valores 5+9+11+6+9+7=47. Se podría implementar en la aplicación otra opción para devolver el camino más corto (o más largo), pero esto, que es implementado por Wolfram, no existe en nuestra aplicación aunque resultaría fácil de implementar.

En la Figura vemos los dos únicos caminos Hamiltonianos posibles para ese grafo: {"0,3":[[0,1,2,5,4,3],[0,2,5,1,4,3]]}. Puede importarlo con el siguiente JSON. Recordemos que Wolfram parece ignorar los caminos Hamiltonianos en grafos dirigidos.

{"nodes":[
    {"index":0,"parent":[{"index":-1}]},
    {"index":1,"parent":[{"index":0},{"index":4,"markerStart":"none","markerEnd":"arrow","lineType":"quadratic","lineOffset":"-7 7"}]},
    {"index":2,"parent":[{"index":0},{"index":1}]},
    {"index":3,"parent":[{"index":1},{"index":2}]},
    {"index":4,"parent":[{"index":5},{"index":3,"markerStart":"none","markerEnd":"arrow"}]},
    {"index":5,"parent":[{"index":0},{"index":2},{"index":1,"markerStart":"none","markerEnd":"arrow","lineType":"quadratic","lineOffset":"0 4"}]}
],
"config":{
    "markerStart":"arrow",
    "algorithm":"Find Hamiltonian path all",
    "findAll":true
}}

El código JavaScript para encontrar todos los caminos Hamiltonianos de un grafo es findHamiltonianPathAll() que vemos a continuación. Itera por todos los nodos usando findHamiltonianPath() que vimos en el apartado anterior. Y isGraphDirected() para comprobar si el grafo es dirigido que ya hemos visto en un tema anterior.

function findHamiltonianPathAll({matrix=[], findAll=false}) {
    let result = {};
    try {
        let n = matrix.length;
        let directed = isGraphDirected({matrix});
        if (typeof directed==="string") throw new Error(directed);
        for (let i=0; i<n; i++) {
            let m = directed ? n : i;
            for (let j=0; j<m; j++){
                if (i!==j) {
                    let res = findHamiltonianPath({matrix, firstIndex:i, lastIndex:j, findAll});
                    if (res.length>0) result[`${i},${j}`] = res;
                    if (typeof res==="string") {
                        result.warning = res;
                        return result;
                    }
                }
            }
        }
    } catch(e){result = e.message}
    return result;
}

Encontrar ciclo Hamiltoniano findHamiltonianCycle()

Un ciclo Hamiltoniano es un camino Hamiltoniano donde el primer y último nodo del camino tienen una arista que los une. Recordamos que un camino Hamiltoniano es el que recorre todos los nodos del grafo una única vez. En la Figura vemos el ciclo [0,5,2,4,3,6,1,7,0] de un grafo corona. Un camino es una lista de nodos con una arista entre dos nodos, y cuando un camino es un ciclo se agrega al final de la lista el nodo inicial.

El nodo inicial de un ciclo puede ser cualquiera. Así [4,3,6,1,7,0,5,2,4] es el mismo ciclo que [0,5,2,4,3,6,1,7,0]. Es usual tomar el primer nodo como inicio del ciclo. También vemos que el inverso de un ciclo es el mismo ciclo para un grafo no dirigido, así el ciclo [0,7,1,6,3,4,2,5,0] es inverso del anterior y refleja el mismo ciclo.

El siguiente JSON importará el grafo anterior.

{"nodes":[
    {"index":0,"parent":[{"index":-1}]},
    {"index":1,"parent":[{"index":-1}]},
    {"index":2,"parent":[{"index":-1}]},
    {"index":3,"parent":[{"index":-1}]},
    {"index":4,"parent":[{"index":1},{"index":2},{"index":3}]},
    {"index":5,"parent":[{"index":0},{"index":2},{"index":3}]},
    {"index":6,"parent":[{"index":0},{"index":1},{"index":3}]},
    {"index":7,"parent":[{"index":0},{"index":1},{"index":2}]}
],
"config":{
    "algorithm":"Find Hamiltonian cycle"
}}

Para el ajuste visual a círculo que vimos en un tema anterior usábamos el argumento orden nodos para presentar visualmente los nodos en ese orden. Pasando ahí un ciclo Hamiltoniano como 0,5,2,4,3,6,1,7,0 encontrado antes, vemos el resultado en la Figura, donde hay una arista entre dos nodos que se ubica sobre la circunferencia.

El siguiente JSON importará ese grafo.

{"nodes":[
    {"index":0,"nodeOffset":"1.29 8.79","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":"-18.71 51.21","parent":[{"index":-1}]},
    {"index":2,"nodeOffset":"3.71 8.79","parent":[{"index":-1}]},
    {"index":3,"nodeOffset":"-16.29 51.21","parent":[{"index":-1}]},
    {"index":4,"nodeOffset":"52.5 5","parent":[{"index":1},{"index":2},{"index":3}]},
    {"index":5,"nodeOffset":"2.5 -25","parent":[{"index":0},{"index":2},{"index":3}]},
    {"index":6,"nodeOffset":"-17.5 35","parent":[{"index":0},{"index":1},{"index":3}]},
    {"index":7,"nodeOffset":"-67.5 5","parent":[{"index":0},{"index":1},{"index":2}]}
],
"config":{
    "algorithm":"Find Hamiltonian cycle"
}}

En la Figura vemos la opción encontrar todos, inicialmente desactivado con lo que se devolverá el primer ciclo Hamiltoniano encontrado. En otro caso devolverá todos los ciclos, con el siguiente resultado para el grafo Corona que vimos antes:

[[0,5,2,4,3,6,1,7,0],
[0,5,2,7,1,4,3,6,0],
[0,5,3,4,2,7,1,6,0],
[0,5,3,6,1,4,2,7,0],
[0,6,1,4,3,5,2,7,0],
[0,6,3,5,2,4,1,7,0]]

La aplicación ofrece los seis ciclos resaltados en el grafo Corona, mediante el uso de los botones de navegación ubicados en la parte superior derecha del área del SVG.

Con la otra opción con caminos inversos activada por cada ciclo encontrado devolverá también su inverso. Por ejemplo [0,5,2,4,3,6,1,7,0] y su inverso[0,7,1,6,3,4,2,5,0], que en el fondo son el mismo ciclo para un grafo no dirigido. Si antes obteníamos seis ciclos ahora obtenemos el doble:

[[0,5,2,4,3,6,1,7,0],
[0,5,2,7,1,4,3,6,0],
[0,5,3,4,2,7,1,6,0],
[0,5,3,6,1,4,2,7,0],
[0,6,1,4,3,5,2,7,0],
[0,6,1,7,2,4,3,5,0],
[0,6,3,4,1,7,2,5,0],
[0,6,3,5,2,4,1,7,0],
[0,7,1,4,2,5,3,6,0],
[0,7,1,6,3,4,2,5,0],
[0,7,2,4,1,6,3,5,0],
[0,7,2,5,3,4,1,6,0]]

La función FindHamiltonianCycle[g, All] busca todos los ciclos Hamiltonianos en Wolfram. El segundo argumento puede ser un número entero devolviendo como máximo ese número de ciclos. O bien "All" para encontrarlos todos. Si se omite se entiende el número 1, con lo que devuelve el primer ciclo encontrado. Vemos en la Figura que encuentra los mismos seis ciclos que obtuvimos en nuestra aplicación con encontrar todos y sin caminos inversos.

El código siguiente usa además las funciones Table[], PathGraph y HighlightGraph para listar y resaltar todos los ciclos.

g = AdjacencyGraph[{{0,0,0,0,0,1,1,1},{0,0,0,0,1,0,1,1},{0,0,0,0,1,1,0,1},{0,0,0,0,1,1,1,0},{0,1,1,1,0,0,0,0},{1,0,1,1,0,0,0,0},{1,1,0,1,0,0,0,0},{1,1,1,0,0,0,0,0}}, 
ImageSize->125, VertexSize->{"Scaled", 0.13}, VertexLabels->{1->Placed[0,Center], 2->Placed[1,Center], 
3->Placed[2,Center], 4->Placed[3,Center], 5->Placed[4,Center], 6->Placed[5,Center], 7->Placed[6,Center], 
8->Placed[7,Center]}, VertexLabelStyle->Directive[Black,12.25], EdgeLabelStyle->Directive[Black,12.25,Bold], 
VertexStyle->White, EdgeStyle->{{Black,Thickness[0.005]}}];
h = FindHamiltonianCycle[g, All];
p = Table[PathGraph[i], {i, h}];
Table[HighlightGraph[g, {Style[EdgeList[i], Red, Thick], Annotation[EdgeList[i], EdgeLabelStyle->Directive[Blue,17.5,Bold]]}], {i, p}]

Puede ver más información Hamiltonian Cycle en Wolfram MathWorld.

En la Figura vemos los dos ciclos Hamiltonianos del grafo dirigido que puede importar con el siguiente JSON.

{"nodes":[
    {"index":0,"parent":[{"index":-1}]},
    {"index":1,"parent":[{"index":0},{"index":4,"markerStart":"none","markerEnd":"arrow","lineType":"quadratic","lineOffset":"-7 7"}]},
    {"index":2,"parent":[{"index":0},{"index":1}]},
    {"index":3,"parent":[{"index":1},{"index":2},{"index":0,"markerStart":"none","markerEnd":"arrow","lineType":"quadratic","lineOffset":"-10 -4"}]},
    {"index":4,"parent":[{"index":5},{"index":3,"markerStart":"none","markerEnd":"arrow"}]},
    {"index":5,"parent":[{"index":0},{"index":2},{"index":1,"markerStart":"none","markerEnd":"arrow","lineType":"quadratic","lineOffset":"0 4"}]}
],
"config":{
    "markerStart":"arrow",
    "algorithm":"Find Hamiltonian cycle",
    "findAll":true
}}

Vimos que Wolfram parecía ignorar los caminos Hamiltonianos en un grafo dirigido. Sin embargo presenta los ciclos Hamiltonianos en un grafo dirigido, como se observa en la Figura, encontrando los mismos ciclos que en nuestra aplicación que vemos en la Figura.

g = AdjacencyGraph[{{0,1,1,0,0,1},{0,0,1,1,1,0},{0,0,0,1,0,1},{1,0,0,0,0,0},{0,0,0,1,0,0},{0,1,0,0,1,0}}, 
ImageSize->215, VertexSize->{"Scaled", 0.07}, VertexLabels->{1->Placed[0,Center], 2->Placed[1,Center], 
3->Placed[2,Center], 4->Placed[3,Center], 5->Placed[4,Center], 6->Placed[5,Center]}, 
VertexLabelStyle->Directive[Black,12.25], EdgeLabelStyle->Directive[Black,12.25,Bold], VertexStyle->White, 
DirectedEdges->True, EdgeStyle->{{Black,Thickness[0.005]}}];
h = FindHamiltonianCycle[g, All];
p = Table[PathGraph[i], {i, h}];
Table[HighlightGraph[g, {Style[EdgeList[i], Red, Thick], Annotation[EdgeList[i], EdgeLabelStyle->Directive[Blue,17.5,Bold]]}], {i, p}]

El código JavaScript de la función findHamiltonianCycle() se expone a continuación. Usa getParents() para obtener los padres de un nodo. El argumento index será 0 por defecto, aunque podría modificarse pero no se incluye en la interfaz de la aplicación. Los argumentos son findAll para la opción encontrar todos y withReversePaths para la opción con caminos inversos que ya explicamos antes. El argumento firstMatch devolverá el primer ciclo encontrado con la opción encontrar todos activada y se usará en el siguiente algoritmo isHamiltonianGraph() que veremos en el siguiente apartado.

function findHamiltonianCycle({matrix=[], index=0, findAll=false, withReversePaths=false, firstMatch=false, path=[], result=[]}) {
    if (iter++, iter>maxIter) return `Maximum iterations ${maxIter} reached`;
    try {
        let n = matrix.length;
        path.push(index);
        let parents = getParents({matrix, index});
        for (let parent of parents){
            if (parent===path[0] && path.length===n) {
                path.push(parent);
                if (result.length===0 || withReversePaths) {
                    result.push(path);
                } else {
                    let pathReverse = path.toReversed().toString();
                    if (result.every(v => v.toString()!==pathReverse)){
                        result.push(path);
                    }
                }
            } else if (!path.includes(parent)) {
                let res = findHamiltonianCycle({matrix, index:parent, findAll, withReversePaths, firstMatch, path:[...path], result});
                if (typeof res==="string") {
                    result.warning = res;
                    result.push(res);
                    return result;
                }
                if ((!findAll || firstMatch) && result.length>0) return result;
            }
        }
        if (path.length<=n) path.pop();
    } catch(e){result = e.message}
    return result;
}

Es el grafo Hamiltoniano isHamiltonianGraph()

Un grafo es Hamiltoniano si tiene un ciclo Hamiltoniano. En la Figura vemos que el grafo de Petersen 5,2 no es Hamiltoniano, a pesar de que tiene caminos Hamiltonianos como vimos en el primer apartado.

La aplicación usa la función isHamiltonianGraph({matrix}) devolviendo un Array. Si no es un grafo Hamiltoniano devolverá [false]. En otro caso devolverá algo como [true, [0,1,2,3,4,5,0]] añadiéndose el primer ciclo Hamiltoniano encontrado.

Vimos en un tema anterior los grafos Platónicos, observando en la Figura que todos los grafos Platónicos son también Hamiltonianos. Con los JSON siguientes podrá importar los grafos Platónicos que son tetraédrico, octaédrico, cúbico, icosaédrico y dodecaédrico.

Tetraédrico

{"nodes":[
    {"index":0,"nodeOffset":"-17.5 20","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":"7.5 -25","parent":[{"index":0}]},
    {"index":2,"nodeOffset":"-0.18 5","parent":[{"index":0},{"index":1}]},
    {"index":3,"nodeOffset":"-59.82 5","parent":[{"index":0},{"index":1},{"index":2}]}
],
"config":{
    "nodeValueAuto":"none",
    "nodeRadius":2,
    "algorithm":"Is Hamiltonian graph"
}}

Octaédrico

{"nodes":[
    {"index":0,"nodeOffset":"-17.5","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":"29.82 -15","parent":[{"index":0}]},
    {"index":2,"nodeOffset":"9.82 5","parent":[{"index":0},{"index":1}]},
    {"index":3,"nodeOffset":"-17.5 -10","parent":[{"index":1},{"index":2}]},
    {"index":4,"nodeOffset":"-44.82 5","parent":[{"index":0},{"index":2},{"index":3}]},
    {"index":5,"nodeOffset":"-64.82 -15","parent":[{"index":0},{"index":1},{"index":3},{"index":4}]}
],
"config":{
    "nodeValueAuto":"none",
    "nodeRadius":2,
    "algorithm":"Is Hamiltonian graph"
}}

Cúbico

{"nodes":[
    {"index":0,"nodeOffset":"-17.5","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":"27.5 -5","parent":[{"index":0}]},
    {"index":2,"nodeOffset":"7.5 -10","parent":[{"index":1}]},
    {"index":3,"nodeOffset":"-37.5 -5","parent":[{"index":0},{"index":2}]},
    {"index":4,"nodeOffset":"-42.5 -15","parent":[{"index":0}]},
    {"index":5,"nodeOffset":"-7.5 -30","parent":[{"index":1},{"index":4}]},
    {"index":6,"nodeOffset":"-17.5 -45","parent":[{"index":2},{"index":5}]},
    {"index":7,"nodeOffset":"-52.5 -30","parent":[{"index":3},{"index":4},{"index":6}]}
],
"config":{
    "nodeValueAuto":"none",
    "nodeRadius":2,
    "algorithm":"Is Hamiltonian graph"
}}

Icosaédrico

{"nodes":[
    {"index":0,"nodeOffset":"-3.5","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":"59.27 -8","parent":[{"index":0}]},
    {"index":2,"nodeOffset":"42.61 1","parent":[{"index":1}]},
    {"index":3,"nodeOffset":"13.17 -7","parent":[{"index":2}]},
    {"index":4,"nodeOffset":"-16.27 -49","parent":[{"index":3}]},
    {"index":5,"nodeOffset":"-16.27 -8","parent":[{"index":0},{"index":4}]},
    {"index":6,"nodeOffset":"-3.5 -11","parent":[{"index":0},{"index":1},{"index":5}]},
    {"index":7,"nodeOffset":"-2.85 -1","parent":[{"index":0},{"index":1},{"index":2}]},
    {"index":8,"nodeOffset":"-2.85 -6","parent":[{"index":1},{"index":2},{"index":3},{"index":6}]},
    {"index":9,"nodeOffset":"-20.17 -21","parent":[{"index":2},{"index":3},{"index":4},{"index":7}]},
    {"index":10,"nodeOffset":"-37.49 -56","parent":[{"index":3},{"index":4},{"index":5},{"index":6},{"index":8}]},
    {"index":11,"nodeOffset":"-54.15 -1","parent":[{"index":0},{"index":4},{"index":5},{"index":7},{"index":9}]}
],
"config":{
    "nodeValueAuto":"none",
    "nodeRadius":2,
    "algorithm":"Is Hamiltonian graph"
}}

Dodecaédrico

{"nodes":[
    {"index":0,"nodeOffset":"-3.5","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":"41.48 -18.51","parent":[{"index":0}]},
    {"index":2,"nodeOffset":"53.84 -26.51","parent":[{"index":1}]},
    {"index":3,"nodeOffset":"45.51 -30.49","parent":[{"index":2}]},
    {"index":4,"nodeOffset":"33.15 -38.49","parent":[{"index":3}]},
    {"index":5,"nodeOffset":"13.17 -57","parent":[{"index":4}]},
    {"index":6,"nodeOffset":"-6.81 -88.49","parent":[{"index":5}]},
    {"index":7,"nodeOffset":"-19.17 -130.49","parent":[{"index":6}]},
    {"index":8,"nodeOffset":"-19.17 -176.51","parent":[{"index":7}]},
    {"index":9,"nodeOffset":"-23.48 -18.51","parent":[{"index":0},{"index":8}]},
    {"index":10,"nodeOffset":"-28.5 -11","parent":[{"index":0}]},
    {"index":11,"nodeOffset":"8.26 -32.18","parent":[{"index":1}]},
    {"index":12,"nodeOffset":"-1.15 -47.18","parent":[{"index":2},{"index":10}]},
    {"index":13,"nodeOffset":"-1.15 -59.82","parent":[{"index":3},{"index":11}]},
    {"index":14,"nodeOffset":"-8.41 -74.82","parent":[{"index":4},{"index":12}]},
    {"index":15,"nodeOffset":"-20.17 -96","parent":[{"index":5},{"index":13}]},
    {"index":16,"nodeOffset":"-31.93 -124.82","parent":[{"index":6},{"index":14}]},
    {"index":17,"nodeOffset":"-39.19 -159.82","parent":[{"index":7},{"index":15}]},
    {"index":18,"nodeOffset":"-22.52 -197.18","parent":[{"index":8},{"index":10},{"index":16}]},
    {"index":19,"nodeOffset":"-40.26 -32.18","parent":[{"index":9},{"index":11},{"index":17}]}
],
"config":{
    "nodeValueAuto":"none",
    "nodeRadius":2,
    "algorithm":"Is Hamiltonian graph"
}}

En la Figura vemos la exportación a Wolfram del grafo Platónico icosaédrico, encontrando un ciclo Hamiltoniano y respondiendo true a la función HamiltonianGraphQ[g] que es la equivalente a nuestra función isHamiltonianGraph(). Wolfram sólo devuelve true o false, pero podemos resaltar el ciclo usando los recursos que ya hemos visto en casos anteriores.

Se vacían los valores de los nodos y se ajusta a un factor 0.3 el tamaño de los nodos, como se observa en la Figura.

g = AdjacencyGraph[{{0,1,0,0,0,1,1,1,0,0,0,1},{1,0,1,0,0,0,1,1,1,0,0,0},{0,1,0,1,0,0,0,1,1,1,0,0},{0,0,1,0,1,0,0,0,1,1,1,0},{0,0,0,1,0,1,0,0,0,1,1,1},
{1,0,0,0,1,0,1,0,0,0,1,1},{1,1,0,0,0,1,0,0,1,0,1,0},{1,1,1,0,0,0,0,0,0,1,0,1},{0,1,1,1,0,0,1,0,0,0,1,0},{0,0,1,1,1,0,0,1,0,0,0,1},
{0,0,0,1,1,1,1,0,1,0,0,0},{1,0,0,0,1,1,0,1,0,1,0,0}}, ImageSize->233, VertexSize->{"Scaled", 0.04}, 
VertexLabels->{1->Placed["",Center], 2->Placed["",Center], 3->Placed["",Center], 4->Placed["",Center], 5->Placed["",Center], 
6->Placed["",Center], 7->Placed["",Center], 8->Placed["",Center], 9->Placed["",Center], 10->Placed["",Center], 
11->Placed["",Center], 12->Placed["",Center]}, VertexLabelStyle->Directive[Black,17.5], EdgeLabelStyle->Directive[Black,17.5,Bold], 
VertexStyle->White, EdgeStyle->{{Black,Thickness[0.005]}}];
h = FindHamiltonianCycle[g, 1];
p = Table[PathGraph[i], {i, h}];
Table[HighlightGraph[g, {Style[EdgeList[i], Red, Thick], Annotation[EdgeList[i], EdgeLabelStyle->Directive[Blue,17.5,Bold]]}], {i, p}]
HamiltonianGraphQ[g]

En la Figura vemos el mismo grafo icosaédrico en Wolfram, pero usando el recurso Graph[GraphData["IcosahedralGraph"], s], con una disposición de nodos que usualmente solemos ver.

El código Wolfram siguiente de ese grafo lo hemos escrito manualmente, eliminando todo aquello que sea innecesario.

s = {ImageSize->233, VertexSize->{"Scaled", 0.04}, VertexStyle->White};
g = Graph[GraphData["IcosahedralGraph"], s];
h = FindHamiltonianCycle[g];
p = PathGraph[First[h]];
HighlightGraph[g, {Style[EdgeList[p], Red, Thick]}]
HamiltonianGraphQ[g]

El código JavaScript de la función isHamiltonianGraph() se muestra a continuación. Usa la función ya vista en el apartado anterior findHamiltonianCycle() para encontrar un ciclo Hamiltoniano, buscando en todos los ciclos con findAll:true pero devolviendo el primero encontrado, lo que forzamos con firstMatch:true.

function isHamiltonianGraph({matrix=[]}) {
    let result = [false];
    try {
        let temp = findHamiltonianCycle({matrix, findAll:true, firstMatch:true});
        if (typeof temp==="string") {
            result.push(temp);
        } else {
            result[0] = temp.length>0;
            if (result[0]) result.push(temp[0]);
            if (typeof temp.warning==="string") result.push(temp.warning);
        }
    } catch(e){result = e.message}
    return result;
}