Archive for the ‘RH system’ Category

Algorítmica y complejidad computacional. Problema RH en DCB: estado de la cuestión.

abril 7, 2017

En 2016 nos dedicamos a aterrizar el problema de Recorridos Hamiltonianos en Dígrafos de Cayley Bigenerados desde el punto de vista algorítmico, acabando con la sensación de haber realizado significativos avances.

En 2017 nos hemos centrado en la cuestión de la posible complejidad computacional de este mismo problema y pensamos que este otro tema ya está suficientemente claro para un documento que tenemos previsto preparar a la mayor brevedad posible.

El caso es que de 2016 de los avances en el aterrizaje de la parte algorítmica sólo queda en la memoria la buena sensación pues, debido a múltiples complicaciones vitales, se nos ha olvidado completamente el contenido de éstos.

Por eso precisamente, porque sabemos que estos temas por importantes que sean se olvidan si no se practican, los ponemos negro sobre blanco en el blog. Probablemente se me complique altamente la segunda quincena del mes así que quiero concentrarme en esto durante esta segunda semana que en principio debería de ser más tranquila. Aunque nunca se sabe.

Voy a releer todo lo que escribimos durante 2016 para hacer una “gran” síntesis que incluiremos en el documento ya comentado: algorítmica y complejidad computacional son dos caras de una misma moneda.

En lo que sigue, mientras espero una llamada importante, una compilación de las entradas, con fecha y título (no necesariamente exacto), sin enlace de momento ni resumen del contenido. Pero seguramente los añadiremos, pues nos va a ser más cómodo para su consulta.

Actualización 11 de abril. Hemos incluido también un listado de entradas de 2015, no todas directamente de investigación (éstas entre paréntesis). Y uno de 2014, el único de ese año sobre esta temática.

Finalmente se nos ha complicado también esta semana con un tema más prioritario que éste y que exigirá también elevada concentración. La “gran” síntesis seguramente tendrá que esperar a mayo, esperemos que de 2017. Fin de actualización. 

(more…)

HPC. Las propiedades de los digrafos de Cayley bigenerados relevantes para el problema de hamiltonicidad, cuya protección solicitamos en la segunda solicitud de patente, explicadas gráficamente.

enero 18, 2016

Esta entrada es una republicación con mínimas modificaciones de una entrada anterior. Por ejemplo he borrado todo el punto 3 que  no era técnico sino más bien reivindicativo.

He tenido que preparar estos gráficos (ciertamente  de bastante mala calidad; pido disculpas al lector por ello) y los hago públicos dado que  muestran bien las diferentes propiedades cuyo testeo estoy intentando proteger en las diferentes reclamaciones de la solicitud de patente. Los ejemplos en los casos en blanco y negro  son ficticios y para simplificar los vértices se han etiquetado con números enteros en vez de con permutaciones.

Recordemos que el input en el problema que nos interesa es la permutación identidad  de grado n  y dos generadores (o permutaciones diferentes de la identidad del mismo grado). El problema es decidir (es decir nos interesa el problema de decisión) si un determinado par de generadores tiene recorridos hamiltonianos o no. Por convención, en los gráficos siguientes, la identidad es el vértice etiquetado con el número 1.

Los gráficos siguientes muestran claramente las propiedades estructurales de los Dígrafos de Cayley Bigenerados que son relevantes para el problema de hamiltonicidad.

I. Los test en concreto.

1.IAS regular, IAS Irregular.

Ignacio Reneses patent method. Example IAS regular and IAS irregularSi el par de generadores es no conmutativo o conmutativo pero obedece a unas propiedades aritméticas muy concretas, entonces será IAS regular, en cuyo caso tendrá unas propiedades más interesantes con respecto al problema de hamiltonicidad que si fuese irregular. Por otra parte las propiedades de hamiltonicidad de los casos conmutativos son bien conocidas y de hecho son los  que se utilizan en las aplicaciones (el toro de cualquier dimensión es una red de este tipo). Pero para la escala a la que se está empezando a trabajar, el ancho de banda / latencia que proveen las redes conmutativas, en mi opinión, se está empezando a quedar corto. Para poder aumentar ancho o latencia, tienen que aumentar el grado de los nodos (la dimensión del toro, por ejemplo), lo cual no es del todo interesante.

Una de las ventajas del método es que, para determinar las propiedades de hamiltonicidad, se evita construir todo el Digrafo de Cayley bigenerado. Es  suficiente trabajar con subdígrafos mucho más pequeños (aunque en el peor caso pueden tener tamaño subexponencial, concretamente la cota de Landau).

Teniendo en cuenta que a veces se tiene que trabajar con Dígrafos de Cayley del grupo simétrico o alternado que tienen respectivamente n ! o n!/2 vértices, esto ya supone un ahorro brutal en cuanto al uso de memoria.

Pero el ahorro en tiempo es  mucho más brutal, pues todos estos tests nos dan información sobre las propiedades de hamiltonicidad de los casos sin necesidad de aplicar un algoritmo exponencial de búsqueda.

Resumiendo, pasamos de una complejidad doblemente exponencial (en función del grado de las permutaciones) a una complejidad subexponencial  (idem). Nótese que los peores casos para nuestro método serán poco frecuentes.

