Caminos eulerianos en un grafo

Dices automatizar el obtener el número de caminos de un grafo?
Claro que se puede, hay varias alternativas: fuerza bruta, djikstra, floyd...

jorcoval escribió:Dices automatizar el obtener el número de caminos de un grafo?
Claro que se puede, hay varias alternativas: fuerza bruta, djikstra, floyd...

No hombre.

Yo hablo de conseguir el número de caminos mínimo que recorra todas las aristas del grafo. No generarlos todos.

Dijkstra, floyd...
http://grafos-caminosminimos.wikispaces ... e+Dijkstra
http://grafos-caminosminimos.wikispaces ... d-Warshall

amchacon escribió:Dado un grafo. ¿Cuantos caminos necesito para recorrer todas las aristas sin repetir ninguna?

En el peor de los casos, necesitas N/2 (siendo N el número de nodos)

Ese es para buscar el camino de costes mínimo. Yo busco el mínimo de caminos, los grafos que uso no tiene ningún coste asociado a las aristas.

Pongo un ejemplo, los puentes de euler:


Hay que recorrerlo entero sin repetir aristas. No podemos hacerlo del tirón sin levantar el lápiz, pero podemos levantar el lápiz y terminarlo en una segunda pasada (es decir, en 2 caminos).

Dado un grafo, cuantos caminos como mínimo tengo que hacer para recorrer todas sus aristas sin repetir ninguna?

Djikstra donde la arista recorrida tiene peso infinito y si el algoritmo se bloquea (porque quedan nodos por visitar) saltas a un nodo libre de forma aleatoria?

Basta con entrar en un hilo como este para sentirse como un padre que hablara con su hijo de 15 años...no pillo nada!

Haran escribió:Basta con entrar en un hilo como este para sentirse como un padre que hablara con su hijo de 15 años...no pillo nada!

JAJAJA Yo recuerdo esta asignatura con cierta simpatía... aunque ahora no me acuerdo de nada, mientras la hacia todo tenia lógica y se entendía bien... las había mucho peores

jorcoval escribió:Djikstra donde la arista recorrida tiene peso infinito y si el algoritmo se bloquea (porque quedan nodos por visitar) saltas a un nodo libre de forma aleatoria?

No se trata de "resolver" una solución particular del grafo, sino de determinar cuál es el número mínimo de caminos necesarios para recorrer todas las aristas una sola vez cada una.

Y yo creo que no existe un caso general o un método que permita calcular ese mínimo, distinto de la fuerza bruta.

Puestos a resolverlo, en lugar de Dijkstra y saltos al azar (que solo te da una solución), se me antoja más razonable hacer recorridos en profundidad (backtracking a destajo). Primero se transforma el grafo en su "dual" (aristas<->nodos) y luego se computan los recorridos, todos los posibles para cada nodo (arista en este caso), y con todos los nodos del grafo (algo ciertamente costoso en tiempo). Finalmente cuentas el número de hojas en cada uno y el árbol que menos hojas tenga, es la solución (sin olvidar que en este caso los vértices del árbol son aristas en el grafo original, a la hora de determinar los caminos).

Para una solucion particular es mucho más rápido descomponer el grafo original de manera que quede el mayor número de nodos con grado par. De ese modo, ahí existe un camino euleriano. Y con el resto, tendrás un camino adicional por cada arista, excepto si tiene alguna más adyacente (de las descartadas antes) en cuyo caso no se suma.

raday escribió:

Haran escribió:Basta con entrar en un hilo como este para sentirse como un padre que hablara con su hijo de 15 años...no pillo nada!

JAJAJA Yo recuerdo esta asignatura con cierta simpatía... aunque ahora no me acuerdo de nada, mientras la hacia todo tenia lógica y se entendía bien... las había mucho peores

Es que...porqué sé que va en serio...pero todo lo que decís me suena tanto como si me hablarais de las bríscolas necesarias para que el fleje del promixitrón se engarfe por los costados intermartales. Eso sí, siguien las teorias mersicas de Pröskter y Melpal-Domison y no las de Rasheff-Johnsonnen....

Por cierto...de que hablais? ya se que es más facil googlear...pero es más divertido así.

Haran escribió:Es que...porqué sé que va en serio...pero todo lo que decís me suena tanto como si me hablarais de las bríscolas necesarias para que el fleje del promixitrón se engarfe por los costados intermartales. Eso sí, siguien las teorias mersicas de Pröskter y Melpal-Domison y no las de Rasheff-Johnsonnen....

Por cierto...de que hablais? ya se que es más facil googlear...pero es más divertido así.

Coño, me has hecho dudar si se necesitan n-1 bríscolas o mas!!!

Básicamente es el estudio de la relación entre "puntos" y "aristas" y posibles recorridos...
El típico problema es el del repartidor que tiene que pasar por 20 pueblos unidos todos con como mínimo un camino con algún otro ( o con mas) buscar el camino mas corto...
Se puede complicar mucho mas...

http://en.wikipedia.org/wiki/Travelling ... an_problem

Deschamps escribió:

jorcoval escribió:Djikstra donde la arista recorrida tiene peso infinito y si el algoritmo se bloquea (porque quedan nodos por visitar) saltas a un nodo libre de forma aleatoria?

No se trata de "resolver" una solución particular del grafo, sino de determinar cuál es el número mínimo de caminos necesarios para recorrer todas las aristas una sola vez cada una.

Y yo creo que no existe un caso general o un método que permita calcular ese mínimo, distinto de la fuerza bruta.

Puestos a resolverlo, en lugar de Dijkstra y saltos al azar (que solo te da una solución), se me antoja más razonable hacer recorridos en profundidad (backtracking a destajo). Primero se transforma el grafo en su "dual" (aristas<->nodos) y luego se computan los recorridos, todos los posibles para cada nodo (arista en este caso), y con todos los nodos del grafo (algo ciertamente costoso en tiempo). Finalmente cuentas el número de hojas en cada uno y el árbol que menos hojas tenga, es la solución (sin olvidar que en este caso los vértices del árbol son aristas en el grafo original, a la hora de determinar los caminos).

Para una solucion particular es mucho más rápido descomponer el grafo original de manera que quede el mayor número de nodos con grado par. De ese modo, ahí existe un camino euleriano. Y con el resto, tendrás un camino adicional por cada arista, excepto si tiene alguna más adyacente (de las descartadas antes) en cuyo caso no se suma.

Entonces según he entendido. ¿Fuerza bruta por busqueda en profundidad?

Lo voy a intentar. El problema esque tiene que resolver grafos de hasta 1000 nodos y 2000 aristas en no más de 1 segundo.

wah_wah_69 escribió:http://en.wikipedia.org/wiki/Travelling_salesman_problem

No entiendo la relación con mi problema. Ya he dicho que mis grafos no tienen costes *_*

Haran escribió:Por cierto...de que hablais? ya se que es más facil googlear...pero es más divertido así.

Estoy entrenandome haciendo problemas de programación, mi idea es presentarme el año que viene a la competición local.

Este es un problema que trata sobre grafos. Un grafo no es más que un conjunto de puntos unidos por aristas:



Suponte que tienes que dibujar ese grafo. ¿Podrías hacerlo sin levantar el lápiz del papel y sin repetir ninguna arista? Te lo digo por adelantado, es imposible en este grafo. Pero puedes hacerlo una vez, levantar el lápiz y volver a intentarlo con los puntos que te queden.

Tengo que hacer un programa que me diga cuantas veces tendría que levantar el lápiz para dibujar el grafo.

Un poco de terminología antes de meternos en el ajo:

Paseo: Secuencia de vértices v_1, ..., v_n pertenecientes al grafo, tales que v_1 es el principio y v_n es el final
Camino: Es una paseo tal que no se repite ningún vértice
Sendero: Es un paseo tal que no se repita ninguna arista

Imagino que ya debes haber visto el artículo de wikipedia sobre caminos eulerianos, pero ahí explica el algoritmo de Hierholzer para encontrar un sendero cerrado, ¿has intentado reproducir ese algoritmo?

Como me gustaría meter LaTex ahora mismo...

EDIT: Vale, viendo el problema original, es obvio que se necesita un algoritmo greedy que recorra el grafo hasta que llegues a la primera arista. La idea no es buscar el camino más corto, sino iterar el grafo para encontrar todos los caminos posibles. Creo que aquí podría ir bien Kruskal...

Resuelto, era el numero de vértices de grado impar entre 2.

Caso especial para el 0, donde el numero de caminos es 1

amchacon escribió:Resuelto, era el numero de vértices de grado impar entre 2

¿Resuelto el qué? Eso solo será así con grafos conexos no dirigidos.

¿Es un ejercicio de algún lado, o lo has ideado tú?

Eso es, grafos conexos no dirigidos... Sorry, me puse a resumir el enunciado y se me olvidaron esos detalles.

El problema lo he sacado de la uni, tenía juez automatico y me lo ha cogido bien.

