HPC. Sistemas RH. Enrutamiento por recorridos hamiltonianos en Dígrafos de Cayley 2-generados del grupo cuaternio generalizado.

Presentación 8 de junio 2015.

Hace 2 años (marzo 2013) propusimos en varias entradas un sistema que organizase todas las comunicaciones entre los nodos o precesadores de un sistema HPC o supercomputador (a través de una red de interconexión simulada por un dígrafo de Cayley bigenerado) en vez de mediante rutas punto a punto obtenidas por algoritmos de camino más corto (shortest path), mediante rutas de recorridos hamiltonianos obtenidas siguiendo el método de nuestra patente. Parece oportuno recordar que actualmente la solución punto a punto por caminos más cortos es la que predomina y se complementa con métodos poco eficientes de comunicación colectiva entre procesadores, dado que en las aplicaciones típicas es más óptimo utilizar el enrutamiento mediante camino más corto que otros. 

A esta propuesta la llamamos Sistemas RH o RH Systems. En esa entrada explicábamos el modelo y demostrábamos como podía funcionar con Digrafos de Cayley bigenerados de grupos cuaternios. Por el camino hablábamos de algunos otros temas más abstractos. Por supuesto, ya sólo el plantearse diseñar este tipo de sistemas RH (que está por ver que tengan interés) no sería posible sin las técnicas de la patente.

Por otra parte la entrada más que para proponer un sistema real (no creo que los grupos cuaternios sean los más adecuados para una red de interconexión real ya que por su estructura seguramente no faciliten demasiado ancho de banda; seguramente los digrafos de cayleybigenerados smooth sean más adecuados, aunque en este caso el problema será el diametro, que se podría atenuar añadiendo más  enlaces) es para ilustrar como funcionan las técnicas de la patente para resolver este tipo de problemas con potenciales aplicaciones reales. 

En la primera nota al margen se comenta que mediante plegamiento de ciclos (ver técnicas de la patente) todo Dígrafo de Cayley del grupo cuaternio, Q4n generalizado, se pliega en un Dígrafo de Cayley del grupo dihédrico de orden m, Dihn. Y con esto se puede obtener una fórmula que permite calcular de manera exacta el número de recorridos hamiltonianos (ciclos y caminos) de Qn  (nótese que, creo recordar, éste resultado es un redescubrimiento). 

En la actualización de 3 de marzo que figura al final de la entrada se determinan (manualmente) todos los recorridos hamiltonianos de Q8, Q12, Q16 y Q20.  

En las actualizaciones de 4 y 5 de marzo que idem, se demuestran algunas de las propiedades (es decir de los parámetros según se definen en la patente) tiene que tener necesariamente Qn: el IAS de todos los Dígrafos de Cayley bigenerados de Qn es siempre necesariamente de orden 4 y en todos los Dígrafos de Cayley bigenerados de Qn, los dos ciclos (de los dos generadores) siempre están entrelazados por ciclos (siempre son cycle-entangled).  

Ésta propiedad de entrelazado de ciclos, reivindicación 5 de la (segunda) solicitud de patente, la rechazada (cycle-entanglement, claim 5), tan concreta y perfectamente definible, de manera absolutamente incontrovertida, y la técnica asociada de plegamiento de ciclos, reinvindicación 6 de la (segunda) solicitud de patente. la rechazada (claim 6), que son tan útiles para resolver éste tipo de problemas tan concretos de manera eficiente, está entre las varias novedades, no obvias y útiles, que hemos aportado en nuestra investigación, que hemos publicado mediante una solicitud de patente y ¡¡¡ QUE UN EXAMINADOR DE LA USPTO, TRAS TRES AÑOS DE TRAMITACIÓN E INCONTABLES DÓLARES INVERTIDOS HA CONSIDERADO QUE NO ERA MATERIA PATENTABLE POR SER UNA IDEA ABSTRACTA !!!. Por increíble que pueda parecer, así ha sido. Parece oportuno recordar también ahora que mediante ésta misma propiedad y técnica hemos resuelto con una simple división que se puede hacer en micro segundos múltiples problemas abiertos que se plantearon la investigación experimental realizada por un prestigioso Profesor de una prestigiosa Universidad norteaméricana en torno a 2003 o 2004: tras unos dos años de computación no consiguieron encontrar una solución (determinar si los casos tenían o no ciclos hamiltonianos).  

Utilizando la función copy a post que nos ofrece WordPress  lo volvemos a publicar tal cual con una mínimas ediciones: he incluido una disgresión en una nota al margen y he puesto títulos a las secciones.  

Aprovechamos para recordar que este blog nació para publicar avances en las investigaciones de lo que en su momento era una solicitud de patente y luego se convirtió en patente concedida. Los primeros meses o incluso años del blog todo fue publicación de investigaciones.  

Recordamos también que como resultado de éstas investigaciones (y de nuevos resultados de otros autores publicados tras la publicación de la solicitud de patente; destacamos uno del gran matemático Helfgott, al que no conozco personalmente y con el  que nunca he contactado) hay novedades importantes que añadir a los resultados de la patente, como por ejemplo  un nuevo parámetro, al que hemos llamado circunferencia o resultados relacionados con la  complejidad computacional del problema. Señalamos que ninguno de éstos nuevos resultados contradice los de la patente.  

Fin de presentación junio 2015.  

1. Presentación de los sistemas RH y algunas ventajas.

En los sistemas RH la red de interconexión es un Dígrafo de Cayley bigenerado (o 2-generado) y todo el enrutamiento de  las comunicaciones entre nodos se realizan mediante Recorridos Hamiltonianos (RH), sean de tipo ciclo o de tipo camino.

Cada ciclo o camino hamiltoniano es una ruta, para cada red de interconexión hay un número máximo de caminos disponibles, y en función del problema que se esté resolviendo (del algoritmo que se esté implementando) se podrán utilizar una o varias de esas rutas.

Cuantas más rutas se utilicen más “ancho de banda” tendrá la red para intercambio de información entre nodos, pero también mayor será el coste  desde el punto de vista energético.  Por ello una de las ventajas de los sistemas RH es que el consumo energético se puede graduar en función de las necesidades.

Un problema similar (hamiltonian decomposition; enlace a un artículo de 2007) se ha estudiado con cierta intensidad  por ingenieros de redes en el contexto de tolerancia a fallos en redes de interconexión (fault-tolerance).

Nota al margen.

Por el camino he (¿re?)-descubierto un resultado que podría ser curioso (mediante la aplicación de uno de los resultados de la patente a los grupos cuaternios generalizados): mediante reducciones (que permiten decidir, generar y contar recorridos hamiltonianos) de Dígrafos de Cayley del Grupo Cuaternio generalizado (o grupos Díciclicos) de orden Q4n a Dígrafos de Cayley de grupos Dihédricos de orden D2n/2=Dn bigenerados por una rotación y una reflexión (por ejemplo Q8–>Dih2, Q12–>Dih3, Q16–>Dih4  etc…, es decir dividiendo por cuatro el número de vértices) que nos permite contar el número exacto de recorridos hamiltonanos (ciclos+caminos) de los Digrafos de Cayley de grupos cuaternios generalizados mediante una fórmula, un monomio de una variable (ver el final de la entrada, parte de actualización del 4 de marzo).