2. (a). Propiedad de lisura / smoothness o retorcimiento / twisted.

(more…)

HPC. Las propiedades de los digrafos de Cayley bigenerados relevantes para el problema de hamiltonicidad, cuya protección solicitamos en la segunda solicitud de patente (USPTO Application nº 13/570898), explicadas gráficamente.

diciembre 1, 2015

Disclaimer. Republico esta entrada de hace unas semanas con algunas actualizaciones. Una es relevante pues hacemos avances para una definición más sencilla de la propiedad de smoothness o lisura.

He tenido que preparar estos gráficos (ciertamente  de bastante mala calidad) y los hago públicos dado que  muestran bien las diferentes propiedades cuyo testeo estoy intentando proteger en las diferentes claims.

Los ejemplos son ficticios y para simplificar los vértices se han etiquetado con números enteros en vez de con permutaciones. recordemos que el input es la permutación identidad  de grado n  y dos generadores (o permutaciones diferentes de la identidad del mismo grado). El problema es decidir (es decir no es interesa el problema de decisión) si un determinado par de generadores tiene recorridos hamiltonianos o no. Por convención, en los gráficos siguientes, la identidad es el  vértice etiquetado con el número 1. Los gráficos siguientes muestran claramente las propiedades estructurales de los Dígrafos de Cayley Bigenerados que son relevantes para el problema de hamiltonicidad.

I. Los test en concreto.

(more…)

HPC. Las propiedades de los digrafos de Cayley bigenerados relevantes para el problema de hamiltonicidad, cuya protección solicitamos en la segunda solicitud de patente, explicadas gráficamente.

noviembre 18, 2015

He tenido que preparar estos gráficos (ciertamente  de bastante mala calidad) y los hago públicos dado que  muestran bien las diferentes propiedades cuyo testeo estoy intentando proteger en las diferentes claims.

Los ejemplos son ficticios y para simplificar los vértices se han etiquetado con números enteros en vez de con permutaciones. recordemos que el input es la permutación identidad  de grado n  y dos generadores (o permutaciones diferentes de la identidad del mismo grado). El problema es decidir (es decir no es interesa el problema de decisión) si un determinado par de generadores tiene recorridos hamiltonianos o no. Por convención, en los gráficos siguientes, la identidad es el  vértice etiquetado con el número 1. Los gráficos siguientes muestran claramente las propiedades estructurales de los Dígrafos de Cayley Bigenerados que son relevantes para el problema de hamiltonicidad.

I. Los test en concreto.

1.IAS regular, IAS Irregular.

Ignacio Reneses patent method. Example IAS regular and IAS irregularSi el par de generadores es no conmutativo o conmutativo pero obedece a unas propiedades aritméticas muy concretas, entonces será IAS regular, en cuyo caso tendrá unas propiedades más interesantes con respecto al problema de hamiltonicidad que si fuese irregular. Por otra parte las propiedades de hamiltonicidad de los casos conmutativos son bien conocidas y de hecho son los  que se utilizan en las aplicaciones (el toro de cualquier dimensión es una red de este tipo). Pero para la escala a la que se está empezando a trabajar, el ancho de banda / latencia que proveen las redes conmutativas, en mi opinión, se está empezando a quedar corto. Para poder aumentar ancho o latencia, tienen que aumentar el grado de los nodos (la dimensión del toro, por ejemplo), lo cual no es del todo interesante.

Una de las ventajas del método es que, para determinar las propiedades de hamiltonicidad, se evita construir todo el Digrafo de Cayley bigenerado. Es  suficiente trabajar con subdígrafos mucho más pequeños (aunque en el peor caso pueden tener tamaño subexponencial, concretamente la cota de Landau).

Teniendo en cuenta que a veces se tiene que trabajar con Dígrafos de Cayley del grupo simétrico o alternado que tienen respectivamente n ! o n!/2 vértices, esto ya supone un ahorro brutal en cuanto al uso de memoria.

Pero el ahorro en tiempo es  mucho más brutal, pues todos estos tests nos dan información sobre las propiedades de hamiltonicidad de los casos sin necesidad de aplicar un algoritmo exponencial de búsqueda.

Resumiendo, pasamos de una complejidad doblemente exponencial (en función del grado de las permutaciones) a una complejidad subexponencial  (idem). Nótese que los peores casos para nuestro método serán poco frecuentes.

Actualización 1 de diciembre de 2015.

2 (a). Propiedad de lisura / smoothness o retorcimiento / twisted.

No tengo todavía una definición de la definición de lisura lo más simplificada posible, aunque estoy empezando a pensar que posiblemente la definición más  simple implique la circunferencia. Vamos a desarrollar este tema en este punto. Primero algunos ejemplos.

A continuación un primer ejemplo twisted. Se indican los parámetros del caso en la propia figura.

Ignacio Reneses twisted case only one possible final vertex has hamiltonian traversalsY un segundo caso.

 

 

 

Fin de actualización 1 de diciembre de 2015. 

2 (b). Propiedade Entanglement o entrelazado.

Ignacio Reneses Patent Method. Entanglement property example

Nos hemos saltado la propiedad de smoothness o de ser liso, que normalmente se debería de testear antes, y para la  cual no tenemos gráfico recién realizado.

Si el caso es no entrelazado y además ninguno  de los dos generadores es una involución entonces tendrá unas propiedades de hamiltonicidad más ventajosas que si es entrelazado. Si es entrelazado entonces es posible que sea un caso complicado en sus propiedades de hamiltonicidad.

3. Entrelazado por ciclos o cycle-entanglement.

La primera imagen muestra un caso, el A, que no es entrelazado por ciclos por el generador 1.  Y muestra un caso, el B, que es entrelazado por ciclos. Esto quiere decir que el IAS y el ciclo del generador comparten más de un arco. En el caso A, no entrelazado, sólo  comparten el arco 2–>1. En el caso B, entrelazado por el ciclo del generador 1, comparten los arcos 2–>1 y 4–>3.

Ignacio Reneses Patent Method. Cycle entanglement property example

En la imagen siguiente se muestra como  un caso puede ser entrelazado por un ciclo y no entrelazado por el otro. Por ello hay que testear esta propiedad por los dos ciclos. Se pueden dar los cuatro casos posibles:

–entrelazado por el ciclo del generador 1 y no entrelazado por  el generador 2.

–no entrelazado por el generador del ciclo 1 y entrelazado por el 2.

–no entrelazado por ninguno de los dos.

–entrelazado por los dos.

Ignacio Reneses patent method . Cycle entanglement property 2.

De nuevo esta propiedad  es muy relevante para el problema de hamiltonicidad.

Actualización 1 de diciembre de 2015.

A continuación un caso real entrelazado por los dos ciclos: un digrafo de Cayley del grupo cuaternio de orden 12.

Ignacio Reneses ejemplo real cycle entanglement Quaternion group of order 12Como se puede ver este caso se puede descomponer en 3 IAses, cada uno marcado con un color diferente. El IAS (marcado en color rojo) y el DAS se entrelazan en varios vértices, el 4, el 7 y el 10. Los dos ciclos están entrelazados, ya que contienen varios arcos de los diferentes IASes. En otra entrada hemos demostrado que los digrafos de Cayley de los grupos cuaternios serán en general entrelazados por ciclos.

Fin de actualización 1 de diciembre de 2015.

4. Circunferencia.

No hemos hablado de dos pasos del algoritmo que no son tests, sino que son puramente procedimientos que o bien nos dan información sobre un parámetro del dígrafo (el tamaño del IAS, que expresa el número máximo de vértices que potencialmente pueden ser vértices finales en un recorrido hamiltoniano) o bien permiten resolver el problema de decisión de ciclos hamiltonianos.

Y posteriormente a la patente, tal y como ya hemos  publicado múltiples veces en este mismo blog, hemos visto que hay otro parámetro clave que mostramos graficamente en la siguiente imagen. Como es casi obvio, para calcular este parámetro no hace falta construir toda la circunferencia. Ya hemos comentado en otras entradas como se puede obtener de manera rápida.

Circunferencia

II. La secuencia de tests.

Los tests descritos anteriormente se pueden hacer de manera independiente o en secuencia, añadiendo cada test información adicional al caso o input. En la  imagen siguiente se muestra la secuencia.

Secuencia de tests

En el gráfico anterior hay una errata y un “error” que no voy a corregir. El error es que por  definición los casos en los que un generador es una involución son entangled, y por lo tanto las casillas amarillas están mal puestas.

No estamos afirmando que esto sea la última palabra sobre este problema: quedan algunos flecos por resolver. Pero su solución tendrá que utilizar estas herramientas. Sí la segunda patente se hubiese concedido más rápidamente, seguramente muchos de ellos ya estarían resueltos.

III. Comentarios.

El  lector se preguntará: ¿ que tiene todo esto de idea abstracta ?. Parecen unos tests muy concretos, efectuados sobre un objeto muy concreto, un Digrafo de cayley bigenerado, y con unos resultados muy concretos, y con aplicaciones muy concretas en tecnología de redes.

Resulta que antes de mi investigación era completamente desconocido que cada uno de estos tests pudiesen ser tan relevantes para el problema  de hamiltonicidad, y por lo tanto el resultado es completamente nuevo.

Resulta que este problema de hamiltonicidad en Grafos de Cayley había sido estudiado seguramente por miles de investigadores de diversos campos (matemáticas, ingeniería  etc…;  incluyo a todos aquellos que han publicado sobre el problema de recorridos hamiltonianos en grafos o digrafos vértice transitivos) y no habían llegado al resultado ninguno de ellos (algunos de ellos muy brillantes por cierto; ojo, no digo que no haya habido otros avances, ni mucho menos, pero no eran mi resultado), y por lo tanto no es obvio.

Resulta, nos repetimos,  que cada uno de estos tests tiene importantes aplicaciones prácticas por  su relación con el problema de hamiltonicidad y por lo tanto es útil.

¿ Que son tests sencillos ? Sencillos de descubrir, para nada: ya hemos comentado que miles de investigadores han trabajado en el tema y no han visto la relación de estos tests con las propiedades de hamiltonicidad. Sencillos de ejecutar, sin duda (aunque para los tamaños de las redes que se utilizan en las aplicaciones hacerlos manualmente ya es prohibitivo). Pero si son sencillos de ejecutar, mejor que mejor. La sencillez o complejidad de un proceso no es condición para la concesión de una patente. El caso es que se cumple con los requisitos habituales que se piden para la concesión de  una patente. Sin embargo se han sacado de la manga a última hora la carta de la idea abstracta, que incluso aplicando el nuevo caso de Alice Corp. no es aplicable a mi solicitud.