¿Podrías poner el enunciado entero? Es curioso que puedas calcular el número de caminos de un grafo a partir del grado de los vértices. Y pregunta la mar de estúpida: ¿por qué, si el grado de un vértice es 0, se asume que el número de caminos es 0?

Mithrandir0x escribió:¿Podrías poner el enunciado entero? Es curioso que puedas calcular el número de caminos de un grafo a partir del grado de los vértices. Y pregunta la mar de estúpida: ¿por qué, si el grado de un vértice es 0, se asume que el número de caminos es 0?

Esque yo llamo camino a un paseo tal que no se repita una arista.

Un camino euleriano sería aquel que recorre todas las aristas, dicho camino solo es posible si no hay vertices impares o si el número de vertices impares es 2.

Si ese número es mayor de 2, lo que podemos hacer son varios caminos eulerianos. En cada camino nos iremos cargando 2 vertices impares, al final el número de caminos obtenidos será igual a vertices con grado impar / 2. El problema de eso esque si no hay vertices de grado impar (0) entonces me saldría que no hay caminos (0/2), cuando eso no es cierto. Asi que ese caso hay que estudiarlo aparte.

El enunciado entero es el siguiente:

(edito. Nada, ya lo has comentado)

[image]http://imgs.xkcd.com/comics/travelling_salesman_problem.png[/image]

Que recuerdos esa asignatura.. me costo aprobarla de cojones xD

Muchas gracias por el enunciado. Aunque para ser puristas, lo que define en el enunciado no es un camino euleriano "per se", o tal como a mi me lo enseñaron. Un camino euleriano es aquel que pasa por todas las aristas y llega al mismo punto de origen.

Detalle anecdótico: un grafo es euleriano si, y solo si, el grado de todos los vértices es par.

Mithrandir0x escribió:Un camino euleriano es aquel que pasa por todas las aristas y llega al mismo punto de origen.

Eso es un camino euleriano cerrado, luego está el camino euleriano abierto (donde no necesariamente terminas en la mismo punto).

Yo hubiera dicho que es un problema np completo.... pero si dices que tienes la solucion, mejor pa ti.

Mithrandir0x escribió:Muchas gracias por el enunciado. Aunque para ser puristas, lo que define en el enunciado no es un camino euleriano "per se", o tal como a mi me lo enseñaron. Un camino euleriano es aquel que pasa por todas las aristas y llega al mismo punto de origen.

Detalle anecdótico: un grafo es euleriano si, y solo si, el grado de todos los vértices es par.

Lo mismo me enseñaron a mí. Y tiene todo el sentido del mundo con lo del grado par de todos los vértices.

Anda que no ha cambiado el enunciado desde el inicio!

DemonR escribió:Yo hubiera dicho que es un problema np completo.... pero si dices que tienes la solucion, mejor pa ti.

Los problemas NP no quiere decir que no tengan solución, quiere decir que no se pueden resolver en tiempo polinómico. Por heurística puedes sacar aproximaciones muy buenas en poco tiempo.

dark_hunter escribió:

DemonR escribió:Yo hubiera dicho que es un problema np completo.... pero si dices que tienes la solucion, mejor pa ti.

Los problemas NP no quiere decir que no tengan solución, quiere decir que no se pueden resolver en tiempo polinómico. Por heurística puedes sacar aproximaciones muy buenas en poco tiempo.

Y creo que se confunde con los ciclos hamiltonianos.

Aclaro que eran caminos eulerianos en un grafo conexo y no dirigido

dark_hunter escribió:

DemonR escribió:Yo hubiera dicho que es un problema np completo.... pero si dices que tienes la solucion, mejor pa ti.

Los problemas NP no quiere decir que no tengan solución, quiere decir que no se pueden resolver en tiempo polinómico. Por heurística puedes sacar aproximaciones muy buenas en poco tiempo.

Ya, pero como no esta preguntando una cota maxima sino un numero exacto... y contesta: Resuelto, era el numero de vértices de grado impar entre 2

Eso es una aseveracion rotunda, no veo "como maximo..."

DemonR escribió:Ya, pero como no esta preguntando una cota maxima sino un numero exacto... y contesta: Resuelto, era el numero de vértices de grado impar entre 2

Eso es una aseveracion rotunda, no veo "como maximo..."

Esque es una aseveración rotunda. Es el número exacto.

Lo saqué decomponiendo el grafo en un subconjunto de grafos eulerianos. Dado que un grafo euleriano es cuando hay 0 o 2 vertices de grado impar, pues tendré que hacer n/2 divisiones.

Repito que estoy suponiendo que todos grafos que voy a estudiar son conexos y no dirigidos.