Además de la fórmula, algo para mi casi más sorprendente, ha sido el detalle de que Dígrafos de Cayley de un tipo de grupos con infinitos casos (por ejemplo del Grupo Cuaternio Generalizado) se reducen / pliegan a Dígrafos de Cayley de otro tipo también con infinitos casos (por ejemplo a casos el Grupo Dihédrico). Esto no lo había detectado antes, y bien mirado, no podría ser, en este caso de otra manera, pero puede ser interesante encontrar dos grupos infinitos similares (ver por ejemplo si DC de Grupos Simétricos se reducen a Grupos Simétricos etc…; y ver que otras propiedades se conservan ante el plegamiento).

Por otra parte en este caso la reducción no afecta a la complejidad computacional. Las dos familias son de grupos de orden pequeño (lineal o polinómico) con respecto al grado de las permutaciones. Ya hemos visto lo restrictivas que son las relaciones de la presentación del Grupo de Cuaternios generalizados: sólo admiten un tamaño de IAS, un número de ciclos por uno de los generadores. Sólo dan más “grados de libertad” al otro generador.

No tengo claro si la fórmula obtenida es nueva. Por ejemplo en este paper de 1980 hablan de enumeración de recorridos hamiltonianos en Dígrafos de Cayley bigenerados de grupos metacíclicos, y estos incluyen al grupo cuaternio generalizado, pero ahora mismo no tengo claro si dan una fórmula exacta para recorridos (ciclos + caminos). Lo tengo que leer en profundidad (ya lo conocía; lo cita un autor, uno de cuyos papers leí en profundidad  y que utiliza algunos de los resultados del “recorrido clásico” sobre este problema del que hablamos a continuación; creo que estos dos autores recorrieron de manera independiente, cómo yo más tarde, y seguramente otros antes o despues, este recorrido clásico; yo llegué de manera independiente hasta la generalización del teorema de Rankin que es factible si conoces el teorema para ciclos,  y el dato que los vértices finales tienen que estar en el IAS de la identidad (el special outbound coset); para ir más allá diría que se necesitan más datos experimentales que sólo se pueden generar por ordenador; sin ellos me parece imposible ir más allá), y  creo es muy interesante para los interesados en este campo (Dígrafos de Cayley bigenerados), pero se cita poco, quizás por su antigüedad. El autor, parece que sigue siendo profesor de matemáticas pero inmediatamente despues de publicar el paper abandonó esta línea de investigación (cosa bastante frecuente en este campo;  no sabemos si porque lo encuentran muy fácil o muy difícil o simplemente no interesante). En fin, cómo se puede ver, el autor sigue el “recorrido clásico” (y seguramente el único) para atacar este tipo de  problemas:

–limitarse al caso aparentemente más abordable, el de Digrafos 2-generados.

–utilizar el concepto IAS (para más detalles ver la patente) al que en el artículo llaman outbound coset,

–determinar que un IAS se recorre por un generador o por el otro (lo que otros autores han llamado arc-forcing),

–distinguir entre el IAS de la identidad y todos los otros IAS (aquí lo llaman special outbound coset),

–determinar que los vértices finales tienen que estar dentro del IAS (esto aparece cómo corolario en el paper: the whole product of the ggs must be an element of the special outbound coset, aunque hasta dónde yo se ninguno de los autores que llegaron hasta aquí distinguen entre la forma de los IAS para Dígrafos de grupos abelianos y la forma de todos los no-abelianos (y algunos abelianos), ni da un método rápido para identificar los vértices finales posibles y cuantos puede tener, que son algunas de las contribuciones de la patente, aunque no las principales),

–el famoso teorema de R.A. Rankin para ciclos y su generalización (para el  caso de ciclos no se necesita todo lo anterior, sólo parte).

y  en base a todo esto da una cota superior para el número de recorridos hamiltonianos (empezando por la identidad y expresados en forma de secuencia de generadores) y un método para encontrarlos sobre el que ya hacíamos algún comentario en la patente: simplemente recorrer el cada IAS por un generador o por otro. La cota para superior el número de recorridos hamiltonianos que dan es 2^|V|/|IAS|, múltiplicado s/2 dónde s entiendo que es lo que aquí llamamos el orden del IAS. En el paper a V lo llaman G y |V|/IAS lo llaman t.

En la primera entrada de este blog dimos un método / fórmula que permite calcular una cota superior para el número de recorridos hamiltonianos, basada en nuestro propio algoritmo, que pensamos es bastante más ajustada que esta. Incluso pensamos que para almost all Dígrafos de Cayley bigenerados de los grupos simétricos y alternados, permiten contar el número de recorridos hamiltonianos de manera bastante exacta. Un comentario que hacen en el paper cuadra con esto: the autor knows of not two generated non abelian groups for which the order of the IAS > 2 y el número de caminos hamiltonianos (expresados cómo secuencias de generadores) equals the maximum allowable by theorem 1. 

A continuación un Digrafo de Cayley bigenerado del Grupo Cuaternio de orden 16, es decir de Q16. ¿ Puedes decir cuantos recorridos hamiltonianos (ciclos y caminos) tiene sin necesidad de buscarlos ? Yo si🙂.

Q4*4 = Q16

Actualización 27 de junio. Ya he releído un poco más en profundidad del paper de Housman y no he visto que contenga mi resultado. Fin de actualización.

Fin de nota al margen.

2. El modelo y el problema.

De momento nos centramos en un modelo conexosincrónico y sin “interferencias” y pre-computado.

sincrónico quiere decir que en el tiempo T0 se inician x recorridos en la red,

–iniciándose cada recorrido en un nodo diferente (en otro modelo podría ser aceptable iniciar varios recorridos en un mismo nodo).

–sin “interferencias” quiere decir que se impone la restricción de que dos recorridos no se puedan encontrar en el mismo vértice o arco al mismo tiempo. Aquí hay dos posibilidades de relajación: impedir interferencias en nodos (pero permitirlas en arcos) y viceversa.

pre-computado quiere decir que el objetivo es generar una tabla (de tipo look-up) que contenga la solución de enrutamiento, tabla que se utilizará para organizar las comunicaciones de la red de interconexión. Una alternativa, entiendo que más complicada, es ir generando las diferentes rutas  “adaptivamente“, sobre la marcha.

red conexa quiere decir que con las rutas pre-computadas desde cada punto se pueda llegar a cualquier otro punto con la orientación dada (recordemos que hablamos de dígrafos). Una posibilidad que, en principio, permitiría obviar esta restricción es convertir los dígrafos en grafos. De esta manera todo camino se podría recorrer, de manera alternativa en los dos sentidos (¿ pero sería invertible simultáneamente con los otros también ? No veo ningún motivo para que no sea así)

