Inicio · Parte 04 — Matemática discreta para computación
no dirigido: Σ grados = 2|E|
dirigido: Σ grados de salida = Σ grados de entrada = |E|
densidad = |E| / (|V|(|V|−1))Un grafo es un conjunto de vértices y un conjunto de aristas que los conectan. Es la estructura más versátil de la computación porque casi cualquier relación se modela así: dependencias entre tareas, enlaces entre páginas, amistades, rutas, y —lo que importa en este programa— operaciones de un cálculo.
El lema del apretón de manos dice que la suma de los grados es el doble del número de aristas, porque cada arista contribuye 1 a cada uno de sus dos extremos. De ahí se deduce inmediatamente que el número de vértices de grado impar es par, resultado que parece anecdótico y aparece en problemas de emparejamiento.
La representación importa para el rendimiento. Una matriz de adyacencia ocupa O(V²) y responde «¿hay arista?» en tiempo constante; una lista de adyacencia ocupa O(V+E) y es preferible en grafos dispersos, que son la mayoría de los reales. Los grafos de redes sociales tienen densidad ínfima, y usar matriz sería inviable.
El grafo del laboratorio es un pipeline de machine learning —entrada, limpieza, features, split, entrenamiento, evaluación—, y ese ejemplo no es decorativo: la ejecución de un pipeline, de un sistema de construcción y de un grafo de cómputo de autodiferenciación son el mismo problema sobre la misma estructura.
Grafo de un pipeline de ML.
entrada → limpieza → features → entrenamiento → evaluacion
↘ split ↗
vértices: 6
aristas dirigidas: 6
grados de salida:
entrada 1, limpieza 2, features 1,
split 1, entrenamiento 1, evaluacion 0
suma = 6 = |E| ✓
densidad = 6/(6·5) = 0.2Grados, aristas y el lema del apretón de manos.
python classes/part-04-matematica-discreta-para-computacion/093-grafos-vertices-y-aristas/lab.py
compmath run 093nodosgrado_de_salidaaristas_dirigidassuma_de_gradoslema_apreton_de_manos_no_dirigidodensidad{
"nodos": [
"entrada",
"entrenamiento",
"evaluacion",
"features",
"limpieza",
"split"
],
"grado_de_salida": {
"entrada": 1,
"limpieza": 2,
"features": 1,
"split": 1,
"entrenamiento": 1,
"evaluacion": 0
},
"aristas_dirigidas": 6,
"suma_de_grados": 6,
"lema_apreton_de_manos_no_dirigido": "Σ grados = 2|E|",
"densidad": 0.2
}Grafos de cómputo y autodiferenciación, sistemas de construcción, redes sociales, rutas y GNN.
Los grafos de cómputo, la búsqueda en árbol y las GNN son estructuras discretas; el conteo sostiene la probabilidad que después usa todo modelo generativo.
9780262046305 verificado en International ISBN Agency (2026-08-19).9780198805090 verificado en International ISBN Agency (2026-08-19).