Grafos y árboles: la estructura sobre la que se apoyan la búsqueda y las redes neuronales

Vértices y aristas, grados, matriz de adyacencia, caminos y componentes, BFS y Dijkstra, árboles, árbol de expansión mínima y el grafo de cómputo de una neurona — todo sobre un solo grafo con siete ciudades.

14 minutos Matěj Žalmánek 2026-10-15

Serie Fundamentos de IA Parte 8 de 52

1. Mapa de la inteligencia artificial: qué es cada cosa y cómo encaja todo
2. Breve historia de la inteligencia artificial: de Turing a los modelos de lenguaje
3. Datos, modelo, entrenamiento, inferencia: los conceptos básicos en un solo ejemplo
4. Cómo leer la notación matemática: símbolos, subíndices, sumatorios y cuantificadores
5. Conjuntos y relaciones: las piezas con las que se construyen las definiciones en IA
6. Funciones y aplicaciones: por qué todo modelo de IA es una función
7. Lógica y demostraciones: las reglas con las que se razona en IA
8. Grafos y árboles: la estructura sobre la que se apoyan la búsqueda y las redes neuronales
9. Álgebra lineal para aprendizaje automático: vectores, matrices y por qué la IA sobre todo multiplica
10. Derivadas, gradiente y regla de la cadena: cómo sabe un modelo en qué dirección aprender
11. Descenso de gradiente: cómo aprende un modelo
12. Qué es la probabilidad: del lanzamiento de un dado a los axiomas de Kolmogórov
13. Probabilidad condicionada y teorema de Bayes: cómo cambiar una estimación cuando te enteras de algo nuevo
14. Variable aleatoria y función de distribución: una sola función que lo dice todo sobre la distribución
15. Función de densidad y función de probabilidad: por qué una variable continua tiene probabilidad cero en cada punto
16. Esperanza, varianza y covarianza: dónde está una distribución, qué anchura tiene y qué se relaciona con qué
17. Resumen de las distribuciones de probabilidad: Bernoulli, binomial, Poisson, uniforme, normal y exponencial
18. Ley de los grandes números y teorema central del límite: por qué las medias se comportan de forma tan predecible
19. Estadística y estimación de parámetros: máxima verosimilitud, MAP e intervalos de confianza
20. Teoría de la información: entropía, entropía cruzada y divergencia KL, el origen de las funciones de pérdida
21. Búsqueda en el espacio de estados: BFS, DFS, UCS y A* con animaciones
22. Juegos y adversarios: minimax, poda alfa-beta y Monte Carlo tree search
23. Satisfacción de restricciones: backtracking, propagación de restricciones y AC-3 con un sudoku y un mapa de regiones checas
24. Lógica y sistemas basados en conocimiento: encadenamiento hacia delante y hacia atrás, resolución y sistemas expertos
25. Planificación: STRIPS, el mundo de bloques, heurísticas a partir de la relajación y la planificación en los agentes de IA
26. Búsqueda local y recocido simulado: un viajante por las capitales regionales checas
27. Algoritmos genéticos: población, cruce, mutación y selección en una mochila para la excursión
28. Estrategias evolutivas y programación genética: de la regla de un quinto a la ley de Kepler
29. Optimización por colonia de hormigas: cómo un rastro de feromona encuentra un camino corto
30. Optimización por enjambre de partículas: inercia, experiencia propia y experiencia del enjambre
31. Neuroevolución: evolución de los pesos y la forma de las redes neuronales, y el algoritmo NEAT
32. Conjuntos difusos y funciones de pertenencia: cómo escribir «algo cálido»
33. Lógica difusa y probabilidad: por qué «algo cálido» no significa «probablemente cálido»
34. Lógica difusa: t-normas, implicaciones y reglas SI–ENTONCES
35. Control difuso: Mamdani y Sugeno, del ventilador al péndulo invertido sobre un carro
36. Agrupamiento difuso: el algoritmo fuzzy c-means y los puntos entre clusters
37. Sistemas neuro-difusos (ANFIS): reglas difusas que aprenden de los datos
38. Cadenas de Markov: matriz de transición, distribución estacionaria y PageRank
39. Modelos ocultos de Márkov: el algoritmo de Viterbi y el casino deshonesto
40. Redes bayesianas: por qué está mojada la hierba y qué significa eso para el aspersor
41. El filtro de Kalman: cómo estimar a partir de mediciones imprecisas dónde está un coche y a qué velocidad va
42. Tipos de aprendizaje automático: supervisado, no supervisado, semisupervisado y más
43. Prompts, contexto y RAG: cómo darle a un modelo la información correcta
44. Autocodificadores variacionales (VAE): imágenes nuevas a partir de un espacio latente continuo
45. Redes generativas adversarias (GAN): el falsificador contra el detective
46. Modelos de difusión: cómo el ruido puro se convierte en una imagen
47. Procesos de decisión de Markov: estados, acciones, recompensas y ecuaciones de Bellman
48. Q-learning y DQN: aprender el valor de las acciones, de la tabla a la red neuronal
49. Gradiente de la política y PPO: aprender directamente la política
50. Cómo funciona un agente de IA: un modelo de lenguaje en un bucle con herramientas
51. Programación con agentes de IA: encargo, pruebas y revisión
52. Evaluación y seguridad de los sistemas de IA: cómo medir y cómo vigilar

