Notebook	Colab
Notebook 01 — Grafos (práctica de esta sección)

Grafos: fundamentos

“A mathematician, like a painter or a poet, is a maker of patterns.” — G. H. Hardy

Los grafos son una de las estructuras más poderosas y ubicuas en ciencias de la computación. Modelan redes sociales, mapas de carreteras, circuitos eléctricos, relaciones en bases de datos, y — como veremos en el módulo — el espacio de posibles acciones de un agente inteligente.

Este capítulo construye el vocabulario formal que necesitamos para hablar con precisión sobre grafos. Nada aquí es difícil; lo importante es que los conceptos queden claros antes de usarlos en algoritmos.

1. Definición formal

Un grafo $G$ es un par $G = (V, E)$ donde:

• $V$ es un conjunto finito de vértices (o nodos).
• $E$ es un conjunto de aristas (o arcos).

Cómo se definen las aristas depende del tipo de grafo.

2. Grafos no dirigidos y dirigidos

Grafo no dirigido

Las aristas son pares no ordenados de vértices: ${u, v}$ donde $u \neq v$. La arista ${u, v}$ y la arista ${v, u}$ son la misma arista — la relación es simétrica.

Ejemplo: una red de carreteras entre ciudades, donde puedes ir y venir por el mismo camino.

Grafo dirigido (digrafo)

Las aristas son pares ordenados: $(u, v)$. Aquí $(u, v)$ y $(v, u)$ son aristas distintas. Llamamos arco a cada par ordenado. La dirección importa.

Ejemplo: páginas web con hipervínculos — una página puede enlazar a otra sin que el enlace sea recíproco.

3. Grafos simples y multigrafos

Un grafo simple satisface dos condiciones:

1. Sin autoloops: no existe arista de un vértice a sí mismo, es decir, ${v, v} \notin E$.
2. Sin aristas múltiples: entre dos vértices hay a lo sumo una arista.

Un multigrafo relaja estas restricciones: puede haber múltiples aristas entre el mismo par de vértices, y pueden existir autoloops.

4. Vocabulario esencial: recorridos, caminos y ciclos

Dado un grafo $G = (V, E)$ necesitamos hablar sobre secuencias de vértices conectados.

Recorrido (walk)

Una secuencia de vértices $v_0, v_1, v_2, \ldots, v_k$ tal que cada par consecutivo $(v_i, v_{i+1})$ es una arista. Puede repetir vértices y aristas.

Camino (path)

Un recorrido donde ningún vértice se repite. Formalmente: $v_i \neq v_j$ para todo $i \neq j$.

La longitud de un camino es su número de aristas $k$.

Ciclo (cycle)

Un camino $v_0, v_1, \ldots, v_k$ donde además $v_0 = v_k$ (el camino es cerrado). Es decir, empieza y termina en el mismo vértice, y no repite ningún vértice intermedio.

Un grafo acíclico no contiene ciclos.

5. Conectividad

Grafos no dirigidos

Un grafo no dirigido es conexo si existe un camino entre todo par de vértices $u, v \in V$.

Si no es conexo, sus componentes conexas son los subgrafos conexos maximales — los grupos de nodos que sí están conectados entre sí.

Grafos dirigidos

La noción de conectividad se bifurca:

• Fuertemente conexo: existe un camino dirigido de $u$ a $v$ y de $v$ a $u$ para todo par $u, v$.
• Débilmente conexo: el grafo subyacente no dirigido (ignorar direcciones) es conexo.

6. Árboles: grafos especiales

Un árbol es un grafo no dirigido que es simultáneamente:

• Conexo: existe un camino entre todo par de nodos.
• Acíclico: no contiene ciclos.

Estas dos condiciones son equivalentes a $|E| = |V| - 1$.

Los árboles aparecen constantemente en búsqueda porque los algoritmos BFS y DFS generan naturalmente un árbol de búsqueda — la estructura que registra cómo se exploraron los nodos.

7. Grado de un vértice

Grafos no dirigidos

El grado de un vértice $v$, denotado $\deg(v)$, es el número de aristas incidentes a $v$.

Ejemplo concreto: considera el triángulo $A - B - C - A$ (tres vértices, tres aristas).

Suma de grados: $2 + 2 + 2 = 6 = 2 \times 3 = 2|E|$.

¿Por qué siempre vale $\sum_{v \in V} \deg(v) = 2|E|$?

Esta es una igualdad exacta — no una cota ni una aproximación — y vale para cualquier grafo no dirigido, sin importar si es conexo, disperso o denso.

El argumento es de doble conteo: imagina que “distribuyes” cada arista entre sus dos extremos, dando medio punto a cada uno. La suma total de puntos es $|E|$ (una por arista). Pero esa misma suma vista por vértices es $\frac{1}{2}\sum_{v} \deg(v)$, porque el grado de $v$ cuenta cuántas aristas le tocaron. Igualando: $\frac{1}{2}\sum_{v} \deg(v) = |E|$, es decir:

$$\sum_{v \in V} \deg(v) = 2|E|$$

O dicho sin fracciones: cada arista ${u,v}$ contribuye $+1$ al grado de $u$ y $+1$ al grado de $v$ — exactamente 2 en total. No hay margen de error porque cada arista tiene exactamente dos extremos, ni más ni menos (estamos en un grafo simple).

Grafos dirigidos

• Grado de entrada (in-degree) $\deg^+(v)$: número de arcos que llegan a $v$.
• Grado de salida (out-degree) $\deg^-(v)$: número de arcos que salen de $v$.

El grado de salida determina cuántas opciones tiene un agente desde el estado $v$ — esto es el factor de ramificación (branching factor), que reaparecerá en el análisis de complejidad de BFS, DFS e IDDFS.

8. Representaciones en Python

¿Cómo guardamos un grafo en memoria? Hay dos representaciones estándar.

8.1 Lista de adyacencia

Para cada vértice, guardamos la lista de sus vecinos. En Python, lo más natural es un diccionario de listas:

# Grafo dirigido: 0→1, 0→2, 1→3, 2→3, 3→4
graph = {
    0: [1, 2],
    1: [3],
    2: [3],
    3: [4],
    4: [],
}

Para un grafo no dirigido, cada arista aparece en ambas listas:

# Grafo no dirigido: {0,1}, {1,2}, {2,3}
graph = {
    0: [1],
    1: [0, 2],
    2: [1, 3],
    3: [2],
}

8.2 Matriz de adyacencia

Una matriz $A$ de tamaño $|V| \times |V|$ donde $A[i][j] = 1$ si existe la arista $(i, j)$ y $0$ si no.

import numpy as np

# El mismo grafo dirigido de 5 nodos
A = np.array([
    [0, 1, 1, 0, 0],   # nodo 0
    [0, 0, 0, 1, 0],   # nodo 1
    [0, 0, 0, 1, 0],   # nodo 2
    [0, 0, 0, 0, 1],   # nodo 3
    [0, 0, 0, 0, 0],   # nodo 4
])

8.3 ¿Cuál usar?

Regla práctica:

• Grafo disperso ($|E| \ll V^2$): usa lista de adyacencia. La mayoría de los problemas de IA caen aquí — el espacio de estados tiene muchos nodos pero cada uno tiene pocos vecinos.
• Grafo denso ($|E| \approx V^2$): la matriz puede ser más eficiente para consultas de aristas.

Resumen

Siguiente: Espacio de estados →