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.

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.

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 traversals

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.

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.

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 sí o sí estas herramientas. Sí la segunda patente se hubiese concedido más rápidamente, seguramente muchos de ellos ya estarían resueltos.

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

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

Logo de WordPress.com

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

Imagen de Twitter

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

Foto de Facebook

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

Google+ photo

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

Conectando a %s


A %d blogueros les gusta esto: