Tema 2. Fundamentos y aplicaciones de la teoría de grafos. Diagramas en árbol.

Índice

1. Introducción
2. Concepto de grafo: definiciones y tipología
3. Grado, teorema de los apretones de manos y sucesiones gráficas
4. Representación de grafos: matrices y listas
5. Conexión, caminos y ciclos. Grafos eulerianos y hamiltonianos
6. Grafos planos, coloración y el teorema de los cuatro colores
7. Árboles: caracterización y propiedades
8. Árboles generadores y árbol generador mínimo: Kruskal y Prim
9. Diagramas en árbol: combinatoria, probabilidad y árboles con raíz
10. Algoritmos y aplicaciones de la teoría de grafos
11. Aplicación didáctica y relación con el currículo
12. Conclusión
13. Bibliografía y referencias

1. Introducción

En el verano de 1736, el matemático suizo Leonhard Euler (1707-1783) presentó a la Academia de Ciencias de San Petersburgo un breve trabajo, Solutio problematis ad geometriam situs pertinentis, en el que resolvía un pasatiempo que traía de cabeza a los habitantes de Königsberg —hoy Kaliningrado—: la ciudad, atravesada por el río Pregel, tenía dos islas y siete puentes, y sus vecinos se preguntaban si era posible dar un paseo que cruzara cada puente exactamente una vez y regresara al punto de partida. Euler demostró que no era posible, pero lo verdaderamente decisivo fue cómo lo hizo: despojó al problema de toda su geometría —distancias, formas, tamaños— y lo redujo a lo único que importaba, un conjunto de puntos (las masas de tierra) y de líneas que los unían (los puentes). Con ese gesto de abstracción nacieron a la vez dos ramas enteras de la matemática: la teoría de grafos y, en germen, la topología, aquella «geometría de la posición» (geometria situs) que Gottfried Leibniz había intuido medio siglo antes sin llegar a desarrollarla.

Un grafo es, en su esencia, ese objeto de una sencillez desarmante: una colección de vértices —puntos, nodos— y de aristas —líneas que conectan pares de vértices—. Nada más. Y, sin embargo, sobre esa base mínima se levanta una de las teorías más versátiles y de mayor proyección de toda la matemática contemporánea. La razón es que un número inmenso de situaciones del mundo se dejan describir como «objetos y relaciones entre ellos», y esa es exactamente la estructura que un grafo captura: las ciudades y las carreteras que las unen, las personas y sus amistades, las páginas web y sus enlaces, los átomos de una molécula y sus enlaces químicos, las tareas de un proyecto y sus dependencias, las asignaturas y sus incompatibilidades de horario. Comprender un problema como un grafo es, muchas veces, haberlo resuelto a medias.

Este tema pertenece de lleno a la matemática discreta, la que estudia los objetos que se cuentan con números naturales y no se miden en un continuo, y guarda un estrecho parentesco con la combinatoria del tema siguiente. En la arquitectura del currículo vigente —ordenado por la Ley Orgánica 2/2006, de Educación (LOE), modificada por la Ley Orgánica 3/2020 (LOMLOE), y desarrollado por el Real Decreto 217/2022 para la Educación Secundaria Obligatoria (ESO), el Real Decreto 243/2022 para el Bachillerato y, en la Comunitat Valenciana, por los Decretos 107/2022 y 108/2022 del Consell— los contenidos de este tema irrigan varios de los seis sentidos en que la LOMLOE organiza la competencia matemática. Los diagramas en árbol son una herramienta explícita del sentido estocástico para el recuento sistemático y el cálculo de probabilidades desde los primeros cursos de la ESO; los grafos y sus algoritmos alimentan el pensamiento computacional que vertebra el sentido algebraico; y la vocación modelizadora de toda la teoría encarna como pocas el sentido socioafectivo y las conexiones entre las matemáticas y la vida real que el currículo persigue. Enseñar bien estos contenidos es, además, sembrar la educación matemática de calidad que reclama el Objetivo de Desarrollo Sostenible 4 (ODS 4) de la Agenda 2030.

El desarrollo recorrerá cuatro miradas que se irán entrelazando. La mirada fundacional, que fija con rigor qué es un grafo, cómo se clasifican, cómo se representan y qué propiedades básicas —como el grado y el teorema de los apretones de manos— gobiernan su estructura. La mirada de los problemas clásicos, que revive los grandes retos que forjaron la disciplina: los recorridos de Euler y de Hamilton, la planaridad y el célebre teorema de los cuatro colores. La mirada de los árboles, la familia de grafos más importante en las aplicaciones, con sus caracterizaciones, sus árboles generadores mínimos y los diagramas en árbol que enlazan con la combinatoria y la probabilidad. Y la mirada algorítmica y aplicada, que muestra cómo los grafos resuelven hoy problemas de logística, de redes y de ingeniería, y por qué son el fundamento matemático de internet, de los navegadores GPS y de las redes sociales. A lo largo del camino, y no solo al final, señalaremos cómo cada bloque conecta con los saberes básicos del currículo, qué errores suele encontrar el docente, con qué situaciones de aprendizaje se enseña y qué figuras —Euler y Hamilton, pero también Ada Lovelace, Grace Hopper, Fan Chung o Réka Albert— jalonan esta historia.

Figura 1. Los siete puentes de Königsberg modelizados como multigrafo: cuatro masas de tierra (vértices) y siete puentes (aristas).

2. Concepto de grafo: definiciones y tipología

2.1. Definición formal

Formalmente, un grafo es un par G=(V,E) donde V es un conjunto finito y no vacío cuyos elementos se llaman vértices (o nodos), y E es un conjunto de aristas, cada una de las cuales conecta un par de vértices. Cuando la arista une los vértices u y v se dice que u y v son sus extremos, que son adyacentes (o vecinos) y que la arista es incidente con ambos. Dos aristas que comparten un extremo son, a su vez, adyacentes entre sí. El número de vértices |V| se llama orden del grafo y el número de aristas |E|, su tamaño. Salvo mención expresa, en este tema trabajaremos con grafos finitos, que son los que interesan tanto a las aplicaciones como al aula.

La sencillez de la definición esconde una decisión conceptual profunda, la misma que tomó Euler: un grafo no es un dibujo. Dos diagramas de aspecto muy distinto pueden representar el mismo grafo, porque lo único que cuenta es qué vértices están unidos con cuáles, no dónde se sitúan los puntos ni si las líneas son rectas o curvas, largas o cortas, ni si se cruzan al dibujarlas. Esta distinción entre la estructura (los datos de adyacencia) y sus infinitas representaciones gráficas es una de las ideas más formativas del tema y, a la vez, una fuente frecuente de confusión en el alumnado, que tiende a atribuir significado a rasgos accidentales del dibujo.

2.2. Una familia de variantes

Según lo que se permita en E, se obtiene toda una tipología de grafos que conviene manejar con precisión:

• Un grafo simple es el caso básico: no admite lazos (aristas que unen un vértice consigo mismo) ni aristas múltiples (varias aristas entre el mismo par de vértices). Cada arista es entonces un par no ordenado \{u,v\} con u\neq v.
• Un multigrafo admite aristas múltiples o paralelas; es lo que necesitábamos para Königsberg, donde había dos puentes entre la isla y una misma orilla. Si además se permiten lazos, se habla de pseudografo.
• Un grafo dirigido o dígrafo sustituye las aristas por arcos, que son pares ordenados (u,v): la relación tiene ahora un sentido, de origen a destino. Modelizan calles de sentido único, enlaces web (que apuntan de una página a otra) o relaciones de precedencia entre tareas.
• Un grafo ponderado o etiquetado asigna a cada arista un peso mediante una función w:E\to\mathbb{R}, habitualmente un número positivo que representa una distancia, un coste, un tiempo o una capacidad. Casi todas las aplicaciones logísticas trabajan con grafos ponderados.