Temario completo de la serie 52 de 83 temas publicados

Un mapa de ciudades y carreteras, una red de amigos, el espacio de estados de un juego, una red neuronal e incluso el cálculo en el que se obtiene el gradiente — todo eso es un grafo: puntos unidos por líneas. Los grafos son la estructura más universal de la informática y en la inteligencia artificial te los encontrarás a cada paso. Los árboles son su caso particular más sencillo y más útil.

Construiremos toda la parte sobre un solo grafo con siete ciudades de la A a la G y carreteras con su longitud. Sobre él mostraremos paso a paso los grados, cómo guardar un grafo, los caminos más cortos y el árbol de expansión mínima.

1. Qué es un grafo

Definición — grafo

Un grafo es un par G = (V, E), donde V es un conjunto finito de vértices y E un conjunto de aristas.

En un grafo no dirigido una arista es un conjunto de dos elementos {u, v}; en uno dirigido, un par ordenado (u, v) — una flecha de u a v. Un grafo dirigido es, por tanto, una relación sobre V.

Un grafo ponderado tiene además una función w : E → ℝ que asigna a cada arista un peso (longitud, coste, tiempo).

2. Grado de un vértice

Definición — grado y lema del apretón de manos

El grado deg(v) de un vértice v es el número de aristas que salen de él.

Teorema (lema del apretón de manos). En todo grafo no dirigido se cumple ∑_{v ∈ V} deg(v) = 2 |E|.

La suma de los grados es 2 + 4 + 4 + 4 + 4 + 4 + 2 = 24 y hay 12 aristas — justo como dice el teorema. El grado tiene sentido práctico: en una red social es el número de amigos, en la web el número de enlaces, y los vértices de grado alto suelen ser los más importantes.

3. Cómo guardar un grafo en el ordenador

El ordenador no ve una imagen, necesita números. Hay dos formas habituales:

• Matriz de adyacencia — una tabla de |V| × |V|; en la celda (u, v) está el peso de la arista, o 0. Responder «¿hay aquí una arista?» es rápido, pero la memoria crece como |V|².
• Lista de adyacencia — para cada vértice, la lista de sus vecinos. La memoria crece solo como |V| + |E|, lo que para los grafos dispersos (red social, mapa) es una diferencia enorme.

La matriz es simétrica respecto a la diagonal — esa es la seña de un grafo no dirigido. En IA la matriz de adyacencia se usa en las redes neuronales de grafos, que aprenden directamente sobre grafos (moléculas, redes sociales, red de carreteras).

4. Caminos, ciclos y conexidad

Definición — camino, ciclo, conexidad

Un camino de u a v es una sucesión de vértices distintos entre sí u = v₀, v₁, …, v_k = v, en la que cada dos consecutivos están unidos por una arista. Su longitud es k (el número de aristas); en un grafo ponderado, la suma de los pesos.

Un ciclo es un camino que vuelve al vértice de partida (al menos tres aristas).

Un grafo es conexo cuando entre cada dos vértices hay un camino. Las partes conexas maximales de un grafo son sus componentes conexas — y «estar en la misma componente» es una equivalencia, así que las componentes forman una partición de V.

5. Caminos más cortos

El problema «cómo llegar lo más rápido de A a G» es la búsqueda de un camino más corto — justo lo que hacían los algoritmos de la parte sobre la búsqueda en el espacio de estados. Pero depende de qué medimos.

Si nos interesa el número de aristas, basta con la búsqueda en anchura: primero los vecinos de A, luego sus vecinos… El número sobre cada vértice es la distancia desde A en aristas:

A G llevan tres aristas (por ejemplo A–B–E–G). Pero si contamos la longitud de las carreteras, necesitamos el algoritmo de Dijkstra — siempre continúa desde el vértice más cercano aún no cerrado. El número sobre cada vértice es ahora la distancia más corta en kilómetros, y está resaltado el camino más corto hasta G:

El camino más corto A–B–D–E–G tiene cuatro aristas, más que el camino de tres aristas de BFS, pero una longitud de solo 12. El camino A–B–E–G mediría 4 + 7 + 3 = 14. Menos pasos no significa un camino más corto — es exactamente la diferencia entre BFS y UCS que vimos en el laberinto con barro.

6. Árboles

Definición — árbol y árbol con raíz

Un árbol es un grafo conexo sin ciclos. Un bosque es un grafo sin ciclos (cada una de sus componentes es un árbol).

Teorema. Para un grafo con n vértices son equivalentes: (1) es un árbol; (2) es conexo y tiene n − 1 aristas; (3) no tiene ciclos y tiene n − 1 aristas; (4) entre cada dos vértices hay exactamente un camino.

Un árbol con raíz tiene un vértice destacado, la raíz. Los vecinos de un vértice en dirección contraria a la raíz son sus hijos, un vértice sin hijos es una hoja y la profundidad de un vértice es la longitud del camino desde la raíz.

En IA los árboles están por todas partes. Un árbol de decisión clasifica con una serie de preguntas desde la raíz hasta una hoja. Los algoritmos de búsqueda construyen un árbol de búsqueda — el árbol de BFS y DFS de la parte sobre la búsqueda es exactamente eso. Y un programa de ajedrez calcula un árbol de juego, en el que los vértices son posiciones y las aristas jugadas.

7. Árbol de expansión mínima

Definición — árbol de expansión y algoritmo de Kruskal

Un árbol de expansión de un grafo conexo G es un subgrafo que contiene todos los vértices de G y es un árbol. Un árbol de expansión mínima tiene la menor suma de pesos de sus aristas.

Algoritmo de Kruskal: ordena las aristas por peso de menor a mayor y ve añadiendo cada una que no forme un ciclo. Es un algoritmo voraz y, aun así, siempre encuentra el óptimo.

El árbol de expansión tiene 6 aristas para 7 vértices — exactamente n − 1, como dice el teorema sobre los árboles — y una longitud total de 18. Las seis carreteras restantes el algoritmo las rechazó, porque habrían formado un ciclo.

8. Grafos acíclicos y el cálculo de una red neuronal

Definición — DAG y orden topológico

Un grafo dirigido acíclico (DAG) es un grafo dirigido sin ciclos dirigidos.

Un orden topológico es una ordenación de los vértices tal que cada arista (u, v) va de izquierda a derecha — u está antes que v. Teorema. Un grafo dirigido tiene un orden topológico si y solo si es acíclico.

Así calcula cualquier red neuronal. Aquí está el cálculo de una sola neurona ŷ = σ(w · x + b) y de su error L(ŷ, y) como grafo de cómputo: las entradas a la izquierda, las operaciones como vértices, y las flechas muestran qué depende de qué. Los números son el orden topológico:

La red calcula hacia delante en orden topológico — primero el producto, luego la suma, la sigmoide y el error. Y cuando después aprende, recorre el mismo grafo hacia atrás: la retropropagación del error (backpropagation) pasa por los vértices en orden topológico inverso y en cada uno aplica la regla de la cadena. Bibliotecas como PyTorch construyen este grafo solas en cada cálculo. Por cierto, también el grafo de dependencias entre módulos en el temario de esta serie es un DAG.

9. Los grafos en la inteligencia artificial

• El espacio de estados es un grafo: los estados son vértices; las acciones, aristas con coste. Buscar es encontrar un camino en un grafo.
• Los grafos de cómputo de las redes neuronales son DAG; el entrenamiento es un recorrido de ida y vuelta.
• Los grafos de conocimiento guardan hechos como aristas «Praga — es la capital de — Chequia», y los buscadores componen con ellos sus respuestas.
• Las redes bayesianas son DAG de dependencias probabilísticas — llegaremos a ellas en el módulo sobre modelos probabilísticos.
• Las redes neuronales de grafos aprenden directamente sobre grafos: predicen propiedades de moléculas, el tráfico o recomendaciones.

10. Resumen

• Un grafo es un conjunto de vértices y aristas; las aristas pueden tener dirección y peso. La suma de los grados es el doble del número de aristas.
• Un grafo se guarda con una matriz de adyacencia o con listas de adyacencia — mucho más económicas para grafos dispersos.
• BFS encuentra el camino con menos aristas, Dijkstra el más corto según los pesos — y no tiene por qué ser el mismo.
• Un árbol es un grafo conexo sin ciclos con n − 1 aristas; el árbol de expansión mínima lo encuentra el algoritmo voraz de Kruskal.
• Una red neuronal es un DAG de cómputo: hacia delante se calcula en orden topológico, el gradiente hacia atrás.

¿Lo ves de otra manera? Escribe a support@coden-app.com.