HPC. US Patent application nº 13 / 570898: La importancia de la circunferencia para el problema de recorridos hamiltonianos en Dígrafos de Cayley Bigenerados.

1.Aunque todavía no hemos terminado la entrada anterior (admito que la entrada a la que enlazamos está un poco confusa con todas las actualizaciones y casos, pero la conclusión es completamente clara para quien quiera verla; no hace falta inteligencia artificial, ni siquiera natural para ver el patrón: así se las ponían a Don Pelayo, ok, a Fernando VII :-)), en la que analizamos tres tipos de casos relacionados con Dígrafos de Cayley bigenerados de S6 cuyas propiedades de hamiltonicidad nos sorprendieron, ya está quedando muy clara la importancia del parámetro de la circunferencia para el problema de recorridos hamiltonianos en Dígrafos de Cayley bigenerados.

Nota.

Lo prometido es deuda. Como complemento de la entrada a la  que hemos enlazado, dos casos twisted cuyos generadores no son de orden dos y en los que encontramos (fácilmente, según anoté; en este contexto fácil quiere decir sin que el algoritmo de la patente inicial entre en modo backtraking), recorridos hamiltonianos en todos los vértices finales posibles. Arriba, en los dos casos, los parámetros. En el primer caso la circunferencia es de orden 2 (pero contiene 4 IASes). En el segundo caso la circunferencia es de ¿ orden 5 ? y ¿ contiene 10 IASes ?. Este segundo caso es muy interesante y lo analizaremos en profundidad en breve.

Ignacio Reneses caso twisted dos generadores no de orden 2

Ignacio Reneses caso twisted fácil dos generadores no de orden 2

Fin de nota.

Ojo: la circunferencia es un concepto nuestro que tiene una definición técnica muy clara, según hemos visto en anteriores entradas. Según he visto, el mismo nombre se utiliza para otros conceptos.

Cuando tengamos terminada la entrada (ya ahora vamos más rápido dado que hemos recuperado el programa que elaboramos y utilizamos  en su momento) detallaremos las conclusiones aquí. Adelanto de lo que esté emergiendo: cuando (x^(-1) y)^n = (yx^-1)^n (y por lo tanto la circunferencia = 2, o contiene dos IASes), entonces tenemos casos complicados (posiblemente sin recorridos hamiltonianos en ninguno o al menos alguno de los vértices finales posibles).

Por otra parte no son los únicos complicados: cuando  es entangled en algunos  de los otros vértices (no opuestos a la identidad en el IAS) podemos encontrar también casos complicados (aunque tengan recorridos hamiltonianos en todos los vértices finales posibles, puede no ser sencillo encontrarlos). Y no olvidemos los casos twisted, que pueden no ser entangled (salvo por tener un generador de orden 2).    

De momento me pregunto sobre que valor tendrá la circunferencia en los casos cycle-entangled (que son los más “densos”compactos posibles).

2. Algo de casuística, de momento sin sistematismos (solo para comprobar algunos casos), sobre este interrogante:

Caso 1. 12354786. 26745831. IAS 6. Es cycle-entangled. Unknown según Ruskey & Effler.

Se confirma que está entangled por la permutación opuesta a la identidad en el IAS.

{“9”, “2”, “7”, “5”, “6”, “3”, “8”, “4”},
{“9”, “2”, “7”, “6”, “5”, “8”, “4”, “3”},
{“3”, “9”, “8”, “6”, “5”, “2”, “4”, “7”},
{“3”, “9”, “8”, “5”, “6”, “4”, “7”, “2”},
{“2”, “3”, “4”, “5”, “6”, “9”, “7”, “8”},
{“2”, “3”, “4”, “6”, “5”, “7”, “8”, “9”},
{“9”, “2”, “7”, “6”, “5”, “3”, “8”, “4”},
{“9”, “2”, “7”, “5”, “6”, “8”, “4”, “3”},
{“3”, “9”, “8”, “5”, “6”, “2”, “4”, “7”},
{“3”, “9”, “8”, “6”, “5”, “4”, “7”, “2”},
{“2”, “3”, “4”, “6”, “5”, “9”, “7”, “8”}

{“2”, “3”, “4”, “6”, “5”, “8”, “9”, “7”},
{“7”, “2”, “8”, “6”, “5”, “3”, “9”, “4”},
{“7”, “2”, “8”, “5”, “6”, “9”, “4”, “3”},
{“3”, “7”, “9”, “5”, “6”, “2”, “4”, “8”},
{“3”, “7”, “9”, “6”, “5”, “4”, “8”, “2”},
{“2”, “3”, “4”, “6”, “5”, “7”, “8”, “9”},
{“2”, “3”, “4”, “5”, “6”, “8”, “9”, “7”},
{“7”, “2”, “8”, “5”, “6”, “3”, “9”, “4”},
{“7”, “2”, “8”, “6”, “5”, “9”, “4”, “3”},
{“3”, “7”, “9”, “6”, “5”, “2”, “4”, “8”},
{“3”, “7”, “9”, “5”, “6”, “4”, “8”, “2”}

