¿ Que diferencia un caso liso (smooth) de uno retorcido (twisted) ?

julio 20, 2016

Disclaimer: entrada en construcción. Terminará cuando se elimine esta advertencia.

En esta entrada intentamos contestar a la pregunta del título. Realmente es una entrada de investigación pues todavía no tengo claro si lo  que proponemos va a funcionar.

Para establecer la diferencia entre los dos casos, establecemos el siguiente procedimiento:

–numeramos todos los arcos de cada IAS con un mismo número. Por ejemplo el IAS de la identidad con el número 1, el DAS de la identidad con el número 2 etc….

–de esta manera cada ciclo de orden n se podrá describir con n números, de los  que hemos utilizado para numerar los IASes.

–hacemos  una tabla que cruce todos los ciclos de un mismo orden. Por ejemplo en los casos 2-4 generados, una tabla que cruce todos los ciclos de orden 4.

–Ponemos una cruz en los cruces de un ciclo consigo mismo, pues estos cruces no nos interesan. En las otras casillas anotamos los números que los dos ciclos que se cruzan tienen en común. En las casillas en las que los ciclos correspondientes no tienen secuencias o subsecuencias en común anotamos el número cero. Por ello evitaremos utilizar éste número a la hora de numerar todos los IASes.

Afirmamos (y ya veremos si finalmente esto es así o no) que los casos twisted y los casos smooth se pueden diferenciar analizando la tabla. Todavía no puedo expresar claramente la propiedad, pero en las tablas de casos smooth, no se van a repetir la secuencia de las casillas (total o parte de ella) más de dos veces (es decir no van a aparecer secuencias o subsecuencias iguales en más de 2 casillas).

Un primer ejemplo, el caso Sigma-Tau 2-5:

Trade Lane Megacities. Los rios de la vertiente occidental de los Zagros: los Zabs, Diyala, Karkheh y Karun.

julio 15, 2016

Nota. Tenía preparada esta entrada hace tiempo, como continuación de una anterior sobre un tema similar. Ahora que se ha publicado un nuevo artículo con resultados de arqueogenética de la zona de los Zagros, aquella sobre la que hablamos en esta entrada, en el período del Neolítico, parece oportuno publicarla. Aprovechamos para expresar nuestra solidaridad con los vecinos del norte.

En el título citamos los principales ríos de la zona, aunque, como veremos hay más.

Los dos (tres) primeros son afluentes del Tigris. El estatus sobre esto del tercero, el Karkheh, no está claro pues se dispersa en una marisma que une el Tigris con el Shatt el Arab. El cuarto es afluente de este último río, resultado de la confluencia de Tigris y Eufrates. Hemos descrito la situación actual. Es posible que en el pasado fuese diferente: en llanuras el curso delos ríos cambia con cierta frecuencia.

Las cuencas de los tres ríos señalados en el título penetran los Zagros casi hasta su vertiente oriental. En la imagen siguiente una panorámica general. El Diyala es aquel que confluye con el el Tigris dónde está localizado Baghdad.

rios zagros

1. Zabs y Diyala.

Las cuencas del gran y pequeño Zab se localizan casi enteramente en el territorio del actual Irak. Al otro lado de los Zagros en su vertiente oriental encontramos la cuenca endorreíca del lago Urmia. La ciudad principal que se encuentra en la zona baja, entre las dos cuencas es Arbil.  Y también entre ambos Zab, aunque ya en la orilla del Tigris se encontraba Assur, capital del Imperio Asirio.

Más al sur encontramos el Diyala, Río importante ya que su cuenca ha sido la más usada a lo largo de la historia como corredor oeste – este. Su longitud es de unos 600 km.

Diyala basin

Desde el punto de vista de la geografía humana es una cuenca ocupada, en su parte alta, montañosa, por las etnias kurdas,  y más al sur por otra etnias iraquíes. Anteriormente en la zona de Sulaymaniyah estaban localizados los Lullubum de las fuentes mesopotámicas.

Y desde el punto de vista de la geografía urbana en esta cuenca se encuentran parte de Baghdad (localizado en la confluencia Tigris-Diyala), Ba´qubah, Al Muqdadiyah, As Sulaymaniyah o Sanandaj. 

