Algoritmos con Python - Ciclos en grafos
Python
Publicado el 3 de Marzo del 2021 por Gonzalo
3.095 visualizaciones desde el 3 de Marzo del 2021
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.
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.