Caso 2. 12354786. 26845713. IAS 10. Es cycle-entangled. Unknown según Ruskey & Effler.

Idem anterior.

{“8”, “2”, “9”, “5”, “6”, “3”, “7”, “4”},
{“8”, “2”, “9”, “6”, “5”, “7”, “4”, “3”},
{“4”, “8”, “3”, “6”, “5”, “2”, “7”, “9”},
{“4”, “8”, “3”, “5”, “6”, “7”, “9”, “2”},
{“9”, “4”, “2”, “5”, “6”, “8”, “7”, “3”},
{“9”, “4”, “2”, “6”, “5”, “7”, “3”, “8”},
{“3”, “9”, “8”, “6”, “5”, “4”, “7”, “2”},
{“3”, “9”, “8”, “5”, “6”, “7”, “2”, “4”},
{“2”, “3”, “4”, “5”, “6”, “9”, “7”, “8”},
{“2”, “3”, “4”, “6”, “5”, “7”, “8”, “9”},
{“8”, “2”, “9”, “6”, “5”, “3”, “7”, “4”},
{“8”, “2”, “9”, “5”, “6”, “7”, “4”, “3”},
{“4”, “8”, “3”, “5”, “6”, “2”, “7”, “9”},
{“4”, “8”, “3”, “6”, “5”, “7”, “9”, “2”},
{“9”, “4”, “2”, “6”, “5”, “8”, “7”, “3”},
{“9”, “4”, “2”, “5”, “6”, “7”, “3”, “8”},
{“3”, “9”, “8”, “5”, “6”, “4”, “7”, “2”},
{“3”, “9”, “8”, “6”, “5”, “7”, “2”, “4”},
{“2”, “3”, “4”, “6”, “5”, “9”, “7”, “8”}

{“2”, “3”, “4”, “6”, “5”, “8”, “9”, “7”},
{“9”, “2”, “7”, “6”, “5”, “3”, “8”, “4”},
{“9”, “2”, “7”, “5”, “6”, “8”, “4”, “3”},
{“4”, “9”, “3”, “5”, “6”, “2”, “8”, “7”},
{“4”, “9”, “3”, “6”, “5”, “8”, “7”, “2”},
{“7”, “4”, “2”, “6”, “5”, “9”, “8”, “3”},
{“7”, “4”, “2”, “5”, “6”, “8”, “3”, “9”},
{“3”, “7”, “9”, “5”, “6”, “4”, “8”, “2”},
{“3”, “7”, “9”, “6”, “5”, “8”, “2”, “4”},
{“2”, “3”, “4”, “6”, “5”, “7”, “8”, “9”},
{“2”, “3”, “4”, “5”, “6”, “8”, “9”, “7”},
{“9”, “2”, “7”, “5”, “6”, “3”, “8”, “4”},
{“9”, “2”, “7”, “6”, “5”, “8”, “4”, “3”},
{“4”, “9”, “3”, “6”, “5”, “2”, “8”, “7”},
{“4”, “9”, “3”, “5”, “6”, “8”, “7”, “2”},
{“7”, “4”, “2”, “5”, “6”, “9”, “8”, “3”},
{“7”, “4”, “2”, “6”, “5”, “8”, “3”, “9”},
{“3”, “7”, “9”, “6”, “5”, “4”, “8”, “2”},
{“3”, “7”, “9”, “5”, “6”, “8”, “2”, “4”}

Caso 3. 12346587. 21456738. IAS10. Es  cycle-entangled. No tiene ciclos hamiltonianos según Ruskey & Effler. 

{“3”, “2”, “8”, “4”, “5”, “6”, “7”, “9”},
{“3”, “2”, “8”, “4”, “6”, “5”, “9”, “7”},
{“2”, “3”, “9”, “8”, “4”, “6”, “5”, “7”},
{“2”, “3”, “9”, “8”, “6”, “4”, “7”, “5”},
{“3”, “2”, “7”, “9”, “8”, “6”, “4”, “5”},
{“3”, “2”, “7”, “9”, “6”, “8”, “5”, “4”},
{“2”, “3”, “5”, “7”, “9”, “6”, “8”, “4”},
{“2”, “3”, “5”, “7”, “6”, “9”, “4”, “8”},
{“3”, “2”, “4”, “5”, “7”, “6”, “9”, “8”},
{“3”, “2”, “4”, “5”, “6”, “7”, “8”, “9”},
{“2”, “3”, “8”, “4”, “5”, “6”, “7”, “9”},
{“2”, “3”, “8”, “4”, “6”, “5”, “9”, “7”},
{“3”, “2”, “9”, “8”, “4”, “6”, “5”, “7”},
{“3”, “2”, “9”, “8”, “6”, “4”, “7”, “5”},
{“2”, “3”, “7”, “9”, “8”, “6”, “4”, “5”},
{“2”, “3”, “7”, “9”, “6”, “8”, “5”, “4”},
{“3”, “2”, “5”, “7”, “9”, “6”, “8”, “4”},
{“3”, “2”, “5”, “7”, “6”, “9”, “4”, “8”},
{“2”, “3”, “4”, “5”, “7”, “6”, “9”, “8”}

{“2”, “3”, “4”, “5”, “7”, “6”, “9”, “8”},
{“3”, “2”, “9”, “4”, “5”, “7”, “6”, “8”},
{“3”, “2”, “9”, “4”, “7”, “5”, “8”, “6”},
{“2”, “3”, “8”, “9”, “4”, “7”, “5”, “6”},
{“2”, “3”, “8”, “9”, “7”, “4”, “6”, “5”},
{“3”, “2”, “6”, “8”, “9”, “7”, “4”, “5”},
{“3”, “2”, “6”, “8”, “7”, “9”, “5”, “4”},
{“2”, “3”, “5”, “6”, “8”, “7”, “9”, “4”},
{“2”, “3”, “5”, “6”, “7”, “8”, “4”, “9”},
{“3”, “2”, “4”, “5”, “6”, “7”, “8”, “9”},
{“3”, “2”, “4”, “5”, “7”, “6”, “9”, “8”},
{“2”, “3”, “9”, “4”, “5”, “7”, “6”, “8”},
{“2”, “3”, “9”, “4”, “7”, “5”, “8”, “6”},
{“3”, “2”, “8”, “9”, “4”, “7”, “5”, “6”},
{“3”, “2”, “8”, “9”, “7”, “4”, “6”, “5”},
{“2”, “3”, “6”, “8”, “9”, “7”, “4”, “5”},
{“2”, “3”, “6”, “8”, “7”, “9”, “5”, “4”},
{“3”, “2”, “5”, “6”, “8”, “7”, “9”, “4”},
{“3”, “2”, “5”, “6”, “7”, “8”, “4”, “9”}

Caso 4. 12356784. 21456738. IAS 6.

{“3”, “2”, “8”, “4”, “5”, “6”, “7”, “9”},
{“3”, “2”, “8”, “5”, “6”, “7”, “9”, “4”},
{“2”, “3”, “9”, “8”, “5”, “6”, “7”, “4”},
{“2”, “3”, “9”, “5”, “6”, “7”, “4”, “8”},
{“3”, “2”, “4”, “9”, “5”, “6”, “7”, “8”},
{“3”, “2”, “4”, “5”, “6”, “7”, “8”, “9”},
{“2”, “3”, “8”, “4”, “5”, “6”, “7”, “9”},
{“2”, “3”, “8”, “5”, “6”, “7”, “9”, “4”},
{“3”, “2”, “9”, “8”, “5”, “6”, “7”, “4”},
{“3”, “2”, “9”, “5”, “6”, “7”, “4”, “8”},
{“2”, “3”, “4”, “9”, “5”, “6”, “7”, “8”}

{“2”, “3”, “4”, “6”, “7”, “8”, “9”, “5”},
{“3”, “2”, “9”, “4”, “6”, “7”, “8”, “5”},
{“3”, “2”, “9”, “6”, “7”, “8”, “5”, “4”},
{“2”, “3”, “5”, “9”, “6”, “7”, “8”, “4”},
{“2”, “3”, “5”, “6”, “7”, “8”, “4”, “9”},
{“3”, “2”, “4”, “5”, “6”, “7”, “8”, “9”},
{“3”, “2”, “4”, “6”, “7”, “8”, “9”, “5”},
{“2”, “3”, “9”, “4”, “6”, “7”, “8”, “5”},
{“2”, “3”, “9”, “6”, “7”, “8”, “5”, “4”},
{“3”, “2”, “5”, “9”, “6”, “7”, “8”, “4”},
{“3”, “2”, “5”, “6”, “7”, “8”, “4”, “9”}

En fin, idem lo que hemos comentado en el primer párrafo: el patrón está claro, así se las ponían a Fernando VII.  ¿ Pero cuando un caso es cycle-entangled, entonces se da necesariamente la relación (x^(-1) y)^n = (yx^-1)^n) ? 

3. Aunque con las explicaciones de todas las entradas anteriores sobre este tema está claro a que nos referimos cuando hablamos de circunferencia, tengo que ver cual es la mejor definición de este concepto. La definición por el orden no es la más clara pues orden 2 tienen los casos entangled por  la permutación opuesta a la identidad en el IAS, cuya circunferencia tiene dos “IASes” (uno es el DAS) y orden 2 tienen aquellos que no son entangled (salvo a lo mejor por tener un generador de orden 2) y cuya circunferencia contiene 4 IASes.   Nos quedamos por lo tanto con la definición que da el número de IASes.

Por otra parte el lector preparado (en sentido de Erdos) habrá detectado un patrón en la permutación opuesta a la identidad en aquellos casos en los que la circunferencia contiene sólo dos IASes. Lo dejamos aquí.

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: