Skip to the content ForoHackers
Log inJoin

Teoría de grafos: por dónde empezar

Graph theory
#3414 · · Quote · 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

You are not logged in, so this goes up anonymously: no account, no name and no address is stored with it, and it may carry no link and no image. Log in or join to post under your name. Our web server's logs keep the address and time of every request for up to 14 days; to keep yours out of them, use Tor. To reach the staff in confidence, use the drop. Sign as a returning source (a key kept only in this browser)

Sending takes a few seconds here: your browser first works out a proof of work against spam.

Reply