La respuesta que vamos a presentar frente a la USPTO y cuya preparación me ha costado tres meses de trabajo es un documento de 60 páginas en el que, basándose en el documento Interim Guidance y en el documento de ejemplos basado en éstas, los dos emitidos por la USPTO, contiene todos los argumentos posibles para  demostrar que, si el Examinador comprendiese bien la innovación y siguiese estas instrucciones, la patente solicitada se debería de conceder, sí o sí. Le preguntaré a mi agente: si no ve problemas publicaré aquí mi respuesta de 60 páginas una vez hayamos presentado la respuesta, para que el lector pueda juzgar por sí mismo.

Predigo que una vez presentada, el Examinador no se va a leer en detalle el documento (soy consciente de que los Examinadores tienen poco tiempo; aunque sorprenda esto en el país que supuestamente lidera la innovación global, la USPTO, en relación con la cantidad de solicitudes que se presentan está sub-financiada:  por otra parte al  documento no le sobra una coma), que va a tardar más tiempo del que deberían en resolver mi respuesta a la final rejection y que mientras tanto se va cruzar por el camino otro caso judicial que va a afectar a mi solicitud de manera retroactiva (ya me ha pasado en dos ocasiones, con Bilski y con Alice Corp.), y de acuerdo con este nuevo caso la van a denegar de nuevo. Seguramente ya lo están preparando y ya me huelo la tostada sobre por dónde vendrán los tiros. No pueden alegar ausencia de novedad, obviedad, inutilidad ni que sea una idea abstracta. No les queda ninguna carta en este sentido y se tienen que sacar de la  manga alguna otra carta u obstrucción.

Actualización. Una entrada con las últimas novedades al respecto. Fin de actualización.

Otra posibilidad es que se conceda, ya que no tienen más remedio pero abran una vía de recurso administrativo posterior (tipo PTAB) en el que terceras partes puedan recurrir la concesión, variando la condición de novedad. Esta segunda posibilidad no me da ningún miedo ya que el resultado, cada uno de los tests, se mantendrá firme ante cualquier recurso.

Los abusos de poder propios de regímenes comunistas proteccionistas de su industria nacional, como está empezando a ser EEUU, son así.  La arrogancia de las grandes potencias, como EEUU, es así. Como soy más fuerte, impongo mis intereses, cueste lo  que cueste.

Nota. Lo que sigue ya no tiene por qué referirse necesariamente a mi invención. Fin de nota.

Hubo un tiempo en el que en este mismo país, en EEUU, si alguna invención era interesante, en vez de robarla utilizando como armas nuevos casos judiciales o nuevas regulaciones, sacaban el talonario y la compraban (no digo que este sea mi caso: podría ser  que finalmente la industria no se interese por  mi  invención).

Lamentablemente esto ha cambiado y ahora a las multinacionales de EEUU, amparadas por las nuevas regulaciones que han impulsado ellas mismas para protegerse, les sale más rentable aislarse del entorno innovador y robar las invenciones de los demás, en general pequeños inventores, a tutiplén.

P.s. Quiero añadir que  tras estar tres meses trabajando en el documento y estudiando todas estas materias, y siendo  justos, mi conclusión es  que hay  un problema real  con las ideas abstractas que a veces se patentan o intentan patentar, pero, tal y como ya han señalado muchos, la solución que han articulado no es la adecuada.

Tenían otras opciones y terceras partes se las indicaron (por ejemplo alegar falta de novedad u obviedad) pero optaron (desde luego no de manera inconsciente) por ir por la vía  de las ideas abstractas. ¿ Por qué ?. Porque esto les deja la puerta abierta a los examinadores para tomar decisiones arbitrarias. Y es lo que los diseñadores de las políticas públicas de innovación en EEUU quieren (lo que en principio cualquier poder desea): poder tomar decisiones arbitrarias. Esta sí, esta no, por que me sale de los cojones, y punto (pido disculpas por la expresión).

O quizás el problema no sea tanto la regulación (vía decisión judicial) en sí, sino como se está aplicando por la USPTO, como mi caso pone de manifiesto. Y eso que en las Interim Guidance y en los ejemplos está muy clara la intención. Si has decidido  no conocer a fondo una invención porque no tienes tiempo o por lo que sea, no la deniegues…

Patente 8266089B2 / Solicitud 13-570898 / RH Systems. Las potenciales aplicaciones.

octubre 21, 2015

Entrada en construcción.

Las potenciales aplicaciones de los resultados de la patente ya concedida y de la solicitud pendiente están claras: las redes de interconexión.

Nota. Los sistemas RH son una propuesta ingenieril propia, posterior a las patentes, de redes basadas en Digrafos de Cayley en las que todas las comunicaciones se realizan mediante recorridos hamiltonianos. Obviamente son sólo una de las posibles aplicaciones ingenieriles de los resultados de la patente ya concedida y solicitud pendiente .  Fin de nota.   Fin de nota.

