Algoritmos de grafos
Los algoritmos de grafos operan en redes de vértices y aristas para responder preguntas sobre conectividad, distancias, estructuras de expansión y flujos, constituyendo el núcleo algorítmico de problemas modelados como grafos.
Definition
Los algoritmos de grafos son procedimientos que calculan propiedades o resuelven problemas de optimización en grafos —estructuras matemáticas que consisten en vértices conectados por aristas—, tales como la alcanzabilidad, las distancias más cortas, los árboles de expansión y los flujos máximos.
Scope
Esta área abarca algoritmos sobre grafos y redes: recorrido sistemático (búsqueda en anchura y en profundidad), cálculo de caminos más cortos, árboles de expansión mínima, flujo en redes y emparejamiento, y los problemas estructurales (conectividad, orden topológico, ciclos) que estos soportan. Trata las representaciones de grafos (listas y matrices de adyacencia) y su efecto en el costo del algoritmo, y conecta con los paradigmas de diseño (voraz, programación dinámica) y estructuras de datos (colas de prioridad) en los que se basan los algoritmos de grafos. Excluye el estudio combinatorio abstracto de grafos perteneciente a las matemáticas discretas.
Sub-topics
Core questions
- ¿Cómo se representa un grafo y cómo afecta la representación a la eficiencia del algoritmo?
- ¿Cómo revelan la conectividad y la estructura los recorridos en anchura y en profundidad?
- ¿Cómo se calculan los caminos más cortos bajo diferentes condiciones de peso de las aristas?
- ¿Qué estructuras abarcan un grafo con un costo mínimo y cómo se encuentran?
- ¿Cuánto flujo puede pasar por una red y qué lo limita?
Key concepts
- vértices y aristas
- lista y matriz de adyacencia
- búsqueda en anchura y en profundidad
- caminos más cortos
- árbol de expansión mínima
- ordenación topológica
- flujo en red
- flujo máximo corte mínimo
Key theories
- La búsqueda en grafos como fundamento
- La búsqueda en anchura y en profundidad visita sistemáticamente todos los vértices alcanzables y constituye la base para la conectividad, la ordenación topológica, la detección de ciclos y muchos otros cálculos en grafos.
- Dualidad flujo máximo-corte mínimo
- El flujo máximo a través de una red es igual a la capacidad de su corte mínimo; esta dualidad, establecida por Ford y Fulkerson, subyace a los algoritmos de flujo y se conecta con problemas de emparejamiento y conectividad.
Clinical relevance
Los algoritmos de grafos modelan y resuelven una vasta gama de problemas reales: enrutamiento y navegación (caminos más cortos), diseño de redes e infraestructuras (árboles de expansión), programación y resolución de dependencias (ordenación topológica), emparejamiento bipartito en asignación y recomendación, y problemas de flujo en logística, telecomunicaciones y segmentación de imágenes.
History
La teoría algorítmica de grafos creció rápidamente a mediados del siglo XX: el algoritmo de caminos más cortos de Dijkstra (1959), el trabajo de Ford y Fulkerson sobre el flujo máximo (1956), y los algoritmos de árboles de expansión de Kruskal y Prim (1956-1957). Los algoritmos basados en la búsqueda en profundidad de Robert Tarjan en la década de 1970 proporcionaron soluciones en tiempo lineal a muchos problemas de conectividad, consolidando los algoritmos de grafos como un área central.
Key figures
- Edsger W. Dijkstra
- Lester Ford
- Delbert Fulkerson
- Robert Tarjan
Related topics
Seminal works
- dijkstra1959
- cormen2009
- kleinberg2006
Frequently asked questions
- ¿Cuándo se debe representar un grafo como una lista de adyacencia en lugar de una matriz de adyacencia?
- Las listas de adyacencia utilizan un espacio proporcional al número de aristas y son eficientes para grafos dispersos y para el recorrido. Las matrices de adyacencia utilizan un espacio proporcional al cuadrado del número de vértices y permiten búsquedas de aristas en O(1), lo que las hace adecuadas para grafos densos o algoritmos que prueban aristas con frecuencia.
- ¿Los problemas de grafos son siempre eficientemente resolubles?
- Muchos problemas centrales de grafos (recorrido, caminos más cortos, árboles de expansión, flujos) tienen algoritmos eficientes en tiempo polinómico, pero otros —como el problema del viajante, la coloración de grafos y la clique máxima— son NP-hard, y se abordan con métodos de aproximación o basados en búsqueda.