2.3. Grafos con nombre propio

Ciertas familias reaparecen tan a menudo que reciben nombre propio. El grafo completo K_n es el grafo simple de n vértices en el que todos están unidos entre sí; tiene, por tanto, \binom{n}{2}=\dfrac{n(n-1)}{2} aristas, una fórmula que conecta directamente con la combinatoria y que cuenta los apretones de manos posibles en un grupo de n personas. El grafo camino P_n y el grafo ciclo C_n son, respectivamente, una sucesión abierta y una cerrada de vértices consecutivos. Un grafo es regular de grado k (o k-regular) si todos sus vértices tienen el mismo número k de vecinos. Un grafo es bipartito si sus vértices se reparten en dos conjuntos disjuntos de modo que toda arista une un vértice de uno con otro del segundo —nunca dos del mismo lado—; el bipartito completo K_{m,n} contiene todas las aristas posibles entre un grupo de m y otro de n vértices. Los grafos bipartitos modelizan de forma natural las situaciones de emparejamiento (personas y tareas, estudiantes y proyectos) y admiten una hermosa teoría de emparejamientos cuyo resultado central es el teorema de Hall.

Un subgrafo de G es un grafo formado por parte de sus vértices y parte de sus aristas; si conserva todos los vértices se llama subgrafo generador (o recubridor), noción esencial para los árboles generadores del apartado 8. Finalmente, dos grafos son isomorfos cuando existe una biyección entre sus vértices que preserva las adyacencias: son «el mismo grafo» con otras etiquetas o dibujado de otro modo. Decidir de forma eficiente si dos grafos son isomorfos es un problema sutil, uno de los pocos cuya clasificación de complejidad ha permanecido esquiva durante décadas, lo que muestra que hasta las preguntas más elementales sobre grafos pueden encerrar una dificultad computacional formidable.

A partir de un grafo se construyen otros que revelan información distinta. El grafo complementario \overline{G} tiene los mismos vértices pero une exactamente los pares que en G no eran adyacentes, de modo que G y \overline{G} se reparten entre ambos todas las aristas del completo K_n; muchas propiedades se iluminan al examinar el complementario. Otras operaciones —la unión, el producto o el grafo línea, que convierte las aristas de G en los vértices de un grafo nuevo— permiten reformular problemas y trasladar resultados de unos grafos a otros, y constituyen la gramática con la que se combinan las piezas básicas de la teoría.

Figura 2. Cuatro tipos de grafo según lo que se admita en las aristas: simple, multigrafo, dirigido y ponderado.

3. Grado, teorema de los apretones de manos y sucesiones gráficas

3.1. El grado de un vértice

El grado de un vértice v, denotado \deg(v) o g(v), es el número de aristas incidentes con él; equivale al número de vecinos en un grafo simple. Por convenio, un lazo suma 2 al grado, pues incide dos veces en su vértice. Un vértice de grado 0 es aislado y uno de grado 1, colgante o terminal. Se llaman grado mínimo y grado máximo del grafo, y se denotan \delta(G) y \Delta(G), al menor y al mayor de los grados de sus vértices. Un grafo es k-regular cuando todos los grados coinciden con un mismo valor k: así, un ciclo C_n es 2-regular y el grafo completo K_n es (n-1)-regular.

3.2. El teorema de los apretones de manos

La primera propiedad estructural de todo grafo —y la más citada— relaciona los grados con el número de aristas. Se conoce como lema del apretón de manos (handshaking lemma) y ya aparece, implícito, en el propio trabajo de Euler de 1736:

La demostración es de una transparencia ejemplar: al sumar los grados de todos los vértices contamos las incidencias entre vértices y aristas, y cada arista aporta exactamente dos a esa cuenta, una por cada uno de sus dos extremos. Por tanto, la suma total de los grados es el doble del número de aristas. El nombre procede de su lectura social: si en una reunión varias personas se dan la mano, la suma total de manos estrechadas por cada asistente es par, porque cada apretón involucra a dos personas y se cuenta dos veces.

De esta identidad se sigue un corolario tan sencillo como útil: en todo grafo, el número de vértices de grado impar es par. En efecto, la suma de todos los grados es par (es 2|E|); si separamos los sumandos pares de los impares, la suma de los pares es par, luego la de los impares también debe serlo, y una suma de números impares solo es par si hay una cantidad par de ellos. Este corolario es el que zanja el problema de Königsberg: sus cuatro vértices tienen grado impar, y ya veremos que un recorrido que use cada arista una vez exige a lo sumo dos vértices de grado impar. Es también el argumento que prueba que en cualquier fiesta el número de personas que han estrechado un número impar de manos es par, un resultado que sorprende y que resulta perfectamente accesible en el aula como primera experiencia de demostración por conteo doble.

Figura 3. El lema del apretón de manos en un grafo de cinco aristas: la suma de los grados duplica el número de aristas.

3.3. Sucesiones de grados

Ordenando los grados de todos los vértices se obtiene la sucesión de grados del grafo, por ejemplo (3,3,2,2) para el grafo de la figura anterior. Surge entonces una pregunta natural y profunda: dada una lista de números, ¿existe siempre un grafo cuyos vértices tengan esos grados? No siempre; una tal lista se llama sucesión gráfica cuando sí existe. El teorema de Erdös-Gallai y el algoritmo constructivo de Havel-Hakimi caracterizan exactamente qué sucesiones lo son, y su primera condición necesaria es justamente el corolario anterior: la suma ha de ser par. En dígrafos, cada vértice tiene un grado de entrada y un grado de salida, y la suma de todos los grados de entrada iguala a la de todos los de salida, pues ambas cuentan el número total de arcos. Estas ideas, aparentemente técnicas, son un magnífico terreno para ejercitar el razonamiento y la conjetura que la competencia específica de razonamiento y prueba del currículo LOMLOE sitúa en el corazón del quehacer matemático.

4. Representación de grafos: matrices y listas

Para trabajar con un grafo —y, sobre todo, para que lo manipule un ordenador— hace falta codificarlo de forma que no dependa del dibujo. Hay dos grandes maneras de hacerlo, y elegir bien entre ellas es la primera decisión de todo algoritmo sobre grafos.

4.1. La matriz de adyacencia

La matriz de adyacencia de un grafo de n vértices, numerados de 1 a n, es la matriz cuadrada A de orden n cuyo elemento a_{ij} es el número de aristas que unen el vértice i con el j (simplemente 1 o 0 en un grafo simple, según sean o no adyacentes). En un grafo no dirigido la matriz es simétrica, a_{ij}=a_{ji}, porque la adyacencia es una relación recíproca; en un dígrafo, en cambio, deja de serlo, y esa asimetría codifica el sentido de los arcos. La suma de los elementos de una fila (o columna) es el grado del vértice correspondiente.

La matriz de adyacencia no es un mero almacén de datos: es un puente entre la teoría de grafos y el álgebra lineal que el alumnado estudia en Bachillerato, y encierra una propiedad tan elegante como útil. Si se calcula la potencia A^k, resulta que su elemento (i,j) cuenta exactamente el número de recorridos de longitud k que van del vértice i al j. Así, el álgebra de matrices —producto, potencias— se convierte en una herramienta para contar caminos, y toda una rama moderna, la teoría espectral de grafos, estudia la estructura de un grafo a través de los autovalores de sus matrices; entre sus figuras contemporáneas destaca la matemática Fan Chung, cuyos trabajos sobre grafos aleatorios y espectros son referencia obligada. Que una cuestión combinatoria —contar caminos— se resuelva multiplicando matrices es un ejemplo espléndido de las conexiones entre bloques matemáticos que el currículo anima a tender.