Como es bien conocido estas, es decir las redes de interconexión, se utilizan como medio de comunicación en sistemas informáticos multinodos. Los nodos de la red pueden ser procesadores, unidades de memoria, sensores o incluso periféricos de salida. También una combinación de cualquiera de estos elementos.  

A continuación algunos de los sistemas multinodos (reales) en los que los resultados de la patente y solicitud podrían tener aplicaciones. En esta edición reseñamos todas las potenciales aplicaciones y nos centramos en la recopilación de enlaces y extractos en una que no habíamos considerado antes, los data centers.

El lector debe de tener en cuenta que aunque algunas de las aplicaciones son reales (es decir se han implementado en sistemas reales), otras serán puramente académicas, teóricas, muy alejadas del frente de aplicaciones reales.

(more…)

Rh Systems. Redes de interconexión de tipo bus.

octubre 20, 2015

Otra serie de artículos relacionados, bastante indirectamente, con los sistemas RH. Si una red de interconexión punto a punto se puede modelar por un grafo, una red de interconexión de tipo bus se puede modelar por hipergrafos, en cuyo caso los vértices siguen siendo vértices, pero los hiperarcos pueden /suelen contener más de dos vértices. Aparentemente se publicó algo sobre este tipo de redes de interconexión en los 90, y posteriormente se dejó de publicar (aunque he encontrado un artículo de 2009 en el que hablan sobre ellas).

Hay diferencias entre las redes de interconexión de tipo bus y los sistemas RH.

En una red punto a punto (como en principio lo son los sistemas RH), físicamente las comunicaciones se hacen de nodo a nodo (de router a router, de conmutador a conmutador); en una red multibus, las comunicaciones se hacen de nodo a todos los otros nodos que comparten un mismo bus.

Otra diferencia es que las primeras utilizan la técnica de conmutación de circuitos (en cada bus) y los segundos están más pensados (hasta ahora) en modo conmutación de paquetes. Al extremo, si contemplamos arcos que contengan todos los vértices del dígrafo, entiendo que estamos contemplando sistemas similares a los RH. Tema a estudiar.

0. 1986.

Analysis of Multiple-Bus Interconnection Networks*

T. N. MUDGE, J. I? HAYES, G. D. BUZZARD, AND D. C. WINSOR

Advanced Computer Architecture Laboratory, Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, Michigan 48109-I 109 Received February 4, 1985 The performance of multiple-bus interconnection networks for multiprocessor systems is analyzed, taking into account conflict arising from memory and bus interference. A discrete stochastic model of bandwidth is presented for systems in which each memory is connected either to all the buses or to a subset of the available buses. The effects of the assumptions made concerning independence among requests for different memories (spatial independence) and resubmission of blocked requests (temporal independence) are investigated systematically. The basic bandwidth model is extended to account for spatial dependence, and compared to previously proposed models. Finally, the various analytic models are shown to be in close agreement with simulation results. 

1.1992.

Larry Finkelstein y Gene Cooperman.

PERMUTATION ROUTING VIA CAYLEY GRAPHS WITH AN EXAMPLE FOR BUS INTERCONNECTION NETWORKS.

ABSTRACT

Cayley graphs have been used extensively to design interconnec- tion networks and provide a natural setting for studying point-to-point routing (1, 2, 3, 5, 6, 7, 12). The extension of these techniques to the more important problem of permutation routing on interconnection networks presents funda- mental problems. This is due to the potentially explosive growth in both the size of the graph and the number of generating permutations, referred to as one-step permutation routes, used to define the underlying graph. This pa- per describes a technique for moderating that growth so that the techniques in (8) can be applied for finding optimal permutation routes. In a particularly striking example, a bus interconnection architecture involving 1.0× 1017 per- mutations (nodes of the Cayley graph) is reduced to a computation on a graph with only 3,950 nodes. Further, it is shown how many of the 58,624 generators (directed edges labelled by one-step permutation routes) at each node of the graph may be eliminated as locally redundant.

2. 1996. 

Bus interconnection networks

3. 1999.

Broadcasting in bus interconnection networks.

A. Ferreira, A. Goldman, S.W. Song.

4. 2009.

Scalable arbitration of partitioned bus interconnection networks in 3D-IC systems.

In this paper, we describe a scalable interconnection network architecture intended for very large multicore processors implemented on stacked chip 3D integrated circuits (3D-IC). These networks provide fully interconnected, low latency, single hop performance with wiring complexity that scales linearly with the size of the network. The enabling technology for these networks is a novel, fully distributed arbitration and control algorithm that operates solely at the edges of the network without the need for any routers within the network core. This paper is focused on a description of that algorithm. We present simulation results for average, worst-case, and per-node latencies showing that our arbitration algorithm performs efficiently, scales for a wide range of partition sizes, and effectively manages highly non-uniform traffic patterns.

P.s. Por el camino me he encontrado este artículo en el que sugieren una nueva forma de ver  / modelar las redes de interconexión (de tipo NoC): como sistemas termodinámicos.

Toward a science for future NoC design

