31 mar 2026

Isomorfismos en grafos

Resolver problema de grafos isomórficos con método fuerza bruta

El método de fuerza bruta para saber si dos grafos son isomorfos se basa en ir obteniendo las permutaciones del primer grafo hasta que consigamos una permutación cuya matriz de adyacencia sea igual que la del segundo grafo. El algoritmo está limitado por el número de permutaciones, pues por ejemplo, con 10 nodos hay 10! = 3 628 800 permutaciones y con 20 nodos hay 20! ≈ 2.43×10¹⁸ permutaciones, lo que supone que sea computacionalmente impracticable a partir de 10 nodos, planteándose el algoritmo de McKay que veremos en estos temas para resolver este problema de isomorfismos.

Aunque el método de fuerza bruta es poco práctico, puede resultar interesante observar sus limitaciones y así valorar mejor la implementación del algoritmo de McKay.

Vimos en el tema anterior los isomorfismos entre grafos, exponiendo el mismo ejemplo que vemos en la Figura, donde esos dos grafos son isomorfos. El segundo es la permutación de [0,3,2,1,4] y también de [3,0,4,1,2].

{"nodes":[
    {"index":0,"nodeColor":"lightpink","parent":[{"index":-1}]},
    {"index":1,"nodeColor":"lightcyan","parent":[{"index":0}]},
    {"index":2,"nodeColor":"lightgreen","parent":[{"index":0},{"index":1}]},
    {"index":3,"nodeColor":"beige","parent":[{"index":1},{"index":4}]},
    {"index":4,"nodeColor":"gold","parent":[{"index":1},{"index":2}]}
],
"config":{
    "algorithm":"Is graph isomorphic",
    "adjacencyMatrix":"0 0 1 1 0\n0 0 0 1 1\n1 0 0 1 1\n1 1 1 0 1\n0 1 1 1 0 "
}}

0 1 1 0 0
1 0 1 1 1
1 1 0 0 1
0 1 0 0 1
0 1 1 1 0

{"nodes":[
    {"index":0,"nodeOffset":"0 50","nodeColor":"lightpink","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":-16.67,"nodeColor":"lightcyan","parent":[{"index":-1}]},
    {"index":2,"nodeOffset":"41.67 25","nodeColor":"lightgreen","parent":[{"index":0}]},
    {"index":3,"nodeOffset":-16.67,"nodeColor":"beige","parent":[{"index":0},{"index":1},{"index":2}]},
    {"index":4,"nodeOffset":-8.33,"nodeColor":"gold","parent":[{"index":1},{"index":2},{"index":3}]}
],
"config":{}}

0 0 1 1 0
0 0 0 1 1
1 0 0 1 1
1 1 1 0 1
0 1 1 1 0

En la Figura vemos las opciones para ejecutar el algoritmo isGraphIsomorfic(). En matriz adyacencia incluiremos la del segundo grafo para chequear si ambos son isomorfos. Se puede poner en formato Array de JavaScript o en ese formato que vemos SSV (valores separado por espacio).

Entre los métodos isomorfismo vemos los tres primeros del tipo fuerza bruta y el último McKay al que aplican las opciones a partir de usar refinamiento inclusive que veremos en siguientes temas.

Con fuerza bruta con todas las permutaciones en orden obtenemos el siguiente resultado si tomamos el primer grafo de la Figura y la segunda matriz de adyacencia:

Time: 2 ms

Es el grafo isomórfico: [true,
"Found a match in permutation 13 (0,3,2,1,4) out of a total of 5! = 120"]

En el tema anterior relacionamos las 120 permutaciones, resaltando en color verde y azul las dos permutaciones 0,3,2,1,4 y 3,0,4,1,2 que producen el segundo grafo. El algoritmo encontró la primera que es la que ocupa la posición 13 en la lista de permutaciones.

01234, 10234, 02134, 20134, 21034, 12034, 01324, 10324, 03124, 30124, 31024, 13024, 03214,
30214, 02314, 20314, 23014, 32014, 31204, 13204, 32104, 23104, 21304, 12304, 01243, 10243,
02143, 20143, 21043, 12043, 01423, 10423, 04123, 40123, 41023, 14023, 04213, 40213, 02413,
20413, 24013, 42013, 41203, 14203, 42103, 24103, 21403, 12403, 01432, 10432, 04132, 40132,
41032, 14032, 01342, 10342, 03142, 30142, 31042, 13042, 03412, 30412, 04312, 40312, 43012,
34012, 31402, 13402, 34102, 43102, 41302, 14302, 04231, 40231, 02431, 20431, 24031, 42031,
04321, 40321, 03421, 30421, 34021, 43021, 03241, 30241, 02341, 20341, 23041, 32041, 34201,
43201, 32401, 23401, 24301, 42301, 41230, 14230, 42130, 24130, 21430, 12430, 41320, 14320,
43120, 34120, 31420, 13420, 43210, 34210, 42310, 24310, 23410, 32410, 31240, 13240, 32140,
23140, 21340, 12340

Con el método fuerza bruta con permutación inicial incluyendo 0,3,2,1,4 en la opción permutación inicial para fuerza bruta que vemos en la Figura, nos sirve para chequear si esa permutación es la del isomorfismo, pues empezará a buscar a partir de esa en la lista. Vemos en el resultado que la encuentra en primera posición.

