Generar nuevos grafos 2
Nuevo grafo Kneser
En el asistente de generación de Grafos SVG que se accede con generamos nuevos grafos. En el tema anterior vimos los nuevos grafos simples, en este veremos algunos más avanzados.
El grafo de Kneser n, k es un grafo no dirigido que tiene tantos nodos como el resultado del binomial ❨ nk ❩, que solemos escribir también como C(n, k), donde dos nodos están conectados sí y sólo sí están en subconjuntos disjuntos de las combinaciones resultantes de C(n, k).
Un grafo Kneser no puede ser dirigido arriba o abajo pues no cumpliría la definición. Por ejemplo, si los subconjuntos A = {0, 1, 2} y B = {3, 4, 5} son dos combinaciones de las generadas por C(6, 3) sobre el conjunto de índices M = {0, 1, 2, 3, 4, 5}, dado que A y B son disjuntos, hemos de encontrar las aristas A-B y también B-A en el grafo no dirigido. E incluso A🡒B y B🡒A en el grafo todo dirigido o con aristas dobles. Pero si, por ejemplo, sólo existe A🡒B y no B🡒A como en un grafo dirigido arriba o abajo, estaremos incumpliendo la definición. Podríamos denominarlos grafos Kneser dirigidos, pero sin olvidar que no son verdaderos grafos Kneser. Esto se advierte en la aplicación en un comentario, como se observa en la Figura.
Puede encontrar információn teórica en Kneser graph de Wolfram MathWorld.
En la Figura vemos un grafo Kneser n=5, k=2 no dirigido.
0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0
Esta es la matriz de adyacencia resultante al aplicar la función generateKneserGraph({n:5, k:2, direction:"undirected"}).
Cada nodo tiene un grado de C(n-k, k), en este caso C(3, 2) = 3 como se observa al tener cada nodo 3 aristas que conectan con otros tantos nodos.
A la matriz de adyacencia anterior podemos aplicarle un ajuste visual a círculo, con la opción de 2 círculos concéntricos y orden de nodos 0,9,1,5,8,7,4,6,3,2, obteniéndose entonces una vista que es como la del grafo de Petersen.
En la Figura vemos los 6 posibles resultados del grafo de Kneser 5,0; 5,1; 5,2; 5,3; 5,4; 5,5.
El número de nodos son C(5, 0) = 1, C(5, 1) = 5, C(5, 2) = 10, C(5, 3) = 10, C(5, 4) = 5, C(5, 5) = 1.
Con n ≤ 2k el grafo es desconectado, es decir, no tiene aristas. Esto sucede con k = 3, 4, 5 puesto que 5 ≤ 2×3, 5 ≤ 2×4 y 5 ≤ 2×5, obvio este último pues sólo tiene un nodo.
La sucesión 1, 5, 10, 10, 5, 1 son las combinaciones de n=5 elementos tomados según k = 0, 1, 2, 3, 4, 5. En la aplicación Combine Tools calculamos funciones combinatorias como estas combinaciones o binomial, cuya fórmula es la siguiente:
| C(n, k) = | n! |
| k! (n-k)! |
En esa aplicación de combinatoria también podemos obtener la siguiente tabla del binomial, donde observamos la sucesión 1, 5, 10, 10, 5, 1:
| n↓k→ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 1 | 2 | 1 | 0 | 0 | 0 | 0 | 0 |
| 3 | 1 | 3 | 3 | 1 | 0 | 0 | 0 | 0 |
| 4 | 1 | 4 | 6 | 4 | 1 | 0 | 0 | 0 |
| 5 | 1 | 5 | 10 | 10 | 5 | 1 | 0 | 0 |
| 6 | 1 | 6 | 15 | 20 | 15 | 6 | 1 | 0 |
| 7 | 1 | 7 | 21 | 35 | 35 | 21 | 7 | 1 |
Si M = {0, 1, 2, 3, 4} es el conjunto de índices y n=5, k=2 entonces las combinaciones son estos C(5, 2) = 10 subconjuntos:
{{0, 1}, {0, 2}, {0, 3}, {0, 4}, {1, 2},
{1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}
Si a cada uno de subconjuntos le asignamos un nodo en el grafo y luego interseccionamos el producto cartesiano poniendo un "1" cuando dos subconjuntos son disjuntos, obtenemos los valores de esta tabla:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ||
|---|---|---|---|---|---|---|---|---|---|---|---|
| {0,1} | {0,2} | {0,3} | {0,4} | {1,2} | {1,3} | {1,4} | {2,3} | {2,4} | {3,4} | ||
| 0 | {0,1} | 1 | 1 | 1 | |||||||
| 1 | {0,2} | 1 | 1 | 1 | |||||||
| 2 | {0,3} | 1 | 1 | 1 | |||||||
| 3 | {0,4} | 1 | 1 | 1 | |||||||
| 4 | {1,2} | 1 | 1 | 1 | |||||||
| 5 | {1,3} | 1 | 1 | 1 | |||||||
| 6 | {1,4} | 1 | 1 | 1 | |||||||
| 7 | {2,3} | 1 | 1 | 1 | |||||||
| 8 | {2,4} | 1 | 1 | 1 | |||||||
| 9 | {3,4} | 1 | 1 | 1 | |||||||
0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0
El resultado es precisamente la matriz de adyacencia que vimos más arriba.
[[0,7], [0,8], [0,9], [1,5], [1,6], [1,9], [2,4], [2,6], [2,8], [3,4], [3,5], [3,7], [4,2], [4,3], [4,9], [5,1], [5,3], [5,8], [6,1], [6,2], [6,7], [7,0], [7,3], [7,6], [8,0], [8,2], [8,5], [9,0], [9,1], [9,4]]
Relacionando los índices en la tabla donde aparece un "1" obtenemos esta lista de aristas.
Importamos esa lista de aristas tal como vemos en la Figura, tras lo cual hacemos un ajuste visual a círculo, con 2 círculos concéntricos y el orden de nodos que ya vimos 0,9,1,5,8,7,4,6,3,2, obteniendo el mismo grafo de la Figura.
El grafo Kneser 5,2 sin ajuste visual se observa en la Figura, que podemos importar en la aplicación a partir de la matriz de adyacencia que ya vimos antes. La aplicación hace un ajuste visual a círculo, para lo cual dispone las opciones radio del círculo y orden, tomando valores none, ciclo Hamiltoniano, círculos concéntricos, orden inverso, orden par impar, orden impar par. Para n=5, k=2 el valor círculos concéntricos aplicará el orden 0,9,1,5,8,7,4,6,3,2 que ya hemos visto para obtener el equivalente al Grafo de Petersen.
Se conjetura que para n > 2k, a excepción de Kneser 5,2, el grafo Kneser tiene un ciclo Hamiltoniano, uno de los valores que podemos usar para un ajuste visual del grafo Kneser 6,2 de la Figura. El Ciclo Hamiltoniano también es un algoritmo que puede ejecutar en la sección de acciones, resaltándose el ciclo con colo rojo y que bordeará el círculo del ajuste visual.
Tras generar el Kneser 6,2 y ejecutar el algoritmo ciclo Hamiltoniano, hemos reducido el radio de los nodos (nodeRadius = 2) y anulado el texto de los nodos (nodeValueAuto = none), con lo que se obtiene el siguiente JSON que puede usar para importar en la aplicación.
{"nodes":[
{"index":0,"nodeOffset":"35.83","parent":[{"index":-1}]},
{"index":1,"nodeOffset":"-10.56 13.23","parent":[{"index":-1}]},
{"index":2,"nodeOffset":"42.28 44.18","parent":[{"index":-1}]},
{"index":3,"nodeOffset":"15.56 13.23","parent":[{"index":-1}]},
{"index":4,"nodeOffset":"-7.32 72.36","parent":[{"index":-1}]},
{"index":5,"nodeOffset":"81.45 2.64","parent":[{"index":2},{"index":3},{"index":4}]},
{"index":6,"nodeOffset":"42.64 54.13","parent":[{"index":1},{"index":3},{"index":4}]},
{"index":7,"nodeOffset":"59.87 35","parent":[{"index":1},{"index":2},{"index":4}]},
{"index":8,"nodeOffset":"-18.5 35","parent":[{"index":1},{"index":2},{"index":3}]},
{"index":9,"nodeOffset":"23.32 -21.54","parent":[{"index":0},{"index":3},{"index":4},{"index":7},{"index":8}]},
{"index":10,"nodeOffset":"-41.83 19.18","parent":[{"index":0},{"index":2},{"index":4},{"index":6},{"index":8}]},
{"index":11,"nodeOffset":"-19.46 54.13","parent":[{"index":0},{"index":2},{"index":3},{"index":6},{"index":7}]},
{"index":12,"nodeOffset":"-43.74 47.36","parent":[{"index":0},{"index":1},{"index":4},{"index":5},{"index":8},{"index":11}]},
{"index":13,"nodeOffset":"-67.36 2.64","parent":[{"index":0},{"index":1},{"index":3},{"index":5},{"index":7},{"index":10}]},
{"index":14,"nodeOffset":"-54.68 -21.54","parent":[{"index":0},{"index":1},{"index":2},{"index":5},{"index":6},{"index":9}]}
],
"config":{
"nodeValueAuto":"none",
"nodeRadius":2,
"algorithm":"Hamiltonian cycle (Backtracking)"
}}
En Wolfram Cloud podemos ejecutar el Kneser 5,2 con el código Graph[GraphData[{"Kneser", {5, 2}}], s], usando el recurso GraphData[] que permite generar multitud de grafos.
El código Wolfram siguiente presentará el grafo de la Figura, que es equivalente al que obtuvimos en la aplicación. En la variable s intentamos asimilar un estilo parecido a nuestro grafo, para lo cual usamos el recurso Graph[].
s = {ImageSize -> 250,
VertexSize -> {"Scaled", 0.13},
VertexLabels ->Placed["Name", Center],
VertexLabelStyle -> Directive[Black,17.5],
EdgeLabelStyle -> Directive[Black,17.5,Bold],
VertexStyle -> White, EdgeStyle -> {{Black,Thickness[0.005]}}};
Graph[GraphData[{"Kneser", {5, 2}}], s]
Dijimos que un grafo Kneser no puede ser dirigido abajo o arriba, como el de la Figura generado en la aplicación. En Wolfram no es posible poner aristas dirigidas en un Kneser, ni siquiera con algo como Graph[GraphData[{"Kneser", {6, 1}}], DirectedEdges->True, s] pues lo ignorará.
La función JavaScript para generar el grafo Kneser es generateKneserGraph() que vemos a continuación:
function generateKneserGraph({n=0, k=0, direction="none"}) {
let dev = {error: "", matrix: []}, temp;
try {
let list = Array.from({length: n}, (v,i) => i);
let result = combine(list, k);
let m = result.length;
let subsets = result.map(v => new Set(v));
dev.matrix = Array.from({length: m}, () => Array.from({length: m}, () => 0));
for (let i=0; i<m; i++) {
for (let j=0; j<i; j++) {
if (subsets[i].intersection(subsets[j]).size===0) {
if (["undirected", "directed-up"].includes(direction))
dev.matrix[i][j] = 1;
if (["undirected", "directed-down"].includes(direction))
dev.matrix[j][i] = 1;
}
}
}
} catch(e){dev.error = `#Error generateKneserGraph(): ${clean(e.message)}`}
return dev;
}Usa la función combine(list, k) de la aplicación Combine Tools para obtener las combinaciones sin repetición. Esa función combinatoria devuelve el resultado como Arrays. Se obtienen los subconjuntos en Arrays que luego pasamos a conjuntos (Set de JavaScript). Luego filtramos los disjuntos para agregar los nodos con ayuda de intersection() del prototipo de Set.
function combine(list=[], k=0, n=list.length, res=[], result=[], n0=list.length){
if (k===0){
result.push([...res]);
} else if (n>0) {
res.push(list[n0-n]);
combine(list, k-1, n-1, res, result);
res.pop();
combine(list, k, n-1, res, result);
}
return result;
}Nuevo grafo Johnson
Un grafo Johnson n, k tiene sus nodos dados por las subconjuntos de las combinaciones del conjunto de índices M = {0, 1, 2, 3, ..., n-1} que expresamos como binomial ❨ nk ❩ y que solemos escribir también como C(n, k), con dos nodos conectados sí y sólo sí la intersección de los subconjuntos tiene un tamaño k-1.
Puede ver más información en Johnson Graph de Wolfram MathWorld.
Un grafo Johnson no puede ser dirigido arriba o abajo pues no cumpliría la definición. Si una arista entre dos nodos A y B cumple la definición tendrá que existir la arista A-B y B-A, o incluso A🡒B y B🡒A, por lo que el grafo deber ser necesariamente no dirigido o o todo dirigido, pero nunca dirigido arriba o abajo. En caso de permitirse podríamos hablar de grafo Johnson dirigido, pero sin olvidar que no son verdaderos grafos Johnson. Esto se advierte en la aplicación con un texto, como se observa en la Figura.
En la Figura vemos un grafo Johnson 5,2.
0 1 1 1 1 1 1 0 0 0 1 0 1 1 1 0 0 1 1 0 1 1 0 1 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 0 1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 1 1 0 0 1 1 0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0
Esta es su matriz de adyacencia, tal como sale de la función generateJohnsonGraph({n=5, k=2, direction="none"}) que veremos más abajo.
Si M = {0, 1, 2, 3, 4} es el conjunto de índices y n=5, k=2 entonces las combinaciones son estos C(5, 2) = 10 subconjuntos:
{{0, 1}, {0, 2}, {0, 3}, {0, 4}, {1, 2},
{1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}
Si a cada uno de subconjuntos le asignamos un nodo en el grafo y luego hacemos el producto cartesiano poniendo un "1" cuando la intersección entre dos subconjuntos tiene tamaño k-1 = 2-1 = 1 obtenemos los valores de esta tabla:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ||
|---|---|---|---|---|---|---|---|---|---|---|---|
| {0,1} | {0,2} | {0,3} | {0,4} | {1,2} | {1,3} | {1,4} | {2,3} | {2,4} | {3,4} | ||
| 0 | {0,1} | 1 | 1 | 1 | 1 | 1 | 1 | ||||
| 1 | {0,2} | 1 | 1 | 1 | 1 | 1 | 1 | ||||
| 2 | {0,3} | 1 | 1 | 1 | 1 | 1 | 1 | ||||
| 3 | {0,4} | 1 | 1 | 1 | 1 | 1 | 1 | ||||
| 4 | {1,2} | 1 | 1 | 1 | 1 | 1 | 1 | ||||
| 5 | {1,3} | 1 | 1 | 1 | 1 | 1 | 1 | ||||
| 6 | {1,4} | 1 | 1 | 1 | 1 | 1 | 1 | ||||
| 7 | {2,3} | 1 | 1 | 1 | 1 | 1 | 1 | ||||
| 8 | {2,4} | 1 | 1 | 1 | 1 | 1 | 1 | ||||
| 9 | {3,4} | 1 | 1 | 1 | 1 | 1 | 1 | ||||
Los valores de la tabla anterior son los mismos que los de la matriz de adyacencia que vimos más arriba. En la aplicación podemos exportar la lista de aristas, que coincide con las de la tabla donde hay un "1":
[[0,1], [0,2], [0,3], [0,4], [0,5], [0,6], [1,2], [1,3], [1,4], [1,7], [1,8], [2,3], [2,5], [2,7], [2,9], [3,6], [3,8], [3,9], [4,5], [4,6], [4,7], [4,8], [5,6], [5,7], [5,9], [6,8], [6,9], [7,8], [7,9],[8,9]]
Recordemos que la anterior lista de aristas está en modo compacto para un grafo no dirigido, por lo que cuando hablamos de [i, j] se entenderá que existe también la arista [j, i]. Ver más en la estructura de datos lista de aristas.
Las funciones que generan nuevos grafos siempre devuelven una matriz de adyacencia. Importando en la aplicación la matriz de adyacencia del grafo Johnson 5,2 obtenemos el grafo en la parte superior de la Figura. La aplicación realiza un ajuste visual a círculo usando la opción radio para presentar los nodos en círculo. La opcion orden toma valores none, ciclo Hamiltoniano, círculos concéntricos, orden inverso, orden par impar, orden impar par.
Todos los grafos Johnson tiene un ciclo Hamiltoniano. En la presentación inferior de la Figura hemos aplicado la opción ciclo Hamiltoniano que aplica el orden 0, 1, 2, 3, 6, 4, 7, 8, 9, 5, observando que las aristas cubren la circunferencia, a diferencia del de la Figura presentado con orden ninguno, que viene a ser el orden natural 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
Las combinaciones de n=5, k=2 son la sucesión 1, 5, 10, 10, 5, 1. En la Figura vemos los grafos Johnson generados para esos seis casos, aplicando orden ciclo Hamiltoniano en todos los casos. En la Figura vemos como presenta Wolfram el 5,2 usando el código que se expone más abajo.
El código Wolfram que genera el Johnson 5,2 es Graph[GraphData[{"Johnson", {5, 2}}], s], usando el recurso GraphData[].
s = {ImageSize -> 250, VertexSize -> {"Scaled", 0.13}, VertexLabels ->Placed["Name", Center],
VertexLabelStyle -> Directive[Black,17.5], EdgeLabelStyle -> Directive[Black,17.5,Bold],
VertexStyle -> White, EdgeStyle -> {{Black,Thickness[0.005]}}};
Graph[GraphData[{"Johnson", {5, 2}}], s]Se observa que Wolfram usa el orden de nodos 1, 2, 8, 9, 4, 7, 5, 6, 10, 3 que se corresponde con un ciclo Hamiltoniano. En base cero ese orden es 0, 1, 7, 8, 3, 6, 4, 5, 9, 2. Si hacemos un ajuste visual al grafo obtenido con la matriz de adyacencia que vimos más arriba, usando este orden de nodos, veremos que las aristas se posicionan sobre la circunferencia. Y más arriba teníamos otro ciclo 0, 1, 2, 3, 6, 4, 7, 8, 9, 5, con lo que hay más de un ciclo Hamiltoniano en los grafos Johnson, al menos en este 5,2.
Los grafos Johnson n,1 y n,n-1 son también grafos completos, como el 20,1 de la Figura. Hemos aplicado nodeRadius = 2 y nodeValueAuto = none que no muestra las etiquetas de los nodos.
Hemos dicho que un verdadero grafo Johnson no puede ser dirigido. En cualquier caso la aplicación permite aplicar dirección, como el 4,2 dirigido arriba de la Figura.
El código de la función JavaScript para generar un grafo Johnson es generateJohnsonGraph(), donde obtenemos las combinaciones y luego filtramos aquellas cuya intersección tenga un tamaño k-1 como explicamos más arriba:
function generateJohnsonGraph({n=0, k=0, direction="none"}) {
let dev = {error: "", matrix: []}, temp;
try {
let list = Array.from({length: n}, (v,i) => i);
let result = combine(list, k);
let m = result.length;
let subsets = result.map(v => new Set(v));
dev.matrix = Array.from({length: m}, () => Array.from({length: m}, () => 0));
for (let i=0; i<m; i++) {
for (let j=0; j<i; j++) {
if (subsets[i].intersection(subsets[j]).size===k-1) {
if (["undirected", "directed-up"].includes(direction))
dev.matrix[i][j] = 1;
if (["undirected", "directed-down"].includes(direction))
dev.matrix[j][i] = 1;
}
}
}
} catch(e){dev.error = `#Error generateJohnsonGraph(): ${clean(e.message)}`}
return dev;
}Usa la función combine(list, k) de la aplicación Combine Tools para obtener las combinaciones sin repetición.
function combine(list=[], k=0, n=list.length, res=[], result=[], n0=list.length){
if (k===0){
result.push([...res]);
} else if (n>0) {
res.push(list[n0-n]);
combine(list, k-1, n-1, res, result);
res.pop();
combine(list, k, n-1, res, result);
}
return result;
}Nuevo grafo Petersen
Un grafo Petersen generalizado n,k es no dirigido con conjunto de nodos N = {u0, ..., un-1, v0,..., vn-1} y donde las aristas pueden ser de tres formas diferentes [ui, ui+1], [ui, vi], [vi, vi+k] con índice 0 ≤ i ≤ n-1. Podrían admitise aristas todo dirigidas A🡘B, pero en ningun caso pueden ser dirigidos arriba o abajo. Podrían denominarse grafos Petersen dirigidos, pero sin perder de vista que no cumplen la definición.
El grafo de Petersen de tamaño 5,2 es un caso particular del grafo de Petersen generalizado que puede ser de tamaño n, k con n≥3 y con 1 ≤ k ≤ ⌊ (n-1)/2 ⌋
El conjunto de nodos Ni y Nj puede ser cualquiera, pero si partimos del conjunto de índices M = {0, 1, 2, ..., n-1} de tamaño n, la definición se convierte en Ni = {0, 1, ..., n-1} y Nj = {n, n+1, ..., 2n-1} siendo todas las aristas de alguna de las formas siguientes:
- Aristas externas [i, i+1] para 0 ≤ i ≤ n-2 y [i, 0] para i = n-1
- Aristas radiales [i, j] para 0 ≤ i ≤ n-1 con j = n+i
- Aristas internas [j, j+k] para n ≤ j ≤ 2n-1
En base a esta definición plantearemos el algoritmo en JavaScript que veremos más abajo.
En la Figura vemos el Grafo Petersen 5,2, que genera la siguiente matriz de adyacencia:
0 1 0 0 1 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 1 1 0 0
Si importamos la matriz de adyacencia anterior obtenemos la vista de la Figura, que sigue siendo Petersen 5,2. Aplicando un ajuste visual a círculo con 2 círculos concéntricos obtendremos la misma vista que el de la Figura. Y eso es lo que hacemos en la aplicación tras obtener la matriz de adyacencia desde la función generatePetersenGraph({n:5, k:2}) que veremos después.
En la Figura vemos los primeros grafos Petersen generalizados desde 3,1 hasta 7,3 que se ajusta a las limitaciones n≥3, 1 ≤ k ≤ ⌊ (n-1)/2 ⌋
Ajustamos los radios de los nodos con nodeRadius = 2 y quitamos el texto con nodeValueAuto = none.
En la Figura vemos el grafo Petersen 5,2 en Wolfram que usa la función PetersenGraph[]. En el código siguiente para ejecutar en Wolfram Cloud pasamos en la variable "s" el estilo para asimilar el aspecto al de nuestra aplicación.
La diferencia con el de la aplicación es que empieza poniendo los nodos interiores y luego los exteriores, en sentido contrario a las agujas del reloj (al revés que en la aplicación) y enumerando nodos desde 1.
Si al generarlo en nuestra aplicación usamos la opción orden inverso, como se observa en la Figura, también obtendremos la disposición de los nodos interiores y exteriores igual que Wolfram (aunque con distinto sentido de giro).
s = {ImageSize -> 250, VertexSize -> {"Scaled", 0.13}, VertexLabels ->Placed["Name", Center],
VertexLabelStyle -> Directive[Black, 17.5], VertexStyle -> White, EdgeStyle -> {{Black,Thickness[0.005]}}};
PetersenGraph[5, 2, s]
Hemos dicho que la definición de un grafo de Petersen es sólo para no dirigidos. Sin embargo la aplicación permite hacerlos dirigidos, como el de la Figura que es dirigido arriba. En Wolfram esto no es posible, ignorando algo como DirectedEdges->True si se lo pasáramos para forzarlo a dirigido.
El código JavaScript para obtener el grafo de Petersen generalizado es generatePetersenGraph():
function generatePetersenGraph({n=0, k=0, direction="none", reverse=false}) {
let dev = {error: "", matrix: []}, temp;
try {
n = Math.max(3, n);
k = Math.max(1, k);
let kMax = Math.floor((n-1)/2);
k = Math.min(k, kMax);
dev.matrix = Array.from({length: 2*n}, () => Array.from({length: 2*n}, () => 0));
if (direction!=="none") {
if (reverse && direction==="directed-up") {
direction = "directed-down";
}
if (reverse && direction==="directed-down") {
direction = "directed-up";
}
//externos
let [from, to, a, b] = reverse ? [n+1, 2*n, n, 2*n-1] : [1, n, 0, n-1];
for (let i=from; i<to; i++) {
if (["undirected", "directed-up"].includes(direction)) dev.matrix[i][i-1] = 1;
if (["undirected", "directed-down"].includes(direction)) dev.matrix[i-1][i] = 1;
}
if (direction==="undirected" || direction==="directed-up" && a>=b || direction==="directed-down" && a<b) {
dev.matrix[a][b] = 1;
} else if (direction==="undirected" || direction==="directed-up" && a<b || direction==="directed-down" && a>=b) {
dev.matrix[b][a] = 1;
}
//radiales
for (let i=0; i<n; i++) {
if (["undirected", "directed-up"].includes(direction)) dev.matrix[n+i][i] = 1;
if (["undirected", "directed-down"].includes(direction)) dev.matrix[i][n+i] = 1;
}
//internos
[from, to, a] = reverse ? [0, n, 0] : [n, 2*n, n];
for (let i=from; i<to; i++){
let j = a + (i+k) % n;
if (direction==="undirected" || direction==="directed-up" && i>=j || direction==="directed-down" && i<j) {
dev.matrix[i][j] = 1;
}
if (direction==="undirected" || direction==="directed-up" && i<j || direction==="directed-down" && i>=j) {
dev.matrix[j][i] = 1;
}
}
}
} catch(e){dev.error = `#Error generatePetersenGraph(): ${clean(e.message)}`}
return dev;
}Nuevo grafo circulante
Un grafo circulante es un grafo no dirigido que se define con n nodos y una lista de índices J = 1, 2, 3, ..., ⌊ n/2 ⌋, de tal forma que sus aristas son [i, i+j] y [i, i-j] para cada 0 ≤ i ≤n y j ∈ J. Cuando la lista de índices contiene todos los elementos hasta ⌊n/2⌋ obtenemos un grafo completo. Y con la lista de aristas J = 1 obtenemos un grafo cíclico.
Con k=i+j o k=i-j podríamos entender que las aristas [i, k] podrían ser no dirigidas o dirigidas i-k, i🡒k, i🡘k, que podríamos denominar como grafo circulante dirigido, pero sin perder de vista que no cumple exactamente la definición.
En la Figura vemos un grafo circulante con n = 6 nodos y la lista J = 1,2,3. Es un grafo completo.
La lista no tiene por que ser con elementos correlativos, como el grafo circulante de la Figura, con n = 8, J = 1,4. Se obtiene el grafo escalera o rueda Möbius.
En la Figura vemos el grafo circulante anterior n = 8, J = 1,4 en Wolfram, que usa la función GraphData[{"Circulant", {8, {1, 4}}}] en el código que se expone a continuación.
s = {ImageSize -> 250, VertexSize -> {"Scaled", 0.13}, VertexLabels ->Placed["Name", Center],
VertexLabelStyle -> Directive[Black, 17.5], VertexStyle -> White, EdgeStyle -> {{Black,Thickness[0.005]}}};
Graph[GraphData[{"Circulant", {8, {1, 4}}}], s]
Si aplicamos un ajuste visual a círculo con 2 círculos concéntricos al grafo que obtuvimos en la Figura obtenemos el de la Figura, que se presenta de forma parecida al de Wolfram anterior.
En la Figura vemos un grafo circulante con n = 20 nodos y la lista J = 1,3,5,7,9. Hemos reducido el radio de los nodos (nodeRadius = 2) y anulado el texto de los nodos (nodeValueAuto = none).
El grafo circulante podría ser dirigido, como el de la Figura que es un circulante n=6, J=1,2 dirigido arriba, aunque no cumple la definición como ya comentamos.
El código JavaScript para generar un grafo circulante es generateCirculantGraph():
function generateCirculantGraph({n=0, list=[], direction="none"}) {
let dev = {error: "", matrix: []}, temp;
try {
let k = Math.floor(n/2);
list = list.slice(0, k);
dev.matrix = Array.from({length: n}, () => Array.from({length: n}, () => 0));
if (direction!=="none") {
for (let i=0; i<n; i++) {
for (let k of list) {
let m = i+k;
if (m>n-1) m = (i+k) % n;
if (direction==="undirected" || direction==="directed-up" && i>=m || direction==="directed-down" && i<m) {
dev.matrix[i][m] = 1;
}
if (direction==="undirected" || direction==="directed-up" && i<m || direction==="directed-down" && i>=m) {
dev.matrix[m][i] = 1;
}
}
}
}
} catch(e){dev.error = `#Error generateCirculantGraph(): ${clean(e.message)}`}
return dev;
}Nuevo grafo platónico
Los Grafos Platónicos son los que se aplican sobre los sólidos Platónicos y son los siguientes:
- Grafo tetraédrico con 4 nodos y 6 aristas.
- Grafo octaédrico con 6 nodos y 12 aristas.
- Grafo cúbico con 8 nodos y 12 aristas.
- Grafo icosaédrico con 12 nodos y 30 aristas.
- Grafo dodecaédrico con 20 nodos y 30 aristas.
Aplicando ajuste visual a rejilla o a círculo a cada uno de los grafos de la Figura, podemos visualizar en la Figura el tetráedrico con 1 círculo concéntrico; el octaédrico con 2 círculos concéntricos; el cúbico con rejilla 4 columnas y orden de nodos 0, 5, 2, 7, 6, 3, 4, 1; el icosaédrico con 1 círculo concéntrico y orden de nodos 0, 1, 2, 3, 4, 9, 7, 11, 5, 10, 8, 6; el dodecaédrico con 1 círculo concéntrico y orden de nodos 0, 1, 2, 3, 4, 5, 6, 7, 17, 15, 13, 11, 19, 9, 8, 18, 16, 14, 12, 10.
Todos los grafos Platonicos tienen un ciclo Hamiltoniano. A los dos últimos anteriores les hemos aplicando el orden de nodos obtenido del algoritmo ciclo Hamiltoniano que se puede ejecutar en la aplicación.
Hemos reducido el radio de los nodos (nodeRadius = 2) y anulado el texto de los nodos (nodeValueAuto = none) para simplificar la presentación.
En la Figura vemos como Wolfram presenta el Platónico dodecaédrico con GraphData["DodecahedralGraph"], con disposición de los nodos diferente a los que vimos antes.
La aplicación genera el código siguiente:
s = {ImageSize -> 250, VertexSize -> {"Scaled", 0.052}, VertexLabels ->Placed["Name", Center],
VertexLabelStyle -> Directive[Black, 0], VertexStyle -> White, EdgeStyle -> {{Black,Thickness[0.005]}}};
Graph[GraphData["DodecahedralGraph"], s]
Hemos eliminado el texto de los nodos y modificado el tamaño de los vértices actuando sobre los controles de la Figura que son factores con valor por defecto 1, de tal forma que factores mayores de 1 incrementan tamaños y menores los decrementan. Podemos actuar sobre el tamaño de la imagen, el de los vértices, el del texto y el grueso de las aristas. También se puede modificar directamente el código.
Los grafos Platónicos deberían ser no dirigidos, pues algunos se obtienen aplicando grafo Petersen o grafo circulante, donde expusimos que se definen no dirigidos.
En cualquier caso si aplicamos dirigido arriba obtenemos al icosaédrico que vemos en la Figura, donde las aristas van de un nodo como mayor índice a otro con menor índice. Wolfram no admite Platónicos dirigidos.
El código JavaScript ejecuta generatePlatonicGraph({typeGraph, direction}) haciendo uso de otros tipos de grafos ya vistos, a excepción del icosaédrico. Devuelve la matriz de adyacencia y el nodo centro y círculos concéntricos, como por ejemplo para el tetraédrico:
{"error":"",
"matrix":
[[0,1,1,1],
[1,0,1,1],
[1,1,0,1],
[1,1,1,0]],
"nodeCenter":0,
"concentric":1}
Necesitamos esos dos parámetros pues tras la obtención de la matriz de adyacencia se aplicará un ajuste visual a círculo pasándole esos valores. En la Figura vemos el resultado de importar en la aplicación la matriz de adyacencia del tetraédrico [[0,1,1,1],[1,0,1,1],[1,1,0,1],[1,1,1,0]] y su resultado posterior al aplicar el ajuste visual con 0 como nodo centro y un círculo concéntrico.
En la ejecución del grafo Platónico usamos los siguientes recursos:
- Tetraédrico con grafo rueda n=4 ejecutándose
generateWheelGraph({n:4, direction}). - Octaédrico con grafo circulante n=6, J=1,2 ejecutándose
generateCirculantGraph({n:6, list:[1,2], direction}). - Cúbico con grafo Petersen n=4, k=1 ejecutándose
generatePetersenGraph({n:4, k:1, direction}). - Icosaédrico directamente con la lista de aristas
[[0,1], [1,2], [2,3], [3,4], [4,5], [5,0], [6,8], [7,9], [8,10], [9,11], [10,6], [11,7], [0,6], [0,11], [0,7], [1,6], [1,7], [1,8], [2,7], [2,8], [2,9], [3,8], [3,9], [3,10], [4,9], [4,10], [4,11], [5,10], [5,11], [5,6]]convirtiéndola en una matriz de adyacencia. - Dodecaédrico con grafo Petersen n=10, k=2 ejecutándose
generatePetersenGraph({n:10, k:2, direction}).
Para el tetraédrico se devuelve con nodo centro 0 y un círculo concéntrico, el octaédrico sin nodo centro (nodeCenter = -1) y un círculo concéntrico y el resto sin nodo centro también pero con dos círculos concéntricos.
El código JavaScript para generar grafos Platónicos es generatePlatonicGraph(), usando los ya vistos generateWheelGraph(), generateCirculantGraph() y generatePetersenGraph.
function generatePlatonicGraph({typeGraph="tetrahedral", direction="undirected"}) {
let dev = {error: "", matrix: [], nodeCenter: -1, concentric: 1}, temp = null;
try {
if (direction==="directed-all") direction = "undirected";
if (typeGraph==="tetrahedral"){
if (temp = generateWheelGraph({n:4, direction}), temp.error) throw new Error(temp.error);
dev.nodeCenter = 0;
} else if (typeGraph==="octahedral"){
if (temp = generateCirculantGraph({n:6, list:[1,2], direction}), temp.error) throw new Error(temp.error);
} else if (typeGraph==="cubical"){
if (temp = generatePetersenGraph({n:4, k:1, direction}), temp.error) throw new Error(temp.error);
dev.concentric = 2;
} else if (typeGraph==="icosahedral") {
let matrix = Array.from({length: 12}, () => 0).map(v => Array.from({length:12}, () => 0));
let arrEdges = [[0,1], [1,2], [2,3], [3,4], [4,5], [5,0], [6,8], [7,9], [8,10], [9,11], [10,6], [11,7], [0,6],
[0,11], [0,7], [1,6], [1,7], [1,8], [2,7], [2,8], [2,9], [3,8], [3,9], [3,10], [4,9], [4,10], [4,11],
[5,10], [5,11], [5,6]];
for (let edge of arrEdges) {
let [i, j] = edge;
if (direction==="undirected" || direction==="directed-up" && i>=j || direction==="directed-down" && i<j) {
matrix[i][j] = 1;
}
if (direction==="undirected" || direction==="directed-up" && i<j || direction==="directed-down" && i>=j) {
matrix[j][i] = 1;
}
}
temp = {matrix};
dev.concentric = 2;
} else if (typeGraph==="dodecahedral") {
if (temp = generatePetersenGraph({n:10, k:2, direction}), temp.error) throw new Error(temp.error);
dev.concentric = 2;
}
if (temp!==null) dev.matrix = temp.matrix;
} catch(e){dev.error = `#Error generatePlatonicGraph(): ${clean(e.message)}`}
return dev;
}Nuevo grafo permutación cíclica
El grafo de una permutación cíclica representa en forma de grafo los ciclos y puntos fijos de una permutación cíclica. En la Figura generamos el grafo de la permutación cíclica (0 4 5)(2 6 3 7).
Es necesario fijar el número de nodos que en el ejemplo de la Figura es 8, pues hace referencia a los elementos M = {0, 1, 2, 3, 4, 5, 6, 7}. Así con la permutación (0 4 5)(2 6 3 7) se entiende que los índices que falten si no se explicitan son los puntos fijos, con lo que esa permutación equivale a (0 4 5)(2 6 3 7)(1).
El orden de los ciclos puede ser cualquiera, por lo que la permutación anterior podría escribirse con otro orden de ciclos como (2 6 3 7)(1)(0 4 5). El orden de los elementos dentro de cada ciclo puede ser distinto siempre que se mantenga el orden cíclico. Usualmente suele usarse la forma canónica, que se basa en usar en cada ciclo el equivalente que tenga el primer menor elemento, ordenar los ciclos por su primer elemento y omitir los puntos fijos. Por ejemplo, la permutación cíclica (5 0 4)(1)(3 7 2 6) es la misma que su forma canónica que hemos visto (0 4 5)(2 6 3 7).
La aplicación si tiene en cuenta el orden de los nodos pero solo a efectos de presentación, pues mantendrá los ciclos. Con orden nodos automático se aplica el mismo orden en el que aparecen en la permutación. Así (0 4 5)(2 6 3 7) tendrá el orden de nodos 0, 4, 5, 2, 6, 3, 7 poniéndose al final los puntos fijos o índices que falten.
En la Figura vemos el grafo de la permutación cíclica del ejemplo (0 4 5)(2 6 3 7) sobre el conjunto de elementos con n=8, es decir, M = {0, 1, 2, 3, 4, 5, 6, 7}. Se aplica orden de nodos igual que la permutación 0, 4, 5, 2, 6, 3, 7 si el control orden nodos automático está activado, como vemos en la Figura.
Otro orden de nodos producirá otras presentaciones, posiblemente con aristas que se cruzan o pasan por debajo de los nosdos, pero siempre se mantendrán los ciclos. Vemos que la arista "5🡒0" queda parcialmente cubierta bajo el nodo "4". Manualmente podemos aplicar una separación de la arista con la propiedad lineOffset.
La forma óptima de presentar visualmente una permutación cíclica es usar el ajuste visual a círculo, pues las aristas no se ocultaran bajo otros elementos ni cruzarán otras aristas si los nodos siguen el orden de la permutación y el círculo tiene un radio adecuado. En la Figura vemos las opciones ajustar a círculo y radio. Si este ajuste está activado se ignora el orden que se haya pasado y se procede a ajustar a círculo aplicando el orden de la permutación a la matriz de adyacencia que se obtiene de la función generatePermutationCyclesGraph({n=0, cycles=[]}) que veremos después.
En la Figura vemos el mismo grafo de la permutación cíclica (0 4 5)(2 6 3 7) del ejemplo anterior, ahora ajustada a círculo, siguiendo el orden de la permutación 0, 4, 5, 2, 6, 3, 7, 1 sin necesidad de explicitarla en la aplicación.
En la Figura vemos el control con autobucles inicialmente desactivado que nos sirve para incluir o excluir los autobucles, que se corresponden con los ciclos de longitud un nodo. En la Figura vemos el grafo que incluye el autobucle "1🡒1" tras activar esa opción.
Hay una diferencia entre generar el grafo con o sin autobucles y la acción de la propiedad showSelfLoops que ya se expuso en un tema anterior.
showSelfLoops Con esta propiedad mostrar autobucles (showSelfLoops), que encontraremos al final de la sección de líneas (aristas) inicialmente activada, se mostrarán los autobucles como una arista usando el tipo de curva cúbica. Si se desactiva no se muestra la arista, pero si la flecha cuando el grafo es dirigido, como se observa en la Figura.
En la Figura vemos como Wolfram Cloud presenta la permutación cíclica (1 5 6)(3 7 4 8), usando la función PermutationCyclesGraph. En primer lugar observamos que en Wolfram siempre empiezan las listas en 1, así que la permutación (0 4 5)(2 6 3 7) se convierte en (1 5 6)(3 7 4 8). Además no presenta el punto fijo (2).
El código para Wolfram Cloud que vemos a continuación usa ResourceFunction["PermutationCyclesGraph"][Cycles[{{1,5,6},{3,7,4,8}}]]. En la Figura ajustamos el tamaño del grafo con el factor 0.7 para asimilarlo al que obtenemos en nuestra aplicación. Luego aplicamos Graph[g,s] para incluirle estilo parecido al de nuestra aplicación.
s = {ImageSize -> 175, VertexSize -> {"Scaled", 0.1105}, VertexLabels ->Placed["Name", Center],
VertexLabelStyle -> Directive[Black, 14.8733], VertexStyle -> White, EdgeStyle -> {{Black,Thickness[0.005882]}}};
g = ResourceFunction["PermutationCyclesGraph"][Cycles[{{1,5,6},{3,7,4,8}}]];
Graph[g,s]
Además de Wolfram Cloud también tenemos el recurso Wolfram Alpha, que con más limitaciones es posible presentar el grafo de una permutación cíclica con una entrada tan simple como permutation (1 5 6)(3 7 4 8). Nos da un montón de información sobre la permutación cíclica, entre ellas el grafo de ciclos que vemos en la Figura y que es también circular, como el obtenido en la aplicación. Aunque también debemos iniciar las listas desde 1 e ignora los puntos fijos.
En la aplicación Combine Tools encontramos en la pestaña Calculadora de ciclos la operación Grafo de una permutación cíclica (Grafo de ciclos), tal como se observa en la Figura.
Esa herramienta usa los mismos recursos que la aplicación para generar el grafo. Se introduce el conjunto de elementos M = {0, 1, 2, 3, 4, 5, 6, 7}, la permutación cíclica σ = (0 4 5)(2 6 3 7), damos el ancho y alto del grafo y seleccionamos la operación grafo de ciclos para producir la estructura de datos JSON y crear el SVG del grafo.
Además se puede configurar la separación de las aristas con la propiedad lineOffset que se indica con desplazamientos líneas del grafo. Vemos que se pasa 5-0: -1.2 indicando que la arista "5🡒0" debe separarse 1.2 unidades de Viewport a la izquierda por el signo negativo, pues positivo se separa a la derecha. A excepción de esta separación de arista, el grafo obtenido es el mismo que el de la Figura.
En esa herramienta no he implementado el ajuste a círculo que vimos antes.
Hay que diferenciar entre permutación de un grafo que es una operación que se aplica sobre un grafo para permutarlo y que vimos en un tema anterior sobre las operaciones que podemos aplicar a un grafo. Y los dos nuevos grafos que estamos viendo en este tema que son nuevo grafo de una permutación cíclica que estamos viendo en este apartado y nuevo grafo de una permutación que veremos después.
El código JavaScript generatePermutationCyclesGraph({n=0, cycles=[]}) para generar el grafo de una permutación cíclica se expone a continuación. Usa la función convertToAdjacencyMatrix() para convertir en matriz de adyacencia una lista de aristas. Devuelve también la permutación cíclica agregando los puntos fijos y ordenando los ciclos por su primer elemento.
function generatePermutationCyclesGraph({n=0, cycles=[]}) {
let dev = {error: "", matrix: [], cycles: []}, temp;
try {
let m = Math.max(n, Math.max(...cycles.flat()));
for (let i=0; i<n; i++) {
if (!cycles.some(v => v.includes(i))) {
cycles.push([i]);
}
}
cycles.sort((v,w) => v[0]-w[0]);
dev.cycles = cycles;
let edges = [];
for (let i=0; i<cycles.length; i++) {
let cycle = cycles[i];
if (cycle.length>1) {
for (let j=1; j<cycle.length; j++) {
edges.push([cycle[j-1], cycle[j]]);
}
edges.push([cycle[cycle.length-1], cycle[0]]);
} else {
edges.push([cycle[0], -1]);
}
}
temp = convertToAdjacencyMatrix({array:edges, mode:"edgeList", compactUndirected:false});
if (typeof temp==="string") throw new Error(temp);
dev.matrix = temp.matrix;
} catch(e){dev.error = `#Error generatePermutationCyclesGraph(): ${clean(e.message)}`}
return dev;
}Nuevo grafo de una permutación
El grafo de una permutación es el que tiene por nodos los elementos de la permutación y sus aristas representan las inversiones de la permutación. Si σ es una permutación hay una inversión entre dos índices i y j si i<j y σ(i)>σ(j).
En la Figura vemos que generamos el grafo de una permutación, obteniéndose la matriz de adyacencia del grafo y la lista de aristas. Esa lista de aristas contiene las inversiones de la permutación.
En la Figura vemos el grafo de la permutación 1, 3, 4, 0, 2, mostrándose a continuación el resultado obtenido. Las inversiones son las aristas del nuevo grafo [[1,0],[3,0],[3,2],[4,0],[4,2]], a las que en la aplicación agregamos aristas a nodos raíces [0,-1],[2,-1]. No es estrictamente necesario agregar estos enlaces a nodos raíces, pues si importamos la lista de aristas obtenida de las inversiones, la aplicación agregará esos enlaces.
{"error":"",
"matrix":[[0,1,0,1,1],[1,0,0,0,0],[0,0,0,1,1],[1,0,1,0,0],[1,0,1,0,0]],
"edges":[[1,0],[3,0],[3,2],[4,0],[4,2],[0,-1],[2,-1]]}
En la Figura vemos el grafo de la permutación 2, 4, 5, 1, 3 obtenida en Wolfram Cloud, que basada en índices que empiezan en 1 es la misma que la de la permutación 1, 3, 4, 0, 2 con índices que empiezan en 0 que vemos en Figura obtenida en nuestra aplicación, aunque la ubicación de lo nodos sea distinta.
El código para Wolfram Cloud que exponemos a continuación usa el recurso PermutationGraph, encontrando más información en Permutation Graph de Wolfram MathWorld.
s = {ImageSize -> 250, VertexSize -> {"Scaled", 0.13}, VertexLabels ->Placed["Name", Center],
VertexLabelStyle -> Directive[Black, 17.5], VertexStyle -> White, EdgeStyle -> {{Black,Thickness[0.005]}}};
g = ResourceFunction["PermutationGraph"][{2,4,5,1,3}];
Graph[g, s]Hay que diferenciar entre permutación de un grafo que es una operación que se aplica sobre un grafo para permutarlo y que vimos en un tema anterior sobre las operaciones que podemos aplicar a un grafo. Y los dos nuevos grafos que estamos viendo en este tema que son nuevo grafo de una permutación cíclica que vimos en el apartado anterior y nuevo grafo de una permutación de este apartado.
A continuación exponemos el código JavaScript de la función eneratePermutationGraph(). Usa la función convertToAdjacencyMatrix() para convertir en matriz de adyacencia una lista de aristas.
function generatePermutationGraph({permutation=[]}) {
let dev = {error: "", matrix: [], edges: []}, temp;
try {
let n = Math.max(...permutation) + 1;
let list = Array.from({length: n}, (v,i) => i);
if (permutation.toSorted((v, w) => v-w).join(",")!==list.join(",")) {
throw new Error(`missing elements 0,1,2,...,n in the permutation`);
}
function inversions(permutation=[], list=[]) {
let inversions = [];
let m = list.length;
for (let i=0; i<m-1; i++){
for (let j=i+1; j<m; j++) {
if (permutation[i]>permutation[j]){
inversions.push([permutation[i], permutation[j]]);
}
}
}
return inversions;
}
dev.edges = inversions(permutation, list);
let vertexs = [...new Set(dev.edges.map(v => v[0]))].toSorted();
for (let i=0; i<n; i++) {
if (!vertexs.includes(i)) dev.edges.push([i, -1]);
}
temp = convertToAdjacencyMatrix({array:dev.edges, mode:"edgeList", compactUndirected:true});
if (typeof temp==="string") throw new Error(temp);
dev.matrix = temp.matrix;
} catch(e){dev.error = `#Error generatePermutationGraph(): ${clean(e.message)}`}
return dev;
}Inversiones de una permutación
En la aplicación Combine Tools tenemos una parte destinada a la calculadora de permutaciones cíclicas, donde podemos realizar operaciones diversas, entre las que está la operación inversiones de una permutación. Lo que sigue se explica en ese tema, exponiéndolo aquí para tratar de explicar como las inversiones de una permutación nos devuelve directamente una lista de aristas para construir el grafo de la permutación.
En notación de permutaciones cíclicas la permutación del ejemplo 1, 3, 4, 0, 2 se escribe separada por espacios σ = 1 3 4 0 2 en lo que se llama notación en 1 línea.
i 1 2 3 4 5 M(i) 0 1 2 3 4 σ(i) 1 3 4 0 2
En permutación cíclicas los índices i de las listas y permutaciones siempre empiezan en 1. En primer lugar definimos un conjunto de elementos M sobre los que se aplican las permutaciones. Estos elementos se inician en cualquier valor alfanúmerico, pero deben ser correlativos. Podría ser algo como M = {"a", "b", "c", ...}. Como la aplicación de grafos usa indices enteros correlativos que se inician en cero, entonces el conjunto será M = {0, 1, 2, 3, 4} para el ejemplo que estamos viendo. Mientras que el conjunto de índices siempre empiezan en 1, así tenemos que, por ejemplo, M(3) = 2. Para nuestra permutación en notación 1 línea σ = 1 3 4 0 2 enfrentada a los mismos índices i resulta que σ(3) = 4.
En ese tema explicamos como convertimos la notación 1 línea σ = 1 3 4 0 2 en notación en ciclos σ = (0 1 3)(2 4) y que no vamos a detallar aquí. Para llevar a cabo la mayor parte de las operaciones en esa aplicación de la calculadora de ciclos usamos la notación en ciclos.
Siendo M = {0, 1, 2, 3, 4} y la permutación ciclica σ = (0 1 3)(2 4) las inversiones de una permutación cíclica se calcula con la función inversions(σ) = [["1","0"], ["3","0"], ["3","2"], ["4","0"], ["4","2"]]
Si σ es una permutación cíclica hay una inversión entre los índices i y j si i<j y σ(i)>σ(j). La inversión puede representarse como la pareja [i, j] basada en índices o bien como [σ(i), σ(j)] basada en elementos, que es la que usamos en la aplicación. La función Inversiones (B) utiliza el basado en índices.
inversionsB(σ) [[1,4], [2,4], [2,5], [3,4], [3,5]] inversions(σ) [["1","0"], ["3","0"], ["3","2"], ["4","0"], ["4","2"]]
La función inversionsB(σ) devuelve las inversiones basadas en índices i, recordando que los índices en permutaciones cíclicas siempre empiezan en 1 como dijimos más arriba. Observe en la tabla más arriba que enfrenta i con σ(i) que, por ejemplo, i=1 < i=4 y que σ(1)=1 > σ(4)=0 existiendo, por tanto, una inversión en los índices [1, 4]. De igual forma se pueden probar todas las combinaciones entre dos índices i<j y ver que se producen el resto de inversiones cuando σ(i)>σ(j).
Por otro lado inversions(σ) devuelve las inversiones basada en elementos σ(i), donde ahora el elemento puede ser un valor alfanumérico correlativo cualquiera, de ahí que se devuelva entrecomillado. En el ejemplo vista de la primera inversión en índices [1, 4] devolveríamos los elementos ["1","0"].
Para la aplicación de grafos los índices siempre empiezan en 0 y son correlativos, por lo que usaremos las inversiones basadas en elementos donde la lista se define como los enteros correlativos a partir de cero M = {0, 1, 2, 3, 4}, obteniéndose [["1","0"], ["3","0"], ["3","2"], ["4","0"], ["4","2"]], que en la aplicación de grafos se usan como números enteros en lugar de alfanuméricos (String), pues hemos de componer la lista de aristas [[1,0],[3,0],[3,2],[4,0],[4,2],[0,-1],[2,-1]], agregando las aristas a nodos raíces (-1). Y el grafo resultante de importar esta lista de aristas, que son las inversiones de la permutación σ = 1 3 4 0 2, es lo que denominamos grafo de esa permutación.
Nuevo grafo Sudoku
En la Figura vemos como generar un grafo Sudoku de 4×4 o de 9×9. Como expuse en la Aplicación Sudoku, un Sudoku es un juego consistente en un tablero de 9×9 celdas con las restricciones de colocar un número del conjunto {1,2,3,4,5,6,7,8,9} en cada celda debiendo aparecer sólo uno de ellos en cada fila, columna y caja. Una caja es cada uno de los rectángulos de 3×3 celdas. Las cajas se agrupan en filas denominadas bandas y columnas denominadas pilas. El objetivo del juego es rellenar todas las celdas respetando esas restricciones.
Si definimos p = 1, 2, 3, ... podemos construir tableros de Sudoku de forma genérica con dimensiones p2×p2 = 1×1, 4×4, 9×9, 16×16, .... Pero lo usual es que sean de 9×9. En la aplicación de grafos sólo contemplamos 4×4 y 9×9.
En la Figura se presenta el grafo Sudoku de 4×4 generado. Hay aristas entre todos los nodos de cada fila, columna y caja de 2×2.
Las aristas horizontales y verticales aparecen visualmente superpuestas, como se observan separando las verticales de la última columna.
En la Figura vemos el grafo de Sudoku 9×9, aplicando un ajuste visual zoom con valor 75% para reducir el tamaño.
En la Figura vemos el Sudoku Graph en Wolfram usando el recurso ResourceFunction["SudokuGraph"][3] con valor 3 para uno de 32×32 = 9×9. Como es usual en Wolfram, los índices se inician en 1.
En el código siguiente se ajustan de forma automática las medidas de la imagen, nodos, texto y aristas para el Sudoku 9×9 con los valores siguientes. En cualquier caso se puede ajustar cada de una de ellas manualmente.
s = {ImageSize -> 350, VertexSize -> {"Scaled", 0.052}, VertexLabels ->Placed["Name", Center],
VertexLabelStyle -> Directive[Black, 12.249], VertexStyle -> White, EdgeStyle -> {{Black,Thickness[0.0025]}}};
g = ResourceFunction["SudokuGraph"][3];
Graph[g, s]El código JavaScript para generar el grafo Sudoku se expone a continuación:
function generateSudokuGraph({numbers=4}) {
let dev = {error: "", matrix: []}, temp;
try {
let p = numbers;
let q = Math.sqrt(p);
let n = p**2;
dev.matrix = Array.from({length: n}, () => 0).map(v => Array.from({length:n}, () => 0));
for (let i=0; i<n; i++) {
for (let j=0; j<n; j++) {
if (i!==j && (j%p===i%p || Math.floor(i/p)===Math.floor(j/p))) {
dev.matrix[i][j] = 1;
dev.matrix[j][i] = 1;
}
}
}
let boxPivots = [];
for (let k=0; k<q; k++){
let kqp = k*q*p;
for (let m=0; m<q; m++){
let pivot = kqp + m*q;
boxPivots.push(pivot);
}
}
let diagonals = [];
if (p===4) {
diagonals = [[0, 5], [1, 4]];
} else {
diagonals = [
[0, 10], [0, 11], [0, 19], [0, 20],
[1, 9], [1, 11], [1, 18], [1, 20],
[2, 9], [2, 18], [2, 10], [2, 19],
[9, 19], [9, 20],
[10, 18], [10, 20],
[11, 18], [11, 19]
];
}
diagonals.push(...diagonals.map(v => [...v].reverse()));
for (let pivot of boxPivots) {
for (let diagonal of diagonals){
dev.matrix[pivot + diagonal[0]][pivot + diagonal[1]] = 1;
dev.matrix[pivot + diagonal[1]][pivot + diagonal[0]] = 1;
}
}
} catch(e){dev.error = `#Error generateSudokuGraph(): ${clean(e.message)}`}
return dev;
}
El primer bucle del código genera las aristas horizontales y verticales. El resto es para generar las aristas diagonales en cada caja, para lo que guardamos en boxPivots el primer nodo superior izquierda de cada caja (pivotes). No he encontrado una forma automática de definir las diagonales para cualquier tamaño de p, por lo que solo se definen para p=2 y p=3 que da lugar a los Sudokus 4×4 y 9×9.
Como vemos en la Figura observando la primera caja del grafo 9×9, las diagonales son las que se observan en el código [0, 10], [0, 11], [0, 19], ... Luego aplicamos estas diagonales de la primera caja trasladándolas al resto de cajas usando los pivotes de boxPivots.
Coloreado grafo Sudoku
En la sección de acciones de la aplicación encontramos múltiples algoritmos a aplicar a un grafo. Entre ellos están los de coloreado de grafos, donde se trata de colorear todos los nodos de un grafo de tal forma que dos nodos vecinos no tengan el mismo color. Encontraremos los algoritmos greedy, Welsh Powell y Brelaz. Este último es más eficiente, encontrando el coloreado con el menor número de colores.
5 3 0 0 7 0 0 0 0 6 0 0 1 9 5 0 0 0 0 9 8 0 0 0 0 6 0 8 0 0 0 6 0 0 0 3 4 0 0 8 0 3 0 0 1 7 0 0 0 2 0 0 0 6 0 6 0 0 0 0 2 8 0 0 0 0 4 1 9 0 0 5 0 0 0 0 8 0 0 7 9
Como se observa en la Figura, podemos pasar una lista de colores iniciales de tantos números enteros como nodos tenga el grafo, 81 en el caso del grafo Sudoku. Se define una lista de colores coloreado red, blue, green, ... que se hace corresponder con los números 1, 2, 3, ..., de tal forma que si ponemos un 0 en la lista de colores iniciales significará que ese nodo está sin colorear. Para un grafo Sudoku esta lista de colores iniciales viene a ser el Sudoku parcialmente lleno que encontramos en este juego, que podemos denominar tablero inicial.
El campo máximo número de colores puede ser un valor -1 significando que no hay límite para el máximo o en otro caso se utilizará ese valor como límite. Para un grafo Sudoku podemos poner que el máximo número de colores a utilizar serán 9.
En la Figura vemos como el algoritmo Brelaz colorea el grafo Sudoku usando solo 9 colores. Y esto es lo mismo que resolver el juego, pues cada color red, blue, green, yellow, ... indica un número de color {1, 2, 3, ..., 9} que son los números que van en cada casilla del tablero. Vemos que cada fila, columna y caja contiene un color distinto para cada uno de sus 9 nodos.
La aplicación devuelve también el siguiente resultado, donde observamos la asociación de números de colores 1→red, 2→blue, 3→green, 4→yellow, 5→cyan, 6→orange, 7→pink, 8→magenta, 9→lime y el tablero Sudoku finalizado, indicando que se han usado Número de colores = 9.
Time: 37 ms
Colores: 1→red, 2→blue, 3→green, 4→yellow, 5→cyan, 6→orange, 7→pink, 8→magenta, 9→lime
Coloreado (Brelaz): [
5,3,4,6,7,8,9,1,2,
6,7,2,1,9,5,3,4,8,
1,9,8,3,4,2,5,6,7,
8,5,9,7,6,1,4,2,3,
4,2,6,8,5,3,7,9,1,
7,1,3,9,2,4,8,5,6,
9,6,1,5,3,7,2,8,4,
2,8,7,4,1,9,6,3,5,
3,4,5,2,8,6,1,7,9]
Índice del array es el índice del nodo, valor del array es el índice del color
Número de colores = 9
Valor nodo→color ⇒
0→cyan (5), 1→green (3), 2→yellow (4), 3→orange (6), 4→pink (7), 5→magenta (8), 6→lime (9), 7→red (1), 8→blue (2), 9→orange (6), 10→pink (7), 11→blue (2), 12→red (1), 13→lime (9), 14→cyan (5), 15→green (3), 16→yellow (4), 17→magenta (8), 18→red (1), 19→lime (9), 20→magenta (8), 21→green (3), 22→yellow (4), 23→blue (2), 24→cyan (5), 25→orange (6), 26→pink (7), 27→magenta (8), 28→cyan (5), 29→lime (9), 30→pink (7), 31→orange (6), 32→red (1), 33→yellow (4), 34→blue (2), 35→green (3), 36→yellow (4), 37→blue (2), 38→orange (6), 39→magenta (8), 40→cyan (5), 41→green (3), 42→pink (7), 43→lime (9), 44→red (1), 45→pink (7), 46→red (1), 47→green (3), 48→lime (9), 49→blue (2), 50→yellow (4), 51→magenta (8), 52→cyan (5), 53→orange (6), 54→lime (9), 55→orange (6), 56→red (1), 57→cyan (5), 58→green (3), 59→pink (7), 60→blue (2), 61→magenta (8), 62→yellow (4), 63→blue (2), 64→magenta (8), 65→pink (7), 66→yellow (4), 67→red (1), 68→lime (9), 69→orange (6), 70→green (3), 71→cyan (5), 72→green (3), 73→yellow (4), 74→cyan (5), 75→blue (2), 76→magenta (8), 77→orange (6), 78→red (1), 79→pink (7), 80→lime (9)
Hice la aplicación SUDOKU hace ya tiempo para resolver este juego usando una serie de técnicas y, como último recurso, mediante un algoritmo del tipo vuelta atrás. En la Figura puede ver como resolvemos el tablero inicial que antes resolvimos usando el coloreado Brelaz.
5,3,4,6,7,8,9,1,2, 6,7,2,1,9,5,3,4,8, 1,9,8,3,4,2,5,6,7, 8,5,9,7,6,1,4,2,3, 4,2,6,8,5,3,7,9,1, 7,1,3,9,2,4,8,5,6, 9,6,1,5,3,7,2,8,4, 2,8,7,4,1,9,6,3,5, 3,4,5,2,8,6,1,7,9
Obtenemos exactamente la misma solución usando otras técnicas en la aplicación Sudoku, pero por ahora no he implementado el coloreado en esa aplicación, pues como veremos a continuación, el coloreado no resuelve sino los Sudokus más simples.
El coloreado Brelaz sólo resuelve los Sudokus más simples como hemos dicho. En la Figura vemos como el algoritmo no puede resolver el Sudoku siguiente con 26 números iniciales:
2 0 6 3 0 0 8 9 0 0 0 0 0 1 0 6 0 0 0 3 9 0 0 0 0 0 0 3 0 0 6 2 0 1 0 0 1 0 0 0 4 0 0 5 0 0 8 0 0 0 0 0 3 0 0 4 0 0 0 6 0 0 0 6 0 0 5 0 0 0 0 8 8 0 0 0 0 1 0 0 9
2,1,6,3,5,4,8,9,7, 4,5,8,7,1,9,6,2,3, 7,3,9,2,6,8,4,1,5, 3,7,5,6,2,0,1,8,4, 1,0,0,0,4,0,0,5,0, 0,8,0,0,0,0,0,3,0, 0,4,0,0,0,6,0,7,0, 6,0,0,5,0,0,0,4,8, 8,0,0,4,0,1,0,6,9
Cuando sobrepasa los 9 colores máximos que hemos impuesto finalizará la ejecución devolviendo los 10 primeros colores 1→red, 2→blue, 3→green, 4→yellow, 5→cyan, 6→orange, 7→pink, 8→magenta, 9→lime, 10→brown y dejando muchos nodos sin color, con valor 0 en el array de salida. Si no imponemos máximo número de colores o bien imponemos 10 colores, veremos que precisamente necesitará 10 colores para colorearlo, por lo que no será una solución de un Sudoku 9×9.
Se resuelve en la aplicación Sudoku con la solución de la Figura sin usar vuelta atrás
2 1 6 3 5 7 8 9 4 7 5 8 9 1 4 6 2 3 4 3 9 2 6 8 5 7 1 3 9 4 6 2 5 1 8 7 1 6 7 8 4 3 9 5 2 5 8 2 1 7 9 4 3 6 9 4 3 7 8 6 2 1 5 6 7 1 5 9 2 3 4 8 8 2 5 4 3 1 7 6 9
pues encuentra los 55 números restantes con las siguientes técnicas:
Naked single: 34 Hidden single: 21 Hidden pair: 1 Locked: 3 W-wing: 1 Hidden rectangle (I): 2 Finned X-wing: 1 Finned Swordfish: 3 Finned Jellyfish: 1 Finned Franken Swordfish (base): 1 Sashimi Franken Swordfish (base): 1
En Wolfram existe la función SudokuSolve que resuelve los Sudoku. En la Figura vemos la resolución del primer ejemplo.
ResourceFunction["SudokuSolve"][{{5, 3, 0, 0, 7, 0, 0, 0, 0},{6, 0, 0, 1, 9, 5, 0, 0, 0},{0, 9, 8, 0, 0, 0, 0, 6, 0},
{8, 0, 0, 0, 6, 0, 0, 0, 3},{4, 0, 0, 8, 0, 3, 0, 0, 1},{7, 0, 0, 0, 2, 0, 0, 0, 6},{0, 6, 0, 0, 0, 0, 2, 8, 0},
{0, 0, 0, 4, 1, 9, 0, 0, 5},{0, 0, 0, 0, 8, 0, 0, 7, 9}}]
Y en la Figura el segundo ejemplo.
ResourceFunction["SudokuSolve"][{{2, 0, 6, 3, 0, 0, 8, 9, 0}, {0, 0, 0, 0, 1, 0, 6, 0, 0}, {0, 3, 9, 0, 0, 0, 0, 0, 0},
{3, 0, 0, 6, 2, 0, 1, 0, 0}, {1, 0, 0, 0, 4, 0, 0, 5, 0}, {0, 8, 0, 0, 0, 0, 0, 3, 0}, {0, 4, 0, 0, 0, 6, 0, 0, 0},
{6, 0, 0, 5, 0, 0, 0, 0, 8}, {8, 0, 0, 0, 0, 1, 0, 0, 9}}]