Traditionally, the design space exploration for systems-on-chip has focused on the computational aspects of the problem at hand. However, as the number of components on a single chip and their performance continue to increase, the design of the communication architecture plays a major role in defining the area, performance, and energy consumption of the overall system. From a technology point of view, this paradigm shift is meant to mitigate the problem of interconnects, keep the design complexity under control, and reduce costs. Since neither point-to-point, nor bus-based communication scale well in terms of power and performance figures, the network-on-chip architecture has been suggested as a promising solution for future multicore systems.

In this talk, we plan to address the concept of “network” in multiprocessor systems-on-chip and identify specific design principles and optimization techniques that are relevant to our research community. More precisely, we plan to discuss fundamental mathematical techniques that can be used to design, control, and optimize such networks in a rigorous manner at nanoscale. At the same time, we plan to also highlight alternatives to the conventional paradigm of network design. This new vision is based on rigorous developments in the field of statistical physics and information theory that allow us to model the network as a thermodynamical system. The hope is that this new modeling paradigm can enable not only capturing the intrinsic interactions among various network components, but also developing powerful techniques for predicting and optimizing the on-chip network behavior.

Ver también:

The Chip Is the Network: Toward a Science of Network-on-Chip Design.

Radu Marculescu1 and Paul Bogdan2 1 Department of Electrical and Computer Engineering, Carnegie Mellon University,

Abstract

In this survey, we address the concept of network in three different contexts representing the deterministic, probabilistic, and statistical physics-inspired design paradigms. More precisely, we start by considering the natural representation of networks as graphs and discuss the main deterministic approaches to Network-on-Chip (NoC) design. Next, we introduce a probabilistic framework for network representation and optimization and present a few major approaches for NoC design proposed to date. Last but not least, we model the network as a thermodynamic system and discuss a statistical physics-based approach to characterize the network traffic. This formalism allows us to address the network concept in the most general context, point out the main limitations of the proposed solutions, and suggest a few open-ended problems.

Along these lines, Bogdan and Marculescu [32] propose a paradigm shift in NoC design based on the analogy between the network and thermodynamic gas behaviors. This becomes possible based on the observation that each buffer of the NoC, at any point in time, can be characterized by a particular energy level. More precisely, the main idea is that packets in the network move from one node to another in a manner that is similar to particles moving in a Bose gas and migrating between various energy levels as a result of temperature variations

Sistemas RH. Un artículo reciente relevante.

septiembre 22, 2015

Disclaimer. Pido disculpas al lector por mezclar en esta entrada cuestiones que no tienen mucho que ver: política local española, artículo técnico de ingeniería de redes, crítica de la normativa del sistema de patentes de EEUU etc…. Narrativa postmoderna oblige

Ya no va a haber nada nuevo con respecto al tema de Cataluña (salvo quizás el debate Margallo-Junqueras que creo es mañana), ni siquiera el día de las Elecciones, y estoy de nuevo concentrado 100% en éste tema y he encontrado éste artículo en el que hablan de un problema muy similar (si no es el mismo) que el que nos hemos planteado en las varias entradas sobre los sistemas RH.

Nota. Recordamos al lector que en un sistema RH, un tipo de sistemas HPC que hemos propuesto nosotros en varias entradas en este blog, a diferencia de lo que es habitual actualmente, todas las comunicaciones entre nodos (punto a punto y colectivas) se realizarían mediante recorridos hamiltonianos. Por ello es de interés diseñar redes que, dado un tamaño o numero de nodos, permitan que múltiples recorridos de este tipo puedan circular en la red simultáneamente sin interferencias.

Teniendo en cuenta la dificultad que suponía, antes de los resultados de nuestra patente incluso determinar si en una red de interconexión dada (modelada por un Dígrafo de Cayley 2-generado) existe un sólo recorrido hamiltoniano, para este tipo de sistemas teóricos que hemos propuesto nosotros es de gran interés un método como el que hemos patentado que sea capaz:

a) tanto de identificar aquellos casos que potencialmente tienen recorridos hamiltonianos, puediendo obtener además una idea aproximada de la cantidad de recorridos hamiltonianos que se podrían obtener. Esto es interesante pues,  incluso utilizando los métodos constructivos de la patente intentar generar un recorrido hamiltoniano tiene un coste en recursos computacionales, sobre todo, aunque no  solo, si no los tiene.

b) como de generar o construir, dada una topología de red de interconexión, múltiples (o si fuese necesario todos los posibles) recorridos hamiltonianos.

En la primera patente queríamos proteger ambos resultados, el  a) y el b). Por motivos puramente normativos (es decir por como se redactaron las claims, no sustanciales) nos concedieron sólo la protección para el segundo.  En la segunda solicitud, la continuation, insistimos para proteger el primer resultado, el a), que son varios pasos independientes del método completo, que tienen un elevado valor por si mismos, y por estar afectados por el caso Alice Corp, que ya si podría añadir razones sustanciales, de nuevo se  ha denegado, aunque en la respuesta al examinador, pienso, quedó claro que estas razones sustanciales no aplicaban a nuestro caso. Pero el examinador, que  pensamos no conoce en detalle la invención, no lo ha considerado así y tenemos que insistir perdiendo más tiempo e invirtiendo un mayor coste.