4.2. La lista de adyacencia

La lista de adyacencia guarda, para cada vértice, la relación de sus vecinos. Si el grafo tiene n vértices y m aristas, ocupa un espacio del orden de n+m, muy inferior al orden n^2 de la matriz cuando el grafo es disperso (sparse), es decir, cuando tiene muchos menos aristas que el máximo posible —el caso de casi todas las redes reales, desde una red de carreteras hasta una red social—. A cambio, comprobar si dos vértices concretos son adyacentes es inmediato con la matriz y algo más lento con la lista. La regla práctica es clara: matriz para grafos pequeños o densos y para el cálculo algebraico; lista para grafos grandes y dispersos y para recorrerlos con eficiencia. Existe además la matriz de incidencia, de dimensión vértices por aristas, con un 1 en la casilla (v,e) cuando el vértice v es extremo de la arista e; es útil en ciertos desarrollos teóricos y en las aplicaciones a redes de flujo.

Figura 4. El mismo grafo codificado como matriz de adyacencia (simétrica) y como lista de adyacencia.

5. Conexión, caminos y ciclos. Grafos eulerianos y hamiltonianos

5.1. Recorridos, caminos y ciclos

Moverse por un grafo consiste en recorrer aristas encadenadas. Un recorrido es una sucesión alternada de vértices y aristas, cada una uniendo el vértice anterior con el siguiente; su longitud es el número de aristas que emplea. Según qué se permita repetir, se distinguen varios tipos, y conviene fijar la terminología para no confundirlos. Un camino (o paseo) es un recorrido que no repite aristas; un camino simple es un recorrido que no repite vértices —y, por tanto, tampoco aristas—. Un recorrido es cerrado cuando termina en el mismo vértice en que empezó; un ciclo es un camino cerrado que no repite vértices salvo el inicial y el final. El menor ciclo de un grafo tiene longitud 3 —un triángulo—, salvo que haya lazos o aristas múltiples.

5.2. Conexión y componentes

Un grafo es conexo si existe un camino entre cada par de vértices; en caso contrario, se descompone en piezas maximales llamadas componentes conexas. La distancia entre dos vértices es la longitud del camino más corto que los une, y el mayor de esos valores es el diámetro del grafo, una medida de «lo lejos» que pueden estar dos nodos. Ciertos elementos son críticos para la conexión: un puente es una arista cuya eliminación desconecta el grafo, y un vértice de corte o de articulación, un vértice cuya supresión hace lo propio. Identificarlos es esencial en el diseño de redes robustas —de comunicaciones, de suministro eléctrico—, donde un puente representa un punto único de fallo que conviene evitar o duplicar.

Para medir cuán robusta es la conexión se define la conectividad de un grafo como el menor número de vértices que hay que suprimir para desconectarlo, y análogamente la conectividad por aristas; un grafo es k-conexo si hacen falta al menos k supresiones. El resultado central es el teorema de Menger, que iguala ese número con la cantidad de caminos internamente disjuntos entre dos vértices: existen k rutas alternativas que no comparten nodos intermedios si, y solo si, se necesitan k supresiones para incomunicarlos. Es el fundamento teórico del diseño de redes tolerantes a fallos —de telecomunicaciones, de transporte o de suministro—, en las que la existencia de caminos alternativos garantiza que la caída de un enlace no aísle a ningún nodo, una preocupación central de las infraestructuras resilientes que persigue el ODS 9.

5.3. Grafos eulerianos: el legado de Königsberg

Volvamos al problema que abrió el tema. Un recorrido euleriano es aquel que usa cada arista exactamente una vez; si además es cerrado, se llama circuito euleriano y el grafo que lo admite es un grafo euleriano. Euler resolvió por completo la cuestión con un criterio de una limpieza admirable, basado únicamente en los grados:

Un grafo conexo posee un circuito euleriano si, y solo si, todos sus vértices tienen grado par. Posee un recorrido euleriano abierto (con extremos distintos) si, y solo si, tiene exactamente dos vértices de grado impar, que serán forzosamente su inicio y su final.

La condición es necesaria por una razón intuitiva: cada vez que el recorrido «entra» a un vértice por una arista debe «salir» por otra distinta, de modo que las aristas de cada vértice interior se emparejan y su grado ha de ser par; solo el inicio y el final pueden quedar descompensados. Que la condición sea también suficiente —que siempre que se cumpla exista de verdad el recorrido— es el corazón del teorema. Como los cuatro vértices de Königsberg tienen grado impar, no hay ni circuito ni recorrido euleriano: queda demostrada la imposibilidad del paseo. Este resultado tiene una prolongación práctica moderna en el problema del cartero chino, planteado por el matemático Mei-Ko Kwan en 1962: hallar la ruta cerrada más corta que recorra todas las calles de un barrio (todas las aristas) al menos una vez, con aplicaciones directas a la recogida de residuos, el reparto postal o la inspección de redes —un vínculo natural con la eficiencia logística y el ODS 11 sobre ciudades sostenibles—.

5.4. Grafos hamiltonianos: un problema engañosamente parecido

Cambiemos ahora una sola palabra en la pregunta: en lugar de recorrer cada arista una vez, busquemos recorrer cada vértice una vez. Un ciclo hamiltoniano es un ciclo que pasa por todos los vértices del grafo exactamente una vez, y un grafo que lo posee es hamiltoniano. El nombre honra al físico y matemático irlandés William Rowan Hamilton, que en 1857 comercializó el juego icosiano, un pasatiempo consistente en hallar un recorrido cerrado por los vértices de un dodecaedro.

El parecido con el problema de Euler es solo aparente, y en el contraste se esconde una de las lecciones más profundas de toda la matemática moderna. Mientras que el criterio de Euler es local y sencillo —basta mirar los grados, un cálculo inmediato—, para los grafos hamiltonianos no se conoce ninguna caracterización simple: decidir si un grafo cualquiera tiene un ciclo hamiltoniano es un problema NP-completo, uno de los problemas «difíciles» por excelencia de la teoría de la complejidad, para el que no se conoce ningún algoritmo eficiente. Solo disponemos de condiciones suficientes, como el teorema de Dirac —si todo vértice de un grafo de n\ge 3 vértices tiene grado al menos n/2, el grafo es hamiltoniano— o el más general teorema de Ore. Que dos preguntas tan gemelas —una sobre aristas, otra sobre vértices— tengan dificultades tan dispares es una idea que sigue inspirando la investigación; matemáticas actuales como Daniela Kühn, reconocida por sus avances sobre ciclos hamiltonianos en grafos densos, trabajan hoy en esa frontera. La versión con pesos del problema hamiltoniano es el célebre problema del viajante de comercio (Travelling Salesman Problem, TSP): hallar la ruta más corta que visite n ciudades y regrese al origen. El TSP es el paradigma de la optimización combinatoria difícil y aparece, disfrazado, en logística, fabricación de circuitos y secuenciación de ADN.

Figura 5. Dos preguntas gemelas: el recorrido euleriano usa cada arista una vez (criterio de grados); el ciclo hamiltoniano visita cada vértice una vez (problema difícil).

6. Grafos planos, coloración y el teorema de los cuatro colores

6.1. Planaridad y la fórmula de Euler

