Saltar al contenido ForoHackers

Teoría de grafos: por dónde empezar

Teoría de grafos
#3414 · · Citar · Denunciar

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

No has iniciado sesión, así que esto se publica como anónimo: no se guarda con ello ninguna cuenta, nombre ni dirección, y no puede llevar enlaces ni imágenes. Inicia sesión o únete para publicar con tu nombre. Los registros de nuestro servidor web guardan la dirección y la hora de cada petición hasta 14 días; para que la tuya no quede en ellos, usa Tor. Para escribir al equipo de forma confidencial, usa el buzón. Firmar como fuente habitual (una clave guardada solo en este navegador)

Enviar tarda unos segundos aquí: tu navegador resuelve antes una prueba de trabajo contra el spam.

Responder