HPC. Sobre la utilidad de la propiedad de entrelazado o entanglement y…a la búsqueda de casos retorcidos o twisted.

Disclaimer. Estoy a la búsqueda de dos cosas: casos que demuestren la utilidad de la propiedad entanglement y también de casos que sean twisted (para poder dar la definición más sencilla posible. 

Republico parte de una entrada de hace meses que considero de interés para este tema. La pongo otro título. La entrada original que incluía una larga introducción se titulaba HPC. Casos extraños de S6, 720 vértices y el lector podrá encontrarla fácilmente con una búsqueda de internet.

Es una entrada de investigación que iré completando. Ver actualización posterior.

En la base de datos elaborada por Ruskey y Effler hay en total 227 casos de S6. Recordamos que a estos dos investigadores sólo les interesaba encontrar ciclos hamiltonianos.

Y antes de empezar señalamos que las dos propiedades son parecidas: al igual que un caso entangled, que un caso sea twisted no implica necesariamente que sea complicado (realmente a diferencia de los entangled no he encontrado muchos casos twisted). Al contrario la propriedad de smooth no tiene claro oscuros: si un caso es smooth entonces hay 100% garantías de que tendrá recorridos hamiltonianos en todos los vértices finales posibles y el algoritmo de la primera patente los encontrará a la primera, sin backtraking.

Por grados:

–grado 6, 84.

–grado 8, 140.

–grado 9, sólo 3 (sólo incluían aquellos casos en los que un generador es una involución; aún así parecen pocos).

De todos estos me interesan:

a) Entangled pero no cycle-entangled en los que se han encontrado ciclos hamiltonianos.

Aquellos en los que han encontrado ciclos hamiltonianos (importante: ellos sólo buscaban ciclos, no caminos) y por lo tanto entiendo que son fáciles, pero son entangled (y por lo tanto potencialmente difíciles) y no cycle-entangled. A estos los llamo raros en el sentido de que los entangled son potencialmente difíciles. Hay 12 de éstos de grado 6, y he contado unos 22 de grado 8. Recordamos que por definición cuando uno de los dos generadores es de orden 2 el caso se considera entangled. Cuando digo que los entangled son potencialmente difíciles, me refiero a que o bien es posible que no tengan recorridos hamiltonianos en algunos vértices finales posibles o bien es posible que los tengan pero haya que utilizar el backtraking para encontrarlos. No digo que estos dos eventos se den en todos los entangled. Los más problemáticos serán cuando uno de los dos generadores sea de orden 2. De cualquier manera quede claro que no hay nada extraño en encontrar casos entangled no cyce entangled y con generadores que no sean de orden 2 con recorridos hamiltonianos. La pregunta es si se han encontrado con facilidad o con dificultad. Señalemos que un caso entangled puede tener vértices finales posibles para los que es fácil encontrar recorridos hamiltonianos.

Caso 1. G6, 123465 (orden 2), 234516 (orden 5). IAS, 6. Este es interesante por tener un generador de orden 2.

Caso 2. G6, 124563 (4), 236541 (4). IAS 6. No sorprende.

Caso 3. G6, 132564 (6), 214635 (4). IAS 6. No sorprende.

Caso 4. G6, 132564 (6), 234651 (5). IAS 6. No sorprende.

Caso 5. G6, 132564 (6), 412653 (5). IAS 6. No sorprende.

Casos 6, 7, 8, 9 son todos similares a los casos 2, 3, 4 o 5 y por lo tanto no sorprendentes.

Caso 10. G6, 124365 (2), 231546 (6). IAS 6. Interesante.

Caso 11. G6, 124365 (2), 341526 (6). IAS 6. Interesante.

Caso 12. G6, 124365 (2), 342561 (6). IAS 6. Interesante.

Continuará….

Actualización 2. 7 de diciembre de 2015.

De acuerdo con el comentario de la actualización siguiente, comprobar cual es la circunferencia de los casos anteriores, sobre todo de aquellos con un generador de orden 2.

Fin de actualización.

b) Casos no Rankin, sin ciclos hamiltonianos.

Aquellos en los que no han encontrado positivamente ciclos hamiltonianos y no entran dentro del teorema de Rankin. Son, si no he contado mal, cinco  casos. 2 se pueden explicar por ser cycle entangled, otros dos según anoté son cycle-entangled (mañana lo volveré a comprobar) y en uno no comprobé ésta propiedad (lo comprobaré mañana). Los interesantes son aquellos que no sean ni rankin ni cycle entangled, si finalmente se confirma que hay alguno (podrían ser 3). Habría que analizar sus propiedades. Si se confirma que hay algún caso de estos, podrían ser twisted.

Los casos:

Caso 1. 12354786 (orden 6), 26745183 (3), IAS (orden 10). Cycle-entangled por  un generador.