Un grafo es plano si puede dibujarse en el plano de modo que sus aristas no se corten salvo en los vértices. Conviene subrayar, una vez más, que la planaridad es una propiedad de la estructura y no de un dibujo concreto: un grafo es plano si existe algún dibujo sin cruces, aunque el que tengamos delante los tenga. Un dibujo plano divide el plano en regiones llamadas caras, incluida la cara exterior o infinita que rodea a todo el grafo. Entre el número de vértices, aristas y caras se cumple una de las relaciones más bellas de la matemática, la fórmula de Euler para grafos planos conexos:

donde V es el número de vértices, A el de aristas y C el de caras. Es la misma fórmula que Euler descubrió hacia 1750 para los poliedros —el cubo tiene 8 vértices, 12 aristas y 6 caras, y en efecto 8-12+6=2—, y no es casualidad: la superficie de todo poliedro convexo, «aplastada» sobre el plano, produce un grafo plano. La fórmula se demuestra con elegancia por inducción sobre el número de aristas, y es un invariante topológico: vale para cualquier dibujo plano del grafo, tenga la forma que tenga.

Figura 6. Comprobación de la fórmula de Euler en un grafo plano con cuatro vértices, cinco aristas y tres caras.

6.2. Grafos que no son planos: Kuratowski

De la fórmula de Euler se deduce una cota sencilla y potente: en todo grafo plano simple con al menos tres vértices se cumple A\le 3V-6, porque cada cara está bordeada por al menos tres aristas y cada arista limita a lo sumo dos caras. Esta desigualdad basta para demostrar que ciertos grafos no pueden ser planos. El grafo completo K_5 tiene V=5 y A=10, pero 3V-6=9<10: es imposible dibujarlo sin cruces. Y el bipartito completo K_{3,3} —el famoso problema de las «tres casas y tres pozos», que pide conectar cada una de tres casas con tres suministros sin que las tuberías se crucen— tiene V=6 y A=9; como es bipartito no tiene triángulos, y una cota afinada, A\le 2V-4=8<9, prueba que tampoco es plano.

Lo asombroso es que estos dos grafos son, en esencia, los únicos obstáculos a la planaridad. El teorema de Kuratowski (1930), debido al matemático polaco Kazimierz Kuratowski, afirma que un grafo es plano si, y solo si, no contiene ninguna subdivisión de K_5 ni de K_{3,3}. Toda no-planaridad, por complicado que sea el grafo, se reduce a llevar escondido uno de esos dos culpables. Es un teorema de una economía sorprendente y un ejemplo perfecto de cómo la matemática encuentra orden y finitud donde cabría esperar un caos ilimitado de casos.

Figura 7. Los grafos K_5 y K_{3,3}: los dos únicos obstáculos a la planaridad según el teorema de Kuratowski.

6.3. Coloración y el teorema de los cuatro colores

Colorear un grafo consiste en asignar un color a cada vértice de modo que dos vértices adyacentes nunca compartan color. El menor número de colores que lo permite es el número cromático \chi(G). El problema, que parece un juego, modeliza un sinfín de situaciones de asignación de recursos escasos: colores son franjas horarias para exámenes que no deben solaparse, frecuencias para antenas que no deben interferir, o registros de un procesador; en todos ellos, «adyacente» significa «en conflicto». Optimizar estas asignaciones —usar el mínimo de recursos— es un problema con enorme repercusión en la eficiencia energética y organizativa, y conecta con varios Objetivos de Desarrollo Sostenible relativos al uso responsable de los recursos.

La joya de esta teoría nació de una pregunta inocente que se hizo en 1852 el joven Francis Guthrie al colorear el mapa de los condados de Inglaterra: ¿bastan siempre cuatro colores para pintar cualquier mapa de modo que dos regiones fronterizas tengan colores distintos? Traducido a grafos —cada región es un vértice, y dos vértices se unen si las regiones son vecinas—, todo mapa produce un grafo plano, y la conjetura afirma que todo grafo plano es 4-coloreable. Fácil de enunciar, resultó endiabladamente difícil de probar: resistió más de un siglo, hasta que en 1976 Kenneth Appel y Wolfgang Haken lo demostraron con la ayuda de un ordenador que verificó, una por una, casi dos mil configuraciones irreducibles. Fue el primer gran teorema demostrado con asistencia computacional, y abrió un debate filosófico que aún colea: ¿es legítima una demostración que ningún ser humano puede revisar íntegramente a mano? El resultado más modesto de que cinco colores siempre bastan sí tiene una prueba elegante y accesible, y es la que suele presentarse con fines formativos.

El cálculo exacto del número cromático es, en general, un problema difícil, pero existen casos luminosos. Un grafo es 2-coloreable si, y solo si, es bipartito, lo que a su vez equivale —por el teorema de König— a que no contenga ningún ciclo de longitud impar; entonces basta ir alternando dos colores como en un tablero de ajedrez. Los grafos completos exigen el máximo, \chi(K_n)=n, y un ciclo necesita dos o tres colores según su longitud sea par o impar. En la práctica se emplean algoritmos voraces que colorean los vértices uno a uno con el primer color disponible: no siempre alcanzan el mínimo, pero son rápidos y suficientes en numerosas aplicaciones de horarios y de asignación de frecuencias. Este contraste entre problemas fáciles —decidir si un grafo es bipartito— y difíciles —hallar el número cromático general— vuelve a poner de relieve la idea de complejidad que recorre todo el tema.

7. Árboles: caracterización y propiedades

Entre todos los grafos, una familia sobresale por su importancia teórica y por su omnipresencia en las aplicaciones: los árboles. Son los grafos más simples que mantienen todo conectado, y esa combinación de conexión y economía los convierte en la estructura estrella de la informática y del propio título de este tema.

7.1. Definición y caracterizaciones equivalentes

Un árbol es un grafo conexo y sin ciclos (acíclico). Un grafo acíclico no necesariamente conexo —una colección de árboles— se llama bosque. Los vértices de grado 1 de un árbol son sus hojas, y los de grado mayor, sus nodos internos. La fuerza del concepto reside en que admite muchas definiciones equivalentes, cada una de las cuales ilumina una faceta distinta. Para un grafo G con n vértices, las siguientes afirmaciones dicen lo mismo:

• G es un árbol (conexo y acíclico).
• G es conexo y tiene exactamente n-1 aristas.
• G es acíclico y tiene exactamente n-1 aristas.
• Entre cada par de vértices existe un único camino simple.
• G es conexo y toda arista es un puente (al quitar cualquiera, se desconecta).
• G es acíclico, pero al añadir cualquier arista nueva se forma exactamente un ciclo.

Que seis propiedades tan distintas —sobre conexión, sobre número de aristas, sobre unicidad de caminos, sobre fragilidad— resulten equivalentes es uno de los teoremas más satisfactorios de la teoría de grafos y un ejercicio ideal de razonamiento matemático: demostrar un «bucle de implicaciones» que las encadena todas. La propiedad del camino único es quizá la más intuitiva y la que explica por qué los árboles modelizan tan bien las jerarquías: en un organigrama, un árbol genealógico o un sistema de carpetas, hay una y solo una ruta de un punto a otro.

7.2. Propiedades fundamentales

De estas caracterizaciones se desprenden hechos que conviene tener presentes. Todo árbol con n vértices tiene exactamente n-1 aristas: es el número justo para conectar n puntos sin gastar ni una arista de más. Se demuestra por inducción o mediante un argumento de «poda» sucesiva de hojas. Además, todo árbol con al menos dos vértices posee al menos dos hojas, lo que se sigue del lema del apretón de manos. Los árboles son, en un sentido preciso, los grafos conexos con el menor número posible de aristas (quitar cualquiera los desconecta) y, a la vez, los acíclicos con el mayor número posible (añadir cualquiera crea un ciclo): viven exactamente en la delicada frontera entre la conexión y la aciclicidad.