Time: 0 ms
Es el grafo isomórfico: [true,
"Found a match in permutation 1 (0,3,2,1,4) out of a total of 5! = 120.
(Initial permutation given 0,3,2,1,4)"]

Con el método fuerza bruta con permutaciones aleatorias el algoritmo selecciona aleatoriamente permutaciones de la lista hasta que encuentra una. En esta ejecución hizo 111 intentos hasta descubrir 0,3,2,1,4.

Time: 1 ms
Es el grafo isomórfico: [true,
"Found a match in iteration 111 with the random permutation 0,3,2,1,4"]

En la Figura vemos como Wolfram encuentra que esos dos grafos son isomórficos usando IsomorphicGraphQ[g1, g2].

g1 = AdjacencyGraph[{{0,1,1,0,0},{1,0,1,1,1},{1,1,0,0,1},{0,1,0,0,1},{0,1,1,1,0}}, ImageSize -> 188, VertexSize -> {"Scaled", 0.17}, 
VertexLabels -> {1 -> Placed[0,Center], 2 -> Placed[1,Center], 3 -> Placed[2,Center], 4 -> Placed[3,Center], 5 -> Placed[4,Center]}, 
VertexLabelStyle -> Directive[Black,17.5], EdgeLabelStyle -> Directive[Black,17.5,Bold], 
VertexStyle -> {1 -> RGBColor["lightpink"],2 -> LightCyan,3 -> LightGreen,4 -> RGBColor["beige"],5 -> RGBColor["gold"]}, EdgeStyle -> {{Black,Thickness[0.005]}}]
g2 = AdjacencyGraph[{{0,0,1,1,0},{0,0,0,1,1},{1,0,0,1,1},{1,1,1,0,1},{0,1,1,1,0}}, ImageSize -> 188]
IsomorphicGraphQ[g1, g2]

El algoritmo también puede aplicarse a grafos dirigidos, como los de la Figura que son isomórficos.

Es el grafo isomórfico: 
[true,"Found a match in permutation 110 (3,4,2,1,0) out of a total of 5! = 120"]

{"nodes":[
    {"index":0,"nodeColor":"lightpink","parent":[{"index":-1}]},
    {"index":1,"nodeColor":"lightcyan","parent":[{"index":0}]},
    {"index":2,"nodeColor":"lightgreen","parent":[{"index":0},{"index":1}]},
    {"index":3,"nodeColor":"beige","parent":[{"index":1},{"index":4}]},
    {"index":4,"nodeColor":"gold","parent":[{"index":1},{"index":2}]}
],
"config":{
    "markerStart":"arrow",
    "algorithm":"Is graph isomorphic",
    "adjacencyMatrix":"0 0 0 0 0\n1 0 0 0 0\n0 1 0 0 0\n1 1 1 0 0\n0 0 1 1 0"
}}

{"nodes":[
    {"index":0,"nodeColor":"lightpink","nodeOffset":"-16.67 50","parent":[{"index":-1}]},
    {"index":1,"nodeColor":"lightcyan","nodeOffset":"33.34 25","parent":[{"index":0}]},
    {"index":2,"nodeColor":"lightgreen","nodeOffset":"16.67 -25","parent":[{"index":1}]},
    {"index":3,"nodeColor":"beige","nodeOffset":"-33.34","parent":[{"index":0},{"index":1},{"index":2}]},
    {"index":4,"nodeColor":"gold","nodeOffset":"0 -75","parent":[{"index":2},{"index":3}]}
],
"config":{
    "markerEnd":"arrow"
}}

0 0 0 0 0
1 0 0 0 0
0 1 0 0 0
1 1 1 0 0
0 0 1 1 0

En la Figura vemos como Wolfram encuentra que esos dos grafos dirigidos son isomórficos usando IsomorphicGraphQ[g1, g2].

g1 = AdjacencyGraph[{{0,1,1,0,0},{0,0,1,1,1},{0,0,0,0,1},{0,0,0,0,0},{0,0,0,1,0}}, ImageSize -> 88, VertexSize -> {"Scaled", 0.36}, VertexLabels -> {1 -> Placed[0,Center], 
2 -> Placed[1,Center], 3 -> Placed[2,Center], 4 -> Placed[3,Center], 5 -> Placed[4,Center]}, VertexLabelStyle -> Directive[Black,17.5], 
EdgeLabelStyle -> Directive[Black,17.5,Bold], VertexStyle -> {1 -> RGBColor["lightpink"],2 -> LightCyan,3 -> LightGreen,4 -> RGBColor["beige"],5 -> RGBColor["gold"]}, 
DirectedEdges -> True, EdgeStyle -> {{Black,Thickness[0.005]}}]
g2 = AdjacencyGraph[{{0,0,0,0,0},{1,0,0,0,0},{0,1,0,0,0},{1,1,1,0,0},{0,0,1,1,0}}, ImageSize -> 88]
IsomorphicGraphQ[g1, g2]

Limitación al aplicar fuerza bruta para saber si dos grafos son isomórficos

El grafo de la Figura tiene 20 nodos. A partir de ese hemos obtenido la permutación 14, 6, 8, 4, 12, 7, 11, 10, 9, 18, 19, 15, 17, 5, 2, 3, 0, 13, 1, 16 con la operación operatePermuteGraph(), obteniéndose otra matriz de adyacencia distinta, con lo que ambos son isomorfos. Hemos ajustado visualmente el segundo grafo a rejilla, algo que no interviene en la ejecución para saber si son isomórficos.

Ejecutando isGraphIsomorfic() con el método de fuerza bruta con todas las permutaciones en orden, el algoritmo devuelve falso pero advirtiendo que no puede revisar más de 9! = 362880 permutaciones, por lo que ese resultado es incierto. De hecho ni siquiera pudo revisar las 362880 primeras permutaciones en 1373 milisegundos, pues el control de iteraciones máximas que por defecto se establece en 10000 fueron insuficientes.

Time: 1373 ms

Es el grafo isomórfico: [false,
"No permutation was found in the 20! = 2432902008176640000 that shows they are isomorphic.
Since n>9 the number of permutations is limited to 9! = 362880 so the result of being
false is uncertain.
Maximum iterations '10000' reached before finishing 362880 permutations"]

Ampliando el máximo de iteraciones a 400000 para que revise el máximo de 362880 permutaciones tampoco consigue nada en más de 45 segundos de ejecución, como era de esperar.

Time: 45464 ms

Es el grafo isomórfico: [false,
"No permutation was found in the 20! = 2432902008176640000 that shows they are isomorphic.
Since n>9 the number of permutations is limited to 9! = 362880 so the result of being
false is uncertain."]

Una simple operación como dividir 362880 ÷ 45 = 8064 perm/seg obtenemos el ratio de cuántas permutaciones se revisan por segundo. Así que para revisarlas todas, suponiendo que la que estamos buscando está al final, necesitaremos 2.43×10¹⁸ ÷ 8064 ≈ 3.01×10¹⁴ seg que viene a ser más de 9.55 millones de años.

Sin embargo con el algoritmo de McKay con las opciones por defecto que veíamos en la Figura solo necesitaremos 6 ms o menos para ver que son isomorfos.

Time: 6 ms

Es el grafo isomórfico: [true,
"Canonical graphs are the same: 0,17,0,18,0,19,1,6,1,9,1,16,2,3,2,9,2,15,3,7,3,11,4,5,4,7,4,12,5,8,5,13,6,8,6,14,7,10,8,10,9,10,11,12,11,18,12,17,13,14,13,17,14,19,15,16,15,18,16,19"]

Con este JSON podrá importar el ejemplo.

{"nodes":[
    {"index":0,"nodeOffset":"22.54 57.27","parent":[-1,1,14]},
    {"index":1,"nodeOffset":"44.52 -43.2","parent":[3,6]},
    {"index":2,"nodeOffset":"17.4 48.75","parent":[0,12]},
    {"index":3,"nodeOffset":"83.9 -1.06","parent":[4,8]},
    {"index":4,"nodeOffset":"32.7 36.8","parent":[2,10]},
    {"index":5,"nodeOffset":"71.71 -176.86","parent":[6,15]},
    {"index":6,"nodeOffset":"86.62 -162.22","parent":7},
    {"index":7,"nodeOffset":"100.97 -144.59","parent":[8,16]},
    {"index":8,"nodeOffset":"81.92 -115.15","parent":9},
    {"index":9,"nodeOffset":"62.27 -87.71","parent":[10,17]},
    {"index":10,"nodeOffset":"26.75 -88.91","parent":11},
    {"index":11,"nodeOffset":"-8.56 -88.44","parent":[12,18]},
    {"index":12,"nodeOffset":"-26.56 -117.68","parent":13},
    {"index":13,"nodeOffset":"-44.32 -145.05","parent":[14,19]},
    {"index":14,"nodeOffset":"-32.12 -161.29","parent":5},
    {"index":15,"nodeOffset":"52.8 -75.39","parent":16},
    {"index":16,"nodeOffset":"110.07 -22.57","parent":17},
    {"index":17,"nodeOffset":"64.51 58.23","parent":18},
    {"index":18,"nodeOffset":"-29.03 58.18","parent":19},
    {"index":19,"nodeOffset":"-70.45 -27.13","parent":15}
],
"config":{
    "lineHeight":18.75,
    "algorithm":"Is graph isomorphic",
    "adjacencyMatrix":"0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0\n0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0\n0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0\n0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0\n0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0\n0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1\n0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0\n0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0\n0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0\n0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0\n0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1\n0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1\n1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0\n0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0\n0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0\n1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0\n1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0\n0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0\n0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0"
}}

Matriz adyacencia grafo inicial:

0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0
0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0
0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0
0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1
1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0

Este JSON es el del grafo permutado.

{"nodes":[
    {"index":0,"nodeOffset":"2.08 6.25","parent":-1},
    {"index":1,"nodeOffset":"4.17 6.25","parent":-1},
    {"index":2,"nodeOffset":"6.25 6.25","parent":-1},
    {"index":3,"nodeOffset":"8.33 6.25","parent":-1},
    {"index":4,"nodeOffset":"10.42 6.25","parent":-1},
    {"index":5,"nodeOffset":"9.66","parent":[1,2]},
    {"index":6,"nodeOffset":"19.32","parent":4},
    {"index":7,"nodeOffset":"28.98","parent":[3,6]},
    {"index":8,"nodeOffset":"38.64","parent":[2,7]},
    {"index":9,"nodeOffset":"68.75 -25","parent":6},
    {"index":10,"nodeOffset":"-31.25 -31.25","parent":9},
    {"index":11,"nodeOffset":"-12.5 -56.25","parent":10},
    {"index":12,"nodeOffset":"6.25 -6.25","parent":[8,9]},
    {"index":13,"nodeOffset":"29.55 18.75","parent":[0,1,11]},
    {"index":14,"nodeOffset":"39.2 18.75","parent":[3,4]},
    {"index":15,"nodeOffset":"-44.89 37.5","parent":[2,3]},
    {"index":16,"nodeOffset":"-35.23 37.5","parent":[0,14]},
    {"index":17,"nodeOffset":"-25.57 37.5","parent":[0,4,10]},
    {"index":18,"nodeOffset":"-15.91 37.5","parent":[1,15,16]},
    {"index":19,"nodeOffset":"18.75 12.5","parent":[5,11,12]}
],
"config":{}}

Matriz adyacencia grafo permutado:

0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0
0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0
0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1
1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0
1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0

Es el grafo isomórfico `isGraphIsomorphic()`

El código JavaScript para ejecutar el algoritmo isGraphIsomorphic() se expone a continuación. Hemos quitado el código que implementa el algoritmo de McKay que explicaremos en el siguiente tema y los trozos check invariants y brute force las exponemos más abajo.

function isGraphIsomorphic({matrix=[], matrix2=[], methodIsomorphic="Brute force all perms in order",
    initialPermutation=[], // argument for permutations, the rest are arguments for McKay
    useRefine=true, orderRefine="neighbors-desc-length-desc", typeCanon="edges",
    targetCell="max-length-first", useMcr=true, useMcrPlus=false, useMcrBreak=false,
    typeIndicator="none", canonical1=null, canonical2=null) {
    let result = [false, ""], temp;
    try {
        if (!verifyMode01(matrix)) throw new Error(`(isGraphIsomorphic) Matrix must come in mode 0/1`);
        if (!verifyMode01(matrix2)) throw new Error(`(isGraphIsomorphic) Matrix2 must come in mode 0/1`);
        let n = matrix.length;
        let m = matrix2.length;
        let str = JSON.stringify(matrix);
        let str2 = JSON.stringify(matrix2);
        if (str===str2) {
            result = [true, "Both adjacency matrices are equal"];
        } else {
            // CHECK INVARIANTS (See below)
            if (result[1]==="") {
                if (methodIsomorphic==="McKay") {
                    // MCKAY (see next webpage)
                } else { //Brute force
                    // BRUTE FORCE (See below)
                }
            }
        }
    } catch(e){result = e.message}
    return result;
}

Recibimos las dos matrices de adyacencia en los argumentos matrix y matrix2. Lo primero que hacemos es verificar que ambas vienen en modo valores"0/1", para lo cual usamos esta función:

function verifyMode01(matrix=[]){
    let nums = [...new Set(matrix.flat())].join("");
    return nums==="0"||nums==="1"||nums==="01"||nums==="10";
}

Así que para comprobar isomorfismos no permitimos otros modos de valores como "0/number" para grafos ponderados o "null/value" para etiquetas alfa-numéricas o "false/true" para booleanos, pues complicarán más el algoritmo (ver más sobre modo valores en la matriz de adyacencia).

La primera comprobación es ver si las dos matrices de adyacencia son iguales, lo que hacemos con JSON.stringify(). En caso de ser iguales no hay nada más que hacer, pues claramente una matriz es la permutación identidad de la otra y, por tanto, son isomorfos.

En otro caso realizamos unas comprobaciones preliminares que consiste en chequear algunos invariantes de un isomorfismo, pues en dos grafos isomorfos deben cumplirse lo siguiente:

Tienen el mismo total de vértices, que comprobamos simplemente contando la longitudes de las matrices matrix y matrix2.
Tienen el mismo total de aristas para lo cual usamos getTotalEdges() que cuenta las arista de ambos grafos.
Son dirigidos o no dirigidos lo que hacemos con isGraphDirected()
Tienen los mismos grados de vértices con getVertexDegrees()
Tienen el mismo total de componentes conectados con getConnectedComponents()

Cuando alguno de estos invariantes es distinto nos permite asegurar que los grafos no son isomorfos. Pero si son iguales, aún todos los anteriores, no es suficiente para asegurar que sean isomorfos. Podrían comprobarse otros invariantes, como número de ciclos de una longitud dada y cliques u otros subgrafos de cierto tamaño, entre otros. Pero estos suelen ser más costosos de obtener.

// CHECK INVARIANTS
if (result[1]==="" && m!==n) {
    result[1] = `The graphs do not have the same number of vertices: ${n} ≠ ${m}`;
}
if (result[1]==="") {
    let e1 = getTotalEdges({matrix});
    let e2 = getTotalEdges({matrix: matrix2});
    if (e1!==e2) {
        result[1] = `The graphs do not have the same number of edges: ${e1} ≠ ${e2}`;
    }
}
if (result[1]==="") {
    let dir1 = isGraphDirected({matrix});
    if (typeof dir1==="string") throw new Error(directed);
    let dir2 = isGraphDirected({matrix:matrix2});
    if (typeof dir1==="string") throw new Error(directed);
    if (dir1!==dir2)  {
        result[1] = `The graphs do not have the same direction`;
    }
}
if (result[1]==="") {
    let d1 = getVertexDegrees({matrix}).toSorted((v, w) => v-w).join(",");
    let d2 = getVertexDegrees({matrix: matrix2}).toSorted((v, w) => v-w).join(",");
    if (d1!==d2)  {
        result[1] = `The graphs do not have the same degree of vertices: ${d1} ≠ ${d2}`;
    }
}
if (result[1]==="") {
    let temp = getConnectedComponents({matrix, forceUndirected:true});
    if (typeof temp==="string") throw new Error(temp);
    let c1 = temp.length;
    temp = getConnectedComponents({matrix: matrix2, forceUndirected:true});
    if (typeof temp==="string") throw new Error(temp);
    let c2 = temp.length;
    if (c1!==c2) {
        result[1] = `The graphs do not have the same number of connected components: ${c1} ≠ ${c2}`;
    }
}

Tal como vemos en la web Graph Theory, Part III, los dos grafos de la Figura no son isomórficos, a pesar de cumplir todos los invariantes anteriores, incluso el total de grados, pues ambos tienen 4 vértices de grado 2 y otros 4 de grado 3. Como hay 8! = 40320 permutaciones (recuerde que la aplicación limita hasta 9! = 362880), con 50000 iteraciones el algoritmo los puede comprobar todos, verificando en 578 ms con total seguridad que ninguna permutación del primer grafo da como resultado el segundo. Se obtiene este resultado:

Time: 578 ms

Es el grafo isomórfico: [false,
"No permutation was found in the 8! = 40320 
that shows they are isomorphic"]

Se podrían usar como invariantes los ciclos que podríamos obtener con getCyclesAll(), pues ambos tienen 6 ciclos, pero el primero tiene 2 de tamaño 4 y 4 de tamaño 6, mientras que el segundo grafo también tiene 6 ciclos pero con otros tamaños, como se observa a continuación a partir de los resultados de ese algoritmo getCyclesAll(), con lo que podría deducirse que no son isomórficos, pues en otro caso sería una condición necesaria (aunque no suficiente) que ambos tuvieran el mismo número de ciclos y los mismos tamaños.

Tamaño de ciclos
Primer grafo:
  4           4           6               6               6               6
[[0,1,3,2,0],[4,5,7,6,4],[0,1,3,7,5,4,0],[0,1,3,7,6,4,0],[0,2,3,7,5,4,0],[0,2,3,7,6,4,0]]
Segundo grafo:
  4           4           3           6               6               8
[[0,1,3,2,0],[2,3,7,6,2],[4,5,7,6,4],[0,1,3,7,6,2,0],[2,3,7,5,4,6,2],[0,1,3,7,5,4,6,2,0]]

Con estos JSON puede importar los grafos anteriores.

{"nodes":[
    {"index":0,"nodeOffset":"2.5","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":"67.5 15","parent":[{"index":0}]},
    {"index":2,"nodeOffset":"-37.5 15","parent":[{"index":0}]},
    {"index":3,"nodeOffset":"27.5 30","parent":[{"index":2},{"index":1}]},
    {"index":4,"nodeOffset":"-22.5 -5","parent":[{"index":0}]},
    {"index":5,"nodeOffset":"22.5 -10","parent":[{"index":4}]},
    {"index":6,"nodeOffset":"-42.5 -10","parent":[{"index":4}]},
    {"index":7,"nodeOffset":"2.5 -15","parent":[{"index":5},{"index":6},{"index":3}]}
],
"config":{
    "algorithm":"Is graph isomorphic",
    "maxIter":50000,
    "adjacencyMatrix":"0 1 1 0 0 0 0 0\n1 0 0 1 0 0 0 0\n1 0 0 1 0 0 1 0\n0 1 1 0 0 0 0 1\n0 0 0 0 0 1 1 0\n0 0 0 0 1 0 0 1\n0 0 1 0 1 0 0 1\n0 0 0 1 0 1 1 0"
}}

{"nodes":[
    {"index":0,"nodeOffset":"19.17","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":"72.5 15","parent":[{"index":0}]},
    {"index":2,"nodeOffset":"-27.5 15","parent":[{"index":0}]},
    {"index":3,"nodeOffset":"19.17 30","parent":[{"index":2},{"index":1}]},
    {"index":4,"nodeOffset":"-14.17 20","parent":[{"index":-1}]},
    {"index":5,"nodeOffset":"12.5 15","parent":[{"index":4}]},
    {"index":6,"nodeOffset":"-47.5 15","parent":[{"index":4},{"index":2}]},
    {"index":7,"nodeOffset":"-14.17 10","parent":[{"index":5},{"index":6},{"index":3}]}
],
"config":{}}

Time: 1 ms

Es el grafo isomórfico: [false,
"Canonical graph
0,6,0,7,1,4,1,5,2,4,2,5,3,6,3,7,4,7,5,6
is not the same as
0,3,0,7,1,2,1,5,2,4,3,6,4,5,4,6,5,7,6,7"]

Aunque no estamos ahora explicando el algoritmo de McKay, sólo por curiosidad mostramos que con McKay sólo tarda 1 ms en comprobar que no son isomórficos, pues el grafo canónico que se obtiene no es el mismo en ambos casos. Esto lo explicaremos en temas siguientes.

Veamos ahora la parte del código que comprueba por fuerza bruta si existe alguna permutación cuya matriz de adyacencia resultante sea igual que la del segundo grafo.

// BRUTE FORCE
let useInitialPermutation = methodIsomorphic==="Brute force all with initial perm";
let useRandomPermutations = methodIsomorphic==="Brute force random perms";
let indexes = Array.from({length:n}, (v,i) => i);
let totalPermutations = factorial(n);
if (useRandomPermutations) {
    let permutations = new Set();
    let list = [...indexes];
    permutations.add(list.join(","));
    while (iter++, iter<=maxIter && !result[0] && permutations.size<totalPermutations) {
        let temp = operatePermuteGraph({matrix, indexes: list});
        if (temp.error) throw new Error(temp.error);
        let submatrix = temp.matrix;
        result[0] = JSON.stringify(submatrix)===str2;
        if (!result[0]) {
            let listJoin = "";
            do {
                if (iter++, iter>maxIter) break;
                list = permuteRandom(indexes);
                listJoin = list.join(",");
            } while (permutations.has(listJoin));
            if (listJoin!=="") permutations.add(listJoin);
        }
    }
    if (result[0]){
        result[1] = `Found a match in iteration ${iter} with the random permutation ${list.join(",")}`
    } else {
        if (iter>maxIter) {
            result[1] = `The maximum number of iterations ${maxIter} was reached without being able to ensure that they are isomorphic (permutations ${permutations.size} of ${totalPermutations})`;
        } else if (permutations.size===totalPermutations) {
            result[1] = `The maximum number of permutations ${totalPermutations} was reached and we can assure that they are not isomorphic (iterations ${iter} of ${maxIter})`;
        }
    }
} else {
    let msg = "";
    if (n>nMaxPermutations) msg = `Since n>${nMaxPermutations} the number of permutations is limited to ${nMaxPermutations}! = ${maxPermutations} so ` +
            `the result of being false is uncertain`;
    if (useInitialPermutation) {
        if (initialPermutation.length>0) {
            indexes = initialPermutation;
            msg += ` (Initial permutation given ${initialPermutation.join(",")})`;
        } else {
            indexes = permuteRandom(indexes);
            msg += ` (Random initial permutation ${indexes.join(",")})`;
        }
    }
    let lists = permute(indexes);
    let list = [];
    let i = -1;
    for (i=0; i<lists.length; i++) {
        iter++;
        if (iter>maxIter) {
            msg += `. Maximum iterations '${maxIter}' reached before finishing ${lists.length} permutations`;
            break;
        }
        list = lists[i];
        let temp = operatePermuteGraph({matrix, indexes: list});
        if (temp.error) throw new Error(temp.error);
        if (JSON.stringify(temp.matrix)===str2) {
            result[0] = true;
            break;
        }
    }
    if (result[0]) {
        result[1] = `Found a match in permutation ${i+1} (${list.join(",")}) out of a total of ${n}! = ${totalPermutations}`;
    } else {
        result[1] = `No permutation was found in the ${n}! = ${totalPermutations} that shows they are isomorphic`;
    }
    if (msg!=="") result[1] += `. ${msg}`;
}

El algoritmo dispone de la variable resultado result = [false, ""] donde la primera posición del array nos dice si son isomórficos y la segunda nos dará una frase con comentarios.

Encontramos la primera parte que usa permutaciones aleatorias. Para ello usamos el conjunto de JavaScript Set en la variable permutations donde iremos almacenando las permutaciones aleatorias obtenidas, con objeto de desechar aquellas que previamente ya hubiésemos chequeado. Al inicio probamos con la permutación identidad que tenemos en indexes y que es la lista de nodos [0, 1, 2, ..., n-1]. Permutamos el primer grafo con la operación operatePermuteGraph(), comprobando que la matriz de adyacencia y la inicial sean iguales, en cuyo caso hemos encontrado un isomorfimo y finalizamos.

En otro caso obtenemos una permutación aleatoria usando la función auxiliar permuteRandom() que implementa el algoritmo de Fisher-Yates, buscando la siguiente que previamente no hubiésemos ya procesado y que hemos venido guardando en permutations.

// https://en.wikipedia.org/wiki/Random_permutation#Fisher-Yates_shuffles
function permuteRandom(list=[]) {
    let result = [...list];
    let n = list.length;
    if (n>1) {
        for (let i=0; i<n-1; i++) {
            let j = Math.floor(i + Math.random() * (n-i));
            [result[i], result[j]] = [result[j], result[i]];
        }
    }
    return result;
}

En caso de usar permutaciones en orden, no aleatorias, usamos la función auxiliar permute() que implementa el algoritmo de las permutaciones de Heap que ya habíamos visto en la serie de temas sobre combinatoria. Esta función finaliza cuando haya generado el máximo de permutaciones que permitimos en la aplicación y que declaramos en la constante global maxPermutations = 362880 que es el resultado de 9!

const nMaxPermutations = 9;
const maxPermutations= 362880;

// https://www.wextensible.com/temas/combinatoria/permutaciones-heap.html
function permute(list=[], n=list.length, result=[]){
    if (result.length<maxPermutations) {
        if (n<=1) {
            result.push([...list]);
        } else {
            for (let j=n-1; j>-1; j--){
                [list[j], list[n-1]] = [list[n-1], list[j]];
                permute(list, n-1, result);
                [list[j], list[n-1]] = [list[n-1], list[j]];
            }
        }
    }
    return result;
}

Como lista de entrada a la función anterior podemos usar los naturales de la matriz del grafo inicial [0,1, 2, ..., n-1] o la que se pase como permutación inicial para fuerza bruta. El resto es bien simple, pues se trata de iterar por todas esas permutaciones en orden obtenidas y permutar el grafo con operatePermuteGraph(), comprobando que la matriz de adyacencia y la inicial sean iguales, en cuyo caso hemos encontrado un isomorfimo y finalizamos. O en otro caso habremos de recorrerlas todas (limitadas a 362880 como comentamos antes) si no son isomórficos.

Es el subgrafo isomórfico `isSubgraphIsomorphic()`

Otra cosa que podemos hacer con isomorfismos es comprobar si un grafo es isomorfo a algún subgrafo inducido de otro. En la Figura comprobamos si el grafo de la derecha es isomorfo a algún subgrafo inducido de la izquierda, lo cual resulta cierto.

El algoritmo isSubGraphIsomorphic() que veremos despúes usa exclusivamente el método del algoritmo de McKay que se expondrá en temas siguientes, aunque también podría usar los métodos de permutaciones que hemos visto en apartados anteriores, pero poco interés tendría en tanto que no tiene valor práctico, como ya hemos comentado. Aún con la mejora de McKay, ese algoritmo isSubGraphIsomorphic() usa las combinaciones, lo que le confiere un caracter exponencial que ya hemos visto en un tema anterior al tratar con cliques, limitando el número máximo de nodos que podemos tener en un grafo.

Existen algoritmos que resuelven el problema de isomorfismo de subgrafos, como el algoritmo de Ullmann que aún no he estudiado. Tiene en general un coste exponencial, así que en cualquier caso parece díficil librarse del caracter exponencial para este problema.

Time: 1 ms
Es el subgrafo isomórfico: {
"isomorphic":true,
"indexes":[0,1,2,3,5],
"submatrix":
[[0,0,1,1,1],
[0,0,0,1,1],
[1,0,0,0,1],
[1,1,0,0,1],
[1,1,1,1,0]]}

Vemos que el algoritmo isSubGraphIsomorphic() encontró que el subgrafo inducido por los nodos [0,1,2,3,5] en el primer grafo es isomorfo al segundo grafo.

{"nodes":[
    {"index":0,"nodeOffset":"23.97 24.36","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":"-55.28 0.65","parent":[{"index":-1}]},
    {"index":2,"nodeOffset":"45.24 29.42","parent":[{"index":0}]},
    {"index":3,"nodeOffset":"6.46 -13.77","parent":[{"index":0},{"index":1}]},
    {"index":4,"nodeOffset":"-28.64 29.42","parent":[{"index":0},{"index":1},{"index":2}]},
    {"index":5,"nodeOffset":"3.42 -24.49","parent":[{"index":0},{"index":1},{"index":2},{"index":3}]},
    {"index":6,"nodeOffset":"-58.77 -0.78","parent":[{"index":0},{"index":1},{"index":2},{"index":3},{"index":4}]}
],
"config":{
    "algorithm":"Is subgraph isomorphic",
    "adjacencyMatrix":"0 1 1 0 0\n1 0 1 1 1\n1 1 0 0 1\n0 1 0 0 1\n0 1 1 1 0"
}}

{"nodes":[
    {"index":0,"parent":[{"index":-1}]},
    {"index":1,"parent":[{"index":0}]},
    {"index":2,"parent":[{"index":0},{"index":1}]},
    {"index":3,"parent":[{"index":1,"lineTextOffset":"-0.75 0.25"},{"index":4}]},
    {"index":4,"parent":[{"index":1},{"index":2}]}
],
"config":{}}

0 1 1 0 0
1 0 1 1 1
1 1 0 0 1
0 1 0 0 1
0 1 1 1 0

En la Figura vemos como Wolfram comprueba que el subgrafo g2 es isomórfico a algún subgrafo de g1, que se consigue con IsomorphicSubgraphQ[g1, g2].

Como veremos después al ver getIsomorphicSubgraphs(), Wolfram considera todos los subgrafos mientras que nosotros solo consideramos los subgrafos inducidos.

g2 = AdjacencyGraph[{{0,0,1,1,1,1,1},{0,0,0,1,1,1,1},{1,0,0,0,1,1,1},{1,1,0,0,0,1,1},{1,1,1,0,0,0,1},{1,1,1,1,0,0,0},{1,1,1,1,1,0,0}}, ImageSize -> 200, 
VertexSize -> {"Scaled", 0.16}, 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]}, VertexLabelStyle -> Directive[Black,17.5], EdgeLabelStyle -> Directive[Black,17.5,Bold], 
VertexStyle -> White, EdgeStyle -> {{Black,Thickness[0.005]}}]
g1 = AdjacencyGraph[{{0,1,1,0,0},{1,0,1,1,1},{1,1,0,0,1},{0,1,0,0,1},{0,1,1,1,0}}, ImageSize -> 200]
IsomorphicSubgraphQ[g1,g2]

A continuación vemos el JavaScript que implementa isSubgraphIsomorphic() usando getInducedSubgraph() para obtener los subgrafos inducidos por cada permutación y isGraphIsomorphic() que vimos en el apartado anterior para comprobrar si dos grafos son isomórficos.

Aunque veremos el algoritmo de McKay en temas siguientes, por ahora explicamos que se basa en obtener un etiquetado canónico en cada grafo y observar si son iguales, en cuyo caso serán isomorfos. Así en este algoritmo obtenemos canonical1 como el etiquetado para el subgrafo, valor que pasamos al algoritmo isGraphIsomorphic() evitando tener que estar obteniéndolo con cada comparación.

function isSubgraphIsomorphic({matrix=[], submatrix=[]}) {
    let result = {isomorphic: false, indexes: [], submatrix: []}, temp;
    try {
        let n = matrix.length;
        let m = submatrix.length;
        if (m>0) {
            let indexes = Array.from({length:n}, (v,i) => i);
            let lists = combine(indexes, m);
            if (typeof lists==="string") throw new Error(lists);
            if (lists.hasOwnProperty("warning")) result.warnings = [lists.warning + ` (checking with ${lists.length} combinations of a total ${binomial(n, m)})`];
            iter = 0;
            temp = getPartitionTree({matrix:submatrix});
            if (typeof temp==="string") throw new Error(temp);
            if (temp.canonicalLabel===null) throw new Error(`Canonical label of submatrix is null`);
            let canonical1 = temp.canonicalLabel;
            for (let list of lists) {
                if (temp = getInducedSubgraph({matrix, indexesSubgraph:list}), typeof temp==="string") throw new Error(temp);
                let submatrix2 = temp;
                if (temp = isGraphIsomorphic({matrix:submatrix, matrix2:submatrix2, methodIsomorphic:"McKay", canonical1}), typeof temp==="string") throw new Error(temp);
                if (temp[0]) {
                    result.isomorphic = true;
                    result.indexes = list;
                    result.submatrix = submatrix2;
                    break;
                }
            }
        }
    } catch(e){result = e.message}
    return result;
}

El algoritmo para combinar los nodos es el que expusimos en el tema Combinaciones sin repetición: algoritmo mejorado, controlando cuando lleguemos a un máximo de iteraciones para devolver los resultados hasta el momento y un aviso al respecto.

// https://www.wextensible.com/temas/combinatoria/combinaciones-2.html
function combine(list=[], k=0, n=list.length, res=Array.from({length:k}, ()=>""), 
result=[], n0=list.length, k0=res.length){
    try {
        if (iter++, iter>maxIter) {
            result.warning = `Maximum iterations '${maxIter}' reached in combine() with n='${n0}' and k='${k0}'`;
            return result;
        }
        if (k===0){
            result.push([...res]);
        } else {
            for (let j=n; j>=k; j--){
                res[k0-k] = list[n0-j];
                combine(list, k-1, j-1, res, result);
            }
        }
    } catch(e) {result = e.message}
    return result;
}

En la Figura vemos un grafo completo con 40 nodos y otro con 20 nodos, ejecutando isSubgraphIsomorphic() para saber si hay algún subgrafo en el primero que sea isomorfo con el segudo. Obviamente en todo grafo completo cualquier otro grafo con los mismos o menos nodos será isomorfo, pues un grafo completo tiene aristas entre todos los nodos. Pero este ejemplo nos servirá para observar el comportamiento con grafos grandes, pues el algoritmo debe obtener las combinaciones de nodos que en total serán C(40, 20) ≈ 1.38 × 10¹¹, pero que se limitará a obtener las que pueda computar en el máximo de iteraciones que por defecto se establece en 10000.

Así la aplicación devuelve el mensaje Maximum iterations '10000' reached in combine() with n='40' and k='20' (Checking with 8585 combinations of a total 137846528820), con lo que sólo generó 8585 combinaciones de 20 nodos que serán sobre las que obtendrá los subgrafos inducidos para comprobar sin alguno es isomorfo. Obviamente el primero que encuentre ya es isomorfo y no necesita revisar más, así que la ejecución sólo toma 8 ms.

Time: 8 ms

Es el subgrafo isomórfico: {
"isomorphic":true,
"indexes":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19],
"submatrix":[[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0]],
"warnings":["Maximum iterations '10000' reached in combine() with n='40' and k='20' 
(checking with 8585 combinations of a total 137846528820)"]}

{"nodes":[
    {"index":0,"nodeOffset":"2.5","parent":-1},
    {"index":1,"nodeOffset":"56.26 -24.51","parent":0},
    {"index":2,"nodeOffset":"59.86 -23.04","parent":[0,1]},
    {"index":3,"nodeOffset":"63.16 -20.64","parent":[0,1,2]},
    {"index":4,"nodeOffset":"66.01 -17.36","parent":[0,1,2,3]},
    {"index":5,"nodeOffset":"68.28 -13.28","parent":[0,1,2,3,4]},
    {"index":6,"nodeOffset":"69.86 -8.51","parent":[0,1,2,3,4,5]},
    {"index":7,"nodeOffset":"70.64 -3.16","parent":[0,1,2,3,4,5,6]},
    {"index":8,"nodeOffset":"70.54 2.64","parent":[0,1,2,3,4,5,6,7]},
    {"index":9,"nodeOffset":"69.51 8.74","parent":[0,1,2,3,4,5,6,7,8]},
    {"index":10,"nodeOffset":"67.5 15","parent":[0,1,2,3,4,5,6,7,8,9]},
    {"index":11,"nodeOffset":"64.51 21.26","parent":[0,1,2,3,4,5,6,7,8,9,10]},
    {"index":12,"nodeOffset":"60.54 27.36","parent":[0,1,2,3,4,5,6,7,8,9,10,11]},
    {"index":13,"nodeOffset":"55.64 33.16","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12]},
    {"index":14,"nodeOffset":"49.86 38.51","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13]},
    {"index":15,"nodeOffset":"43.28 43.28","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]},
    {"index":16,"nodeOffset":"36.01 47.36","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]},
    {"index":17,"nodeOffset":"28.16 50.64","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]},
    {"index":18,"nodeOffset":"19.86 53.04","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17]},
    {"index":19,"nodeOffset":"11.26 54.51","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]},
    {"index":20,"nodeOffset":"2.5 55","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19]},
    {"index":21,"nodeOffset":"-6.26 54.51","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]},
    {"index":22,"nodeOffset":"-14.86 53.04","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21]},
    {"index":23,"nodeOffset":"-23.16 50.64","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22]},
    {"index":24,"nodeOffset":"-31.01 47.36","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23]},
    {"index":25,"nodeOffset":"-38.28 43.28","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24]},
    {"index":26,"nodeOffset":"-44.86 38.51","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25]},
    {"index":27,"nodeOffset":"-50.64 33.16","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26]},
    {"index":28,"nodeOffset":"-55.54 27.36","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27]},
    {"index":29,"nodeOffset":"-59.51 21.26","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28]},
    {"index":30,"nodeOffset":"-62.5 15","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29]},
    {"index":31,"nodeOffset":"-64.51 8.74","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]},
    {"index":32,"nodeOffset":"-65.54 2.64","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31]},
    {"index":33,"nodeOffset":"-65.64 -3.16","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32]},
    {"index":34,"nodeOffset":"-64.86 -8.51","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33]},
    {"index":35,"nodeOffset":"-63.28 -13.28","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34]},
    {"index":36,"nodeOffset":"-61.01 -17.36","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35]},
    {"index":37,"nodeOffset":"-58.16 -20.64","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36]},
    {"index":38,"nodeOffset":"-54.86 -23.04","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37]},
    {"index":39,"nodeOffset":"-51.26 -24.51","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38]}
],
"config":{
    "nodeValueAuto":"none",
    "nodeRadius":2,
    "lineColor":"darkgray",
    "algorithm":"Is subgraph isomorphic",
    "adjacencyMatrix":"0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\n1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\n1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\n1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\n1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\n1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1\n1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1\n1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1\n1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1\n1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1\n1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1\n1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1\n1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1\n1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1\n1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1\n1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1\n1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1\n1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1\n1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1\n1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0"
}}

{"nodes":[
    {"index":0,"nodeOffset":"2.5","parent":-1},
    {"index":1,"nodeOffset":"59.86 -23.04","parent":0},
    {"index":2,"nodeOffset":"66.01 -17.36","parent":[0,1]},
    {"index":3,"nodeOffset":"69.86 -8.51","parent":[0,1,2]},
    {"index":4,"nodeOffset":"70.54 2.64","parent":[0,1,2,3]},
    {"index":5,"nodeOffset":"67.5 15","parent":[0,1,2,3,4]},
    {"index":6,"nodeOffset":"60.54 27.36","parent":[0,1,2,3,4,5]},
    {"index":7,"nodeOffset":"49.86 38.51","parent":[0,1,2,3,4,5,6]},
    {"index":8,"nodeOffset":"36.01 47.36","parent":[0,1,2,3,4,5,6,7]},
    {"index":9,"nodeOffset":"19.86 53.04","parent":[0,1,2,3,4,5,6,7,8]},
    {"index":10,"nodeOffset":"2.5 55","parent":[0,1,2,3,4,5,6,7,8,9]},
    {"index":11,"nodeOffset":"-14.86 53.04","parent":[0,1,2,3,4,5,6,7,8,9,10]},
    {"index":12,"nodeOffset":"-31.01 47.36","parent":[0,1,2,3,4,5,6,7,8,9,10,11]},
    {"index":13,"nodeOffset":"-44.86 38.51","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12]},
    {"index":14,"nodeOffset":"-55.54 27.36","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13]},
    {"index":15,"nodeOffset":"-62.5 15","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]},
    {"index":16,"nodeOffset":"-65.54 2.64","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]},
    {"index":17,"nodeOffset":"-64.86 -8.51","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]},
    {"index":18,"nodeOffset":"-61.01 -17.36","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17]},
    {"index":19,"nodeOffset":"-54.86 -23.04","parent":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]}
],
"config":{
    "nodeValueAuto":"none",
    "nodeRadius":2,
    "lineColor":"darkgray"
}}

En la Figura vemos a la izquierda un grafo con 16 nodos y otro a la derecha con 8 nodos para comprobar que en el primero no hay ningún subgrafo inducido que sea isomórfico al segundo. Con 10000 iteraciones obtenemos el aviso Maximum iterations '10000' reached in combine() with n='16' and k='8' (Checking with 5806 combinations of a total 12870), con lo que sólo pudo comprobar en 5806 combinaciones de 12870, no encontrando hasta ese momento ningún subgrafo isomórfico. Se obtiene este resultado.

Es el subgrafo isomórfico: {
"isomorphic":false,
"indexes":[],
"submatrix":[],
"warnings":["Maximum iterations '10000' reached in combine() with n='16' and k='8' 
(checking with 5806 combinations of a total 12870)"]}

Por lo tanto aunque el resultado es falso, como no hemos podido comprobar todas las combinaciones no podemos asegurar que haya alguno. Si incrementamos las iteraciones hasta 30000 veremos que devuelve falso sin ningún aviso, con este resultado Es el subgrafo isomórfico: {"isomorphic":false,"indexes":[],"submatrix":[]}, con lo que ya podemos asegurar que no hay ningún subgrafo inducido isomorfo.

{"nodes":[
    {"index":0,"nodeOffset":"16.13 23.42","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":"22.12 9.71","parent":[{"index":0}]},
    {"index":2,"nodeOffset":"24.74 15.64","parent":[{"index":0}]},
    {"index":3,"nodeOffset":"24.19 3.06","parent":[{"index":1}]},
    {"index":4,"nodeOffset":"17.63 5.31","parent":[{"index":2},{"index":3}]},
    {"index":5,"nodeOffset":"24.05 10.55","parent":[{"index":0}]},
    {"index":6,"nodeOffset":"48.51 -8.68","parent":[{"index":4}]},
    {"index":7,"nodeOffset":"66.57 -20.98","parent":[{"index":6},{"index":5}]},
    {"index":8,"nodeOffset":"41.84 -20.65","parent":[{"index":5}]},
    {"index":9,"nodeOffset":"50.17 17.29","parent":[{"index":8}]},
    {"index":10,"nodeOffset":"-8.54 -26.62","parent":[{"index":6}]},
    {"index":11,"nodeOffset":"38.63 -18.04","parent":[{"index":10},{"index":9}]},
    {"index":12,"nodeOffset":"-23.78 -35.53","parent":[{"index":7},{"index":9}]},
    {"index":13,"nodeOffset":"-25.17 -72.95","parent":[{"index":12},{"index":3}]},
    {"index":14,"nodeOffset":"-34.48 -81.02","parent":[{"index":13},{"index":11}]},
    {"index":15,"nodeOffset":"-34.48 -153.72","parent":[{"index":14},{"index":10},{"index":8,"lineType":"quadratic","lineOffset":"0 -11.65"}]}
],
"config":{
    "algorithm":"Is subgraph isomorphic",
    "adjacencyMatrix":"0 1 0 1 0 0 0 0\n1 0 1 0 0 1 0 0\n0 1 0 0 1 0 0 0\n1 0 0 0 0 1 1 0\n0 0 1 0 0 1 0 1\n0 1 0 1 1 0 0 0\n0 0 0 1 0 0 0 1\n0 0 0 0 1 0 1 0"
}}


{"nodes":[
    {"index":0,"parent":[{"index":-1}]},
    {"index":1,"parent":[{"index":0}]},
    {"index":2,"parent":[{"index":1}]},
    {"index":3,"parent":[{"index":0}]},
    {"index":4,"parent":[{"index":2}]},
    {"index":5,"parent":[{"index":3},{"index":4},{"index":1}]},
    {"index":6,"parent":[{"index":3}]},
    {"index":7,"nodeOffset":"25 -25.6","parent":[{"index":4},{"index":6}]}
],
"config":{}}

0 1 0 1 0 0 0 0
1 0 1 0 0 1 0 0
0 1 0 0 1 0 0 0
1 0 0 0 0 1 1 0
0 0 1 0 0 1 0 1
0 1 0 1 1 0 0 0
0 0 0 1 0 0 0 1
0 0 0 0 1 0 1 0

Obtener subgrafos isomórfico `getIsomorphicSubgraphs()`

Para obtener todos los subgrafos inducidos isomórficos hacemos lo mismo que en el apartado anterior, obteniendo de todas las combinaciones de nodos del grafo principal con el número de nodos del subgrafo los correspondiente subgrafos inducidos, para luego comprobar si son isomorfos en cuyo caso devolvemos ese subgrafo.

En la Figura encontramos todos los subgrafos isomorfos al de la Figura, encontrando seis tal como vemos en el siguiente resultado, aunque realmente sólo hay 2 matrices de adyacencia diferentes. También devuelve los índices de nodos del grafo principal de los subgrafos inducidos.

Time: 1 ms
Obtener subgrafos isomórficos: {
"indexes":[[0,1,2,3,5],[0,1,2,3,6],[0,2,3,4,5],[0,3,4,5,6],[1,2,3,4,6],[1,3,4,5,6]],
"submatrix":[
[[0,0,1,1,1],[0,0,0,1,1],[1,0,0,0,1],[1,1,0,0,1],[1,1,1,1,0]],
[[0,0,1,1,1],[0,0,0,1,1],[1,0,0,0,1],[1,1,0,0,1],[1,1,1,1,0]],
[[0,1,1,1,1],[1,0,0,1,1],[1,0,0,0,1],[1,1,0,0,0],[1,1,1,0,0]],
[[0,1,1,1,1],[1,0,0,1,1],[1,0,0,0,1],[1,1,0,0,0],[1,1,1,0,0]],
[[0,0,1,1,1],[0,0,0,1,1],[1,0,0,0,1],[1,1,0,0,1],[1,1,1,1,0]],
[[0,1,1,1,1],[1,0,0,1,1],[1,0,0,0,1],[1,1,0,0,0],[1,1,1,0,0]]],
"totalIsomorphics":6,
"differentSubmatrix":2}

{"nodes":[
    {"index":0,"nodeOffset":"23.97 24.36","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":"-55.28 0.65","parent":[{"index":-1}]},
    {"index":2,"nodeOffset":"45.24 29.42","parent":[{"index":0}]},
    {"index":3,"nodeOffset":"6.46 -13.77","parent":[{"index":0},{"index":1}]},
    {"index":4,"nodeOffset":"-28.64 29.42","parent":[{"index":0},{"index":1},{"index":2}]},
    {"index":5,"nodeOffset":"3.42 -24.49","parent":[{"index":0},{"index":1},{"index":2},{"index":3}]},
    {"index":6,"nodeOffset":"-58.77 -0.78","parent":[{"index":0},{"index":1},{"index":2},{"index":3},{"index":4}]}
],
"config":{
    "algorithm":"Get isomorphic subgraphs",
    "adjacencyMatrix":"0 1 1 0 0\n1 0 1 1 1\n1 1 0 0 1\n0 1 0 0 1\n0 1 1 1 0"
}}

{"nodes":[
    {"index":0,"parent":[{"index":-1}]},
    {"index":1,"parent":[{"index":0}]},
    {"index":2,"parent":[{"index":0},{"index":1}]},
    {"index":3,"parent":[{"index":1,"lineTextOffset":"-0.75 0.25"},{"index":4}]},
    {"index":4,"parent":[{"index":1},{"index":2}]}
],
"config":{}}

0 1 1 0 0
1 0 1 1 1
1 1 0 0 1
0 1 0 0 1
0 1 1 1 0

En la Figura vemos los 30 subgrafos que Wolfram considera isomórficos, pues no sólo considera los inducidos como hacemos en nuestra aplicación, habiendo sólo 6 inducidos tal como obtuvimos. Usa FindIsomorphicSubgraph[g1, g2, All].

g1 = AdjacencyGraph[{{0,0,1,1,1,1,1},{0,0,0,1,1,1,1},{1,0,0,0,1,1,1},{1,1,0,0,0,1,1},{1,1,1,0,0,0,1},{1,1,1,1,0,0,0},{1,1,1,1,1,0,0}}, ImageSize -> 200, VertexSize -> {"Scaled", 0.16}, 
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]}, VertexLabelStyle -> Directive[Black,17.5], EdgeLabelStyle -> Directive[Black,17.5,Bold], VertexStyle -> White, EdgeStyle -> {{Black,Thickness[0.005]}}];
g2 = AdjacencyGraph[{{0,1,1,0,0},{1,0,1,1,1},{1,1,0,0,1},{0,1,0,0,1},{0,1,1,1,0}}];
s = FindIsomorphicSubgraph[g1, g2, All];
Table[HighlightGraph[g1,{Style[VertexList[i], RGBColor["lightpink"]], Style[EdgeList[i], Red, Thick], Annotation[EdgeList[i], EdgeLabelStyle->Directive[Blue,17.5,Bold]]}], {i,s}]

En la Figura vemos ampliado el primer subgrafo de Wolfram no inducido, donde se elimina la arista "0-6" del inducido. Accedemos a este primer subgrafo cambiando las dos últimas líneas del código Wofram anterior con estas:

i = First[FindIsomorphicSubgraph[g1, g2]];
HighlightGraph[g1,{Style[VertexList[i], RGBColor["lightpink"]], Style[EdgeList[i], Red, Thick], Annotation[EdgeList[i], EdgeLabelStyle->Directive[Blue,17,Bold]]}]

Como vimos en el tema de subgrafos, obtener un subgrafo no inducido se basaba en obtener el inducido y eliminar una o más aristas. Como vemos en la Figura, se trata del subgrafo inducido por los nodos 0,1,3,5,6 al que luego eliminamos la arista [0,6], obteniendo el mismo que vemos en la Figura. Como hemos dicho, Wolfram también considera estos subgrafos a efectos de isomorfismos.

{"nodes":[
    {"index":0,"nodeOffset":"23.97 24.36","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":"-55.28 0.65","parent":[{"index":-1}]},
    {"index":2,"nodeOffset":"45.24 29.42","parent":[{"index":0}]},
    {"index":3,"nodeOffset":"6.46 -13.77","parent":[{"index":0},{"index":1}]},
    {"index":4,"nodeOffset":"-28.64 29.42","parent":[{"index":0},{"index":1},{"index":2}]},
    {"index":5,"nodeOffset":"3.42 -24.49","parent":[{"index":0},{"index":1},{"index":2},{"index":3}]},
    {"index":6,"nodeOffset":"-58.77 -0.78","parent":[{"index":0},{"index":1},{"index":2},{"index":3},{"index":4}]}
],
"config":{
    "algorithm":"Get subgraph",
    "indexesSubgraph":"0,1,3,5,6",
    "deleteEdgesSubgraph":"[0,6]"
}}

El décimo subgrafo de la Figura que obtiene Wolfram es un subgrafo inducido y es como el primero que obtuvimos en nuestra aplicación como se observa en la Figura. En el código de Wolfram ponemos i = FindIsomorphicSubgraph [g1, g2, All][[10]] para obtener el décimo subgrafo.

El código JavaScript para ejecutar getIsomorphicSubgraphs() es similar al que vimos en el apartado anterior isSubgraphIsomorphic() para ver si un subgrafo es isomórfico, sólo que allí finalizábamos al encontrar un isomorfismo y aquí seguimos ejecutando hasta encontrarlos todos.

function getIsomorphicSubgraphs({matrix=[], submatrix=[]}) {
    let result = {indexes:[], submatrix:[], totalIsomorphics: 0, differentSubmatrix: 0}, temp;
    try {
        let n = matrix.length;
        let m = submatrix.length;
        let strSubmatrix = [];
        if (m>0) {
            let indexes = Array.from({length:n}, (v,i) => i);
            let lists = combine(indexes, m);
            if (typeof lists==="string") throw new Error(lists);
            if (lists.hasOwnProperty("warning")) result.warnings = [lists.warning + ` (checking with ${lists.length} combinations of a total ${binomial(n, m)})`];
            iter = 0;
            temp = getPartitionTree({matrix:submatrix});
            if (typeof temp==="string") throw new Error(temp);
            if (temp.canonicalLabel===null) throw new Error(`Canonical label of submatrix is null`);
            let canonical1 = temp.canonicalLabel;
            for (let list of lists) {
                if (temp = getInducedSubgraph({matrix, indexesSubgraph:list}), typeof temp==="string") throw new Error(temp);
                let submatrix2 = temp;
                if (temp = isGraphIsomorphic({matrix:submatrix, matrix2:submatrix2, methodIsomorphic:"McKay", canonical1}), typeof temp==="string") throw new Error(temp);
                if (temp[0]) {
                    result.indexes.push(list);
                    result.submatrix.push(submatrix2);
                    result.totalIsomorphics++;
                    let str = JSON.stringify(submatrix2);
                    if (!strSubmatrix.some(v => v===str)) {
                        strSubmatrix.push(str);
                        result.differentSubmatrix++;
                    }
                }
            }
        }
    } catch(e){result = e.message}
    return result;
}

Resolver problema de grafos isomórficos con método fuerza bruta

Limitación al aplicar fuerza bruta para saber si dos grafos son isomórficos

Es el grafo isomórfico isGraphIsomorphic()

Es el subgrafo isomórfico isSubgraphIsomorphic()

Obtener subgrafos isomórfico getIsomorphicSubgraphs()

Es el grafo isomórfico `isGraphIsomorphic()`

Es el subgrafo isomórfico `isSubgraphIsomorphic()`

Obtener subgrafos isomórfico `getIsomorphicSubgraphs()`