Componentes conectados 2 en grafos
Es vértice articulación isVertexArticulation()
Un vértice articulación es aquel que al eliminarlo hace que el grafo tenga más componenes conectados. El algoritmo isVertexArticulation() nos dice si un vértice es articulación. En la Figura podemos ver que lo es el nodo "1", pero también los nodos "2", "4" y "6". Puede denominarse también vértice separador, pero estos pueden darse en subconjuntos de tamaños mayor que uno como veremos en un apartado siguiente para encontrar conjunto separador de vértices, reservándose el término vértice articulación cuando se trata de un único vértice.
En la Figura se observan las opciones para ejecutar el algoritmo. Con el siguiente JSON puede importar el ejemplo anterior.
{"nodes":[
{"index":0,"nodeOffset":"-23.36 0.77","parent":[{"index":-1}]},
{"index":1,"nodeOffset":"17.74 -24.06","parent":[{"index":0}]},
{"index":2,"nodeOffset":"-8.02 0.71","parent":[{"index":-1},{"index":1}]},
{"index":3,"nodeOffset":"48.85 -24.57","parent":[{"index":2}]},
{"index":4,"nodeOffset":"-22.12 11.84","parent":[{"index":0},{"index":1}]},
{"index":5,"nodeOffset":"-15.38 -2.81","parent":[{"index":2}]},
{"index":6,"nodeOffset":"-6.81 10.47","parent":[{"index":2},{"index":3},{"index":5}]},
{"index":7,"nodeOffset":"-5.42 10.54","parent":[{"index":4}]},
{"index":8,"nodeOffset":"11.73 11.99","parent":[{"index":6}]}
],
"config":{
"algorithm":"Is vertex articulation",
"firstIndex":1
}}
En la Figura vemos la exportación a Wolfram encontrando el nodo etiquetado con "1" como vértice articulación, recordando que los nodos están etiquetados desde "0", por lo que ese nodo tiene índice "2" para Wolfram pues se inician en "1" mientras que en nuestra aplicación se inician en "0".
No encontré una función específica en Wolfram para saber si un vértice es articulación aparte de ArticulationVertices[g] que se considera obsoleta y remite a FindVertexCut[g] que encuentre un corte mínimo de vértices en un grafo. Lo mismo dice una referencia en Wolfram MathWorld Articulation Vertex remitiendo a FindVertexCut[g]. Pero no veo que esa función haga exactamente lo mismo, pues es verdad que encuentra un primer vértice de corte (que es también de articulación), pero no todos ni comprueba alguno específicamente.
Aunque obsoleto ArticulationVertices[g] sigue funcionando y es lo que usamos. Vemos que obtiene los vértices {2, 3, 5, 7}, que se corresponden con [1, 2, 4, 6] en nuestra aplicación pues en Wolfram los índices se inician en "1" y en nuestra aplicación en "0". Y que el nodo "2" ("1" para nosotros) que cuestionamos es vértice articulación pues está incluido en esa lista.
g = AdjacencyGraph[{{0,1,0,0,1,0,0,0,0},{1,0,1,0,1,0,0,0,0},{0,1,0,1,0,1,1,0,0},{0,0,1,0,0,0,1,0,0},{1,1,0,0,0,0,0,1,0},
{0,0,1,0,0,0,1,0,0},{0,0,1,1,0,1,0,0,1},{0,0,0,0,1,0,0,0,0},{0,0,0,0,0,0,1,0,0}}, ImageSize->300, VertexSize->{"Scaled", 0.1},
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]}, VertexLabelStyle->Directive[Black,17.5],
EdgeLabelStyle->Directive[Black,17.5,Bold], VertexStyle->White, EdgeStyle->{{Black,Thickness[0.005]}}];
v = 2;
a = ResourceFunction["ArticulationVertices"][g]
ContainsAll[a, {v}]
If[%,HighlightGraph[g, v, VertexLabelStyle-> Directive[White, 17.5]],g]
Con el grafo dirigido de la Figura si en las opciones que se observan en la Figura marcamos la opción forzar no dirigido, el algoritmo considerará el grafo como no dirigido obteniéndose lo mismo que vimos en el ejemplo anterior.
En otro caso para un grafo dirigido un vértice es articulación si su eliminación supone incrementar el número de componentes fuertemente conectados como explicamos más arriba.
En la Figura vemos los componentes fuertemente conectados en el grafo dirigido, grafo que ya vimos en un apartado anterior cuando explicábamos esto en la Figura.
Se observa que si eliminamos el nodo "0" desaparece el primer componente fuertemente conectado "0🡒1, 1🡒4, 4🡒0" pasando a ser dos componentes fuertemente conectados separados "1" y "4", con lo que el total de componentes fuertementes conectados del grafo se incrementa.
Podemos encontrar todos los vértices de corte o articulación con findVertexSeparator() marcando la opción encontrar todos obteniendo [[0],[1],[2],[4],[6]]. Se puede analizar fácilmente que eliminando cualquiera de estos vértices se incrementa el número de componentes fuertemente conectados.
{"nodes":[
{"index":0,"nodeOffset":"-23.36 0.77","parent":[{"index":-1}]},
{"index":1,"nodeOffset":"9.41 -24.06","parent":[{"index":0}]},
{"index":2,"nodeOffset":"-8.02 0.71","parent":[{"index":-1}]},
{"index":3,"nodeOffset":"32.18 -24.57","parent":[{"index":2}]},
{"index":4,"nodeOffset":"-5.45 -13.16","parent":[{"index":1},{"index":0,"markerStart":"none","markerEnd":"arrow"}]},
{"index":5,"nodeOffset":"-23.71 -2.81","parent":[{"index":2}]},
{"index":6,"nodeOffset":"9.85 -14.53","parent":[{"index":3},{"index":5},{"index":2,"markerStart":"none","markerEnd":"arrow"}]},
{"index":7,"nodeOffset":"-5.42 -14.46","parent":[{"index":4}]},
{"index":8,"nodeOffset":"11.73 -13.01","parent":[{"index":6}]}
],
"config":{
"markerStart":"arrow",
"algorithm":"Is vertex articulation"
}}
Para exportar isVertexArticulation() a Wolfram usábamos ResourceFunction["ArticulationVertices"][g] como vimos antes para un grafo no dirigido. Pero como se observa en la Figura resultando que el nodo "1" (etiquetado con "0") no es un vértice articulación, es posible que no funcione adecuadamente con grafos dirigidos.
g = AdjacencyGraph[{{0,1,0,0,0,0,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,1,0,0},{1,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,1},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}}, ImageSize->219,
VertexSize->{"Scaled", 0.14}, 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]},
VertexLabelStyle->Directive[Black,17.5], EdgeLabelStyle->Directive[Black,17.5,Bold], VertexStyle->White, DirectedEdges->True,
EdgeStyle->{{Black,Thickness[0.005]}}];
v = 1;
a = ResourceFunction["ArticulationVertices"][g];
ContainsAll[a, {v}]
If[%,HighlightGraph[g, v, VertexLabelStyle-> Directive[White, 17.5]],g]El código JavaScript para ejecutar isVertexArticulation() se muestra a continuación. Usa getConnectedComponents() que vimos al inicio de este tema, contando los componentes del grafo, eliminando el vértice en cuestión y volviendo a contar componentes para ver si han aumentado, en cuyo caso el vértice será de articulación. Hacemos una copia de la matriz para no modificar la original que se recibe por referencia.
function isVertexArticulation({matrix=[], index=-1, forceUndirected=true}) {
let result = false;
try {
let components1 = getConnectedComponents({matrix, forceUndirected});
if (typeof components1==="string") throw new Error(components1);
let n = matrix.length;
if (index<0 || index>=n) throw new Error(`Vertex '${index}' does not exists`);
let matrixCopy = JSON.parse(JSON.stringify(matrix));
for (let i=0; i<n; i++){
matrixCopy[i].splice(index, 1);
}
matrixCopy.splice(index, 1);
let components2 = getConnectedComponents({matrix:matrixCopy, forceUndirected});
if (typeof components2==="string") throw new Error(components2);
result = components2.length>components1.length;
} catch(e){result = e.message}
return result;
}Es arista puente isEdgeBridge()
Una arista puente es aquella que al eliminarla hace que el grafo tenga más componenes conectados. También podemos denominarla arista de separación como veremos en un apartado siguiente para encontrar un conjunto separador de aristas, donde pueden darse en subconjuntos de tamaños mayores que uno, reservándose así el término arista puente para el caso de una única arista. En la Figura vemos la arista puente "1-2" pues al eliminar tendremos un grafo con 2 componentes conectados. También son aristas puentes "4-7" y "6-8".
{"nodes":[
{"index":0,"nodeOffset":"-23.36 0.77","parent":[{"index":-1}]},
{"index":1,"nodeOffset":"17.74 -24.06","parent":[{"index":0}]},
{"index":2,"nodeOffset":"-8.02 0.71","parent":[{"index":-1},{"index":1}]},
{"index":3,"nodeOffset":"48.85 -24.57","parent":[{"index":2}]},
{"index":4,"nodeOffset":"-22.12 11.84","parent":[{"index":0},{"index":1}]},
{"index":5,"nodeOffset":"-15.38 -2.81","parent":[{"index":2}]},
{"index":6,"nodeOffset":"-6.81 10.47","parent":[{"index":2},{"index":3},{"index":5}]},
{"index":7,"nodeOffset":"-5.42 10.54","parent":[{"index":4}]},
{"index":8,"nodeOffset":"11.73 11.99","parent":[{"index":6}]}
],
"config":{
"algorithm":"Is edge bridge",
"edge":"1,2"
}}
En la Figura vemos la exportación a Wolfram cuestionando si la arista "2-3" es una arista puente. Vea que se corresponde con las etiquetas "1-2", pues en Wolfram los índices se inician en "1" y en nuestra aplicación en "0".
Usamos FindEdgeCut[g, 2, 3] comprobando que esa arista es de corte. En el siguiente tema veremos la función equivalente en nuestra aplicación a FindEdgeCut[g, s, t] que es encontrar corte mínimo de aristas s-t con findSTEdgeCut(), donde el mínimo para grafos no ponderados se refiere al mínimo número de aristas que son necesarias separar los nodos "s" y "t" en distintos componentes conectados, observando que cuando el grafo tiene una arista puente entre nodos "s" y "t" entonces el corte mínimo entre "s" y "t" es uno y coincide con esa arista puente.
g = AdjacencyGraph[{{0,1,0,0,1,0,0,0,0},{1,0,1,0,1,0,0,0,0},{0,1,0,1,0,1,1,0,0},{0,0,1,0,0,0,1,0,0},{1,1,0,0,0,0,0,1,0},
{0,0,1,0,0,0,1,0,0},{0,0,1,1,0,1,0,0,1},{0,0,0,0,1,0,0,0,0},{0,0,0,0,0,0,1,0,0}}, ImageSize->300, VertexSize->{"Scaled", 0.1},
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]}, VertexLabelStyle->Directive[Black,17.5],
EdgeLabelStyle->Directive[Black,17.5,Bold], VertexStyle->White, EdgeStyle->{{Black,Thickness[0.005]}}];
e = {2, 3};
f = FindEdgeCut[g, First[e], Last[e]];
v = VertexList[f];
h = HighlightGraph[g, f];
Or[And[First[e]==First[v], Last[e]==Last[v]], And[First[e]==Last[v], Last[e]==First[v]]]
If[%, HighlightGraph[h, e, VertexLabelStyle-> Directive[White, 17.5]], h]Luego veremos que con findEdgeSeparator() podemos encontrar todas los conjuntos separadores de aristas de tamaño 1 resultando [[1,2]], [[4,7]], [[6,8]].
isEdgeBridge() En la Figura vemos las opciones arista que si es no dirigido puede pasarse como "u,v" o "v,u" pero si es dirigido y se pasa "u,v" se entiende "u🡒v" y si se pasa "v,u" se entiende "v🡒u". Con la opción arista con valores nodos en lugar de usar los índices de los nodos podemos usar sus etiquetas. Con forzar no dirigido se tratara el grafo como no dirigido.
Las opciones color camino, color texto y color fondo nodo no forma parte del algoritmo isEdgeBridge() y se aplican al resultado obtenido para mostrarlo en el SVG.
Con un grafo dirigido como el de la Figura, si marcamos la opción forzar no dirigido, el algoritmo tratará el grafo como no dirigido, en cuyo caso eliminar la arista "0🡒1" no incrementa el número de componentes débilmente conectados. En otro caso la arista "0🡒1" es puente pues su eliminación incrementará el número de componentes fuertemente conectados.
En la Figura vemos los componentes fuertemente conectados en el grafo dirigido, grafo que ya vimos en un apartado anterior cuando explicábamos esto en la Figura.
Se observa que al eliminar la arista "0🡒1" el componente fuertemente conectado "0🡒1", 1🡒4, 4🡒0" deja de serlo, con lo que tendremos 3 componentes fuertemente conectados "0", "1" y "4", incrementándose el número total.
Con findEdgeSeparator() con la opción encontrar todos obtenemos todas las aristas puente o de separación del grafo: [[[0,1]], [[1,4]], [[2,3]], [[2,5]], [[3,6]], [[4,0]], [[5,6]], [[6,2]]], observando que son las aristas de los dos primeros componentes de la Figura. Eliminar cualquiera de ellas incrementará el número de componentes. Es obvio que eliminar alguna del resto de aristas "4🡒7" o "6🡒8" no modificará el número de componentes.
{"nodes":[
{"index":0,"nodeOffset":"-23.36 0.77","parent":[{"index":-1}]},
{"index":1,"nodeOffset":"9.41 -24.06","parent":[{"index":0}]},
{"index":2,"nodeOffset":"-8.02 0.71","parent":[{"index":-1}]},
{"index":3,"nodeOffset":"32.18 -24.57","parent":[{"index":2}]},
{"index":4,"nodeOffset":"-5.45 -13.16","parent":[{"index":1},{"index":0,"markerStart":"none","markerEnd":"arrow"}]},
{"index":5,"nodeOffset":"-23.71 -2.81","parent":[{"index":2}]},
{"index":6,"nodeOffset":"9.85 -14.53","parent":[{"index":3},{"index":5},{"index":2,"markerStart":"none","markerEnd":"arrow"}]},
{"index":7,"nodeOffset":"-5.42 -14.46","parent":[{"index":4}]},
{"index":8,"nodeOffset":"11.73 -13.01","parent":[{"index":6}]}
],
"config":{
"markerStart":"arrow",
"algorithm":"Is edge bridge",
"edge":"0,1",
"findAll":true
}}
En la Figura vemos la exportación a Wolfram, con el mismo resultado usando FindEdgeCut[g, 1, 2] que no está concebida realmente para ese uso, pero nos remitimos a lo expuesto para el ejemplo de la Figura.
g = AdjacencyGraph[{{0,1,0,0,0,0,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,1,0,0},{1,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,1},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}}, ImageSize->219, VertexSize->{"Scaled", 0.14},
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]}, VertexLabelStyle->Directive[Black,17.5],
EdgeLabelStyle->Directive[Black,17.5,Bold], VertexStyle->White, DirectedEdges->True, EdgeStyle->{{Black,Thickness[0.005]}}];
e = {1, 2};
f = FindEdgeCut[g, First[e], Last[e]];
v = VertexList[f];
h = HighlightGraph[g, f];
And[First[e]==First[v], Last[e]==Last[v]]
If[%, HighlightGraph[h, e, VertexLabelStyle-> Directive[White, 17.5]], h]A continuación se muestra el JavaScript del algoritmo isEdgeBridge() que usa isGraphDirected() para saber si el grafo es dirigido. También usamos getEdges() para obtener las aristas comprobar si la arista en cuestión existe. Y getConnectedComponents() que vimos al inicio de este tema, contando los componentes del grafo, eliminando la arista en cuestión y volviendo a contar componentes para ver si han aumentado, en cuyo caso la arista será puente. Hacemos una copia de la matriz para no modificar la original que se recibe por referencia.
function isEdgeBridge({matrix=[], edge=[-1, -1], forceUndirected=true}) {
let result = false;
try {
let directed = isGraphDirected({matrix});
if (typeof directed==="string") throw new Error(directed);
let components1 = getConnectedComponents({matrix, forceUndirected});
if (typeof components1==="string") throw new Error(components1);
let n = matrix.length;
if (edge[0]<0 || edge[1]<0 || edge[0]>n-1 || edge[1]>n-1) throw new Error(`Edge '[${edge.toString()}]' is wrong`);
let edges = getEdges({matrix, edgesCompact:false});
if (typeof edges==="string") throw new Error(edges);
edges = Object.keys(edges);
if (!edges.some(v => v.toString()===edge.toString())) throw new Error(`Edge '[${edge.toString()}]' doesn't exist`);
let matrixCopy = JSON.parse(JSON.stringify(matrix));
let [i, j] = edge;
matrixCopy[i][j] = 0;
if (!directed || forceUndirected) matrixCopy[j][i] = 0;
let components2 = getConnectedComponents({matrix:matrixCopy, forceUndirected});
if (typeof components2==="string") throw new Error(components2);
result = components2.length>components1.length;
} catch(e){result = e.message}
return result;
}Encontrar todos los vértices articulación findAllArticulationVertex()
Todos los vértices articulación en un grafo son todos aquellos vértices cuya eliminación individual incrementa el número de componentes conectados. En la Figura vemos que "4" y "6" son todos los vértices de articulación del grafo.
Encontrar todos los vértices articulación: [4,6]
{"nodes":[
{"index":0,"nodeOffset":"-23.36 0.77","parent":[{"index":-1}]},
{"index":1,"nodeOffset":"17.74 -24.06","parent":[{"index":0}]},
{"index":2,"nodeOffset":"-8.02 0.71","parent":[{"index":-1}]},
{"index":3,"nodeOffset":"48.85 -24.57","parent":[{"index":2}]},
{"index":4,"nodeOffset":"-22.12 11.84","parent":[{"index":0},{"index":1}]},
{"index":5,"nodeOffset":"-15.38 -2.81","parent":[{"index":2}]},
{"index":6,"nodeOffset":"-6.81 10.47","parent":[{"index":2},{"index":3},{"index":5}]},
{"index":7,"nodeOffset":"-5.42 10.54","parent":[{"index":4}]},
{"index":8,"nodeOffset":"11.73 11.99","parent":[{"index":6}]}
],
"config":{
"lineHeight":18.75,
"algorithm":"Find all articulation vertex"
}}
Para un grafo dirigido todos los vértices de articulación son los que incrementan el número de componentes fuertemente conectados. En la Figura vemos que "0" y "4" son todos los vértices de articulación de ese grafo.
Para entender el motivo vemos en la Figura los dos componentes fuertemente conectados del grafo, que recordamos que son así pues desde cualquier nodo en un componente podemos acceder a cualquier otro del mismo componente. Sólo si eliminamos el nodo "0" o el "4" no tendremos ese acceso en el primer componente y el número de componentes pasa de 2 a 4.
{"nodes":[
{"index":0,"parent":[{"index":-1}]},
{"index":1,"value":"X","parent":[{"index":0,"value":"A"}]},
{"index":2,"parent":[{"index":0,"value":"B"},{"index":1,"value":"C"}]},
{"index":3,"parent":[{"index":1,"value":"D","lineTextOffset":"-0.75 0.25"},{"index":4,"value":"E"}]},
{"index":4,"parent":[{"index":1,"value":"F"},{"index":2},{"index":0,"lineOffset":"1","markerReverse":true,"value":"G"}]}
],
"config":{
"markerEnd":"arrow",
"algorithm":"Find all articulation vertex"
}}El JavaScript de findAllArticulationVertex() se muestra a continuación, usando getConnectedComponents() para obtenerlos al inicio y luego iterar por todos los vértices y comprobar que eliminando ese vértice se incrementa el número de componentes.
function findAllArticulationVertex({matrix=[]}) {
let result = [], temp;
try {
let n = matrix.length;
let components1 = getConnectedComponents({matrix, forceUndirected:false});
if (typeof components1==="string") throw new Error(components1);
for (let index=0; index<n; index++) {
let matrixCopy = JSON.parse(JSON.stringify(matrix));
matrixCopy.map(v => v.splice(index, 1));
matrixCopy.splice(index, 1);
let components2 = getConnectedComponents({matrix:matrixCopy, forceUndirected:false});
if (typeof components2==="string") throw new Error(components2);
if (components2.length>components1.length) result.push(index);
}
} catch(e){result = e.message}
return result;
}Encontrar todas las aristas puente findAllEdgeBridge()
Todas las aristas puente de un grafo dirigido son aquellas aristas que al eliminarlas individualmente incrementan el número de componentes fuertemente conectados del grafo. En la Figura vemos que hay 3 de estas aristas:
Encontrar todas aristas puente: [[0,4],[1,0],[4,2]]
Para entender ese resultado debemos recordar el número de componentes fuertemente conectados que ya vimos para este mismo ejemplo en el primer apartado:
Se observa en la Figura que tiene 2 componentes fuertemente conectados, recordando que estos componentes se caracterizan porque hay un camino desde cualquier nodo a otro dentro del componente. Si eliminamos la arista "0🡒4" ya no existirá ese camino, al igual que al elminar la arista "1🡒0" o la arista "4🡒2", creándose en estos casos tantos componentes como nodos "0,1,2,4" con lo que el número de componentes del grafo pasa de 2 a 5.
{"nodes":[
{"index":0,"parent":[{"index":-1}]},
{"index":1,"value":"X","parent":[{"index":0,"value":"A"}]},
{"index":2,"parent":[{"index":0,"value":"B"},{"index":1,"value":"C"}]},
{"index":3,"parent":[{"index":1,"value":"D","lineTextOffset":"-0.75 0.25"},{"index":4,"value":"E"}]},
{"index":4,"parent":[{"index":1,"value":"F"},{"index":2},{"index":0,"lineOffset":"1","markerReverse":true,"value":"G"}]}
],
"config":{
"markerEnd":"arrow",
"algorithm":"Find all edge bridge"
}}Tal como veremos después en el código JavaScript del algoritmo findAllEdgeBridge() para un grafo dirigido, se trata de obtener los componentes conectados del grafo inicial con getConnectedComponents(), luego obtener todas las aristas del grafo e iterar por ellas eliminando una y comprobar si el número de componentes fuertemente conectados se incrementa, en cuyo caso es una arista puente.
La misma técnica que acabamos de explicar para encontrar todas las aristas puente a de un grafo dirigido podría aplicarse a uno no dirigido. Sin embargo existe un algoritmo más eficiente que vamos a explicar ahora. En la Figura vemos las 4 aristas puente de un grafo dirigido, de tal forma que son todas las aristas que eliminadas invididualmente incrementan el número de componentes conectados.
Encontrar todas aristas puente: [[6,8],[6,9],[1,2],[4,7]]
{"nodes":[
{"index":0,"nodeOffset":"-15.03 0.77","parent":[{"index":-1}]},
{"index":1,"nodeOffset":"17.74 -24.06","parent":[{"index":0},{"index":2}]},
{"index":2,"nodeOffset":"8.65 0.71","parent":[{"index":-1}]},
{"index":3,"nodeOffset":"48.85 -24.57","parent":[{"index":2}]},
{"index":4,"nodeOffset":"-22.12 11.84","parent":[{"index":0},{"index":1}]},
{"index":5,"nodeOffset":"-15.38 -2.81","parent":[{"index":2}]},
{"index":6,"nodeOffset":"-6.81 10.47","parent":[{"index":2},{"index":3},{"index":5}]},
{"index":7,"nodeOffset":"-5.42 10.5","parent":[{"index":4}]},
{"index":8,"nodeOffset":"-9.07 10.5","parent":[{"index":6}]},
{"index":9,"nodeOffset":"8.8 60.5","parent":[{"index":-1},{"index":6}]}
],
"config":{
"lineHeight":18.75,
"algorithm":"Find all edge bridge"
}}Encontrar todas las aristas puente puede también hacerse con findEdgeSeparator({matrix, findAll:true, sizeSeparator:1}) especificando encontrar todos y tamaño separador igual a 1.
En la Figura vemos la ejecución del algoritmo findAllEdgeBridge() que encuentra la única arista puente [2, 3] en un grafo no dirigido más sencillo, con el que intentaré explicar como funciona. Es una adaptación de algunos que pueden verse en Internet, como Finding bridges in a graph.
Se basa en el algoritmo DFS, búsqueda en profundidad recursivo que ya vimos en un tema anterior. En la Figura vemos la ejecución del DFS donde los nodos son visitados según indica el número de orden de los subíndices de los nodos con índices 0, 1, 2, 3, que coincide con el mismo orden 1°, 2°, 3°, 4°. Puede importar el ejemplo con este JSON:
{"nodes":[
{"index":0,"nodeOffset":"-10 -2.5","parent":[{"index":-1},{"index":1},{"index":2}]},
{"index":1,"nodeOffset":"-30 17.5","parent":[{"index":-1}]},
{"index":2,"nodeOffset":"-25 7.5","parent":[{"index":-1},{"index":1},{"index":3}]},
{"index":3,"nodeOffset":"-20 7.5","parent":[{"index":-1}]}
],
"config":{
"algorithm":"Find all edge bridge"
}}Cuando avanzamos por un DFS estaremos en un nodo "i" que tiene una arista a otro nodo "p". Esta arista "i-p" es un puente sí y sólo sí el nodo "p" y todos a los que pudiéramos acceder desde "p" no tiene una arista de vuelta (back) al nodo "i" o alguno por encima desde el que se pueda acceder a "i". Esto significa que el único camino posible entre "i" y "p" es a través de la única arista "i-p".
En la Figura vemos que esto sólo sucede con la arista "2-3" donde desde "3" no podemos acceder a nodos anteriores si no es por esa arista.
Como todo recursivo, no es fácil seguir los acontecimientos. Pero si después de dfs(parent, index), es decir, al retorno de las llamadas recursivas, ponemos la sentencia console.log(index, parent, visited, back), obtenemos estos datos en los retornos de las llamadas recursivas:
| i (index) | p (parent) | visited | back | back[p] | visited[i] | Bridge |
|---|---|---|---|---|---|---|
| 2 | 3 | [1,2,3,4] | [1,2,1,4] | back[3]=4 | visited[2]=3 | 4>3 ⇒ [2, 3] |
| 1 | 2 | [1,2,3,4] | [1,2,1,4] | back[2]=1 | visited[1]=2 | 1<2 |
| 0 | 1 | [1,2,3,4] | [1,1,1,4] | back[1]=1 | visited[0]=1 | 1=1 |
Los números 1,2,3,4 son los números de orden de visita de los nodos que vamos incrementando en la variable orderNumVisit en el algoritmo en cada llamada. En un recursivo como este se producen todas las llamadas primero y luego los retornos en orden inverso, así que el primer retorno se corresponde con la última llamada.
Vea que visited = [1, 2, 3, 4] coincide con el orden de visita del DFS. En back = [1, 2, 1, 4] vamos poniendo el orden de visita cuando se descubre ese nodo, así back[2]=1 significa que el nodo "2" se descubrió con el primer orden de visita (con i=0) al descubrir la arista "0-2" pues "2" es un nodo conectado con "0" por esa arista. Si elimináramos esa arista "0-2" back sería igual que visited en todos los retornos de llamadas, así que back nos informa de lazos entre los nodos.
Se observa que cuando estamos en el nodo "i=2" y vemos "p=3" sucede que tendremos back=[1,2,1,4] donde back[3]=4 > visited[2]=3 con lo que [2, 3] será una arista puente. Si es "<" entonces hay un camino de vuelta desde "p" a alguno por encima de "i", como sucede con "i=1, p=2" donde hay un camino de vuelta "1-2-0-1" a través de "0" que está por encima de "1". Y si es estrictamente "=" el camino de vuelta es al propio "i", como con "i=0, p=1" donde el camino "0-1-2-0" no pasa por nodos que estén por encima.
En el algoritmo findAllEdgeBridge() siguiente usamos isGraphDirected(), getParents(), getEdges() y getConnectedComponents().
function findAllEdgeBridge({matrix=[]}) {
let result = [], temp;
try {
let directed = isGraphDirected({matrix});
if (typeof directed==="string") throw new Error(directed);
let n = matrix.length;
if (!directed) {
let visited = Array.from({length:n}, ()=>-1);
let back = Array.from({length:n}, ()=>-1);
let orderNumVisit = 0;
function dfs(index, lastIndex){
if (iter++, iter>maxIter) return `Maximum iterations '${maxIter}' reached`;
orderNumVisit++;
visited[index] = orderNumVisit;
back[index] = orderNumVisit;
let parents = getParents({matrix, index:index});
if (typeof parents==="string") throw new Error(parents);
for (let parent of parents) {
if (parent!==lastIndex) {
if (visited[parent]===-1) {
dfs(parent, index);
//console.log(index, parent, visited, back)
if (back[parent]>visited[index]) {
result.push([index, parent]);
}
back[index] = Math.min(back[index], back[parent]);
} else {
back[index] = Math.min(back[index], visited[parent]);
}
}
}
}
for (let i=0; i<n; i++) {
if (visited[i]===-1) {
dfs(i, -1);
}
}
} else {
let components1 = getConnectedComponents({matrix, forceUndirected:false});
if (typeof components1==="string") throw new Error(components1);
let edges = getEdges({matrix, edgesCompact:true});
if (typeof edges==="string") throw new Error(edges);
for (let edge of edges) {
let matrixCopy = JSON.parse(JSON.stringify(matrix));
let [i, j] = edge;
matrixCopy[i][j] = 0;
if (!directed) matrixCopy[j][i] = 0;
let components2 = getConnectedComponents({matrix:matrixCopy, forceUndirected:false});
if (typeof components2==="string") throw new Error(components2);
if (components2.length>components1.length) result.push(edge);
}
}
} catch(e){result = e.message}
return result;
}Encontrar conjunto separador de vértices findVertexSeparator()
Encontrar un conjunto separador de vértices con tamaño "k" en un grafo no dirigido supone encontrar "k" vértices cuya eliminación hace que se incremente el número de componentes conectados del grafo. Cuando "k" es 1 entonces equivale a un vértice articulación.
Encontrar separador vértices: [[0,1,3,4],[0,2,3,5], [1,2,4,5]]
En la Figura vemos que la eliminación del subconjunto de vértices [0,1,3,4] de tamaño 4 desconecta el grafo. En total hay 3 de estos subconjuntos de tamaño 4 que desconectan el grafo. Es más, no hay ningún subconjunto inferior a 4 que lo desconecte, por el motivo que explicaremos después.
En la Figura vemos la opciones para ejecutar el algoritmo, con encontrar todos para obtener todos los conjuntos separadores con un tamaño separador determinado, conjuntos con vértices que si se eliminan incrementan el número de componentes conectados, que para el ejemplo hemos puesto que se deben encontrar conjuntos con 4 elementos.
Si se activa mínimo tamaño separador se ignorará la opción tamaño separador, iterando desde tamaño 1 hasta el total de vértices de tal forma que cuando encuentre un primer tamaño del conjunto separador de vértices devolverá ese conjunto encontrado, o todos de ese tamaño en caso de estar marcado encontrar todos. En el ejemplo si se activa esa opcion mínimo tamaño separador se intentará encontrar subconjuntos de tamaño 1, 2 y 3 sin éxito, siendo 4 el primer tamaño que desconecta el grafo.
Con forzar no dirigido se tratará el grafo dirigido como no dirigido. Luego veremos la opción con arista puente con un ejemplo. La opción color fondo nodo no se aplica en el algoritmo, sino posteriormente para presentar el grafo en el SVG. Por ahora este es el JSON del ejemplo:
{"nodes":[
{"index":0,"nodeOffset":"2.5","parent":[{"index":-1}]},
{"index":1,"nodeOffset":"37.14 -5","parent":[{"index":0}]},
{"index":2,"nodeOffset":"37.14 10","parent":[{"index":1},{"index":0}]},
{"index":3,"nodeOffset":"2.5 5","parent":[{"index":2},{"index":1}]},
{"index":4,"nodeOffset":"-32.14 -40","parent":[{"index":3},{"index":2},{"index":0}]},
{"index":5,"nodeOffset":"-32.14 -105","parent":[{"index":4},{"index":0},{"index":1},{"index":3}]}
],
"config":{
"algorithm":"Find vertex separator",
"findAll":true,
"sizeSeparator":4
}}
En la Figura vemos el Grafo de Petersen 5,2 encontrando un conjunto separador de vértices con la opción mínimo tamaño separador marcada, con lo que resulta que son de tamaño 3. Con la opción encontrar todos marcada obtenemos los siguientes 10 conjuntos separadores:
Encontrar separador vértices: [[0,2,6],[0,3,9],[0,7,8], [1,3,7],[1,4,5],[1,8,9], [2,4,8],[2,5,9],[3,5,6], [4,6,7]]
Si marcamos además la opción con arista puente de tal forma que sólo se seleccionan aquellos conjuntos de vértices que estén conectados por una arista, resulta que necesitamos llegar hasta subconjuntos de tamaño 7, obteniéndose 60 posibilidades de las que exponemos sólo algunas para no extendernos, mostrando en la Figura la primera.
Encontrar separador vértices: [[0,1,2,3,4,5,6], [0,1,2,3,4,5,9], ... 56 más ... [2,3,4,5,6,8,9], [2,4,5,6,7,8,9]]
Dado que tiene que comprobar muchas posibilidades hay que imponer la opción máximas iteraciones con un valor de 40000 cuando por defecto está en 10000.
{"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 vertex separator",
"maxIter":40000,
"findAll":true,
"minimumSizeSeparator":true,
"withEdgeBridge":true
}}
En la Figura vemos los dos únicos vértices "0" y "4" con tamaño mínimo de separador del grafo dirigido, marcando las opciones mínimo tamaño separador y encontrar todos.
Recordemos que los 2 componentes fuertementes conectados de este grafo son los que vemos en la Figura, de tal forma que si eliminamos el nodo "0" tendremos 4 componentes conectados, uno por cada nodo restante del grafo pues no hay forma de recorrer todos los nodos si empezamos en cualquiera de ellos. Y de la misma forma con el nodo "4", pues en cualquier caso se incrementa el número de componentes conectados. Vea que la arista "0🡒4" es la que habilita que haya un camino entre cualquier nodo del subgrafo del primer componente, por lo que eliminar el "0" o el "4", incluso esa arista "0🡒4", quita esa posibilidad.
{"nodes":[
{"index":0,"parent":[{"index":-1}]},
{"index":1,"value":"X","parent":[{"index":0,"value":"A"}]},
{"index":2,"parent":[{"index":0,"value":"B"},{"index":1,"value":"C"}]},
{"index":3,"parent":[{"index":1,"value":"D","lineTextOffset":"-0.75 0.25"},{"index":4,"value":"E"}]},
{"index":4,"parent":[{"index":1,"value":"F"},{"index":2},{"index":0,"lineOffset":"1","markerReverse":true,"value":"G"}]}
],
"config":{
"markerEnd":"arrow",
"algorithm":"Find vertex separator",
"findAll":true,
"minimumSizeSeparator":true
}}A continuación vemos el JavaScript para ejecutar findVertexSeparator():
function findVertexSeparator({matrix=[], findAll=false, sizeSeparator=1, minimumSizeSeparator=false, withEdgeBridge=false, forceUndirected=true}) {
let result = [];
result.warnings = [];
try {
let components1 = getConnectedComponents({matrix, forceUndirected});
if (typeof components1==="string") throw new Error(components1);
let n = matrix.length;
let indexes = Array.from({length: n}, (v,i) => i);
sizeSeparator = Math.max(0, Math.min(sizeSeparator, n));
let [from, to] = [sizeSeparator, sizeSeparator];
if (minimumSizeSeparator) [from, to] = [1, n-1];
for (let sc=from; sc<=to; sc++) {
let combinations = combine(indexes, sc);
if (typeof combinations==="string") throw new Error(combinations);
if (combinations.hasOwnProperty("warning")){
result.warnings.push(combinations.warning);
}
for (let listVertexs of combinations) {
if (withEdgeBridge && listVertexs.length>1) {
let path = findCoveragePath({matrix, indexes:listVertexs});
if (typeof path==="string") throw new Error(path);
if (path.length===0) listVertexs = [];
}
let matrixCopy = [];
for (let i=0; i<n; i++){
let arr = [];
for (let j=0; j<n; j++) {
if (!(listVertexs.includes(i) || listVertexs.includes(j))) {
arr.push(matrix[i][j]);
}
}
if (arr.length>0) matrixCopy.push(arr);
}
iter = 0;
let components2 = getConnectedComponents({matrix:matrixCopy, forceUndirected});
if (typeof components2==="string") throw new Error(components2);
if (components2.length>components1.length) {
result.push([...listVertexs]);
if (!findAll) return result;
}
}
if (result.length>0) break;
}
} catch(e){result = e.message}
return result;
}Se usan las siguientes funciones:
getConnectedComponents()para obtener los componentes conectados que vimos al inicio en este tema.combine(list, k)para obtener las combinaciones de una lista de nodos, con el código que vemos después de esta lista.findCoveragePath()para encontrar un camino de cobertura de un conjunto de nodos.
function combine(list=[], k=0, n=list.length, res=Array.from({length:k}, ()=>""), result=[], n0=list.length, k0=res.length){
try {
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;
}El funcionamiento es obtener los componentes conectados del grafo inicial y hacer un bucle que itere por tamaños de conjuntos separadores de vértices para ir probando aquellos que incrementen el número de componentes conectados. Con findCoveragePath() comprobamos si ese conjunto está unido por aristas, para el caso de que se pase la opción con arista puente (withEdgeBridge).
Este algoritmo no es eficiente para grafos con muchos vértices o cuando hay que encontrar todos los resultados. En el ejemplo que vimos más arriba tuvimos que imponer máximas iteraciones a 40000, cuando por defecto se establecen en 10000.
Para el grafo de la Figura con 20 nodos para encontrar todos los conjuntos separadores con mínimo tamaño separador y con arista puente marcados también, necesitamos 4500000 máximas iteraciones, con un tiempo de ejecución de casi 6 segundos.
Time: 5908 ms Encontrar separador vértices: [[0,1,2,3,8,9,10],[0,1,2,3,10,11,12], ...56 más... [11,12,13,15,16,17,18],[11,12,13,15,16,17,19]]
Se encuentran 60 resultados con tamaño 7 exigiendo que los nodos estén conectados con aristas.
{"nodes":[
{"index":0,"nodeOffset":"22.54 57.27","parent":[{"index":-1},{"index":1},{"index":14}]},
{"index":1,"nodeOffset":"44.52 -43.2","parent":[{"index":3},{"index":6}]},
{"index":2,"nodeOffset":"17.4 48.75","parent":[{"index":0},{"index":12}]},
{"index":3,"nodeOffset":"83.9 -1.06","parent":[{"index":4},{"index":8}]},
{"index":4,"nodeOffset":"32.7 36.8","parent":[{"index":2},{"index":10}]},
{"index":5,"nodeOffset":"71.71 -176.86","parent":[{"index":6},{"index":15}]},
{"index":6,"nodeOffset":"86.62 -162.22","parent":[{"index":7}]},
{"index":7,"nodeOffset":"100.97 -144.59","parent":[{"index":8},{"index":16}]},
{"index":8,"nodeOffset":"81.92 -115.15","parent":[{"index":9}]},
{"index":9,"nodeOffset":"62.27 -87.71","parent":[{"index":10},{"index":17}]},
{"index":10,"nodeOffset":"26.75 -88.91","parent":[{"index":11}]},
{"index":11,"nodeOffset":"-8.56 -88.44","parent":[{"index":12},{"index":18}]},
{"index":12,"nodeOffset":"-26.56 -117.68","parent":[{"index":13}]},
{"index":13,"nodeOffset":"-44.32 -145.05","parent":[{"index":14},{"index":19}]},
{"index":14,"nodeOffset":"-32.12 -161.29","parent":[{"index":5}]},
{"index":15,"nodeOffset":"52.8 -75.39","parent":[{"index":16}]},
{"index":16,"nodeOffset":"110.07 -22.57","parent":[{"index":17}]},
{"index":17,"nodeOffset":"64.51 58.23","parent":[{"index":18}]},
{"index":18,"nodeOffset":"-29.03 58.18","parent":[{"index":19}]},
{"index":19,"nodeOffset":"-70.45 -27.13","parent":[{"index":15}]}
],
"config":{
"lineHeight":18.75,
"algorithm":"Find vertex separator",
"maxIter":4500000,
"findAll":true,
"minimumSizeSeparator":true,
"withEdgeBridge":true
}}
Para el grafo de la Figura con 400 nodos, con la opción más simple que es sólo imponer tamaño separador con valor 3, pues sabemos previamente que es el mínimo tamaño de separador, necesitará 160000 iteraciones para encontrar en 1661 ms el primer conjunto [0, 2, 4].
Time: 1661 ms Encontrar separador vértices: [[0,2,4]]
Puede abrir cfi-400-nodes.txt con la lista de aristas de ese grafo en formato de texto que puede copiar e importar en la aplicación tal como explicamos en un tema anterior sobre como importar una lista de aristas.
Encontrar conjunto separador de aristas findEdgeSeparator()
Encontrar un conjunto separador de aristas con tamaño "k" supone encontrar "k" aristas que si se eliminan incrementarán el número de componentes conectados del grafo. Cuando "k" es 1 entonces estaríamos hablando de una arista puente. En la Figura vemos un grafo dirigido con el conjunto separador de aristas [[0,1],[0,6]], encontrándose en total 5 conjuntos con 2 aristas siguiente:
Encontrar separador aristas: [[[0,1],[0,6]], [[3,4],[3,5]], [[3,4],[4,5]], [[3,5],[4,5]], [[6,9],[8,9]]]
Para la ejecución del ejemplo anterior se pasan las opciones encontrar todos y mínimo tamaño separador ambas marcadas, que tal como comentamos en el apartado anterior, con esta última marcada se ignora la opción tamaño separador y buscará desde 1 el primer tamaño, resultando ser en el ejemplo el tamaño 2. La opción forzar no dirigido sólo se aplica a grafos dirigidos, que en caso de marcarse lo tratará como no dirigido.
{"nodes":[
{"index":0,"nodeOffset":"121.05 29","parent":[{"index":6}]},
{"index":1,"nodeOffset":"78.15 25.8","parent":[{"index":0},{"index":7}]},
{"index":2,"nodeOffset":"-0.39 81.8","parent":[{"index":-1}]},
{"index":3,"nodeOffset":"12.09 12","parent":[{"index":2},{"index":7},{"index":8},{"index":11}]},
{"index":4,"nodeOffset":"-9.53 -63.8","parent":[{"index":5},{"index":3}]},
{"index":5,"nodeOffset":"-53.88 -12.8","parent":[{"index":3}]},
{"index":6,"nodeOffset":"44.79 27.2","parent":[{"index":-1}]},
{"index":7,"nodeOffset":"45.54 24.8","parent":[{"index":6}]},
{"index":8,"nodeOffset":"26.74 -2","parent":[{"index":6},{"index":7}]},
{"index":9,"nodeOffset":"44.69 -27.2","parent":[{"index":6},{"index":8}]},
{"index":10,"nodeOffset":"0.26 26.2","parent":[{"index":1},{"index":11},{"index":2}]},
{"index":11,"nodeOffset":"-26 40.2","parent":[{"index":2},{"index":7},{"index":8}]}
],
"config":{
"lineHeight":21.25,
"algorithm":"Find edge separator",
"findAll":true,
"minimumSizeSeparator":true
}}
Para el grafo dirigido de la Figura encontrar todos los conjuntos separadores de vértices con la opción mínimo tamaño separador marcada devuelve los 3 siguientes conjuntos con una única arista, resaltándose la primera [0,4]:
Encontrar separador aristas: [[[0,4]], [[1,0]], [[4,2]]]
Para entender el motivo de que esas 3 aristas incrementan el número de componentes, vemos en la Figura los dos componentes fuertemente conectados, de tal forma que eliminando alguna de las aristas "0🡒4", "1🡒0" o "4🡒2" del primer componente hace que se incremente el número de componentes fuertemente conectados, hasta tantos como vértices de ese subgrafo, pues ya no podremos acceder desde cualquiera de sus nodos a otro.
{"nodes":[
{"index":0,"parent":[{"index":-1}]},
{"index":1,"value":"X","parent":[{"index":0,"value":"A"}]},
{"index":2,"parent":[{"index":0,"value":"B"},{"index":1,"value":"C"}]},
{"index":3,"parent":[{"index":1,"value":"D","lineTextOffset":"-0.75 0.25"},{"index":4,"value":"E"}]},
{"index":4,"parent":[{"index":1,"value":"F"},{"index":2},{"index":0,"lineOffset":"1","markerReverse":true,"value":"G"}]}
],
"config":{
"markerEnd":"arrow",
"algorithm":"Find edge separator",
"findAll":true,
"minimumSizeSeparator":true
}}A continuación vemos el JavaScript para ejecutar findEdgeSeparator().
function findEdgeSeparator({matrix=[], firstIndex=0, lastIndex=0, sizeSeparator=1, minimumSizeSeparator=false, findAll=false, forceUndirected=true}) {
let result = [], temp;
result.warnings = [];
try {
let directed = isGraphDirected({matrix});
if (typeof directed==="string") throw new Error(directed);
let components1 = getConnectedComponents({matrix, forceUndirected});
if (typeof components1==="string") throw new Error(components1);
let n = matrix.length;
if (temp = getEdges({matrix, edgesCompact:true}), typeof temp==="string") throw new Error(temp);
let edges = temp;
sizeSeparator = Math.max(0, Math.min(sizeSeparator, edges.length));
let [from, to] = [sizeSeparator, sizeSeparator];
if (minimumSizeSeparator) {
[from, to] = [1, edges.length];
}
for (let sc=from; sc<=to; sc++) {
let combinations = combine(edges, sc);
if (typeof combinations==="string") throw new Error(combinations);
if (combinations.hasOwnProperty("warning")){
result.warnings.push(combinations.warning + ` (testing cut size ${sc})`);
}
for (let listEdges of combinations) {
let matrixCopy = JSON.parse(JSON.stringify(matrix));
for (let edge of listEdges) {
let [i, j] = edge;
matrixCopy[i][j] = 0;
if (!directed) matrixCopy[j][i] = 0;
}
iter = 0;
let components2 = getConnectedComponents({matrix:matrixCopy, forceUndirected});
if (typeof components2==="string") throw new Error(components2);
if (components2.length>components1.length) {
result.push([...listEdges]);
if (!findAll) return result;
}
}
if (result.length>0) break;
}
} catch(e){result = e.message}
return result;
}Se usan las siguientes funciones:
getConnectedComponents()para obtener los componentes conectados que vimos al inicio en este tema.getEdges()para obtener las aristas del grafo.combine(list, k)para obtener las combinaciones de una lista de nodos, con el código que vemos a continuación.
function combine(list=[], k=0, n=list.length, res=Array.from({length:k}, ()=>""), result=[], n0=list.length, k0=res.length){
try {
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;
}El funcionamiento es obtener los componentes conectados del grafo inicial y hacer un bucle que itere por tamaños de conjuntos separadores de aristas para ir probando aquellas que incrementen el número de componentes conectados.