7.3. Árboles con raíz

Muchas aplicaciones distinguen un vértice especial llamado raíz, obteniendo un árbol con raíz (o enraizado) que impone una jerarquía: la raíz ocupa el nivel 0, sus vecinos son sus hijos (nivel 1), y así sucesivamente, de modo que cada vértice salvo la raíz tiene un único padre. Aparecen entonces las nociones de profundidad de un nodo, altura del árbol y descendientes. Cuando cada nodo tiene a lo sumo dos hijos, se habla de árbol binario, la estructura de datos más influyente de la computación, base de los árboles de búsqueda, de los montículos y de innumerables algoritmos eficientes.

La historia de los árboles está trenzada con la ciencia y muestra su fecundidad interdisciplinar. El físico Gustav Kirchhoff los introdujo en 1847 al analizar redes eléctricas —sus célebres leyes de los circuitos—, y el matemático Arthur Cayley los estudió en 1857 y los aplicó en química para contar los isómeros de los hidrocarburos saturados. A Cayley se debe una fórmula de una belleza sorprendente: existen exactamente n^{n-2} árboles distintos que conectan n vértices etiquetados, de modo que sobre 4 vértices hay 4^{2}=16 árboles posibles. Los árboles nacieron, pues, resolviendo problemas reales de física y de química, un ejemplo temprano del poder modelizador que hoy sigue vivo.

La conexión de Kirchhoff con los árboles llega aún más lejos: su teorema de la matriz-árbol permite contar cuántos árboles generadores tiene un grafo cualquiera mediante el cálculo de un determinante, generalizando la fórmula de Cayley a grafos arbitrarios. Y en el terreno aplicado, el árbol binario de búsqueda organiza los datos de modo que localizar, insertar o borrar un elemento cueste un número de pasos proporcional a la altura del árbol —del orden del logaritmo del número de datos cuando está equilibrado—, lo que explica por qué las estructuras arborescentes son omnipresentes en bases de datos, sistemas de ficheros e índices. El humilde árbol matemático es, así, el caballo de batalla silencioso de la informática cotidiana.

Figura 8. Un árbol de siete vértices y seis aristas, con sus cuatro hojas, y las caracterizaciones equivalentes.

8. Árboles generadores y árbol generador mínimo: Kruskal y Prim

8.1. Árboles generadores

Dado un grafo conexo G, un árbol generador (o recubridor, spanning tree) es un subgrafo que contiene todos los vértices de G y es un árbol. En otras palabras, es un esqueleto mínimo que mantiene el grafo conectado usando solo n-1 de sus aristas y prescindiendo del resto. Todo grafo conexo posee al menos un árbol generador —de hecho, suele tener muchísimos: el completo K_n tiene los n^{n-2} de la fórmula de Cayley—, y obtener uno es tan sencillo como ir retirando aristas de ciclos hasta que no quede ninguno, o recorrer el grafo desde un vértice registrando por dónde se llega a cada nuevo nodo.

8.2. El árbol generador mínimo

El problema adquiere todo su interés cuando el grafo está ponderado. El árbol generador mínimo (AGM, o minimum spanning tree) de un grafo con pesos es el árbol generador cuyo peso total —la suma de los pesos de sus aristas— es el menor posible. La pregunta que resuelve es de una importancia práctica difícil de exagerar: ¿cuál es la forma más barata de conectar todos los puntos de una red? Tender el cableado eléctrico que llegue a todos los pueblos de una comarca, la fibra óptica que enlace todos los edificios de un campus, la red de tuberías que abastezca todos los barrios, gastando la menor cantidad posible de cable, de zanja o de coste: todos son, exactamente, el problema del AGM. No es casual que el primer algoritmo conocido para resolverlo lo publicara el matemático checo Otakar Boruvka en 1926, precisamente para planificar la electrificación de la región de Moravia con el mínimo de tendido —un problema que hoy leeríamos en clave de eficiencia de recursos y de acceso universal a la energía, en la línea del ODS 7 y del ODS 9—.

8.3. Dos algoritmos voraces: Kruskal y Prim

El AGM se calcula con algoritmos voraces (greedy), que construyen la solución tomando en cada paso la mejor opción local disponible; lo notable es que aquí esa estrategia miope conduce, demostrablemente, al óptimo global. Los dos clásicos son:

• El algoritmo de Kruskal (1956) ordena todas las aristas de menor a mayor peso y las va incorporando una a una, descartando cualquiera que formaría un ciclo con las ya elegidas, hasta reunir n-1 aristas. Va, por así decirlo, construyendo un bosque que fusiona sus árboles hasta convertirlos en uno solo.
• El algoritmo de Prim (1957, anticipado por Vojtech Jarník en 1930) parte de un vértice y hace crecer un único árbol, añadiendo en cada paso la arista más barata que conecte el árbol ya formado con un vértice todavía fuera de él.

Ambos son correctos gracias a la llamada propiedad de corte: la arista de menor peso que cruza cualquier partición de los vértices en dos grupos pertenece siempre a algún AGM. Y ambos son eficientes, con un coste que crece de forma casi lineal con el tamaño del grafo, lo que los hace aplicables a redes enormes. La contraposición con el problema del viajante es aleccionadora: hallar el árbol más barato que conecta n puntos es fácil, pero hallar el circuito más barato que los recorre todos es endiabladamente difícil; una diferencia de matiz en el enunciado marca un abismo de complejidad.

El árbol generador mínimo tiene, además, aplicaciones que van más allá de tender redes. Eliminar sus aristas más largas es una técnica clásica de agrupamiento (clustering): los fragmentos que quedan reúnen los puntos más próximos entre sí, algo muy usado en análisis de datos y en reconocimiento de patrones. Y si se admite añadir puntos intermedios auxiliares para acortar todavía más la red total, se llega al problema del árbol de Steiner, más difícil que el AGM pero de gran interés en el diseño de circuitos integrados y de redes de transporte. Una vez más, la frontera entre lo fácil y lo difícil se cruza con solo un pequeño cambio en las reglas del juego.

Figura 9. El algoritmo de Kruskal sobre un grafo ponderado: se eligen aristas de menor a mayor peso evitando ciclos, hasta obtener el árbol generador mínimo.

9. Diagramas en árbol: combinatoria, probabilidad y árboles con raíz

Llegamos al segundo concepto que da título al tema. Un diagrama en árbol es, sencillamente, un árbol con raíz empleado para organizar y enumerar de forma sistemática todas las posibilidades de un proceso que se desarrolla por etapas. Es, con diferencia, la aplicación de la teoría de grafos que más presencia tiene en las aulas de Secundaria, porque es la herramienta natural para el recuento y para la probabilidad, y como tal figura de manera explícita en el sentido estocástico del currículo LOMLOE desde los primeros cursos de la ESO.

9.1. Diagramas en árbol para contar

Cuando una tarea se compone de varias etapas sucesivas, cada una con un número de opciones, un diagrama en árbol despliega todas las combinaciones: se parte de una raíz, de ella salen tantas ramas como opciones tenga la primera etapa, de cada una de esas ramas salen las de la segunda, y así hasta el final; cada hoja representa un resultado posible y cada camino de la raíz a una hoja, la secuencia de decisiones que lo produce. El número de hojas es el producto de las opciones de cada etapa, lo que hace del diagrama la representación visual del principio de multiplicación de la combinatoria. Con él se enumeran y cuentan variaciones, permutaciones y combinaciones sin necesidad de memorizar fórmulas: basta construir el árbol y leer sus hojas. Por ejemplo, para formar los números de dos cifras distintas con los dígitos 1, 2 y 3, el árbol tiene 3 ramas iniciales y 2 desde cada una, es decir 3\cdot 2=6 hojas: 12, 13, 21, 23, 31 y 32.

El mismo instrumento distingue con nitidez los modelos combinatorios según se permita o no repetir y según importe o no el orden. Para las banderas de tres franjas que pueden formarse con cuatro colores disponibles sin repetir color, el árbol tiene 4 ramas iniciales, 3 en el segundo nivel y 2 en el tercero: 4\cdot 3\cdot 2=24 hojas, que son las variaciones de cuatro elementos tomados de tres en tres. Si se permitiera repetir color, cada nivel tendría 4 ramas y saldrían 4^3=64 hojas. Colocar ambos árboles uno junto al otro hace tangible, sin necesidad de fórmulas, la diferencia entre variaciones con y sin repetición, y deja ver por qué el factorial aparece cuando se ordenan todos los elementos.

9.2. Diagramas en árbol para la probabilidad

Su potencia se multiplica en el cálculo de probabilidades de experimentos compuestos. Si cada rama se etiqueta con la probabilidad de la opción correspondiente, dos reglas sencillas resuelven casi cualquier problema. La regla del producto: la probabilidad de un camino completo (de la raíz a una hoja) es el producto de las probabilidades de sus ramas, pues expresa la ocurrencia sucesiva de los sucesos, ya con la probabilidad condicionada incorporada de forma natural en las etapas posteriores. Y la regla de la suma: la probabilidad de un suceso que se realiza por varios caminos distintos es la suma de las probabilidades de esos caminos. En estas dos reglas están, en germen, la probabilidad condicionada, el teorema de la probabilidad total y el teorema de Bayes, que en Bachillerato se formalizan y que el diagrama en árbol permite comprender de manera intuitiva mucho antes.

Consideremos una urna con 3 bolas rojas y 2 azules de la que se extraen dos bolas sin reemplazo. El diagrama en árbol de la figura despliega las dos etapas: en la segunda, las probabilidades cambian porque queda una bola menos. Multiplicando a lo largo de cada camino se obtienen las probabilidades de los cuatro resultados, cuya suma es 1, como debe ser. La probabilidad de sacar exactamente una bola roja, por ejemplo, es la suma de los dos caminos «roja-azul» y «azul-roja»: \dfrac{3}{5}\cdot\dfrac{2}{4}+\dfrac{2}{5}\cdot\dfrac{3}{4}=\dfrac{6}{20}+\dfrac{6}{20}=\dfrac{6}{10}=\dfrac{3}{5}.

Figura 10. Diagrama en árbol de un experimento en dos etapas: la probabilidad de cada rama se multiplica; la de un suceso, se suma sobre sus caminos.

La lectura del árbol también puede hacerse hacia atrás, y en ello reside una de las ideas más finas de la probabilidad. Preguntarse, sabiendo que la segunda bola extraída fue azul, cuál es la probabilidad de que la primera hubiera sido roja invierte el sentido natural del diagrama y conduce, precisamente, al teorema de Bayes: se divide la probabilidad del camino favorable entre la suma de las probabilidades de todos los caminos compatibles con lo observado. Este razonamiento, que en Bachillerato se formaliza y que sustenta desde los diagnósticos médicos hasta los filtros de correo no deseado, resulta mucho más comprensible cuando el alumnado lo ha visto antes como un simple recorrido de ramas en sentido inverso.

9.3. Árboles con raíz por todas partes

El diagrama en árbol es solo la cara más escolar de una idea universal. Los árboles de decisión guían diagnósticos y clasificaciones y son hoy un pilar del aprendizaje automático; los árboles de juego modelizan las jugadas del ajedrez o del tres en raya y sustentan el algoritmo minimax de la inteligencia artificial; los árboles sintácticos describen la estructura de una frase o de un programa; y los árboles de codificación de Huffman comprimen datos asignando códigos más cortos a los símbolos más frecuentes. En todos ellos late la misma estructura de árbol con raíz que el alumnado conoce con las bolas de una urna, un ejemplo perfecto de cómo un concepto elemental bien comprendido abre la puerta a las ideas más avanzadas.

10. Algoritmos y aplicaciones de la teoría de grafos

Si la teoría de grafos ha pasado de pasatiempo decimonónico a herramienta imprescindible del siglo XXI, es por sus algoritmos: procedimientos sistemáticos que responden preguntas sobre grafos gigantescos en fracciones de segundo. Presentarlos en el aula es, además, la ocasión perfecta para desarrollar el pensamiento computacional que el currículo LOMLOE incorpora al sentido algebraico.

10.1. Recorrer un grafo: anchura y profundidad

Explorar un grafo de forma ordenada es la base de casi todo lo demás. La búsqueda en anchura (BFS) parte de un vértice y visita primero todos sus vecinos, luego los vecinos de estos, y así en «ondas» concéntricas; como consecuencia, encuentra los caminos más cortos en grafos sin pesos y calcula distancias. La búsqueda en profundidad (DFS) avanza por una rama hasta agotarla y retrocede después; es idónea para detectar ciclos, hallar las componentes conexas o producir una ordenación topológica de las tareas de un proyecto con dependencias. Ambas recorren el grafo en un tiempo proporcional a su tamaño y son el primer algoritmo que conviene que el alumnado programe —en Scratch, en Python— para tocar con las manos la conexión entre grafo y código.

Esa ordenación topológica tiene una aplicación estelar en la gestión de proyectos. Cuando las tareas de un proyecto se representan como un grafo dirigido acíclico —cada arco indica que una tarea debe terminar antes de que otra pueda empezar—, las técnicas PERT y CPM, nacidas en los años cincuenta, calculan la duración mínima del proyecto y detectan el camino crítico: la cadena de tareas cuyo retraso arrastra sin remedio al conjunto. No es más que un problema de caminos de longitud máxima sobre el grafo de precedencias, y hoy lo incorpora cualquier programa de planificación. Es un ejemplo espléndido de cómo un concepto abstracto —el orden topológico de un dígrafo acíclico— se convierte en una herramienta de uso diario en ingeniería, arquitectura o cualquier organización que planifique tareas encadenadas.

10.2. El camino más corto: Dijkstra

Cuando las aristas tienen pesos —distancias, tiempos, costes—, la pregunta estrella es hallar la ruta más corta entre dos puntos. La respuesta canónica es el algoritmo de Dijkstra, publicado por el neerlandés Edsger Dijkstra en 1959, que calcula la distancia mínima desde un vértice origen a todos los demás avanzando siempre hacia el vértice pendiente más cercano y actualizando las distancias de sus vecinos. Es, literalmente, el algoritmo que gobierna cada navegador GPS y cada aplicación de mapas cuando calcula el trayecto más rápido, así como el enrutamiento de los paquetes de datos por internet. Su pariente, el algoritmo de Bellman-Ford, admite pesos negativos, y la variante A* acelera la búsqueda con una estimación heurística. Optimizar rutas no es un lujo: rutas más cortas significan menos combustible, menos tiempo y menos emisiones, un vínculo directo con la movilidad sostenible del ODS 11 y la acción por el clima del ODS 13.

Figura 11. El algoritmo de Dijkstra halla la ruta de coste mínimo entre dos vértices; junto a cada nodo, su distancia definitiva al origen.

10.3. Un panorama de aplicaciones

La lista de campos que hoy hablan el lenguaje de los grafos es abrumadora, y merece la pena recorrerla porque es lo que convence al alumnado —y al tribunal— de que este tema es todo menos abstracto:

• Internet y la Web. La red es un dígrafo colosal de páginas y enlaces; el algoritmo PageRank, con el que Google revolucionó las búsquedas, no es más que un cálculo sobre ese grafo que mide la importancia de cada página por los enlaces que recibe. El propio encaminamiento de los datos se resuelve con caminos mínimos.
• Redes sociales. Personas y relaciones forman un grafo cuyo análisis revela comunidades, líderes de opinión y vías de difusión; el famoso fenómeno de los «seis grados de separación» afirma que su diámetro social es sorprendentemente pequeño. El estudio moderno de estas redes complejas debe una de sus piezas clave a la física Réka Albert, coautora del modelo de redes «libres de escala» de Barabási-Albert que explica por qué en tantas redes reales unos pocos nodos concentran la mayoría de las conexiones.
• Logística y transporte. Rutas de reparto (el viajante y el cartero chino), horarios, redes de metro y de ferrocarril: optimizarlas ahorra costes y reduce la huella ambiental, en sintonía con los ODS 9, 11, 12 y 13.
• Ciencia e ingeniería. Las moléculas son grafos de átomos y enlaces; la evolución se representa con árboles filogenéticos; las redes eléctricas inteligentes, las de distribución de agua y las de telecomunicaciones se diseñan y se hacen robustas con teoría de grafos, contribuyendo al acceso universal a la energía y a los servicios (ODS 6 y 7).

Detrás de cada uno de estos algoritmos hay una máquina que los ejecuta, y conviene recordar que los cimientos de esa computación los pusieron, entre otros, Ada Lovelace, autora del primer algoritmo concebido para una máquina, y Grace Hopper, pionera de los compiladores: la cadena que va del grafo dibujado en una pizarra al servicio que usamos en el móvil pasa por el talento de muchas mujeres cuyo reconocimiento fue tardío.

11. Aplicación didáctica y relación con el currículo

Los contenidos de este tema, pese a su apariencia especializada, están más presentes en las aulas de Secundaria de lo que parece, y ofrecen un potencial didáctico extraordinario. El marco normativo vigente en la Comunitat Valenciana lo establecen la Ley Orgánica 2/2006 (LOE), modificada por la Ley Orgánica 3/2020 (LOMLOE); el Real Decreto 217/2022, de 29 de marzo, de enseñanzas mínimas de la ESO; el Real Decreto 243/2022, de 5 de abril, para el Bachillerato; y los Decretos 107/2022 y 108/2022, de 5 de agosto, del Consell, que fijan los respectivos currículos autonómicos. Aunque los cuatro ejes —currículo, dimensión didáctica, sostenibilidad e inclusión— se han ido tejiendo a lo largo del desarrollo, conviene consolidarlos aquí.

En la organización del currículo LOMLOE en seis sentidos, este tema tiene su anclaje más firme en el sentido estocástico, que incluye de manera explícita los diagramas de árbol como técnica de recuento sistemático en 1.º y 2.º de ESO y como herramienta para el cálculo de probabilidades de experimentos compuestos en 3.º y 4.º de ESO, prolongándose en el Bachillerato —sobre todo en Matemáticas Aplicadas a las Ciencias Sociales— con la probabilidad condicionada y el teorema de Bayes. Un segundo anclaje está en el sentido algebraico, que acoge el pensamiento computacional: los grafos y sus algoritmos (recorridos, camino mínimo, árbol generador) son un contexto idóneo para introducir la algoritmia y la programación. El tema irriga además el sentido de las conexiones —con el álgebra de matrices, con la geometría de los poliedros, con la geografía— y el sentido socioafectivo, como enseguida veremos con el sociograma.

El enfoque competencial se concreta en las competencias específicas de la materia. La modelización es la competencia reina de este tema: traducir una situación real (un mapa, una red, un torneo) a un grafo es el gesto matemático fundamental. La de razonamiento y prueba encuentra ejemplos accesibles y elegantes —el corolario del apretón de manos, las caracterizaciones equivalentes del árbol, la imposibilidad de Königsberg—. El pensamiento computacional se ejercita programando los algoritmos. Y la de conexiones brilla al enlazar grafos con matrices, con probabilidad o con la tecnología.

La experiencia docente ha identificado errores y preconcepciones frecuentes cuyo conocimiento permite intervenir mejor. El más profundo es confundir el grafo con su dibujo: creer que dos representaciones distintas del mismo grafo son grafos distintos, o que los cruces de un dibujo forman parte de la estructura. En los diagramas en árbol abundan otros: no ser sistemático y olvidar ramas al construirlos; sumar cuando hay que multiplicar (o al revés) las probabilidades; y confundir la extracción con y sin reemplazo, que altera las probabilidades de la segunda etapa. En combinatoria, la confusión clásica entre variaciones y combinaciones (¿importa el orden?) se disuelve, precisamente, dibujando el árbol. Anticipar estos tropiezos es media clase ganada.

Metodológicamente, el tema se presta como pocos a las metodologías activas. El aprendizaje basado en problemas y proyectos es su cauce natural: una situación de aprendizaje eficaz para 3.º-4.º de ESO es «La red de fibra del pueblo», en la que el alumnado modeliza las calles como un grafo ponderado y aplica el algoritmo de Kruskal para diseñar el tendido de coste mínimo, discutiendo de paso el uso responsable de los recursos (ODS 9 y 12). Otras propuestas de gran rendimiento son «¿Se puede dibujar sin levantar el lápiz?», que descubre los grafos eulerianos jugando, o la coloración de mapas reales, que conecta con Geografía y con el teorema de los cuatro colores. La gamificación (el juego de Sim, los laberintos como grafos, los puzles de trazado) y los recursos digitales (GeoGebra, applets, programación en Scratch o Python) refuerzan la motivación y la competencia digital. El Diseño Universal para el Aprendizaje (DUA) aconseja presentar cada idea por varias vías —manipulativa con cuerdas y chinchetas, gráfica, simbólica y digital— y ofrecer distintos niveles de reto.

Merece mención aparte una aplicación de hondo calado educativo: el sociograma. Ideado por Jacob Moreno y Helen Hall Jennings en los años treinta, es un grafo que representa las relaciones de afinidad y rechazo dentro de un grupo, y constituye una herramienta valiosísima de tutoría y convivencia para detectar liderazgos, subgrupos y, sobre todo, alumnado en riesgo de aislamiento o acoso. Que la misma estructura matemática del tema sirva para cuidar el clima del aula es una oportunidad de oro para trabajar el sentido socioafectivo y la educación en valores. En cuanto a la inclusión y la perspectiva de género, además de un lenguaje inclusivo y de la atención a la diversidad del DUA, el tema ofrece referentes femeninos que conviene traer con naturalidad donde corresponde —Ada Lovelace y Grace Hopper en los cimientos de la computación, Fan Chung en la teoría espectral, Réka Albert en las redes complejas, Daniela Kühn en los ciclos hamiltonianos, Mei-Ko Kwan en el problema del cartero—, para que ninguna alumna sienta que estas matemáticas no son «para ella», en coherencia con el ODS 4, el ODS 5 y el principio de inclusión de la LOMLOE.

La evaluación, coherente con el enfoque competencial, debe combinar instrumentos variados —la observación del trabajo por proyectos, portafolios donde se documente la modelización, la resolución de problemas contextualizados y rúbricas que valoren el razonamiento y la comunicación, no solo el resultado—. Y la interdisciplinariedad es natural y rica: con Tecnología y Digitalización (algoritmos, redes), con Geografía e Historia (mapas, redes de transporte, Königsberg), con Biología (filogenia, redes tróficas), con Educación Física (los emparejamientos de un torneo son un grafo) e incluso con Lengua (los árboles sintácticos). Este carácter transversal convierte el tema en un excelente eje para un proyecto interdisciplinar de centro.

12. Conclusión

Recorrer la teoría de grafos es asistir al nacimiento y la madurez de una idea matemática en tiempo récord. Partimos de un pasatiempo sobre siete puentes y del gesto genial de Euler —quedarse solo con los puntos y las líneas— y, en poco más de dos siglos, esa abstracción se ha convertido en el lenguaje con que se describen internet, las redes sociales, la logística mundial y la propia vida molecular. Por el camino hemos fijado los fundamentos —qué es un grafo, cómo se clasifica, se representa y se mide con el grado y el apretón de manos—; hemos revivido los grandes problemas clásicos —los recorridos de Euler y de Hamilton, la planaridad, los cuatro colores—; hemos estudiado con detalle los árboles, esa frontera exacta entre la conexión y la aciclicidad, con sus árboles generadores mínimos de Kruskal y Prim; y hemos desplegado los diagramas en árbol que enlazan el tema con la combinatoria y la probabilidad del aula.

El valor formativo de este tema no reside solo en su contenido, sino en las ideas transversales que lo atraviesan y que el docente debe hacer visibles: la potencia de la modelización, que resuelve un problema con solo saber mirarlo como un grafo; la distinción entre la estructura y sus representaciones; el revelador contraste entre lo fácil y lo difícil —el criterio de Euler frente a la dureza de Hamilton, el árbol mínimo frente al viajante—, que es una primera ventana a la teoría de la complejidad; y la unidad profunda que enlaza un juego decimonónico con la tecnología que llevamos en el bolsillo. Dominar este tema con rigor y saber transponerlo al aula con sensibilidad hacia la diversidad, la equidad y la sostenibilidad permite al futuro profesor o profesora presentar, ante el tribunal y después ante el alumnado, no una colección de definiciones áridas, sino un relato vivo sobre cómo unos simples puntos y líneas se convirtieron en una de las herramientas más poderosas para comprender y mejorar el mundo.

13. Bibliografía y referencias

(a) Referencias científicas y matemáticas

• Euler, L. (1736). «Solutio problematis ad geometriam situs pertinentis». Commentarii Academiae Scientiarum Petropolitanae, 8.
• Biggs, N., Lloyd, E. y Wilson, R. (1976). Graph Theory, 1736-1936. Clarendon Press.
• Bondy, J. A. y Murty, U. S. R. (2008). Graph Theory. Springer.
• Diestel, R. (2017). Graph Theory (5.ª ed.). Springer.
• Wilson, R. J. (1996). Introduction to Graph Theory (4.ª ed.). Longman.
• Harary, F. (1969). Graph Theory. Addison-Wesley.
• Trudeau, R. J. (1993). Introduction to Graph Theory. Dover.
• Grimaldi, R. P. (1997). Matemática discreta y combinatoria. Addison-Wesley Iberoamericana.
• Newman, M. E. J. (2018). Networks (2.ª ed.). Oxford University Press.
• Barabási, A.-L. (2016). Network Science. Cambridge University Press.
• Berge, C. (1958). Théorie des graphes et ses applications. Dunod.
• García Merayo, F. (2005). Matemática discreta. Thomson-Paraninfo.
• Gardner, M. (1985). Circo matemático. Alianza Editorial.

(b) Referencias normativas

• Ley Orgánica 2/2006, de 3 de mayo, de Educación (LOE), modificada por la Ley Orgánica 3/2020, de 29 de diciembre (LOMLOE). BOE núm. 340, de 30 de diciembre de 2020.
• Real Decreto 217/2022, de 29 de marzo, por el que se establece la ordenación y las enseñanzas mínimas de la Educación Secundaria Obligatoria. BOE núm. 76, de 30 de marzo de 2022.
• Real Decreto 243/2022, de 5 de abril, por el que se establecen la ordenación y las enseñanzas mínimas del Bachillerato. BOE núm. 82, de 6 de abril de 2022.
• Decreto 107/2022, de 5 de agosto, del Consell, de ordenación y currículo de la Educación Secundaria Obligatoria en la Comunitat Valenciana. DOGV núm. 9403, de 11 de agosto de 2022.
• Decreto 108/2022, de 5 de agosto, del Consell, de ordenación y currículo del Bachillerato en la Comunitat Valenciana. DOGV núm. 9403, de 11 de agosto de 2022.
• Recomendación del Consejo de la Unión Europea, de 22 de mayo de 2018, relativa a las competencias clave para el aprendizaje permanente. DOUE C 189, de 4 de junio de 2018.
• Naciones Unidas (2015). Transformar nuestro mundo: la Agenda 2030 para el Desarrollo Sostenible (Objetivos de Desarrollo Sostenible). Resolución A/RES/70/1.

Orientaciones para el estudio

• Abra el tema con Königsberg y el teorema de Euler: sepa enunciar con precisión la condición (circuito euleriano si y solo si todos los grados son pares; recorrido abierto con exactamente dos vértices de grado impar) y explicar por qué es necesaria. Es el enganche histórico obligado y el hilo que da unidad al tema.
• Tenga muy preparado el contraste Euler frente a Hamilton: mismo aire, dificultad opuesta (aristas con criterio simple, vértices con problema NP-completo). Bien expuesto, demuestra una comprensión que trasciende el manual y conecta con la teoría de la complejidad.
• Domine el lema del apretón de manos y su corolario (el número de vértices de grado impar es par), con la demostración por doble conteo lista para exponer: es corta, elegante y muy valorada.
• Sepa la fórmula de Euler V-A+C=2, la cota A\le 3V-6 y su uso para probar que K_5 y K_{3,3} no son planos; remátelo con Kuratowski y con el teorema de los cuatro colores (Appel y Haken, 1976, primera demostración asistida por ordenador).
• Memorice las caracterizaciones equivalentes del árbol y la propiedad de las n-1 aristas; tenga a punto una demostración breve (por poda de hojas o por inducción). Es el concepto central del título del tema.
• Prepare el árbol generador mínimo con un ejemplo pequeño resuelto por Kruskal paso a paso, mencionando Prim, el carácter voraz y la propiedad de corte, y el dato histórico de Boruvka (1926, electrificación de Moravia) como ejemplo de aplicación y de sostenibilidad.
• Cuide especialmente los diagramas en árbol: son el contenido con presencia curricular más directa (sentido estocástico). Lleve un ejemplo de probabilidad con y sin reemplazo resuelto, con las reglas del producto y de la suma, y señale su continuidad con la probabilidad condicionada y el teorema de Bayes de Bachillerato.
• Sepa para qué sirve cada algoritmo (BFS y DFS para recorrer; Dijkstra para el camino mínimo del GPS) y enlácelos con el pensamiento computacional del currículo.
• Cierre con las aplicaciones (internet y PageRank, redes sociales y sociograma, logística con el viajante y el cartero chino, redes complejas de Barabási y Réka Albert) y con los ODS pertinentes: es un final potente y diferenciador.
• En la parte didáctica, cite con precisión el RD 217/2022 y el Decreto 107/2022, ubique los contenidos en el sentido estocástico y el algebraico, mencione el sociograma para la convivencia (sentido socioafectivo), una situación de aprendizaje concreta (la red de fibra con Kruskal), el DUA, los errores frecuentes (grafo no es dibujo; sumar frente a multiplicar probabilidades) y los referentes femeninos integrados con naturalidad. Ligar el rigor matemático con su transposición al aula es lo que separa una exposición notable de una sobresaliente.