🚀 go-pugleaf

... a detectar ciclos te refieres a encontrar un subciclo en un grafo, no?

Concorde (para resolver el problema del viajante de comercio) tiene uno (te
paso la direcci�n: http://www.math.princeton.edu/tsp/concorde.html) pero te
costar� encontrarlo entre tanta programaci�n lineal (uno de los algoritmos de
la distribuci�n es el de Held y Karp debe tener una subrutina de detecci�n, as�
como el branch and cut tambi�n presente).

A bote pronto y si no tienes que preocuparte por la eficiencia, puedes
implementar un algoritmo de caminos m�nimos entre toda pareja de v�rtices,
transformarlo en un algoritmo de caminos m�ximos (p.ej. cambiando el signo de
todos los pesos asociados a los arcos) y si se rebasa una cota superior a la
distancia entre dos v�rtices en un grafo (en caso que todos los arcos tengan
peso 1, el n�mero de v�rtices en el grafo, ya que si buscas un camino m�ximo en
un grafo y hay subciclos este no para de crecer) esa pareja de v�rtices
pertenece a un subciclo en el grafo (por supuesto si lo dejas correr por m�s
tiempo te dar� todos los v�rtices que pertenecen a subciclos). Esto es una
chapuza pero no tengo ning�n libro de teor�a de grafos a mano :-(

    Jordi

Francisco de Asis Tarancon Jodral wrote:

> Hola a todos, y antes de nada, gracias por vuestra atencion.
>
> Estoy trabajando con grafos, y me gustaria saber si alguno de ustedes tiene
> o sabe donde hay algun algoritmo para detectar ciclos en un grafo, y
> pasarlos a una matriz aparte. Si el algoritmo no pasa a una matriz a parte,
> es igual, con que detecte los ciclos me conformo.
>
> Muchas Gracias a todos