Caso 2. 12346587 (2), 21456738 (10), IAS (10), cycle-entangled por un generador.

Caso 3. 12356784 (5), 21435687 (2), IAS (10). Según aparece en mi base de datos, entangled. Y se ve que no puede ser cycle-entangled. Entiendo que es entangled no sólo por tener un generador que sea de orden 2 (recordemos que por definición, un caso  con un generador de orden 2 es entangled, pero en el momento en el que elaboré la base de datos, creo recordar que no trabajaba con esta definición). De confirmarse, interesante para analizar con más detalle.

Actualización 4. 7 de diciembre de 2015.

Caso 4. 12346587 (2), 21563784 (4), IAS (10), idem anterior. Este sí podría ser cycle-entangled pero no lo es, según anoté.

Actualización 3. 7 de diciembre de 2015.

Confirmamos que este caso 4 no es cycle-entangled. Y se confirma el patrón señalado en la actualización 1 de 7 de diciembre.

Ignacio Reneses Ejemplo de s6 entangled no cycle entnagled sin ciclos hamiltonianos

Fin de actualización 3.

Caso 5. 12436587 (2), 34156278 (4), IAS (10). en este no he marcado si es entangled o no, si es cycle-entangled o no. Seguramente será lo uno o lo otro.  Es el único que en principio podría ser twisted, pero seguramente será entangled.

Actualización 1. 7 de diciembre de 2015.

¡¡ Confirmado, entangled !!. Importante: la circunferencia es 2. ¿ Puede ser esto informativo ? Es decir, ¿ podría distinguir el orden la circunferencia aquellos casos entangled no cycle-entangled  con recorridos hamiltonianos en todos los vértices finales posibles de aquellos del mismo tipo que tienen vértices finales posibles sin recorridos hamiltonianos ?. El caso: 

Ignacio Reneses Ejemplo de S6 entangled sin ciclos hamiltonianos

De cualquier manera es un caso interesante y aparentemente, sólo con dibujar tres o cuatro IASes se podría demostrar que no es hamiltoniando. Pero tema a comprobar.

Fin de actualización.

c) Resultados Unknown.

Aquellos en los que, tras una búsqueda por ordenador de unos dos años estos dos investigadores no han podido decidir si existen o no existen ciclos hamiltonianos (ellos los califican como unknown, es decir, no se ha podido decidir si tienen o no tienen ciclos hamiltonianos). Si no recuerdo mal, la mayoría de éstos caen dentro de la categoría de cycle-entangled y gracias a nuestro resultado se puede determinar si los tienen o no los tienen. Me interesa sobre todo si existiese algún unknown  que no sea cycle entangled. Y confirmo que existe alguno.

Hay 29 unknowns. De estos 18 son cycle-entangled. El resto son todos entangled. Será muy interesante analizarlos, máxime cuando según he visto la mayoría no tienen generadores de orden 2.  Por definición un caso entangled es twisted, pero descartamos que sean twisted no entangled, que serían los casos que más nos interesa identificar ahora.

Los casos comentados:

Caso 1. G8, 12356784 (orden 5), 21436785 (4), IAS (6). Entangled, no cycle entangled, según anoté.

Caso 2. G8, 12356784 (5), 21436857 (4), IAS (10).  Entangled no cycle-entangled según anoté.

Caso 3. G8, 12356784 (5), 21437865 (4), IAS (6). idem anteriores.

Caso 4. G8,  12356784 (5), 21438756 (4), IAS (10), idem.

Caso 5. G8,   12356784 (5), 21457836 (4), IAS (10), idem.

Caso 6. G8,   12356784 (5), 21463587 (4), IAS (10), idem.

Caso 7. G8,  12436785 (4), 21457836 (4), IAS (10), idem.

Caso 8. G8,  12436785 (4), 21567483 (4), IAS (10), idem.

Caso 9. G8, 12453786 (3), 21436785 (4), IAS (6), idem.

Caso 10. G8, 12453786 (3), 21436857 (4), IAS (10), idem.

Caso 11. G8, 12453786 (3), 21467853 (4), IAS (10), idem.

Como se ve todos tienen unos parámetros bastante similares. Ninguno tiene un generador que sea involución.

Continuará….

Como se puede ver hay casos entangled seguros en los puntos a) y c). Los b) seguramente se confirmará que son cycle-entangled.

Esto significa que cuando se identifica la propiedad de entangled en un caso, se debe de encender la señal naranja de alerta, ya que el caso puede ser complicado. Si uno no quiere complicarse la vida, y hay más casos que cuadren con los otros parámetros, entonces se recomienda abandonar el caso entangled y seleccionar algún otro que teniendo los otros parámetros que interesan, sean unentangled.

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: