Teoría de grafos
“Un grafo es un mapa que descarta la ubicación y conserva solo la conexión.”
La fórmula
G = (V, E), Σ(v∈V) deg(v) = 2|E|Cómo leerla: un grafo es un conjunto de vértices V y un conjunto de aristas E que los une; sumar el grado de cada vértice da el doble del número de aristas
- V
- — el conjunto de vértices — los 'puntos'
- E
- — el conjunto de aristas — las 'líneas' que unen puntos
- deg(v)
- — el grado de v — el número de aristas conectadas a él
- Σdeg(v) = 2|E|
- — la suma de grados es igual al doble del número de aristas (el lema del apretón de manos)
El gancho
Amistades, mapas de metro, internet, moléculas — todos ellos se capturan con una imagen simple: puntos y líneas.
En palabras simples
Un grafo es una colección de puntos (vértices) y líneas (aristas) que los unen. Solo registra qué está conectado con qué, descartando posición, forma y distancia. Es un mapa de relaciones reducido a su esqueleto.
La intuición
Imagina un mapa de metro — las distancias y direcciones reales son incorrectas, pero 'qué estación conecta con cuál' se conserva perfectamente. Ese es el espíritu de un grafo. Sean lo que sean los puntos (personas, ciudades, páginas web) y las líneas (amistades, carreteras, enlaces), mirar solo la estructura de la conexión hace que problemas muy distintos se conviertan en el mismo problema.
Cómo se construye
Dos partes — un conjunto de vértices V y un conjunto de aristas E. El 'grado' de cada vértice es el número de aristas conectadas a él. El lema del apretón de manos: sumar todos los grados da exactamente el doble del número de aristas (cada arista se cuenta una vez en cada uno de sus dos extremos). Este conteo simple es sorprendentemente poderoso.
Ejemplo
Un grafo triangular: 3 vértices, 3 aristas. Cada vértice tiene grado 2, así que la suma de grados es 2+2+2 = 6 = 2 × 3 (el número de aristas). El lema del apretón de manos se cumple exactamente.
Error común
Aquí un 'grafo' no es la curva de una función y=f(x). No hay ejes ni curva — solo una red de puntos y las líneas que los unen. Misma palabra, objeto completamente distinto.
Dónde se usa
El ranking de búsqueda de Google (PageRank), rutas más cortas de GPS, análisis de redes sociales, diseño de circuitos, problemas de programación y coloreado, modelos de propagación de epidemias — todo problema donde las cosas se conectan con cosas es un grafo.
De dónde viene
En 1736 Euler resolvió el acertijo de si se podían cruzar los siete puentes de Königsberg exactamente una vez, abriendo las puertas de la teoría de grafos y la topología (la respuesta: imposible).
Requisitos previos
Comprobación rápida
Según el lema del apretón de manos, ¿cuál es la suma de todos los grados de vértice en un grafo con 5 aristas?
- 5
- 10✓
- 25
- 2.5
Práctica
Encuentra la suma de todos los grados de vértice en un grafo con 4 aristas.
Respuesta: 8
- lema del apretón de manos: suma de grados = 2 × número de aristas
- = 2 × 4 = 8
Idea clave: Cada arista añade 2 al grado total.
Encuentra el número de aristas en el grafo completo K₄ (4 vértices, cada par conectado).
Respuesta: 6
- el número de formas de elegir 2 de 4 vértices, C(4,2)
- = (4·3)/2 = 6
Idea clave: Un grafo completo Kₙ tiene n(n−1)/2 aristas.
Un grafo tiene vértices de grado 3, 3, 2, 2. Encuentra su número de aristas.
Respuesta: 5
- suma de grados = 3+3+2+2 = 10
- aristas = 10 / 2 = 5
Idea clave: El número de aristas es la mitad de la suma de grados.
Explica usando los grados por qué ningún recorrido puede cruzar cada uno de los siete puentes de Königsberg exactamente una vez.
Respuesta: undefined
- tal recorrido (un camino euleriano) necesita 0 o 2 vértices de grado impar
- en Königsberg las cuatro masas de tierra tienen grado impar
- cuatro vértices de grado impar (más de 2) lo hace imposible
Idea clave: Tres o más vértices de grado impar significa que no existe un camino euleriano.