Skip to the content ForoHackers
Log inJoin

Teoría de grafos: por dónde empezar

Graph theory
#908 · Ophuscado · · Report

Un grafo es un conjunto de vértices unidos por aristas, y casi cualquier cosa con conexiones se puede modelar como uno: carreteras, redes, dependencias, amistades, moléculas. La teoría de grafos estudia su estructura y los algoritmos sobre ellos. Un grafo bien elegido suele convertir una pregunta enredada en un problema estándar con solución conocida.

Conceptos clave

  • Representaciones: las listas de adyacencia convienen a los grafos dispersos, las matrices de adyacencia a los densos.
  • Recorridos: la búsqueda en anchura halla caminos con menos aristas; la búsqueda en profundidad da órdenes, ciclos y componentes.
  • Caminos mínimos: el algoritmo de Dijkstra para pesos no negativos, Bellman-Ford cuando los pesos pueden ser negativos.
  • Árboles generadores: los algoritmos de Kruskal y Prim conectan todos los vértices con el menor peso total.
  • Flujos y emparejamientos: el flujo máximo es igual al corte mínimo; un emparejamiento une vértices sin repetir ninguno.

Vocabulario

  • Dirigido y no dirigido: si las aristas tienen sentido o no.
  • DAG: grafo dirigido acíclico, la forma de las dependencias, que se puede ordenar topológicamente.
  • Componente conexa: un conjunto maximal de vértices alcanzables entre sí.
  • Grafo planar: el que se puede dibujar sin que se crucen las aristas.

Qué estudiar, en orden

  1. Construye una clase de grafo con listas de adyacencia y lee un grafo desde un archivo.
  2. Implementa BFS y DFS y úsalas para hallar componentes conexas y detectar ciclos.
  3. Implementa Dijkstra con una cola de prioridad y contrástalo con una búsqueda por fuerza bruta.
  4. Añade la ordenación topológica, el árbol generador mínimo y las componentes fuertemente conexas.
  5. Modela un problema real como un flujo o un emparejamiento y resuélvelo.

Etiquetas relacionadas

#algorithms #combinatorics #discrete-math #data-structures #knowledge-graphs

Log in or join to reply.