En una entrada anterior, un ejemplo del tipo de problemas que se estudian para los sistemas RH, muy similares aunque con diferentes objetivos, a los que se plantean en el artículo que reseñamos  en ésta. En ella, utilizando las técnicas de existencia, no constructivas, de la patente,  utilizamos una familia infinita  de Dígrafos de Cayley, el grupo cuaternio generalizado, que cumplen una condición que hemos impuesto para este tipo de sistemas.

Fin de nota.

Me ha gustado sobre todo porque tiene el enfoque ingenieril, y no el de las matemáticas abstractas, y tiene la claridad con la que se suelen expresar los autores chinos, muy diferentes a la confusión rebuscada (intencional o no) con la que se expresan autores de otros países.

Estoy compilando artículos relevantes relacionados con el tema de la patente publicados den 2015 y ya he encontrado algunos. Es posible que  hagamos una entrada sobre ello.

The Property of Edge-Disjoint Hamiltonian Cycles in Transposition Networks and Hypercube-Like Networks.

Ruo-Wei Hung Department of Computer Science and Information Engineering, Chaoyang University of Technology, Wufeng, Taichung 41349, Taiwan

Abstract.

The presence of edge-disjoint Hamiltonian cycles provides an advantage when implementing algorithms that require a ring structure by allowing message traffic to be spread evenly across the network. Edge-disjoint Hamiltonian cycles also provide the edge-fault tolerant hamiltonicity of an interconnection network. In this paper, we first study the property of edge-disjoint Hamiltonian cycles in transposition networks which belong to a subclass of Cayley graphs. The transposition networks include other famous network topologies as their subgraphs, such as meshes, hypercubes, star graphs, and bubble-sort graphs. We first give a novel decomposition of transposition networks. Using the proposed decomposition, we show that n-dimensional transposition network with n > 5 contains four edge-disjoint Hamiltonian cycles. By using the similar approach, we present linear time algorithms to construct two edge-disjoint Hamiltonian cycles on two variants of hypercubes, including twisted cubes and crossed cubes. Keywords: Edge-disjoint Hamiltonian cycles, edge-fault tolerant hamiltonicity, transposition networks, twisted cubes, crossed cubes.

Extractos.

Parallel computing is important for speeding up computation.

The design of an interconnection network is the first thing to be considered.

Many topologies have been proposed in the literature [4, 6, 10, 14, 20, 33, 34, 38], and the desirable properties of an interconnection network include symmetry, relatively small degree, small diameter, embedding capabilities, scalability, efficient routing, and fault-tolerant robustness.

Among those proposed interconnection networks, the hypercube is a popular interconnection network with many attractive properties such as regularity, symmetry, small diameter, strong connectivity, recursive construction, partition ability, and relatively low link complexity [40]. In the literature, many variants of hypercubes have been proposed for enhancing the architecture of hypercubes.

In this paper, we will study the edge-disjoint Hamiltonian cycles property of two variants of hypercubes, including twisted cubes and crossed cubes.

Cayley graphs arise naturally in interconnection networks and, hence, some interesting properties on them have been studied [5, 37, 41]. The transposition networks form a subclass of Cayley graphs and include other network topologies as their subgraphs, such as meshes, hypercubes, star graphs, and bubble-sort graphs [34, 44]. The transposition networks possess many attractive network properties, such as node symmetric [2], regular, sublogarithmic diameter, small fault-diameter, high node connectivity, embedding capabilities of meshes and hypercubes, simple shortest routing [34], lower bisection width [43], efficient node-disjoint path routing [19], and so on.

In this paper, we will investigate the property of edge-disjoint Hamiltonian cycles in transposition networks. The architecture of an interconnection network is usually modeled by a graph in which the nodes represent the processing elements and the edges represent the communication links. In this paper, we will use graph and network, vertex and node, and edge and link interchangeably.

A Hamiltonian cycle in a graph is a simple cycle that passes through every node of the graph exactly once. A graph is called Hamiltonian if it contains a Hamiltonian cycle. The ring structure is important for distributed computing, and its benefits can be found in [29].

Two Hamiltonian cycles in a graph are said to be edge-disjoint if there exists no common edge in them. A graph admits a Hamiltonian decomposition if all of its edges can be partitioned into disjoint Hamiltonian cycles. The edge-disjoint Hamiltonian cycles can provide an advantage for algorithms that make use of a ring structure [39].

Consider the problem of all-to-all broadcasting in which each node sends an identical message to all other nodes in the network. There is a simple solution for the problem using an η-node ring that requires η−1 steps, i.e., at each step, every node receives a new message from its ring predecessor and passes the previous message to its ring successor.

If the network admits edge-disjoint rings, then messages can be divided and the parts broadcast along different rings without any edge (link) contention. 

If the network can be decomposed into edge-disjoint Hamiltonian cycles, then the message traffic will be evenly distributed across all communication links. Edge-disjoint Hamiltonian cycles also form the basis of an efficient all-to-all broadcasting algorithm for networks that employ wormhole or cut-through routing [35].

Further, edge-disjoint Hamiltonian cycles also provide the edge-fault tolerant hamiltonicity of an interconnected network; that is, when a Hamiltonian cycle of an interconnected network contains more one faulty edge, then the other edge-disjoint Hamiltonian cycle can be used to replace it for transmission.