Estas restricciones se podrán variar para obtener otros modelos en función de necesidades / posibilidades ingenieriles.

Si a cada nodo de la red le asignamos de manera puramente convencional un número entero, entonces una solución de enrutamiento por RH en este modelo sería una lista de RH que cumplan con las restricciones anteriores.

3. Una primera solución trivial al problema y un par de interrogantes.

Ya hemos comentado en una entrada anterior, que si el número de vértices del dígrafo es n, la cota superior (el número máximo) de recorridos hamiltonianos que pueden recorrer simultáneamente el dígrafo sin interferencias en el modelo que estudiamos es exactamente n.

Y de hecho no es difícil ver que cuando existen ciclos hamiltonianos, esta cota se puede alcanzar en la práctica: simplemente a cada nodo se le asigna un recorrido y todos los recorridos siguen la misma  ruta. Es decir se podrían utilizar permutaciones cíclicas de los nodos de la  red: supongamos que el recorrido que empieza por el vértice 1

1->2->3->4->5 ( para simplificar quitamos las flechas: 12345)

describe a un ciclo hamiltoniano en un dígrafo de 5 nodos. Entonces el recorrido que al mismo tiempo empieza por el vértice 2

2->3->4->5->1 (=23451)

es otro ciclo que puede coexistir con el anterior sin interferencias, y lo mismo  34512, 45123  y 51234.

Un solución de enrutamiento sería, según hemos definido anteriormente, la siguiente lista de recorridos hamiltoniandos: 12345, 23451, 34512, 45123, 51234. Este tipo de soluciones se podrían presentar también en forma de cuadrado latino, con al menos una restricción adicional (y diría que es suficiente) a los cuadrados latinos: si en dos columnas adyacentes aparecen los nodos xy, en las mismas dos columnas no deberán aparecer yx). Llamemos a este tipo de soluciones en forma de cuadrados latinos solución del tipo cuadrado latino RH.

Pero esta solución obvia no es del todo satisfactoria: entre otras cosas y principalmente porque dado que todas las comunicaciones punto a punto se tienen que hacer vía recorridos hamiltonianos, sería deseable que entre cualquier par de puntos pase un recorrido hamiltoniano en el que estos dos puntos (cualquiera dos) no estén muy alejados. Sin embargo en el esquema que hemos descrito anteriormente (que podemos llamar enrutamiento RH por permutaciones cíclicas de los nodos) para llegar al antecesor de cualquier nodo habría que pasar por todos los demás nodos.

Por otra parte es posible que el Dígrafo que nos interese no tenga recorridos hamiltonianos. Podría ser un dígrafo con un IAS impar, por ejemplo, y ya sabemos (teorema de Ranking) que en este tipo de Dígrafos no existen ciclos.

Todo esto nos lleva a plantearnos los dos siguientes interrogantes:

–en los casos en los que hay ciclos pero prohibimos la solución de enrutamiento por permutaciones cíclicas, ¿ podemos alcanzar la cota máxima teórica en la práctica también ?

–¿ y en los casos en los que no hay ciclos hamiltonianos ?

Es decir existe una solución de tipo cuadrado latino RH para todo Dígrafo de Cayley bigenerado.  Si la respuesta es negativa, para todo orden existen al menos Dígrafos de Cayley  bigenerados con soluciones de tipo cuadrado latino RH.

4. Contestando a los interrogantes.

Aunque de momento no he estudiado el tema con profundidad no me parece que los interrogantes anteriores tengan una solución obvia. Pero hay una pregunta que ya podemos contestar: (creo) que se puede demostrar fácilmente (manualmente por fuerza bruta) que hay Dígrafos de Cayley Bigenerados que no tienen Cuadrados Latinos RH.

Un contraejemplo es el Digrafo con generadores 12354 y 23145. Aunque las permutaciones son de grado 5, el orden del Dígrafo es 6 (es un producto directo Z3xZ2, conmutativo) y por lo tanto en este caso es factible la técnica de la fuerza bruta.

Si asignamos, de manera puramente convencional, al vértice 12345 la etiqueta 1, a 12354 = 2, a 23154 = 6, a 23145 = 5, a 31245 = 4 y a 31254 = 3, entonces  dos posibles soluciones de enrutamiento de tipo sistema RH, no en forma de Cuadrado Latino RH, sino de rectángulo latino (en el libro Constructions and Combinatorial Problems in Design of Experiments de Raghavarao, en la edición de Dover hablan de estos rectángulos en las páginas 107 a 109, pero no es muy informativo para el tema que nos ocupa) serían [126543, 263415,   632154] y [154326, 215634 y  541263].

Actualización 10 de junio 2015.

No recuerdo como encontré estas soluciones y he estado, por curiosidad, revisando el tema. Debió de ser de manera ad-hoc, las primeras que encontré por fuerza bruta. Por cada vértice inicial hay dos caminos hamiltonianos posibles. Por lo tanto el dígrafo tiene un total de 12 caminos hamiltonianos posibles.

Si llamamos a al generador 1 (la involución) y b al generador 2 (el de orden 3) es fácil ver que, independientemente del vértice en el que empecemos, en éste dígrafo, todos los caminos hamiltonianos se pueden clasificar en dos tipos (en una descripción por arcos): ababab (=d1) y bbabb (=d2) y por lo tanto son similares.

Las dos soluciones combinan 1 d1 y 2 d2.

¿ Existen otros tipos de soluciones de tres caminos ?. Si

[126543,563412, 432156] por ejemplo es una solución con 3 d1.

[154326,263415,415632] es una solución 3 d2, aunque 2 token coinciden en el mismo arco en el mismo  momento y esto está en contra de las restricciones que hemos impuesto al modelo. Sería solución si levantamos ésta restricciones.

[154326,632154,341265] es una solución que combina 2 d2 y 1 d1, con un cruce mismo arco, mismo tiempo y por lo tanto ilegitima.

Con esto agotamos todos los tipos de soluciones posibles de tres recorridos.

¿ Existen soluciones de más de 3 recorridos o caminos ?.

[126543, 263415, 632154, 415632] es una solución de cuatro recorridos, con un cruce mismo arco, mismo  tiempo.  Ilegítima.

Según he comprobado partiendo de las 2 soluciones 1d1/2d2 y de la solución 3d1 que ya hemos dado, no hay soluciones de 4.  Muy posiblemente estas no existen.

Para dar respuesta a estas preguntas se requeriría un estudio más sitemático. Lo dejamos para los lectores. No obstante ya se ve que estudiar los sistemas RH no es sencillo incluso para grafos triviales de 6 vértices.

Fin actualización.

