Mostrar los tags: 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.

Un grafo es un objeto combinatorio compuesto por un conjunto de vértices V (también conocidos como nodos) y un conjunto de aristas E. Las aristas corresponden a pares de vértices, que generalmente son distintos, y sin una noción de orden en el sentido donde (u, v) y (v, u) denotan el mismo borde.

A veces, consideramos una variante, el grafo dirigido, donde los bordes tienen una orientación. En este caso, los bordes se conocen generalmente como arcos. El arco (u, v) tiene origen u y destino v. La mayoría de los algoritmos descritos en este texto operan en grafos dirigidos, pero se pueden aplicar a grafos no dirigidos reemplazando cada borde (u, v) por dos arcos (u, v) y (v, u).

Los grafos pueden contener información adicional, como pesos o letras, en forma de etiquetas en los vértices o los bordes.