Uniendo en forma de arco con orientación noroeste sureste al Tigris y al Eufrates encontramos la cadena montañosa de Hamrin o Hamreen que entiendo no forma parte de los Zagros. Ha sido la frontera tradicional entre la tierra de Babilonia / Sumer al sur, y Asiria al norte. Aunque nuestro interés al redactar esta entrada no es de geopolítica actual, la imagen siguiente es bastante ilustrativa de la localización de esta cadena.

Battle_for_Diyala_05_Jan_08-775438

2. Karkheh y Karun. 

Karkheh karun rivers

Son dos ríos relativamente largos, de casi 1000 km cada uno. El Dez es un importante afluente del Karun.

Desde el punto de vista de la geografía humana, la cuenca norteña del Karkheh sigue siendo kurda (en el entorno de Kermanshah). Más al sur de esta ciudad ya entramos en zona de etnia Lur.

512px-Karunrivermapfinal

3. Otros.

Leer el resto de esta entrada »

Caso de S5 2-4 generado retorcido o twisted (2).

julio 13, 2016

Esta es una entrada en construcción. Estará finalizada cuando desaparezca este mensaje. 

Ahora que tengo un poco de tiempo retomo el punto 2 de la entrada del mismo título para analizar paso a paso el caso que inicialmente motivó la entrada. Voy redactando a medida que vaya realizando avances.

Recordamos que el algoritmo tal y como está programado necesita 27 opciones. Buscamos un método más económico. Y que además ponga de manifiesto que la obstrucción está relacionada con la propiedad de retorcimiento o twistedness.

Se confirma que marcar inicialmente el IAS de la identidad y el opuesto es aparentemente una buen paso.  Hace días detecté la primera consecuencia de marcar estos dos IASes, que comentamos a continuación y hoy he detectado la segunda, que pasamos a redactar inmediatamente. Ninguna de las dos es evidente, sobre todo en un dígrafo dibujado de manera tan confusa. Menos lo ha sido la segunda.

Nota. Este caso pone de manifiesto (me refiero a la primera consecuencia) que uno de los pasos del algoritmo (marcar todos los IASes en cada iteración) para ver si se genera un ciclo o camino no hamiltoniano, es ¿ necesario ? para los casos difíciles. No es buena noticia, pues este paso es computacionalmente muy costoso. Fin de nota.

Pasamos a analizar el caso, con texto y gráficos:

Leer el resto de esta entrada »

Trade Lane Megacities. Barcelona, zona costera.

julio 6, 2016

Por motivos profesionales he viajado en varias ocasiones a Cataluña y más concretamente Barcelona (aunque no sólo) en los últimos meses. Ayer 5 de julio, por última vez, en una pensábamos arriesgada travesía con Vueling, finalmente sin incidentes:-).

1.De manera digamos fortuita casi todo el largo día (primer y último vuelo) transcurrió en la zona costera de Barcelona, literalmente al borde de la playa, del mar, salvo un par de horas. Los tres espacios que no había tenido la oportunidad de conocer y he podido ver primera vez, son un buen resumen de la apariencia urbana de toda esta zona costera:

Leer el resto de esta entrada »

Trade Lane Megacities. Recopilación de enlaces primera 1/2 2016.

julio 2, 2016

Una nueva recopilación de (34 en esta ocasión) enlaces, recopilados en la primera mitad del año, sobre temas de nuestro interés. Como siempre combinamos pasado con presente y una mirada al futuro.

No desarrollamos ningún punto en profundidad. Como casi todo el mundo nos hemos convertido más en recopiladores que en lectores😦. ¿ Quién termina de leer un tweet hoy en día ?:-).

Salvo los dos primeros puntos / enlaces, añadidos hoy mismo, la mayoría son de diciembre de 2015, y enero, febrero y marzo de 2016. Seguramente también alguno de abril 2016. Por ello algunos parecerán atropellados por la actualidad. Pero ya sabe el lector que, aunque tampoco la rehuimos, no nos interesa captar en estas entradas la  actualidad.

Finalmente comentar que los publico en el orden en el que los he ido recopilando y por lo tanto reina el desorden en la recopilación. Por cierto, esta misma frase invertida suena bien, descriptiva de algún fenómeno desconocido, sentenciosa: en la recopilación, reina el desorden.

Espero poder empezar a publicar recopilaciones con algo más de regularidad e incluyendo artículos de fuentes que ya no leo con regularidad como Econacademics blogs o los blogs MR o NEG.

1.Libro: Abriendo los caminos de PuntContactos entre Egipto y el ámbito afroárabe durante la Edad del Bronce [ca.3000 a.C-1065 a.C]

El libro es de 2011, pero realmente no he tenido noticias sobre él hasta hace poco. El subtítulo lo dice todo. El enlace lo es al índice e introducción del libro.

Presentación.

La región de Punt, conocida únicamente a través de las fuentes egipcias, proveyó al país de los faraones de unos productos singulares que, por su valor económico y significación religiosa, le confirieron importantes connotaciones simbólicas en el imaginario egipcio.

Este libro analiza los contactos entre el país de las pirámides y este territorio de una forma diacrónica, emplazándolos en un contexto geopolítico amplio que permite darles una nueva perspectiva. La controvertida ubicación de Punt es dejada a un lado con el fin de responder a los cómos y porqués de estas relaciones, insertándolas en el conjunto de los intercambios que tuvieron lugar en la Edad del Bronce entre Egipto y el llamado ámbito afroárabe, que abarcaba el norte del África oriental y las costas del mar Rojo. Igualmente, los significados económicos y simbólicos dados por los egipcios a los exotica de Punt son incorporados como una herramienta fundamental para definir mejor las características de esos contactos. El trabajo también incluye un análisis historiográfico de las numerosas obras y debates que esta región ha generado entre historiadores y arqueólogos desde la primera mitad del siglo xix. La evolución cronológica y los contextos históricos e ideológicos en que se desarrollaron permiten entender mejor las numerosas preguntas y respuestas que esta misteriosa región ha inspira. 

Relacionado.

Estudios de España  y Arabia en la Antiguedad. 2014.

Añado este otro libro para que no se me olvide. Lo de Arabia en sentido muy amplio, pues un parte importante del libro se dedica a los fenicios. Su autor no necesita presentación.

2. Libro: Los caminos reales del Imperio Persa Aqueménida. 2016.

3. ¿ Existió la ruta de la seda ?. 

Nosotros hemos hablado largo y tendido en el blog sobre esta ruta. Incluso, ya lo hemos comentado en anteriores entradas, hay un libro escrito sobre ella que nos han dedicado en el prólogo:-). ¿ No existe tal ruta entonces ? ¿ Es sólo una construcción conceptual realizada por historiadores posteriormente ? La respuesta en este artículo.

The Road That Never Was: the Silk Road and Trans-Eurasian Exchange

4.Los luvitas. 

Normalmente aparecen como conjunto de tribus que comparten una misma lengua, el luvita precisamente, localizadas entre las civilizaciones hitita y griega. Ahora parece que se les quiere dar mayor entidad. ¿ Otra “Ruta de la Seda” más conceptual que real ?.

5. Domesticación de Dromedarios.

Extracto.

For the first time, it was possible to identify the Southeast Arabian Peninsula as the region of first domestication. “Our results appear to confirm that the first domestication of wild dromedaries occurred on the southeast coast. This was followed by repeated breeding of wild dromedaries with the early-domesticated populations,” Burger explains. The wild ancestor of today’s dromedary had a geographically limited range and went extinct around 2,000 years after the first domestication.

Realmente sorprendente. No creo que sea la última palabra al respecto.

6. Un nuevo concepto de la vivienda

Este es uno de los temas recurrentes del blog. En el s XXI esperamos una revolución tanto en la concepción de la vivienda (algo similar a lo que hizo Ford con el automóvil) como en los métodos de construcción. De todo esto nos hablan en el artículo.

7. Samuel, el otro Ricard(o).

De casta le venía al galgo. El galgo es nuestro economista favorito, David Ricardo. Cuando leímos su principal libro nos gustó el estilo abstracto, muy diferente al de Smith y otros contemporáneos. Samuel fue su abuelo, según he conocido recientemente.

Ricard, Samuel. 1700 Traité général du commerce… Amsterdam: Chez Paul Marret.

Relacionado 1. He visto el libro de Samuel en un libro de Tomás de Marien y Arróspide. Volumen correspondiente al tomo IV, parte …
Relacionado 2. Un artículo que nos pone en contexto el libro de Samuel: [PDF]Los diccionarios de Comercio y Economía en el siglo XVIII …
Aunque siempre de comenta que David Ricardo es de origen español (sefardita) a Samuel Ricard se le cita como de origen francés (en el buscador aparece en muchos enlaces como nacido en Castres en 1637, pero no se citan la fuente), emigrante a los Países Bajos. Su libro es más que un tratado de economía, un tratado de management de la época.
8. Regionalización de EEUU. Una propuesta.

megas-Artboard_3_copy_2

Relacionado. Texas triangle.

Pregunta. ¿ Por que en los estudios de megaregiones o de areas megapolitanas  de EEUU no se considera a la magalopolis de San Francisco y de LA como una sola ?. A diferencia por ejemplo de Boswash…

Entre las dos megalopolis, en la zona costera, monatañosa, existen unos condados prácticamente deshabitados:

Extracto.

The area is not densely populated. The largest city in the region is Oxnard in Ventura County, with a population estimated at 203,007 in 2013

Y la zona de interior, cubierta por el valle del Río San Joaquín, aunque dividida entre las dos areas metropolitanas, realmente no está tampoco demasiado poblada.

SanJoaquinRiverMap

california_simple

Entre Bakerfield, que se incluye en la megalopolis de LA (zona 2 del mapa anterior) y Fresno (zona 1 del mapa anterior), que se incluye en la de SF, hay una serie de ciudades muy poco pobladas,  más bien pueblos, como  Wasco, Delano, Porteville, Visalia, Hanford, Coalinga que se localizan en la zona 3. Es muy posible que en toda esta zona predomine el paisaje rural. Este es el tajo rural que separa la megalópolis de LA de la de SF.

Sobre Visalia: Visalia is a city situated in the agricultural San Joaquin Valley of California, approximately 230 miles (370 km) southeast of San Francisco, 190 miles (310 km) north of Los Angeles, 36 miles (58 km) west of Sequoia National Park and 43 miles (69 km) miles south of Fresno. The population was 124,442 at the 2010 census.

Visalia is the 5th largest city in the San Joaquin Valley after Fresno,Bakersfield, Stockton and Modesto,

California_map

Y las dos ciudades de Nevada (Reno y Las Vegas) que pertenecen a sendas megalopolis están realmente a una distancia grande y separadas por una zona desértica.

La pregunta que se impone es si finalmente estas dos megalopolis, LA y SF, acabarán uniendose, conformando una unidad como Boswash. Realmente un ave con parada por ejemplo en Visalia podría hacer esto posible.

Leer el resto de esta entrada »

Trade Lane Megacities. Canal de Panamá: la ampliación ya está en funcionamiento.

junio 27, 2016

No tenemos tiempo para publicar sobre algunos de los contenidos habituales del blog (tenemos un par de entradas con múltiples enlaces, pero no tenemos tiempo de darles la forma final para su publicación). No obstante no queríamos dejar de comentar sobre un evento bastante esperado por aquellos interesados en temas de infraestructuras, el que señalamos en el título. Ver también el especial de Panamá América.

Realmente junio de 2016 está siendo un mes lleno de acontecimientos de todo tipo, nacionales e internacionales, de ocio y negocio (cuya ocurrencia por cierto se está reflejando en las estadísticas del blog, tema sobre el que no hablamos  desde hace tiempo tampoco), y todo esto ha erosionado bastante el relieve que tiene el acontecimiento. Por otra parte el frenazo de la segunda globalización (principalmente por causas económicas) y su impacto en las corrientes ideológicas actuales también hace que el foco se esté centrando menos en este tipo de infraestructuras, en comparación con hace unos años.

Nota.

a) Como es bien conocido, la primera globalización no terminó bien: la I y II GM, y una crisis memorable entre ellas, así lo atestiguan. Aunque algunos no estarán de acuerdo con que entre estos fenómenos (frenazo primera globalización, guerras y crisis) haya una relación causa y efecto, esperemos que el frenazo de la segunda globalización que ahora estamos experimentando sea más suave. De momento hay paralelismos claros como el auge del proteccionismo (Brexit), la “crisis” políticas que están experimentando las democracias occidentales con la emergencia de nuevas fuerzas extremistas con discursos muy discutibles, siempre en contra de la globalización (en cualquiera de sus manifestaciones, sea el movimiento de personas, el  movimiento de capitales, de bienes o servicios, de conocimiento, la protección internacional de los derechos de propiedad etc…).

¿ Siempre que pasa igual ocurre lo mismo ?. Bueno la historia no se repite nunca de la misma manera. Los periodos de las dos globalizaciones son realmente fascinantes por su dinamismo  (las fechas que aparecen son bastante matizables, sobre todo la de 1820 como fecha de comienzo de la primera globalización), por la aceleración de la historia que se ha experimentado en ellos, y teníamos a medio hacer una entrada comparativa sobre ambos (nos interesaban sobre todo los aspectos culturales) pero no será posible hasta más adelante.

Leer el resto de esta entrada »

Caso de S5 2-4 generado retorcido o twisted.

junio 21, 2016

Actualización 18 de julio: he detectado un error en el punto 1. En breve lo modificaré, incluyendo seguramente las imágenes (ahora tengo el ordenador con algún problema en el modulo de electricidad). Fin de actualización.

Actualización 20 de julio. ¡¡ Corregido !!. Esta corrección nos ha obligado a borrar parte del teto que habíamos escrito, redundante. Y he cambiado la imagen. Fin de actualización.

En la entrada anterior hemos analizado un caso de S5 2-4 generado entrelazado o entangled que no sólo tenía RHs en dos de los VFs posibles (y eran 7) y hemos determinado el mecanismo que hace que los que no tienen RH no puedan tenerlo y lo que es más importante hemos demostrado que el que este mecanismo sea posible es debido a que el caso es entrelazado. Y también hemos comentado que este mecanismo no podría ser el motivo de que los casos twisted no tengan recorridos hamiltonianos.

¿ Podemos encontrar un mecanismo similar para los casos twisted, mecanismo en el que se vea claramente que puede intervenir por ser twisted ? Esto es lo que vamos a intentar contestar en esta entrada.

Para ello en esta entrada analizamos dos casos. Aunque los dos casos son twisted lo son de manera diferente: el primer caso es más cerrado, los IASes que lo hacen twisted están más cercanos el uno del otro, que en el segundo. Esto tiene consecuencias: si bien, como veremos, en los casos twisted más cerrados el método de activar el ciclo de C4 de todas las maneras posibles y concluir que todas llevan a contradicción funciona de manera bastante directa en los otros casos, los más abiertos, no parece ser así (es lo que queremos determinar).

En los casos twisted del segundo tipo, más abiertos, al aplicar el algoritmo de la patente, ocurre lo que explicamos a continuación. Primero una muestra geáfica, ya que lo hemos dibujado completamente. Sus parámetros son S5, G5, C2C4, IAS5, Circunferencia 6. Figura en la imagen siguiente (de nuevo bastante confusa, pido disculpas por ello):

s5 c2 c2 ias 6 twisted para blog

Sus VFs (excluimos los que sabemos, por el teorema de Rankin, que no pueden tener RHs). Son 23541 y 54123. Al aplicar el algoritmo que hemos implementado (el reflejado en la primera patente) determina que no tiene RHs en ninguno de estos dos vértices, pero dato importante, necesita respectivamente 27 opcions (y 11 llamadas de backtraking) y 42 opciones (y 18 llamadas de backtraking).

Creo relevante señalar a este respecto que en los otros dos casos en los que hemos encontrado demostraciones cortas o más directas de que no podían existir RHs (todos los 2-3 generados; algunos de los 2-4 generados entangled), el algoritmo identificaba que no existían sin opciones…

Otra de las preguntas que nos hacemos en esta entrada es si, en estos casos, hay una demostración más directa, más rápida, más económica, más corta, más comprensible, de que no tienen RHs en los VFs o sólo podemos determinar esto ejecutando todas estas llamadas de backtraking.

En cualquier caso queda claro lo que buscamos: identificar un mecanismo que esté relacionado con la propiedad de ser twisted y que  haga imposible la existencia de un RH en todos o algunos de los VFs. Y es muy posible que el hecho de que los ciclos de orden 4 se deban de activar de una determinada manera (que haya restricciones al respecto) forme parte del mecanismo. Y esto explica también por que el algoritmo necesita tanto backtraking en estos casos: esta propiedad no está incorporada en la implementación.

1.Twisted cerrados. A estos efectos comenzamos analizando un caso twisted cerrado que como veremos admite una demostración de que no contiene RHs sin necesidad de utilizar el algoritmo. Es aplicando aplicando el método que ya describíamos en la descripción de la patente, que consiste en activar de todas las maneras posibles el ciclo de C4 que sale de la identidad.

Es un caso 2-4 generado e IAS de orden 6 y circunferencia de orden 3 (¿ 6 IASes ?), en el que se detectaba que no podía tener recorridos hamiltonianos de manera más rápida que aplicando el algoritmo.

En un segundo punto aplicaremos este método (que ya hemos comentado que no nos satisface del todo, estamos convencidos de que debe de haber un método todavía más directo) al caso abierto, el que ha motivado la entrada para ver si funciona también. Por cierto, en breve aplicaré a este caso el algoritmo para ver tras cuantas opciones determina que no contiene RHs.  Actualización 27 de junio de 2016. Ya lo he aplicado: salvo en el VF 31425, en el que determina que no hay VF tras 3 opciones y una llamada a backtraking en los otros lo encuentra de manera directa tras entre 1 opción (en el otro ciclo potencial y 3 op). De ciclo a ciclo el número de opciones es 3, 3,2,2,2,1. Fin de actualización.  

El caso aparece en la imagen siguiente (no está completo).

caso c2 c4 circ 3 twisted

El método es como sigue:

–el ciclo de orden 4 que sale de la identidad se puede activar de 16 maneras posibles diferentes. Algunas son equivalentes.

primera manera de activarlo: todos inactivados. Como se puede ver se genera contradicción (aparecerían necesariamente ciclos de orden 2). Esto es independiente de la propiedad de twistedness. Esta clase de equivalencia contiene solo un representante.

segunda manera de activarlo: sólo 1 activado (y por lo tanto los otros tres inactivados). En esta clase de equivalencia hay 4 representantes o maneras posibles de activar.  Y es fácil ver que se genera también necesariamente contradicción, de manera independiente a la propiedad de twistedness.

tercera manera de activarlo: tres arcos activados, también con cuatro representantes.  En la imagen siguiente (que representa el último digrafo mostrado anteriormente pero de manera más clara, sin confusión de colores) mostramos la situación cuando se activa el IAS de la identidad tomando como VF la permutación 13254. Esto hace que el ciclo de orden 4 que sale de la identidad se active por dos arcos. En esta situación todavía no se genera ninguna contradicción.

c2c4 ias 6 nuevo para blog

En la imagen se aprecia claramente que al ser twisted, el IAS marcado con A1 conecta con el IAS marcado con A2 y con el marcado como A3 y que también A2 y A3 están conectados. Lo  mismo sucede con los IASes marcados B1, B2 y B3 o los IASes marcados C1,C2 y C3. Y falta un último “cluster” o grupo de IASes que no hemos dibujado de momento para no añadir más confusión. En un caso smooth estas conexiones entre estos IASes no existirían. Es importante que el lector recuerde esto ya que estas conexiones que sólo existen por ser twisted son clave, como veremos.  

En la imagen siguiente vemos  que pasa al activar el tercer arco del ciclo de orden 4. Nótese que si activasemos estos tres arcos del ciclo de orden 4 directamente, llegaríamos a la misma situación que aparece en la imagen.

cntradiccion 200

El marcar el tercer arco tiene consecuencias:

–aparece un posible ciclo de orden 4 (marcado en la figura cómo Contradicción 1) en el que hay tres arcos ya marcados, posible ciclo que hay que corregir.

–aparece otro posible ciclo de orden 4, marcado como contradicción 2.

Si dibujamos el IAS rojo, y extraemos las correspondientes consecuencias aparece otro ciclo de orden 4, en este caso ya inevitable. Se concluye que no puede existir un RH si marcamos los 3 arcos del ciclo de orden 4 de la identidad.

Nota. Según recuerdo el primer digrafo de este caso, el que realizamos hace años y publicamos hace un par de días un poco más arriba en esta misma entrada, contiene exactamente el numero de IASes necesario para demostrar que surge contradicción en cualquiera de las activaciones posibles del ciclo de orden 4 de la identidad. En este caso contiene casi tantos IASes como el total de IASes del digrafo, lo cual no parece una gran ventaja: pero ¿ y si en los casos twisted, a medida que n crece el la contradicción se puede seguir encontrando activando un número de IASes limitado del entorno de la identidad ? . En este caso nadie diría que el método no es ventajoso…Por eso me interesa determinar si también en los casos twisted pero más abiertos, el test es local.

Fin de nota.

De la misma manera que hemos demostrado con todo detalle que emerge contradicción al marcar los 3 arcos del ciclo de orden 4 de la identidad, se podría demostrar que pasa lo mismo con cualquier otra activación de tres arcos de este ciclo (y de cualquier otro), así como al activar sólo dos arcos opuestos en el ciclo de orden 4.

Y es fácil ver de que la causa de todo esto es que el caso sea twisted.

Continuará…

Nota.

Aprovecho para hacer un apunte rápido sobre una pregunta que hicimos en una entrada anterior, a la que asociamos una figura que volvemos a publicar:

smoothes twisted

Cuando construimos el entorno de la identidad puede, en teoría suceder dos cosas: quedan todos los vértices del entorno saturados (es decir de todos ellos entran y salen 2 arcos) o no quedan saturados. En el caso de que queden saturados es fácil demostrar que casos como el de la figura no pueden suceder: supongamos que un IAS de la circunferencia que se encuentre fuera del entorno de la identidad enlaza con un IAS que se encuentre al otro lado del entorno y que en su mismo lado podemos añadir más IASes a la circunferencia. Entonces por simetria debería de entrar en el entorno de la identidad un arco de alguno de estos IASes, lo cual es contradictorio con el hecho de que está saturado. Por lo tanto cuando el entorno de la identidad queda saturado podemos afirmar que el caso será smooth.

Queda por determinar:

–si es posible construir el entorno de la identidad sin que quede saturado;

–si esto fuese posible, que formas posibles pueden adoptar estos casos;

–y si estas formas tienen consecuencias de cara al problema  de recorridos hamiltonianos.

Haremos una entrada específica para comentar sobre todo esto en detalle.

Fin de nota.

2. Twisted más abierto (realizada a partir de 27 de julio de 2016).

Ya hemos comentado que si bien en el caso twisted más cerrado estudiado en el punto 1, cuando se le aplica el algoritmo, se puede determinar que no tiene RHs en pocas opciones (entre 3 y 1) y con pocas llamadas a backtraking (en general ninguna, lo determina directamente) en el caso twisted más abierto que estamos estudiando ahora, cuando se le aplica el algoritmo, tarda bastante más en determinar que no tiene RHs: más de 20 opciones y más de 11 llamadas a backtraking.

Luego es mucho más interesante encontrar una demostración lo más directa posible en estos casos. Diría que la vía de ataque tiene que implicar el IAS de la identidad y el IAS opuesto al de la identidad en la circunferencia.

A continuación dos imágenes que muestran el caso que estudiamos. La primera ya está publicada en esta misma entrada. La segunda es un nuevo dibujo que realmente tampoco mejora mucho en términos de claridad pero al  menos nos da otra perspectiva.

s5 c2 c2 ias 6 twisted para blog

c2c4 IAS5 para blog 22

 Ver entrada con mismo título, nº2.

Caso 2-4 generado de S6, a prueba.

junio 9, 2016

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.

Trade Lane Megacities. El río Mardos-Sefid Rud.

junio 5, 2016

1.Todos hemos oído hablar del par Tigris-Eufrates, los 2 principales ríos de Mesopotamia. Muchos habrán oído hablar y podrán localizar el par Kura-Araxes, otra Mesopotamia en oriente medio, al norte de la anterior y al sur dela Caúcaso.

Pero ¿ quien ha oído hablar del Mardos hoy Sefid Rud ?. Seguramente casi nadie, y eso que es el segundo río más largo de Irán y posiblemente su cuenca haya servido de corredor de pueblos entre Asia Central y Oriente Medio, o a lo  mejor de barrera…

Tres mapas que ayudarán al lector a localizarlo.

En la imagen siguiente, está marcado en verde claro. Desemboca en el Caspio, y posiblemente a esto debamos su perfil bajo en notoriedad.

klett_extra_large_middle_east_physical_lg 222

En el segundo mapa las cuencas hidrográficas de Irán (la mayoría de ellas endorreicas):

Cuencas hidrográficas de Irán

Y en la imagen siguiente (fuente) detalle sobre si cuenca. La masa acuosa que aparece al oeste no es el mar Negro, sino el Lago Urmia. La cuenca del río sobre el que hablamos se encuentra por lo tanto entre el Caspio y el Urmia. También al oeste, al otro lado de la cadena Zagros, ya la cuenca del Tigris.

Sefidrivermap

Para que el lector se haga una idea de sus dimensiones, es tan largo como el Guadalquivir, unos 650 km. La mitad que el Ebro o el Tajo. No tenemos tiempo para profundizar sobre la geografía urbana y humana histórica de su cuenca.

A continuación, para que el lector tenga una visión completa de la zona, una imagen dónde se muestran la cuenca del Urmia y del Sefid Rud.

Leer el resto de esta entrada »

Historia de la teoría de la complejidad computacional: nuevos primeros pasos.

mayo 31, 2016

A raíz de la entrada anterior, en la que hablábamos de Yves Lecerf, y su contribución a las ciencias computacionales, he encontrado este enlace a un capítulo de un libro en el que hablan sobre temas que hoy se incluirían dentro de la teoría de complejidad computacional, pero en realidad antes de que ésta disciplina existiese.

Curiosamente el capítulo del libro (de 1968, año complejo en Francia en otros aspectos), se titula Complexité y el contenido, como ya hemos comentado, es sobre los problemas de complejidad computacional: explosión combinatoria etc…Como veremos el artículo que de alguna manera creó la disciplina como un ente autónomo es de 1965 lo cual explica el uso de estos nombres.

La lista de nombres que aparecen en una historia de la complejidad computacional en el ámbito anglosajón (es decir EEUU; el enlace lo es a un artículo sobre la historia de la teoría de la complejidad computacional, fundamentalmente en EEUU, escrita por uno de sus protagonistas, que además es uno de los editores del primer blog que empezó a publicar sobre estos temas, bien conocido) suelen comenzar con Hartmanis y Stearns (1965), Cobham (1964), Edmonds (1965) y ya, cuando la disciplina madura y toma plena forma, Levin, Cook (la visión de Cook, escrita en 1983; habla de un artículo de Bennett de 1962: Bennett, J. H. On Spectra. Doctoral dissertation, Department of Mathematics, Princeton University, 1962) y Karp con sus bien conocidos respectivos resultados. También se suele / puede incluir a Rabin (1959) como precursor.

Tanto Hartmanis (Hartmanis, J. January 1981. Observations about the development of theoretical computer science. Annals of the History of Computing, Volume 3, Number 1, pp. 42-51. ) como Stearns han escrito sus respectivas versiones del periodo en el que fueron protagonistas.

En otras tradiciones como la soviética, como mucho se remontan a los 50 (Trakhtenbrot, de este mismo autor es la historia de la teoría de la complejidad computacional en la Unión Soviética que aparece en el enlace anterior, titulada A Survey of Russian Approaches to Perebor (Brute-Force Search) Algorithms ). Por cierto Levin pertenece a esta otra tradición, sobre la que hablaremos luego de nuevo.

Nota. Cabe preguntarse en que medida el interés que surgió en paralelo en estos temas a uno y otro lado del telón de acero fueron producto de la Guerra Fría. Llama por ejemplo la casi total ausencia de europeos occidentales entre los pioneros. También por su diferente recepción a uno y otro lado.

Extracto.

It is not surprising that we were attracted by the same problems as our colleagues in the West (of course, we were working independently and in parallel), and we worked out almost the same techniques: complexity measures, crossing sequences, diagonalization, gaps, etc. All of these ideas arose quite naturally; we became most excited, and they evoked in us enthusiasm similar to that described by Hartmanis in his historical account (1981).

Fin de nota.

En el artículo sobre el que hablamos desde el principio nos hablan de otras épocas y otros nombre que no había visto asociados a esta disciplina:

Leer el resto de esta entrada »


Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

Únete a otros 26 seguidores