In this paper, we first study the edge-disjoint Hamiltonian cycles property of transposition networks. We show that 4-dimensional transposition network admits a Hamiltonian decomposition, and then show that n-dimensional transposition network with n > 5 contains four edge-disjoint Hamiltonian cycles. Then, we use the same approach to construct two edgedisjoint Hamiltonian cycles in twisted cubes and crossed cubes which are two variants of hypercubes. In the following, we give a briefly survey on transposition networks, twisted cubes, and crossed cubes.

Llevo un cierto tiempo estudiando la respuesta del examinador  a mi segunda  solicitud de patente, y cuanto más la releo menos entiendo el por qué de la final rejection,  teniendo en cuenta la importancia del problema que resolvemos de cara a importantes aplicaciones, como se pone de manifiesto de nuevo en éste reciente artículo  de 2014.

Nota. Tampoco entiendo la posición de otra parte, pero esto me lo callo, pues ya dijimos  que no  íbamos a dar detalles de determinados temas y vamos a ser firmes en ésto. Fin de nota.

Los motivos de la final rejection y los argumentos que  utiliza el examinador me parecen cada vez más absurdos y ya casi puedo confirmar que no se ha leído o no ha comprendido lo que tiene entre manos.

Aún así hay que intentar rebatirlos. Uno se encuentra en la disyuntiva de preparar una respuesta larga bien armada, y que entonces ni la lea ya que tienen sobrecarga de trabajo o  una corta, sucinta, que no explique suficientemente bien mi posición, en cuyo caso la leerá  pero no al comprenderá. Así es la vida del inventor.

Nota. Que ésto suceda en un país como  EEUU, que se supone que es era el país más avanzado (hasta que se han cargado el sistema  de patentes), es muestra suficiente del estado del mundo. Teniendo esto en cuenta todo esto, ¿ que hay de raro en que a un presidente de una Comunidad Autónoma le parezca totalmente natural pervertir de manera criminal el objeto de unas Elecciones Autonómicas; que un conjunto de merecidamente prestigiosos economistas neo-clásicos que dan clases en el país citado y han construido su carrera en base a resultados que indican que el capitalismo, cuyo presupuesto es un Estado de Derecho Democrático, es el mejor sistema, apoyen ésta criminal perversión electoral que además está diseñada y ejecutada por un conjunto de organizaciones vinculadas a la extrema izquierda  comunista; que una multinacional como Google, de ese mismo país, pueda atropellar gratuitamente al usuario y que el sistema  judicial español lo permita, o que un valor como la amistad, tenga hoy un idem nulo ?. Llegados a éste punto, personalmente no espero más que decadencia. Fin de nota.

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

julio 6, 2015

Republicación 6 de julio 2015. 

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. 

HPC. Sobre la propiedad de lisura o smoothness en Dígrafos de Cayley Bigenerados: ¿ una caso que la falsifica ?II.

junio 26, 2015

Nota. Salgo a una comida. Completaré la entrada más tarde, y seguramente la modificaré.

Seguimos la serie de entradas comentando sobre el método de la patente US 8266089 y sobre los tests incluidos en las 6 reclamaciones sustanciales (el resto son variaciones) de la solicitud de patente (de tipo continuation) 13/570898, de manera completamente injustificada por parte del examinador y que espero que finalmente se concedan en una próxima revisión. 

Ya hemos visto que no hay posibilidad de caso que falsee nuestro resultado, tal y cómo insinuábamos en el título. Nuestro resultado es robusto.

Pero sí creo que tras la sucesión de las últimas entradas la situación ha podido algo quedar confusa para el lector y quiero aclara las conclusiones principales del resultado:

1. Casi todos los Dígrafos de Cayley bigenerados son lisos o smooth y por lo tanto tienen recorridos hamiltonianos (en general varios, en general muchos) en todos los vértices finales posibles. Éste es el principal resultado de nuestra investigación y creo que es una buena noticia para los diseñadores de redes de interconexión. Esto que era completamente desconocido abre nuevas posibilidades al diseñador de redes, como diseñar redes en las que todo el enrutamiento se haga mediante recorridos hamiltonianos. Entiendo que habrá aplicaciones para las que este tipo de redes sea el más adecuado u óptimo. Teniendo esto en cuenta es altamente interesante disponer de un test que permita identificar los casos smooth. El test existe y lo hemos incluido como reclamación en la segunda solicitud de patente y por motivos que se me escapan (en la primera está claro, un formalismo legal; en la segunda, pese a la incidencia del caso Alice Corp. v CLS Bank, los motivos son completamente oscuros) se han rechazado.

2. El método que hemos presentado en la patente es secuencial pero es fácilmente paralelizable en la mayoría de sus etapas y sobre todo en la  que es computacionalmente más intensiva, tal y como hemos detallado en una anterior entrada.

3. Cuando por los motivos que sea al diseñador de redes de interconexión o de otro tipo, o a cualquier otro tipo de usuario le interesa (seguramente porque el caso tiene otras propiedades muy interesantes no relacionadas con la propiedad de hamiltonicidad) trabajar con un caso que no sea liso o smooth en el entorno de la identidad, y por lo tanto sea potencialmente complicado, no está todo perdido. El método de la patente incluye una serie de tests que permite identificar casos con propiedades estructurales diferentes a los que se puede aplicar técnicas diferentes.

(more…)

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

junio 15, 2015

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.