Digo posibles porque ninguna de estas dos soluciones, cómo se verá, cumple con la condición de red conexa. Sin embargo es obvio que cualquier solución que sea Cuadrado Latino si cumpliría con la condición de red conexa que hemos impuesto al modelo. Me queda ahora la duda si para todo Rectángulo Latino esta condición fallaría.  

Por otra parte señalar que no se cuan representativo es este Dígrafo de los que nos interesan, ya que es conmutativo, pero por algo hay que empezar…

5. Explicando los cuadrados latinos.

Por si no ha quedado claro, los rectángulos y cuadrados latinos de los que estamos hablando se deben de  interpretar cómo sigue:

–cada columna representa un momento del tiempo.

–cada fila representa una ruta, ficha o token, que a su vez representa un recorrido hamiltoniano.

–y cada entrada representa la posición (el vértice) ocupada por la ficha x en el momento.

Por ejemplo, si levantamos la restricción de red conexa, para la primera solución del caso anterior tendríamos  la siguiente solución o Tabla de Rutas:

Tiempo 1 Tiempo 2 Tiempo 3 Tiempo 4 Tiempo 5 Tiempo 6
Ruta 1 Vértice 1 Vértice 2 Vértice 6 Vértice 5 Vértice 4 Vértice 3
Ruta 2 Vértice 2 Vértice 6 Vértice 3 Vértice 4 Vértice 1 Vértice 5
Ruta 3 Vértice 6 Vértice 3 Vértice 2 Vértice 1 Vértice 5 Vértice 4
 

En los Sistemas RH ya operativos (implementados desde el punto de vista ingenieril) las rutas, fichas o tokens no serían más que ondas portadoras, o para que se entienda, autobuses (buques) que pueden transportar la información (pasajeros, contenedores llenos de mercancías) que se van generando en los diferentes nodos (casas, fábricas). Cómo es habitual, cada nodo estaría dotado de uno o varios procesadores. Cómo ya hemos comentado, las rutas están pre-establecidas y son repetitivas. Ojo, de momento sólo estoy desarrollando el tema desde el punto de vista matemático; no se si tiene sentido su implementación desde el punto de vista de ingeniería de telecomunicaciones.

7. Buscando métricas para determinar cual es la solución óptima. Según todo lo anterior, el Input para nuestro problema es un Dígrafo de Cayley bigenerado, y el Output es una Tabla de Rutas cómo la mostrada anteriormente (de momento nos valen cuadrados y rectángulos).

Imagino que dado un Dígrafo de Cayley Bigenerado, la solución de enrutamiento RH no es única, es decir para cada dígrafo no hay una única Tabla de Rutas. Y si hay varias soluciones, cómo las comunicaciones punto a punto se realizan a través de las rutas de tipo recorridos hamiltonianos,   podemos añadir una subrutina que permita encontrar una solución óptima para estas comunicaciones punto a punto.

Sobre este tema tengo mucho menos claro  cual sería la métrica relevante. Me  imagino que para cada algoritmo existirá una solución optimizada para comunicaciones punto a punto diferente. En principio, cada nodo tiene almacenado la Tabla de Rutas y cuando quiere enviar una información a otro nodo, en función de la posición del nodo objetivo al que quiere enviar la información, calcula si le conviene coger el primer “autobús” que pase o esperar al siguiente (al final todo se reduce a tiempo de comunicación=tiempo de espera + tiempo de tránsito).

En lo que sigue presentamos un primer intento de subrutina que nos permitiría discriminar entre soluciones de acuerdo con este criterio (cómo primer intento, posiblemente no será la más adecuada). Aprovechamos para mostrar con un ejemplo la importancia de la restricción de red conexa.

Dada la matriz (cuadrada o rectangular) con la Solución de Enrutamiento RH o Tabla de Rutas,  construimos una matriz cuadrada vértices x vértices y a cada par de vértices le asignamos la distancia mínima entre cada par, de entre las distancias que aparezcan en los recorridos o rutas solución.  Interesa encontrar la matriz que tenga una suma de todas sus entradas menor.

Siguiendo el ejemplo anterior a continuación figuran dos tablas:

–la primera tabla es una copia de la de arriba),

–y la segunda es la tabla o  matriz de la  que estamos hablando. Para cada par de vértices se indica con un número entero la distancia mínima entre dos vértices dados en la dirección considerada (número de arcos que un token tiene que recorrer para ir de un vértice a otro) o el hecho de que no se puede ir de un vértice a otro por ninguna de las rutas de la tabla 1 (indicando NO en rojo), lo cúal demostraría que la red, por estas rutas, es inconexa. En algunos casos para cada par se indica la ruta(s) para los que la distancia es mínima.

 TABLA 1 Tiempo 1 Tiempo 2 Tiempo 3 Tiempo 4 Tiempo 5 Tiempo 6
Ruta 1 Vértice 1 Vértice 2 Vértice 6 Vértice 5 Vértice 4 Vértice 3
Ruta 2 Vértice 2 Vértice 6 Vértice 3 Vértice 4 Vértice 1 Vértice 5
Ruta 3 Vértice 6 Vértice 3 Vértice 2 Vértice 1 Vértice 5 Vértice 4
 
 TABLA 2 Vértice 1 Vértice 2 Vértice 3 Vértice 4 Vértice 5 Vértice 6
Vértice 1 0 1 (ruta 1) 5 (ruta 1) 2 (ruta 3) 1 (ruta 3) 2 (ruta 1)
Vértice 2 1 (Ruta 3) 0 2 (ruta 2) 3 (rutas 1 y 2) 2 1
Vértice 3 2 1 0 1 3 NO
Vértice 4 1 NO 1 0 2 NO
Vértice 5 NO NO 2 1 0 NO
Vértice 6 3 2 1 2 1 0

Entonces para la primera métrica que estamos considerando, se sumarían todas las entradas de esta segunda matriz o tabla 2 y se obtiene un número X1. Igualmente se podría construir una Tabla del tipo 2 para la segunda “solución” de este caso, obteniendo una suma para sus entradas de X2. Se seleccionaría la Tabla de Rutas que tenga una matriz cuya suma de entradas sea menor.

Téngase en cuenta que utilizo este caso porque de momento es el único que tengo más o menos analizado. Pero en realidad, si imponemos la restricción de red conexa, al contener NO´s, no nos valdría cómo solución ninguna de las dos presentadas.

6. Un posible método para generar soluciones.

A falta, de momento, de una teoría general sobre este problema, que quizás ni sea necesaria, nos podemos conformar con un método constructivo que permita generar, dado un Dígrafo de Cayley Bigenerado, soluciones de enrutamiento, es decir el tipo de Tablas de Rutas cómo la que acabamos de presentar en el punto anterior, optimizadas además para la comunicación punto a punto. Cómo ya se ha comentado lo máximo y mejor que podemos esperar cómo solución es una tabla cuadrada o cuadrado latino. Y no está claro todavía que nos valga con rectángulos (a lo mejor se puede demostrar que para toda solución de tipo rectángulo,  la red es inconexa).

Al analizar el pequeño caso anterior,   ya he visto que el siguiente método (no tengo claro ahora mismo si es un algoritmo más o menos eficiente o ineficiente, de tipo backtraking  o sólo una heurística), diría que obvio,   puede generar soluciones. Lo explicamos para casos en los que no hay ciclos hamiltonianos. Para generar los recorridos hamiltonianos se aconseja utilizar cómo subrutina el algoritmo de mi  patente🙂, pasando previamente por taquilla claro ;-):

Paso 1. Primer RH. generar un primer RH desde el vértice identidad (se puede elegir cualquiera cómo tal) y colocarlo en la primera fila de una tabla o matriz.

Paso 2. Segundo RH. Desde el segundo vértice del primer RH, el anterior, empezar a generar otro RH (también se debe de utilizar el algoritmo), que sea compatible (que no interfiera) con el anterior. Este RH se irá colocando en la segunda fila y a medida que se va generando se deberá ir comprobando que el siguiente vértice no coincide con el del primer RH y que se cumple la restricción si xy entonces no yx de la que hemos hablado antes. Si en algún momento no se cumple alguno de estos requisitos entonces se prueba la segunda alternativa. Si las dos alternativas fallan, se deberá pasar al vértice siguiente y repetir.

Paso 3. Tercer RH y siguientes. Si el output del paso 2 es otro RH entonces repetimos con el siguiente vértice del primer RH para generar un tercer RH en la tercera fila.

Esta parte del método finaliza cuando se hayan probado todos los vértices. Al final obtenemos bien un cuadrado latino, bien un rectángulo latino,  bien un mensaje de que no hay solución. En cualquiera de los dos primeros casos, se inicia la parte de optimización para comunicaciones punto a punto.

Conclusión / problemas abiertos:

–parece prioritario averiguar si los Rectángulos Latinos pueden ser solución para redes de tipo Dígrado de Cayley bigenerado o no.

–una segunda duda, para los casos en los que si hay ciclos, es si la solución por permutaciones cíclicas, la trivial que ya hemos comentado, es siempre peor (en términos de comunicación punto a punto, con la métrica que hemos dado) que cualquier otra. Igual al final no hay que darle tantas vueltas y esta o es la mejor, o no es mucho peor que la mejor…

Es fácil ver que para todo n, según la métrica que hemos dado, la suma de las entradas de la matriz o tabla 2 será igual a  (n^3 – n^2)/2. Esta es la cifra a batir y diría que si existen soluciones no triviales, tienen que mejorarla. Pero primero hay que demostrar que las soluciones no triviales existen.

Actualización 3 de marzo de 2013.

Sobre el problema de los rectángulos latinos, primero conviene estudiarlo, en general, olvidándonos de que las permutaciones del rectángulo latino representen recorridos hamiltonianos.

En este caso si que parece que los rectángulos puedan ser solución que cumpla con la restricción de red conexa:

Para el grado 3, el par [123, 321] es conexo (y en general, para todo n, [n1 n2…nn, nn…n2n1] es solución. Es decir para todo n hay un rectangulo 2xn conexo.

Para el grado 4, la terna [1234, 3241, 4123] es conexa.

En general, por lo tanto, no parece haber obstáculo para que los rectángulos cumplan con la condición de red conexa. El tema no está tan claro si además las permutaciones del rectángulo representan recorridos hamiltonianos. Para tener una idea sobre esto tengo que analizar más casos pequeños.

Para grupos de orden 6, el único que no es conmutativo es un grafo (sus generadores son dos involuciones) y por lo tanto no nos vale.

Para grupos de orden 8 hay dos que no son conmutativos. El grupo dihédrico (D4, identidad 1234 y generadores 2341 y 3214) y el grupo cuaternio (Q8, identidad 12345678, generadores 25476183, 38527416). Aunque son no conmutativos tampoco son muy representativos ya que los dos están entrelazados.

a) Análisis de Q8.

Empezamos por el segundo. El Dígrafo de Cayley de Q8 tiene 2 IAS /DAS, de orden 4. Cada IAS contiene todas las permutaciones del grupo. Es un dígrado muy entrelazad0 e incluso cycle-entangled. Empezando por la identidad, los recorridos hamiltonianos pueden terminar exactamente en 4 vértices diferentes y existe exactamente un recorrido que termina en cada uno de estos vértices finales, 2 ciclos y 2 caminos (aunque la pura fuerza bruta llevaría a analizar 8! casos, es decir 40320, esto se puede demostrar manualmente en 5-10 minutos utilizando el método de la patente, y, sin el método, entiendo que tampoco debe de ser difícil encontrar todos estos recorridos, ya que el caso es pequeño). En este caso todos los recorridos hamiltonianos son palíndromos si los describimos por la secuencia de generadores.

En la imagen siguiente puedes ver el Dígrafo de Cayley de este grupo.

Cayley_graph_Q8.svg

Si re-etiquetamos los vértices de la siguiente manera, J= 1, -k=2, -J=3, k=4, -i=5, -1=6, i=7 y 1=8, entonces los recorridos son los siguientes:

12763458 (ciclo hamiltoniano)

16523874 (ciclo hamiltoniano)

12345876 (camino hamiltoniano)

16387452 (camino hamiltoniano).

Una vez conocidos estos (la secuencia de generadores) se pueden generar todos los demás. En total hay 32. Nos centramos en los 16 que son caminos. Si al generador de color rojo en el gráfico lo llamamos g1 y al generador de color verde lo llamamos g2 y construimos un cuadrado latino con todos los caminos generados por la secuencia g1g1g1g2g1g1g1 (por simetría, diría que la otra secuencia g2g2g2g1g2g2g2 valdría también) obtenemos la siguiente solución para enrutamiento por Cuadrado Latino. 

12345876

23416587

34127658

41238765

58763412

65874123

76581234

87652341

Es una solución guapa, que a posteriori es casi evidente: hay dos grupos de 4 fichas. Mientras el primer grupo de cuatro fichas se va moviendo de manera coordinada en el cuadrado de fuera, el segundo grupo se mueve de manera coordinada en el cuadrado de dentro y hay un momento en que los dos grupos de fichas, a la vez se cambian de cuadrado y repiten la operación, el primer grupo de 4 fichas pasa a moverse de manera coordinada en el cuadrado de dentro y el segundo en el de fuera. Me pregunto si esta solución vale para el grupo de cuaternios generalizado.

A group is called a generalized quaternion group or dicyclic group if it has a presentation[4]

\langle x,y \mid x^{2n} = y^4 = 1, x^n = y^2, y^{-1}xy = x^{-1}\rangle.\,\!

for some integer n ≥ 2. This group is denoted Q4n and has order 4n.

Luego analizaremos Q12 y Q16.

Antes veamos cómo se comporta esta solución con respecto a la comunicación punto a punto. No está mal: 112. La mitad de la solución cíclica trivial, que sería 224. De nuevo, por simetría entiendo que la solución g2g2g2g1g2g2g2 daría el mismo valor, 112.

¿ Podemos mejorar este valor con alguna otra solución ? Despúes de analizar Q12 y Q16, me da la impresión (que podría ser falsa) que esta segunda solución trivial no va a escalar bien a este respecto. Siempre va a ser mejor que la primera trivial, la cíclica, pero será mejorable. Repito, de momento sólo una impresión.

b) Análisis de Q12.

Este dígrafo tiene 12 vértices, 1 generador, g1, es de orden 6 y el otro, g2, de orden 4, ciclo de 6, es cycle-entangled (se puede reducir a uno con generadores de ordenes 3 y 2 respectivamente). Tiene 3 IAS de orden 4 cada uno. Y por lo tanto los recorridos hamiltonianos pueden terminar también en cuatro vértices posibles.

No se por qué a Q12 lo llaman díciclico de orden 12 en vez de cuaternio. Nosotros seguiremos Puedes ver dos imágenes de Q12 a continuación (pido perdón al lector por lo artesanal de las imágenes; no he encontrado ninguna en google images y las he tenido que fabricar sobre la marcha…Ya he encontrado una página dónde puedes ver todos los dígrafos de Cayley de orden pequeño, incluido el que nos ocupa).

La primera sería la imagen clásica. Las etiquetas de los vértices son puramente convencionales o arbitrarias. El lector puede comprobar que se cumplen las relaciones descritas en la presentación. Por otra parte en este caso se rompe la simetría que tenía Q8 (ya que los dos generadores eran intercambiables).

Q12

Antes de seguir leyendo, intente el lector encontrar todos los recorridos hamiltonianos (ciclos o caminos) de este dígrafo,  si es que existen, empezando por el vértice 1. Obviamente debe de intentar evitar la fuerza bruta pura (12! = 479.001.600 posibilidades) e incluso una fuerza bruta más sofisticada (se enfrentaría a unas 2^12 = 4096).

En la segunda imagen aparecen los IAS / DAS coloreados (negro, violeta y verde; el verde y el negro no se distinguen mucho).

Es posible que haya una representación gráfica menos engorrosa. Si empezando por el vértice 1, este digrafo tuviese recorridos hamiltonianos, tendrían que terminar necesariamente en los vértices 6, 10 (ciclos), 7 y 3 (caminos).

Grafo de Cayley del Grupo cuaternio de orden 12

–Ya en la representación clásica se ve fácilmente que, si empezamos en el vértice 1, al menos un camino que termina en el vértice 7 existe:

la secuencia de generadores es g1g1g1g1g1g2g1g1g1g1, palíndromica y la de vértices es  12345689-10-11-12-7;

Utilizando el método de la patente se puede demostrar fácilmente que éste es el único recorrido que existe entre 1 y 7) y ahora mismo no veo ninguna razón para que la solución de cuadrado latino dada para Q8 sirva también para Q12.

–Menos obvio, pero muy fáciles de encontrar incluso manualmente con el  método de la patente, es que existe también dos caminos que iniciándose en el vértice 1 terminan en el vértice 3 (en este caso ya no son palíndromos cada uno considerado individualmente, pero sí se puede obtener un camino dándole la vuelta al otro):

Secuencia de generadores: g2g2g2g1g1g2g1g2g1g2g1, y de vértices: 174-10-11-12-568923.

Secuencia de generadores: g1g2g1g2g1g2g1g1g2g2g2 y de vértices: 12-12-7459-10-11-683.

–En cuanto a los ciclos, si empezamos en 1 y terminamos en 6, hay también 2 (que de nuevo se pueden obtener el uno del otro revertiendolos):

Secuencia de generadores: g1g2g1g1g2g1g1g2g1g1g2 y de vértices:  12-12-783459-10-11-6

Secuencia de generadores: g2g1g1g2g1g1g2g1g1g2g1  y de vértices: 1789234-10-11-12-56.

–Y si empezamos en 1 y terminamos en 10, se puede demostrar que tenemos 1 sólo recorrido, 1 ciclo:

Secuencia de generadores:  g1g1g2g1g1g2g1g1g2g1g1 y de vértices: 123-11-12-745689-10.

Por lo tanto, si empezamos por el vértice 1 en total hay 6 recorridos hamiltonianos. Y en total, el dígrafo tiene 72 recorridos hamiltonianos.

c) Análisis de Q16.

En la imagen siguiente se puede ver una representación “clásica”de un Dígrafo de Cayley de Q16 (también llamado Díciclico de Orden 16). La representación no es muy clara. El dígrafo tiene 16 vértices, g1 de orden 8 y g2 de orden 4. 4 IAS/DAS, cada uno de orden 4 (el orden 4 de los IAS / DAS parece común a todos los Qn; un paso siguiente debería ser demostrar que esto tiene que ser necesariamente así, que está implícito en las relaciones). Es cycle-entangled por los dos ciclos (cosa que también parece común  a esta familia de dígrafos y que también habría que demostrar).

(Nota al margen: Ojo, de confirmarse que las dos propiedades anteriores se cumplen para todos los miembros de la  familia (esto ya se ha demostrado, ver la actualización del 4 de marzo de 2013 al final de la entrada), teniendo en cuenta los resultados de la patente ya podemos saber que todos los Dígrafos de Cayley bigenerados de grupos cuaternios generalizados tienen necesariamente ciclos hamiltonianos en los dos vértices posibles: si el IAS es siempre 4 y todos los DC de los cuaternios son cycle-entangled, se obtendrá un dígrafo plegado con un IAS de orden 2 y sabemos que estos siempre tienen ciclos hamiltonianos (ver la última actualización para ver que tipo de Digrafo de Cayley 2-generado se obtiene).

Posiblemente este resultado ya sea conocido por otros medios y utilizando otros métodos; creo recordar que hay un teorema bastante general que incluye estos casos; lo averiguaré:

The generalized quaternion groups have the property that every abelian subgroup is cyclic.[8] It can be shown that a finite p-group with this property (every abelian subgroup is cyclic) is either cyclic or a generalized quaternion group as defined above.[9] Another characterization is that a finite p-group in which there is a unique subgroup of order p is either cyclic or generalized quaternion (of order a power of 2).[10] )

Y en este paper de Glover y Marusic de 2005 comentan que: And finally, perhaps the biggest achievement on the subject is a result of Witte (now Morris) which says that a Cayley (di)graph of any p-group has a Hamilton cycle [37]. El paper 37 es de 1986 y se títula Cayley Digraphs of  primer power order are hamiltonian.  Un resultado potente.

Y un paper reciente del mismo autor títulado 2-generated Cayley digraphs on nilpotent groups have hamiltonian paths.

Estos resultados son potentes pero dicen que tienen ciclos y caminos no que tienen ciclos y caminos en todos los vértices finales posibles. Cuando tenga tiempo tendré que leer en detalle los papers. Fin de la nota al margen).

Bueno, volviendo al tema que nos ocupa, en este caso si el recorrido hamiltoniano empieza en 1 puede terminar en 10, 8 (ciclos), 4 y 14 (caminos).

dic16 modificado

De nuevo se puede ver fácilmente que el camino que termina en 14 existe y es un palíndromo. 12345678-15-16-9-10-11-12-13-14. Se puede demostrar fácilmente que es único. La secuencia de los generadores es obvia, y de nuevo entiendo que aplicando esta secuencia a cada vértice podemos encontramos un conjunto de recorridos hamiltonianos que deben de ser solución de tipo cuadrado latino en el problema que nos ocupa. Diría además que este tipo de caminos siempre existen también en todos los DC de la familia cuaternia (ojo, en este caso no tengo demostración pero es algo obvio y creo que no debería incluso ser difícil de demostrar que siempre es única, ya que visualmente es casi evidente también).

A continuación figura la representación del dígrafo marcando cada uno de los  IAS de un color: negro el IAS de la identidad (vértice 1 por convención), violeta el DAS de la identidad, verde y marrón.

Q16 IAS

En lo que sigue determinamos cuantos y qué recorridos hamiltonianos tiene este dígrafo cuando empieza por 1.

–Vértice inicial 1, vértice final 4. Hay tres en total:

Secuencia generadores: g2g2g2g1g1g1g2g1g1g2g1g1g2g1g1 y secuencia vértices 1-14-5-10-11-12-13-678-15-16-9234.

Secuencia generadores (de nuevo por reversión de la anterior): g1g1g2g1g1g2g1g1g2g1g1g1g2g2g2 y secuencia 123-12-13-14-567-16-9-10-11-2-15-4.

Secuencia generadores: g1g2g1g2g1g2g1g1g1g2g1g2g1g2g1 (palíndromo) y secuencia de vértices: 1-2-13-14-569-10-11-12-72-15-16-34

–Vértice inicial 1, vértice final 10. PDTE.

–Vértice inicial 1, vértice final 8. PDTE.

P.s. viendo el gráfico anterior, me pregunto si el IAS sigue siendo 4 cómo pueden crecer los DC de los cuaternios….Tengo tanta curiosidad que si no fuese tan tarde analizaría Q20. ¿ Quién dijo tarde ?

dic20 MOdf

Cómo se ve el dígrafo es “brumoso” y puedo haberme equivocado al elaborar el IAS basándome en él. Pero parece confirmarse que el IAS de Q20 es también de orden 4 y por lo tanto habrá 5 IAS.

Fin actualización 3 de marzo de 2013. 

Actualización 4 de marzo de 2013. 

Se confirma que el IAS de Q20 es de orden 4 y cycle-entangled por los dos ciclos. Procedo a intentar demostrar que tiene que ser así necesariamente para todo Qn utilizando la presentación del caso generalizado.

Proposición 1: para todo Qn, el IAS /DAS es de orden 4, es decir (x^-1y)^4= (y^-1x)^4= 1

Demostración (para la demostración utilizamos álgebra y damos la estrategia):

Primero se demuestra utilizando las identidades de la presentación y^-1xy=x^-1 e y^4=1 que el exponente no puede ser menor que 4.

Por ejemplo no puede ser 3 dado que entonces  x^-1y=y^4=1 lo cual es contradictorio con la hipótesis de partida (x^-1y)^3=1. En lo que sigue para simplificar anotamos y^-1 cómo y-1.

y-1xy-1xy-1x = 1. Añadimos y a los dos lados y simplificamos obtenemos.

y-1xy-1 = y. Añadimos y a los dos lados y simplificando obtenemos.

y-1x =yy Añadimos y en los dos lados y simplificando obtenemos.

x-1 = yyy. Añadimos y en los dos lados y simplificando obtenemos.

x-1y = yyyy = y^4 = 1 que es contradictorio.

De la  misma manera se puede demostrar que el exponente no puede ser 1 o 2 ni superior a 4, hasta 8 (creo). Se entraría siempre en contradicción con la identidad y^4 =1.

Actualización 5 de marzo (anidada en la actualización del 4 de marzo).  

Ahora hay que demostrar que el exponente de (x^-1) tampoco puede ser múltiplo de 4 (8,12,16 etc…). Esto se puede demostrar de la misma manera anterior y utilizando las relaciones o identidades x^n=y^2 y x^2n=1 para simplificar en la parte de la derecha. De esta manera se puede ver que si (x^-1y)^8=1 entonces (x^-1y)^4 = 1 y así para todos los exponentes. Ahora no tengo claro que esta demostración adicional sea necesaria.

Fin actualización 5 de marzo.

Proposición 2: para todo Qn, los dos ciclos son necesariamente cycle-entangled. No tengo claro cómo formular esto de manera algebraica de momento. Creo que aquí es mejor utilizar un argumento numérico.

Demostración: Hemos demostrado que el IAS / DAS es de orden 4. A continuación una tabla dónde se muestran los parámetros de Qn para varios tamaños con una explicación.

n Orden digrafo = |V| = 4n / Número de arcos = 2|V|.Por definición de la familia. Orden IAS / número de arcos en cada IAS.Según se ha demostrado anteriormente Número de IASs. Se obtiene de dividir el Orden del Dígrafo por el Orden del IAS Orden y = 4 /  número de ciclos de este orden (|V|/ orden y). Por definición de la familia Qn. Orden x = 2n. / número de ciclos de este orden. Por definición de la familia Qn.
2 8 / 16 4 / 8 2 4 / 2 4 / 2
3 12 / 24 4 / 8 3 4 / 3 6 / 2
4 16 / 32 4 / 8 4 4 / 4 8 / 2
5 20 / 40 4 / 8 5 4 / 5 10 / 2
6 24 / 48 4 / 8 6 4 / 6 12 /2

El argumento sería algo así:

Primero, demostramos que el generador x tiene que ser necesariamente cycle-entangled. Partimos de las siguientes 3 proposiciones evidentes:

Proposición a. para todo Qn hay exactamente 2 ciclos disjuntos generados por el generador x.

Proposición b. para todo Qn hay exactamente n IASs.  A cada IAS le asignamos un color diferente y por lo tanto tenemos n colores diferentes.

Proposición c. Cada ciclo del generador x tiene exactamente  |V| / 2 arcos es decir 2n arcos.

Si todos los arcos de un ciclo fuesen de un color diferente, entonces tendríamos 2n colores lo cual está en contradicción la proposición b que sabemos que es verdadera. Por lo tanto en un mismo ciclo del generador x los colores se tienen que repetir que es la condición suficiente para que el ciclo sea cycle-entangled.

Creo que el argumento es correcto (diría que sobra la proposición a) y que se podría aplicar de igual manera (quizás haya que complicarlo y todavía no lo tengo explícito) para demostrar que el ciclo generado por y también tiene que ser cycle-entangled.

Entonces por los resultados de la patente se puede demostrar que para todo n el Dígrafo de Cayley 2-generado de Qn se reduce a un Dih(n/4) (Q8 se reduce a Dih2; Q12 a Dih 3 etc…), es decir a un Dígrafo de Cayley 2- generado de un grupo Dihedral de orden menor y generado siempre por una rotación y una reflexión. Y por lo que estoy viendo (de momento en sólo un caso, Q8 reducido a Dih3) el número de ciclos se conserva pero se intercambian los vértices ¿?. Tras un estudio más detenido ya no tengo ninguna duda que el número de ciclos en cada vértice final posible se tiene que conservar. Cuando regrese del viaje lo demostraré.

Para que el lector sepa de que hablo a continuación puede ver Q8 reducido a Dih2 y Q12 reducido a Dih3.

A la derecha Q8. A la izquierda D2. En D2 aparecen los vértices que en Q8 están separados (perdón por lo artesanal y sucio de la figura; cuando borrar no es una operación teórica o electrónica, queda así de sucio:-)).

Q8 a D2

En la siguiente imagen (de nuevo perdón por lo artesanal y por lo sucio) aparece a la derecha Q12 (o Díciclico 12) y a la derecha Dih 3, de nuevo con los pares de vértices de Q8 que se identifican al plegarse el dígrafo.  Las cifras enmarcadas por los cuadrados en Q8 indican el número de ciclos que terminan en cada uno de los vértices posibles.  En D3, el 1 sobre el par (8,1) sólo significa que es la identidad, pero el 1 sobre el par (3,6) o el dos sobre el par (10,7)  significan número de ciclos que terminan en cada uno.

Q12 a D3

¿ Que  sabemos de los recorridos hamiltonianos en los digrafos de grupos dihédricos 2-generados ?  Diría que para los 2-generados el problema es trivial o al menos ya está demostrado, pero todavía no he encontrado el teorema en concreto. Por fin en esta tesis (que por cierto es muy interesante y habla también del grupo simétrico) nos sacan de dudas (ojo, no se refieren a todos los 2-generados):

Hence now we know that all Cayley graphs of a dihedral group are Hamiltonian if the generating set contains at least one rotation.

Our further considerations can be restricted to the case that the generating set contains only reflections. If S = {Si, Sj} is a generating set for Dn, then C = (I, Si, SjSi, . . . , Si(SjSi)n−1, (SjSi)n = I) (4.3) is a Hamilton cycle and Cay(Dn, S) is Hamiltonian for all generating sets containing two elements.

As a result we have

Proposition 4.10 (Holsztynski and Strube [21]). All Cayley graphs of the dihedral group Dp, where p is a prime, are Hamiltonian.

Proof. Let p be a prime number. The only minimal generating sets of Dp are
either of the form A1 = {Ra1 , Sa2} or A2 = {Sa1 , Sa2}. We have already shown that Cayley graphs of the dihedral group with these forms of generating sets are Hamiltonian.

Para más detalles ver los siguientes resultados recientes:

–ver aquí (Hamiltonian Cayley digraphs on direct products of dihedral groups de 2012),

–o aquí (ON HAMILTON CIRCUITS IN CAYLEY DIGRAPHS OVER GENERALIZED DIHEDRAL GROUPS, de 2012 también). En este paper hablan de un artículo no publicado de S. J.Curran, Hamiltonian circuits on Cayley digraphs on Abelian groups and dihedrical groups que no he encontrado. 

Fin de esquemas de demostraciones. 

Cómo Qn existe para todo n, con esto por fin me queda claro que hay familias infinitas de dígrafos cycle-entangled.

También he analizado los caminos empezando por el vértice 1 y tiene

–el trivial (único en ese vértice final, el 18) y,

–en el otro vértice posible hay 4 (2 secuencias de generadores reversibles).

Parece emerger un patrón claro ((Grupo Q4n de quaterniones generalizado, número de recorridos hamiltonianos empezando por el vértice identidad, número total de recorridos hamiltonianos diferentes), (Q8=4*2, 2*2, 4*8 (8 es el número de vértices) = 32), (Q12=4*3,2*3, 2*3*12 = 72), (Q16=4*4, 2*4, 2*4*16 = 128), (Q20=4*5,2*5,2*5*20 = 200),….(Q4n, 8n^2)) que de confirmarse permitiría contar el número de caminos en todo Q4n mediante una fórmula sencilla. Y posiblemente en ciclos ocurra algo parecido. Cómo ya he dicho antes creo que se puede demostrar que este patrón no es casual y lo demostraré cuando regrese de mi viaje.  Aunque tampoco sé si este resultado es nuevo o ya se ha publicado bajo una forma más general (Dígrafos de Cayley 2-generados de p-grupos, nilpotentes)…y ojo parecidos a los grupos dihédrico o cuaternion generalizado no debemos de olvidar los grupos quasidihédrico y semi-dihédrico.

Finalmente sigue cómo problema abierto encontrar una manera de identificar en el dígrafo plegado los vértices que son finales posibles de caminos hamiltonianos  en el dígrafo original. Estoy seguro de que este problema debe de tener una solución fácil pero se me resiste.

P.s. Cada que vez que tras unos años o meses vuelvo a leer sobre este tema caigo en confusión: cuando leo los papers o surveys no está claro si se habla de grafos o dígrafos, de 2-generados o n-generados (es decir con número de generadores g = > 3), si se habla de ciclos o de caminos hamiltonianos, si lo que se ha solucionado son problemas de decisión, construcción o conteo, si hablamos de casos abelianos (esto está más claro) o no abelianos etc…

Durante la redacción de esta entrada he llegado a varios resultados (con respecto a los Digrafos de Cayley bigenerados del grupo cuaternio generalizado de cualquier orden que yo no conocía y no esperaba y realmente no se si son nuevos o simplemente he redescubierto la rueda.

Por ello aunque hay varias surveys ya desde los años 80 (en general muy buenas), y algunas bastante recientes, en una próxima entrada voy  a  hacer mi propia recopilación de resultados y así me pongo al día.

Fin actualización 4 de marzo. 

Actualización 11 de junio 2015. Bibliografía de investigaciones similares encontradas:

A Routing Scheme for Constructing Node-to-Node Disjoint Paths in Alternating Group Graphs.  ¿ 2001 ?. Es sobre caminos más cortos.

AN ALGEBRAIC APPROACH FOR FINDING DISJOINT PATHS IN THE ALTERNATING GROUP GRAPH. ¿ 2008 ?

Disjoint Hamilton cycles in the star graph. ¿2008? Abstract In 1987, Akers, Harel and Krishnamurthy proposed the star graph Σ(n) as a new topology for interconnection networks. Hamiltonian properties of these graphs have been investigated by several authors. In this paper, we prove that Σ(n) contains bn/8c pairwise edge-disjoint Hamilton cycles when n is prime, and Ω(n/ log log n) such cycles for arbitrary n. 

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: