¿Alguien se atreve a dar una solucion?

[skanciador]

A esto me refiero.

Es un problema de circuito hamiltoniano de grafos.

Desgraciadamente los circuitos hamiltonianos solo son atacables por "fuerza bruta" y solo haciendo todos los posibles recorridos es posible saber si tiene solucion.


Los teoremas que acotan la posibilidad (Dirac, Ore) no son mas que condiciones suficientes, pero no necesarias...es decir: Un grafo admite un circuito hamiltoniano si se cumplen esas condiciones (que en el problema dado, no cumplen), pero hasta donde yo se, la inversa no es aplicable...es decir...que no necesariamente por no cumplir esa condicion no haya una solucion.

El teorema de Bondy-Chvátal que si es condicion necesaria, nos lleva a un grafo cerradura identico al original...por lo que no nos dice nada.

¿Alguna idea?

(Nunca he estudiado la rama de grafos, asi que mis conocimientos rayan en lo anecdotico...no mas que lo que pueda verse en una busqueda de google y algun ejemplo sencillo de cierta literatura... )

P.S. Yo apostaria a que no tiene solucion...pero no se como probarlo...
_________________


···

[roc46]

Yo siempre puedo decir aquellos de: "yo es que soy de letras"
_________________

[nastafniek]

esta clarisimo y sin lugar a dudas emitir en esta tribuna una solución podría desvirtuar el loable fin de difundir las matematicas entre el común de los ciudadanos...
_________________


TE DEBO UNA CENA HI KI!!!!!!!!!

[skanciador]

Me he encontrado por ahi una "demostracion", que con parecer poco seria matematicamente hablando, me ha convencido. Concluye que el problema no tiene solucion.

Coloreamos los nodos en rojo y azul, poniendo el primero del color que queramos y todos los unidos a el del otro color.

Por ejemplo, si ponemos como rojo el 1, seran azules el 2, el 8 y el 11. Y asi sucesivamente.

Y vemos que podemos colorear absolutamente todos los nodos de esa forma sin que en ninguno se produzcan indeterminaciones de color. Cada nodo esta conectado siempre solo a nodos del color contrario, por lo que para ir de un nodo a otro, siempre voy cambiando de color.



Bien. Esta claro entonces que el recorrido ha de ser por fuerza de un color a otro: de rojo a azul, de ahi a rojo, de ahi a azul, etc...

Examinamos los casos dependiendo de por que color comenzamos y sabiendo que tenemos 6 rojos y 5 azules.

A) Empezando por Azul, seria un camino A-R-A-R-A-R-A-R-A-R...y para...ya he agotado los 5 puntos azules...y aun me queda un rojo por visitar cuando he acabado en un rojo. No tiene solucion.

B) Empezando por rojo, es un camino R-A-R-A-R-A-R-A-R-A-R que podria (quiza) hacerse...pero he acabado en un nodo rojo...y aun tengo que volver al comienzo, que tambien es rojo...y ya no me quedan azules por los que pasar. No tiene solucion.


_________________


···

[ferelxyx]

creo que no se puede por ser impares y la mejor ruta seria esta
donde tienes que pasar por el dos de nuevo para ir al uno

1-2-6-8-5-4-7-3-10-11-9-2-1
_________________

http://foro.hardlimit.com

[Joker]

esperas que hagamos tu trabajo
_________________


unete al Ejercito mas poderoso http://ridick.minitroopers.es

[Andradas]

[peluso13]

pues yo tiraría la primera a la derecha... las horas que son... la casa de campo tiene que tener movimiento...

por lo que puedo determinar que... A-F-O-L-L-A-R



_________________

[TORHXX]

esto para un Lunes por la mañana no debe de ser muy bueno


y menos para este lunes
_________________


http://torhxx.tumblr.com

[Pableras]

muy bien skancito..... ya has jugado a problemas de lógica sencillos....

Ahora dedicate la literatura y gramática que es lo tuyo...

_________________
Hasta una patada en el culo te empuja hacia adelante

[skanciador]

[Andradas]

[skanciador]

[Pableras]

[skanciador]