Temas de Python - Algoritmos con Python - Ciclos en grafos

Varios problemas clásicos se refieren a ciclos en gráficos, ya se refieran a desplazamientos geográficos o anomalías en un gráfico de dependencia. Los problemas más simples consisten en detectar la existencia de ciclos, la existencia de ciclos con peso negativo o la identificación de un peso total mínimo o ciclo de peso medio mínimo.

Otros problemas tienen que ver con explorar la totalidad de un gráfico para encontrar caminos que atraviesen cada borde exactamente una vez (camino euleriano) o, cuando esto no es posible, al menos una vez (problema del cartero chino). Estos problemas son polinomiales, mientras que determinar un ciclo que visita cada vértice exactamente una vez (ciclo hamiltoniano) es NP-Hard.