Caso 2-4 generado de S6, a prueba.

Se trata del caso con propiedades S6, G8, C2C4, IAS6 y circunferencia 3 (6 IASes). Generadores 12436587 y 35147268. Lo estoy dibujando y tengo la expectativa de que sea smooth y por lo tanto tenga IASes en todos los vértices finales posibles. Ya Ruskey y Effler nos confirma que tiene ciclos. De momento buscaremos los paths y si se confirma que los tiene en todos los VFs, en función de lo que tarde daremos también los ciclos. Calculo que el algoritmo, tal y como lo he programado puede tardar varias horas en encontrarlos. Iré actualizando.

Nota.

La fórmula para calcular el número de permutaciones que contiene el entorno para estos casos en concreto (2-4 generados) es:

[2i+i+i*(2(i-2))+i*(2(i-4))]+[(2i-6)+(i-6)*2(i-2)+(i-6)*2(i-4)], con i =orden del IAS.

Ojo, fórmula anterior está en revisión…La nueva y correcta:

2i+i(2i-2)+i(2i-4) + (2i-6)/2*(2i-2) +((2i-6)/2+1)*(2i-4), con i= orden del IAS. Desarrollando se obtiene la fórmula simplificada equivalente (8i^2)-20i+14.

Relacionando la cantidad que se obtenga con la fórmula con el número total de permutaciones se puede determinar si el caso es twisted o no.

Más concretamente, en principio (tema a cerrar) la regla es como sigue: si la cantidad que se obtenga de aplicar esta fórmula es superior al orden del dígrafo /2 el caso será twistd y si es inferior, será smooth.

Entiendo que no es complicado (hay que incorporar el orden del ciclo que no es de orden 2) pasar a una fórmula general para determinar el número de permutaciones del entorno cuando uno de los generadores es una involución y el  otro es de cualquier orden. y también debe de ser posible con cualquier orden para los generadores. Estamos trabajando en ello y en breve las daremos.

Fin de nota.

VF = 42316875, en prueba. Lleva ya 2 horas y media y de momento 6 opciones, sin ninguna llamada a backtraking. No recuerdo ahora mismo como  estimar el numero de opciones que debemos de esperar en casos smooth. Intentaré hacer memoria…Ayer por accidente, tras casi 10 horas (13 opciones se apagó el ordenador). Y recomencé pero con otro vértice, ya que de principio se activan bastantes IASes y por lo tanto es de esperar que la computación tarde menos.

VF=46312875, en prueba. Lleva ya 12 horas y de momento 12 opciones. Como en el VF anterior, cuya computación no terminó por accidente, en la opción 12 empieza a hacer muchas más comprobaciones que en las anteriores opciones. Según mis estimaciones, en el mejor de los casos (si en cada opción dónde haya elección, eligiese el generador de orden 2) tardaría unas 20 opciones. En el peor de los casos, unas 60…Es decir es un caso que puede tardar incluso días. Voy a tener paciencia e intentar que en este VF remate la computación. Y voy a intentar reprogramar el algoritmo para que elija cuando pueda el generador de orden 2 (esto puede ser complicado, pues aunque lo programé yo, no entiendo bien el programa, ya que esta parte en concreto no la tengo bien documentada) y tocarlo puede ser peligroso para su integridad).

Actualización 13 de junio de 2016, 12:30.

El programa sigue ejecutándose. 3 días y medio. 34 opciones y 9 llamadas a backtraking. De momento entiendo que todo dentro de la normalidad: aunque es smooth, por sus propiedades tiene pocos RHs en cada VF y por lo tanto le cuesta encontrar uno. Sigo teniendo paciencia pero no se si voy a poder tener mucho más: necesito usar el ordenador.

Fin de actualización.

Actualización 14 de junio de 2016.

Sigue la búsqueda. ras más de 4 días y medio, 42 opciones y algunas llamadas más a backtraking. Voy a esperar un día más y si no ha encontrado nada lo tengo que parar. Por necesidad de usar el ordenador y porque quiero modificar un poco el programa para tener más información a medida de que vaya ejecutando el programa: básicamente información sobre como va recorriendo el árbol durante l backtraking, cosa que ahora no tengo.

Quizás algún lector se pregunte si no se da aquí un fenómenos similar al delos casos 2-3 generados: que todas las secuencias de generadores posibles no puedan generar un RH. Si esto fuese así se hubiese puesto de manifiesto ya en los ciclos, y sabemos que el caso que estamos poniendo a prueba sí tiene ciclos hamiltonianos. Por lo tanto este tipo de obstrucción no puede darse. Sí es posible que muchas de estas secuencias no puedan generar un RH y por ello el algoritmo tarda en encontrar uno. Aunque este caso es bastante restringido pos sus propiedades (2-4 generado) al ser smooth es de esperar que tenga pocos, pero varios RHs en cada vértice final posible.

Como es evidente los RHs tienen que ser composiciones de las siguientes secuencias básicas de generadores (1 = orden 4 y 2 = orden 2): 1112, 1121, 1211, 2111, 1212, 2121, 2112, con determinadas reglas de composición (por ejemplo evitar componer dos secuencias básicas con dos 2ses seguidos, o con n4 1 seguidos. Por ejemplo: 1112+2111 no sería válida. Con estas siete secuencias básicas y las dos reglas de composición dadas, todavía hay muchas opciones de secuencias que se pueden construir. Algunas de ellas generarán un RH. Me gustaría tener detalles sobre la secuencia de los ciclos que obtuvieron Ruskey y Effler….

Fin de actualización. 

Actualización 15 de junio de 2016, con modificaciones el 16 de junio. 

51 opciones y una llamada de backtraking más. Voy a seguir teniendo paciencia 1 día más.

¿ Demuestra lo comentado en la actualización anterior (el hecho de que no sea aplicable la obstrucción de los casos 2-3 generados a este tipo de casos) que este tipo de casos tienen que tener caminos hamiltonianos en todos los VFs posibles ?  Para nada, puede haber otro tipo de obstrucciones…

¿ Hay casos similares que tienen RHs en los VFs que son ciclos y no los tienen en el resto de RHs posibles ? He revisado la base de datos correspondiente a S4 y s5 y esta situación no es nada frecuente: es frecuente que haya casos sin RHs en los VFs ciclos pero sí tengan en algunos VFs caminos.

Aunque no sea frecuente, confirmo que hay dos casos:

–en uno los dos generadores son de orden 2 y como es sabido en estos casos el dígrafo es un ciclo, que obviamente no puede tener caminos hamiltonianos. Aunque conviene analizar con más detenimiento la obstrucción de estos casos, no lo veo muy relevante para el tema que nos ocupa.

–el otro caso si es relevante: es precisamente 2-4 generado, de S5. Sus otros parámetros son IAS 15 y circunferencia de orden 2 (creo que contiene 4 Iases). No es exactamente comparable con el caso que nos ocupa: primero porque su IAS es de orden impar y por lo tanto es de aplicación el teorema de Rankin (no tiene ciclos y no tiene RHs en algunos de los VFs posibles que sean caminos) y segundo, a diferencia del caso que nos ocupa, es entangled, de hecho muy entangled, en el sentido de que el IAS de la identidad y el DAS se entrelazan en varias permutaciones. Sí puedo confirmar que tiene RHs en los dos VFs más cercanos a la identidad y no en el resto (según anoté, aunque me gustaría volver a aplicar el algoritmo a este caso). El hecho de que tenga RHs en los VFs más cercanos a la identidad pero no en el resto de VFs, se debe a una propiedad aplicable a todos los 2-4 generados, independientemente de sus propiedades estructurales,  a partir de un determinado tamaño o se debe a las propiedades estructurales específicas de este caso en concreto  ? .

Por todo lo comentado, este caso, junto al que estamos analizando son muy interesantes. Publicaremos su dibujo y un análisis más completo en cuanto que tengamos acceso al ordenador.

Fin de actualización.

Actualización 17 de junio de 2016.

64 opciones y 22 llamadas a backtraking. Realmente el número de opciones no dice mucho si no sabemos cuales que número de ellas están activas en este momento (otras se corresponden a trayectorias de backtraking que se han desechado). Voy a intentar ver si es posible recuperar esta información con la información que se va imprimiendo a medida que se ejecuta el programa y en función de lo que consiga decidiré si aborto la ejecución o sigo teniendo paciencia (he visto que también se puede interrumpir; no se que permite la interrupción, pero primero probaré con esta opción).

Entre otras cosas quiero tener disponible el ordenador para poder publicar el dibujo completo del caso de S5  que hemos comentado en la actualización anterior: se aprecia muy claramente (no es evidente pero tampoco complicado detectarlo) cual es el mecanismo que hace que algunos VFs finales posibles no puedan tener RHs y lo más importante, se aprecia que este mecanismo depende 100% de la condición estructural de ser entangled o entrelazado. Por lo tanto este mecanismo no aplica al caso que estudiamos, que entendemos es smooth (no lo hemos dibujado todavía).

Comentar también que encontré manualmente una solución y confirmo que no hay muchas más: calculo que cuatro más como mucho. Por lo tanto estos casos 2-4 generados, como los 2-3 generados tienen pocos RHs para cada VF posible (cuando hay soluciones).  Entiendo que esto es así aunque sean smooth, como creo lo es el caso que exploramos. Por lo tanto no es de esperar que el algoritmo lo encuentre rápidamente. En efecto, recordemos que si usamos el método de fuerza bruta de activar todos los IASes (que ya mejora el método de fuerza bruta de activar todos los arcos por un generador o por otro, método que sería 2^720) estamos explorando en este caso en concreto un árbol de 2^120. Esto está ya al límite de las posibilidades de la frontera tecnológica actual: una búsqueda exhaustiva de una clave de 80 bits (árbol de 2^80), se considera segura…Y de momento llevamos explorado una pequeña parte. Esto es así aunque nuestro algoritmo, aun siendo de búsqueda exhaustiva determinista, no explora un árbol tan extenso como de 2^120 (aunque no tengo claro de momento cual es el tamaño del árbol que estamos explorando).

En el caso de S5 queda claro una vez más por qué la propiedad de entrelazado es causa de que operen mecanismos que generan obstrucciones al problema de recorridos hamiltonianos, mecanismos que no son operativos cuando los casos no son smooth.

Fin de actualización.

Actualización 19 de junio de 2016, 23:25; ampliado 20 de junio de 2016.

Finalmente lo he parado, a 81 opciones y 32 llamadas a backtraking. Con el modo interrupción se pone muy pesado y no me permite utilizar el ordenador. Lo primero que voy a hacer es poner a prueba el algoritmo para los VF ciclos de este mismo caso. Cuanto tarde en encontrar uno (opciones, llamadas a backtraking) nos puede dar una referencia sobre cuanto puede tardar en encontrar un RH en otros VFs.

A continuación el caso de S5 que hemos comentado en las actualizaciones anteriores.

S5 c2c4 IAS15

A continuación una imagen que muestra uno de los posibles RHs en el vértice final posible (VF) 257149386. Diría que no está muy claro…Pido disculpas por ello al lector.

S5 C2C4 IAS15 RH

También el recorrido según lo  ha encontrado el algoritmo (de izquierda a derecha, de arriba a abajo). Lo encuentra tras una opción.

 {vi, {3, 5, 7, 6, 2, 4, 9, 8, 10}, {3, 5, 7, 2, 6, 9, 4, 10, 8}, {5,
2, 9, 6, 3, 7, 10, 4, 8}, {5, 2, 9, 3, 6, 10, 7, 8, 4}, {2,
3, 10, 6, 5, 9, 8, 7, 4}, {2, 3, 10, 5, 6, 8, 9, 4, 7}, {3,
5, 8, 6, 2, 10, 4, 9, 7}, {3, 5, 8, 2, 6, 4, 10, 7, 9}, {5,
2, 4, 6, 3, 8, 7, 10, 9}, {5, 2, 4, 3, 6, 7, 8, 9, 10}, {2,
3, 7, 6, 5, 4, 9, 8, 10}, {2, 3, 7, 5, 6, 9, 4, 10, 8}, {3,
5, 9, 6, 2, 7, 10, 4, 8}, {3, 5, 9, 2, 6, 10, 7, 8, 4}, {5,
2, 10, 6, 3, 9, 8, 7, 4}, {5, 2, 10, 3, 6, 8, 9, 4, 7}, {2,
3, 8, 6, 5, 10, 4, 9, 7}, {2, 3, 8, 5, 6, 4, 10, 7, 9}, {3,
5, 4, 6, 2, 8, 7, 10, 9}, {3, 5, 4, 2, 6, 7, 8, 9, 10}, {5,
2, 7, 6, 3, 4, 9, 8, 10}, {5, 2, 7, 3, 6, 9, 4, 10, 8}, {2,
3, 9, 6, 5, 7, 10, 4, 8}, {2, 3, 9, 5, 6, 10, 7, 8, 4}, {3,
5, 10, 6, 2, 9, 8, 7, 4}, {3, 5, 10, 2, 6, 8, 9, 4, 7}, {5,
2, 8, 6, 3, 10, 4, 9, 7}, {5, 2, 8, 3, 6, 4, 10, 7, 9}, {2,
3, 4, 6, 5, 8, 7, 10, 9}, {3, 6, 8, 5, 2, 4, 10, 7, 9}, {6,
5, 4, 2, 3, 8, 7, 10, 9}, {6, 5, 4, 3, 2, 7, 8, 9, 10}, {5, 3, 7, 2, 6,
4, 9, 8, 10}, {3, 2, 4, 6, 5, 7, 8, 9, 10}, {
2, 6, 7, 5, 3, 4, 9, 8, 10}, {2, 6, 7, 3, 5, 9, 4, 10, 8}, {
6, 3, 9, 5, 2, 7, 10, 4, 8}, {6, 3, 9, 2, 5, 10, 7, 8, 4}, {
3, 2, 10, 5, 6, 9, 8, 7, 4}, {2, 5, 9, 6, 3, 10, 7, 8, 4}, {
5, 6, 10, 3, 2, 9, 8, 7, 4}, {5, 6, 10, 2, 3, 8, 9, 4, 7}, {
6, 2, 8, 3, 5, 10, 4, 9, 7}, {6, 2, 8, 5, 3, 4, 10, 7, 9}, {
2, 5, 4, 3, 6, 8, 7, 10, 9}, {5, 3, 8, 6, 2, 4, 10, 7, 9}, {
3, 6, 4, 2, 5, 8, 7, 10, 9}, {3, 6, 4, 5, 2, 7, 8, 9, 10}, {
6, 5, 7, 2, 3, 4, 9, 8, 10}, {6, 5, 7, 3, 2, 9, 4, 10, 8}, {
5, 3, 9, 2, 6, 7, 10, 4, 8}, {3, 2, 7, 6, 5, 9, 4, 10, 8}, {
2, 6, 9, 5, 3, 7, 10, 4, 8}, {2, 6, 9, 3, 5, 10, 7, 8, 4}, {
6, 3, 10, 5, 2, 9, 8, 7, 4}, {6, 3, 10, 2, 5, 8, 9, 4, 7}, {
3, 2, 8, 5, 6, 10, 4, 9, 7}, {2, 5, 10, 6, 3, 8, 9, 4, 7}, {
5, 6, 8, 3, 2, 10, 4, 9, 7}, {5, 6, 8, 2, 3, 4, 10, 7, 9}, {
6, 2, 4, 3, 5, 8, 7, 10, 9}, {6, 2, 4, 5, 3, 7, 8,
9, 10}, {2, 5, 7, 3, 6, 4, 9, 8, 10}, {5, 3, 4, 6, 2, 7, 8,
9, 10}, {3, 6, 7, 2, 5, 4, 9, 8, 10}, {3, 6, 7, 5, 2, 9, 4,
10, 8}, {6, 5, 9, 2, 3, 7, 10, 4, 8}, {6, 5, 9, 3, 2, 10, 7,
8, 4}, {5, 3, 10, 2, 6, 9, 8, 7, 4}, {3, 2, 9, 6, 5, 10, 7, 8,
4}, {2, 6, 10, 5, 3, 9, 8, 7, 4}, {2, 6, 10, 3, 5, 8, 9, 4,
7}, {6, 3, 8, 5, 2, 10, 4, 9, 7}, {6, 3, 8, 2, 5, 4, 10, 7,
9}, {3, 2, 4, 5, 6, 8, 7, 10, 9}, {2, 5, 8, 6, 3, 4, 10, 7,
9}, {5, 6, 4, 3, 2, 8, 7, 10, 9}, {5, 6, 4, 2, 3, 7, 8, 9, 10}, {6, 2, 7,
3, 5, 4, 9, 8, 10}, {6, 2, 7, 5, 3, 9, 4, 10,
8}, {2, 5, 9, 3, 6, 7, 10, 4, 8}, {5, 3, 7, 6, 2, 9, 4, 10,
8}, {3, 6, 9, 2, 5, 7, 10, 4, 8}, {3, 6, 9, 5, 2, 10, 7, 8,
4}, {6, 5, 10, 2, 3, 9, 8, 7, 4}, {6, 5, 10, 3, 2, 8, 9, 4,
7}, {5, 3, 8, 2, 6, 10, 4, 9, 7}, {3, 2, 10, 6, 5, 8, 9, 4,
7}, {2, 6, 8, 5, 3, 10, 4, 9, 7}, {2, 6, 8, 3, 5, 4, 10, 7,
9}, {6, 3, 4, 5, 2, 8, 7, 10, 9}, {6, 3, 4, 2, 5, 7,
8, 9, 10}, {3, 2, 7, 5, 6, 4, 9, 8, 10}, {2, 5, 4, 6, 3, 7,
8, 9, 10}, {5, 6, 7, 3, 2, 4, 9, 8, 10}, {5, 6, 7, 2, 3, 9,
4, 10, 8}, {6, 2, 9, 3, 5, 7, 10, 4, 8}, {6, 2, 9, 5, 3, 10,
7, 8, 4}, {2, 5, 10, 3, 6, 9, 8, 7, 4}, {5, 3, 9, 6, 2, 10, 7, 8,
4}, {3, 6, 10, 2, 5, 9, 8, 7, 4}, {3, 6, 10, 5, 2, 8, 9, 4,
7}, {6, 5, 8, 2, 3, 10, 4, 9, 7}, {6, 5, 8, 3, 2, 4, 10,
7, 9}, {5, 3, 4, 2, 6, 8, 7, 10, 9}, {3, 2, 8, 6, 5, 4, 10,
7, 9}, {2, 6, 4, 5, 3, 8, 7, 10, 9}, {2, 6, 4, 3, 5, 7, 8,
9, 10}, {6, 3, 7, 5, 2, 4, 9, 8, 10}, {6, 3, 7, 2, 5, 9, 4,
10, 8}, {3, 2, 9, 5, 6, 7, 10, 4, 8}, {2, 5, 7, 6, 3, 9, 4,
10, 8}, {5, 6, 9, 3, 2, 7, 10, 4, 8}, {5, 6, 9, 2, 3, 10, 7,
8, 4}, {6, 2, 10, 3, 5, 9, 8, 7, 4}, {6, 2, 10, 5, 3, 8, 9,
4, 7}, {2, 5, 8, 3, 6, 10, 4, 9, 7}, {5, 3, 10, 6, 2, 8, 9, 4, 7}, vf}

He comprobado que no tiene RH en el resto de VFs salvo en el último posible, es decir 258146937. En este caso lo ha encontrado tras dos opciones.

 {vi, {2, 3, 4, 6, 5, 8, 7, 10, 9}, {3, 6, 8, 5, 2, 4, 10, 7, 9}, {6,
5, 4, 2, 3, 8, 7, 10, 9}, {5, 2, 8, 3, 6, 4, 10, 7, 9}, {5,
2, 8, 6, 3, 10, 4, 9, 7}, {2, 6, 10, 3, 5, 8, 9, 4, 7}, {6,
3, 8, 5, 2, 10, 4, 9, 7}, {3, 5, 10, 2, 6, 8, 9, 4, 7}, {3,
5, 10, 6, 2, 9, 8, 7, 4}, {5, 6, 9, 2, 3, 10, 7, 8, 4}, {6,
2, 10, 3, 5, 9, 8, 7, 4}, {2, 3, 9, 5, 6, 10, 7, 8, 4}, {2,
3, 9, 6, 5, 7, 10, 4, 8}, {3, 6, 7, 5, 2, 9, 4, 10, 8}, {6,
5, 9, 2, 3, 7, 10, 4, 8}, {5, 2, 7, 3, 6, 9, 4, 10, 8}, {5,
2, 7, 6, 3, 4, 9, 8, 10}, {2, 6, 4, 3, 5, 7, 8, 9, 10}, {6,
3, 7, 5, 2, 4, 9, 8, 10}, {3, 5, 4, 2, 6, 7, 8, 9, 10}, {3,
5, 4, 6, 2, 8, 7, 10, 9}, {5, 6, 8, 2, 3, 4, 10, 7, 9}, {6,
2, 4, 3, 5, 8, 7, 10, 9}, {2, 3, 8, 5, 6, 4, 10, 7, 9}, {2,
3, 8, 6, 5, 10, 4, 9, 7}, {3, 6, 10, 5, 2, 8, 9, 4, 7}, {6,
5, 8, 2, 3, 10, 4, 9, 7}, {5, 2, 10, 3, 6, 8, 9, 4, 7}, {5,
2, 10, 6, 3, 9, 8, 7, 4}, {2, 6, 9, 3, 5, 10, 7, 8, 4}, {6,
3, 10, 5, 2, 9, 8, 7, 4}, {3, 5, 9, 2, 6, 10, 7, 8,
4}, {3, 5, 9, 6, 2, 7, 10, 4, 8}, {5, 6, 7, 2, 3, 9, 4, 10, 8}, {
6, 2, 9, 3, 5, 7, 10, 4, 8}, {2, 3, 7, 5, 6, 9, 4, 10, 8}, {
2, 3, 7, 6, 5, 4, 9, 8, 10}, {3, 6, 4, 5, 2, 7, 8, 9, 10}, {
6, 5, 7, 2, 3, 4, 9, 8, 10}, {5, 2, 4, 3, 6, 7, 8, 9, 10}, {
5, 2, 4, 6, 3, 8, 7, 10, 9}, {2, 6, 8, 3, 5, 4, 10, 7, 9}, {
6, 3, 4, 5, 2, 8, 7, 10, 9}, {3, 5, 8, 2, 6, 4, 10, 7, 9}, {
3, 5, 8, 6, 2, 10, 4, 9, 7}, {5, 6, 10, 2, 3, 8, 9, 4, 7}, {
6, 2, 8, 3, 5, 10, 4, 9, 7}, {2, 3, 10, 5, 6, 8, 9, 4, 7}, {
2, 3, 10, 6, 5, 9, 8, 7, 4}, {3, 6, 9, 5, 2, 10, 7, 8, 4}, {
6, 5, 10, 2, 3, 9, 8, 7, 4}, {5, 2, 9, 3, 6, 10, 7, 8, 4}, {
5, 2, 9, 6, 3, 7, 10, 4, 8}, {2, 6, 7, 3, 5, 9, 4, 10, 8}, {
6, 3, 9, 5, 2, 7, 10, 4, 8}, {3, 5, 7, 2, 6, 9, 4, 10, 8}, {
3, 5, 7, 6, 2, 4, 9, 8, 10}, {5, 6, 4, 2, 3, 7, 8, 9, 10}, {
6, 2, 7, 3, 5, 4, 9, 8, 10}, {6, 2, 7, 5, 3, 9, 4, 10, 8}, {
2, 5, 9, 3, 6, 7, 10, 4, 8}, {2, 5, 9, 6, 3, 10, 7,
8, 4}, {5, 6, 10, 3, 2, 9, 8, 7, 4}, {6, 3, 9, 2, 5, 10, 7,
8, 4}, {3, 2, 10, 5, 6, 9, 8, 7, 4}, {3, 2, 10, 6, 5, 8, 9,
4, 7}, {2, 6, 8, 5, 3, 10, 4, 9, 7}, {6, 5, 10, 3, 2, 8, 9,
4, 7}, {5, 3, 8, 2, 6, 10, 4, 9, 7}, {5, 3, 8, 6, 2, 4, 10, 7,
9}, {3, 6, 4, 2, 5, 8, 7, 10, 9}, {6, 2, 8, 5, 3, 4, 10, 7,
9}, {2, 5, 4, 3, 6, 8, 7, 10, 9}, {2, 5, 4, 6, 3, 7, 8, 9, 10}, {5, 6, 7,
3, 2, 4, 9, 8, 10}, {6, 3, 4, 2, 5, 7, 8, 9, 10}, {3, 2, 7, 5, 6, 4, 9,
8, 10}, {3, 2, 7, 6, 5, 9, 4, 10,
8}, {2, 6, 9, 5, 3, 7, 10, 4, 8}, {6, 5, 7, 3, 2, 9, 4, 10,
8}, {5, 3, 9, 2, 6, 7, 10, 4, 8}, {5, 3, 9, 6, 2, 10, 7, 8,
4}, {3, 6, 10, 2, 5, 9, 8, 7, 4}, {6, 2, 9, 5, 3, 10, 7, 8,
4}, {2, 5, 10, 3, 6, 9, 8, 7, 4}, {2, 5, 10, 6, 3, 8, 9, 4,
7}, {5, 6, 8, 3, 2, 10, 4, 9, 7}, {6, 3, 10, 2, 5, 8, 9, 4,
7}, {3, 2, 8, 5, 6, 10, 4, 9, 7}, {3, 2, 8, 6, 5, 4, 10, 7,
9}, {2, 6, 4, 5, 3, 8, 7, 10, 9}, {6, 5, 8, 3, 2, 4,
10, 7, 9}, {5, 3, 4, 2, 6, 8, 7, 10, 9}, {5, 3, 4, 6, 2, 7,
8, 9, 10}, {3, 6, 7, 2, 5, 4, 9, 8, 10}, {6, 2, 4, 5, 3, 7,
8, 9, 10}, {2, 5, 7, 3, 6, 4, 9, 8, 10}, {2, 5, 7, 6, 3, 9,
4, 10, 8}, {5, 6, 9, 3, 2, 7, 10, 4, 8}, {6, 3, 7, 2, 5, 9, 4, 10,
8}, {3, 2, 9, 5, 6, 7, 10, 4, 8}, {3, 2, 9, 6, 5, 10, 7, 8,
4}, {2, 6, 10, 5, 3, 9, 8, 7, 4}, {6, 5, 9, 3, 2, 10, 7,
8, 4}, {5, 3, 10, 2, 6, 9, 8, 7, 4}, {5, 3, 10, 6, 2, 8, 9,
4, 7}, {3, 6, 8, 2, 5, 10, 4, 9, 7}, {6, 2, 10, 5, 3, 8, 9,
4, 7}, {2, 5, 8, 3, 6, 10, 4, 9, 7}, {2, 5, 8, 6, 3, 4, 10,
7, 9}, {5, 6, 4, 3, 2, 8, 7, 10, 9}, {6, 3, 8, 2, 5, 4, 10,
7, 9}, {3, 2, 4, 5, 6, 8, 7, 10, 9}, {3, 2, 4, 6, 5, 7, 8,
9, 10}, {2, 6, 7, 5, 3, 4, 9, 8, 10}, {6, 5, 4, 3, 2, 7, 8,
9, 10}, {5, 3, 7, 2, 6, 4, 9, 8, 10}, {5, 3, 7, 6, 2, 9, 4, 10, 8}, vf}

Es importante, para la explicación que sigue, ver que:

primero, el mínimo de IASes activados por C2 (por el generador de orden 2) tiene que ser 2 (algunos apuntes que demuestran que esto tiene que ser así; el caso tiene 120 vértices; C4C4C4C2 = identidad; 120 /4 = 30; el orden del IAS x 2 = 30; en resumen si hubiese menos de dos IASes marcados por C2 habría ciclos de C4).

segundo, por otra parte esto no es suficiente, pues (C4C4C4C2)^15 = identidad. Por lo tanto hacen falta más arcos / IASes activados por C2.

–finalmente, en tercer lugar, también hay una cantidad máxima de activaciones por C2, que al rebasarse hace que haya ciclos de C2 activados, lo cual es contradictorio con la existencia de un RH (por ejemplo, no puede haber 4 IASES activados por C2, pues se rebasaría este límite: si activamos 4 haciendo una secuencia de generadores de tipo C2C4 o C4 C2, tenemos que (C4C2)^15=identidad; y si hacemos otra secuencia distribuyendo los 30 arcos de los 2 IASes que activamos por C2 entre la secuencia C4C4C4C2 aparecerán necesariamente ciclos de C2).

Y en la  imagen siguiente se aprecia por qué cuando el VF es 128546937 no puede haber recorridos hamiltonianos: al decidir que este es el vértice final, el IAS verde, azul y negro se activan necesariamente por C4 (ojo, cosa que también pasa en el IAS anterior); hay tres ciclos de C4 a falta de un arco para cerrarse (están marcados en negro más oscuro): esto no pasa en el caso anterior en el que por haber marcado el Vf 257149386, sólo hay un ciclo de C4 en esta situación; esto fuerza que tres IASes de los que quedan (el gris, el verde oscuro y el amarillo, se marquen por C2 lo que sumados a los arcos del IAS de la identidad marcados por C2 también, hacen que se exceda la cantidad permitida de activaciones por C2.

S5 C2C4 IAS15 ciclos c4 marcados

Es fácil ver que si el caso no fuese entrelazado, es decir si fuese smooth, no sucedería esto. En efecto que el mecanismo que hace imposible que haya un RH en estos casos suceda se debe a:

–que en los tres ciclos de C4 que hemos comentado aparecen “los mismos” IASes: el de la identidad (el rojo), en los tres, el verde, en dos de ellos, el azul en dos de ellos y el negro en dos de ellos, y esto es debido a la propiedad de ser entrelazado.

–que los ciclos de 2 de el IAS rojo coinciden con los del verde claro, azul y negro. Al activarse el rojo por C2, obliga a que el verde claro, negro y azul se activen por C4.

Y es muy importante señalar que el mecanismo señalado tampoco opera en los casos twisted, que son, digamos, intermedios entre los entangled (como lo es el que estudiamos) y los smooth.  Como hemos visto en otras entradas, hay casos twisted 2-4 generados que no tienen RHs en ningún VF posible. ¿ Que mecanismo opera en estos casos ?.Sería interesante contestar a esta pregunta si buscamos una teoría general de la hamiltonicidad de los casos 2-4 generados….

En fin para terminar comentamos que el mismo mecanismo que hemos descrito sucede en todos los otros VFs de este mismo caso, hasta el último posible. Dejamos al lector que se explique a sí mismo que pasa cuando el VF es el 258146937. Confirmamos que sí hay RH en este caso. ¿ Como puede ser esto posible ?

Fin de actualización.

Actualización 21 de junio de 2016.

Estamos aplicando el algoritmo al caso en uno de los vértices ciclo. Tras unas 24 horas, 20 opciones y 2 llamadas a backtraking, en la opción 19 y en la 20. Hasta la opción 18 va directo, y en la 18 ya empieza a hacer muchas más operaciones que en las anteriores. Es equivalente a la opción 12 en las anteriores pruebas. Voy a seguir poniendolo a prueba al menos un día más.

Fin de actualización.

Actualización 22 de junio.

Parte diario: 23 opciones y 5 llamadas a backtraking. Se confirma que incluso en los VF ciclos no es sencillo encontrar el RH. Voy a dejar el programa ejecutándose un poco más.

Fin de actualización.

Actualización 23 de junio. 

Parte diario: 31 opciones y 7 llamadas a backtraking.

Fin de actualización.

Actualización 27 de junio de 2016.

Finalmente he abortado hoy la ejecución a las 11:00, tras 63 opciones y 19 llamadas a bactraking  (incluida la llamada antes de la opción 63. Necesito un uso intensivo del ordenador. Claramente no es rápido encontrar RHs en este tipo de digrafos, al menos con nuestro algoritmo aunque se sepa que existen. Todavía no tengo 100% claro el motivo de que tarde tanto, aunque posiblemente tenga que ver con el hecho de que el algoritmo no incorpora todo el conocimiento de que se dispone sobre estos casos 2-4 generados.

La no incoroporación de todo el conocimiento que se tiene sobre un caso es un serio handicap: tampoco lo incorpora en los casos cycle entangled. Y como consecuencia el algoritmo tal y como lo tengo implementado los acaba encontrando, pero puede ser duro hacerlo. En un caso concreto que tengo documentado, de S5, C5C6 IAS6 y cycle entangled, lo encuentra tras 573 opciones e innumerables llamadas a backtraking (no las he contado), lo cual para casos de 120 vértices es muchísimo.

Comentar también tras reflexión la formula que hemos dado en una nota anterior es incompleta: es válida para casos de C2C4 con IASes pequeños, como de orden 5 o 6 pero seguramente es incompleta para otro tipo de casos 2-4 generados en los que el IAS tenga un orden grande. Tema en investigación.

Fin de actualización.

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

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

Logo de WordPress.com

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

Imagen de Twitter

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

Foto de Facebook

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

Google+ photo

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

Conectando a %s


A %d blogueros les gusta esto: