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. El grado de un vértice y el lema del apretón de manos
4. Representación de grafos: matrices y listas
5. Conexión, caminos y ciclos. Grafos eulerianos y hamiltonianos
6. Planaridad, coloración y el teorema de los cuatro colores
7. Árboles: caracterizaciones y propiedades
8. Árboles generadores y árbol generador mínimo
9. Diagramas en árbol: recuento y probabilidad
10. Algoritmos sobre grafos y panorama de aplicaciones
11. Aplicación didáctica y relación con el currículo
12. Conclusión
13. Bibliografía y referencias

1. Introducción

En 1736 Leonhard Euler (1707-1783) envió a la Academia de Ciencias de San Petersburgo una memoria breve, Solutio problematis ad geometriam situs pertinentis, dedicada a un pasatiempo que circulaba entre los vecinos de Königsberg. La ciudad, partida por el río Pregel, tenía dos islas y siete puentes, y la pregunta era si podía darse un paseo que cruzara cada puente exactamente una vez. Euler demostró que no, pero lo decisivo no fue la respuesta sino el método: despojó al problema de toda su geometría —distancias, formas, orillas— y se quedó con lo único que decidía la cuestión, cuatro masas de tierra y las conexiones entre ellas. Ese gesto de abstracción fundó a la vez la teoría de grafos y, en germen, aquella «geometría de la posición» que Leibniz había imaginado medio siglo antes y que acabaría llamándose topología.

Un grafo es un objeto de una sencillez casi provocadora: una colección de vértices y una colección de aristas, cada una de las cuales une dos vértices. Nada más. Sobre esa base mínima se ha levantado una de las teorías más fértiles de la matemática contemporánea, y la razón es que muchísimas situaciones tienen exactamente esa forma —objetos y relaciones entre ellos—: ciudades y carreteras, personas y amistades, páginas web y enlaces, tareas y dependencias, asignaturas y coincidencias de horario. Ver un problema como un grafo es, con frecuencia, haberlo resuelto a medias.

El tema pertenece de lleno a la matemática discreta, la que cuenta con números naturales en lugar de medir en un continuo, y está emparentado de cerca con las técnicas de recuento que se estudian a continuación en el temario. Esa cercanía explica el segundo concepto del título: los diagramas en árbol son la aplicación de la teoría de grafos con mayor presencia real en las aulas de Secundaria, porque son la herramienta natural para enumerar de forma sistemática y para calcular probabilidades de experimentos compuestos. El currículo vigente organiza los saberes de la materia en sentidos —numérico, de la medida, espacial, algebraico, estocástico y socioafectivo— y este tema irriga sobre todo el sentido estocástico, donde los diagramas de árbol aparecen de forma explícita desde los primeros cursos de la etapa, y el sentido algebraico, que acoge el pensamiento computacional.

El desarrollo recorre cuatro miradas entrelazadas: la fundacional, que fija con rigor qué es un grafo, cómo se clasifica y cómo se representa; la de los problemas clásicos que forjaron la disciplina —Euler y Hamilton, la planaridad, los cuatro colores—; la de los árboles, la familia más importante en las aplicaciones, con sus caracterizaciones, sus árboles generadores mínimos y los diagramas del aula; y la algorítmica y aplicada, que explica por qué unos puntos y unas líneas sostienen hoy los navegadores y el estudio de las redes. A lo largo del camino se irá señalando, en cada bloque, con qué saberes conecta, qué errores encuentra el docente y con qué situaciones de aprendizaje se lleva al aula.

Figura 1. El plano de Königsberg reducido a lo esencial: cuatro vértices y siete aristas, dos de ellas paralelas a cada lado de la isla.

2. Concepto de grafo: definiciones y tipología

2.1. Definición formal y vocabulario básico

Un grafo es un par G=(V,E) donde V es un conjunto finito no vacío cuyos elementos son los vértices o nodos, y E es un conjunto de aristas, cada una de ellas determinada por un par de vértices. Si la arista une u y v, se dice que u y v son sus extremos, que son adyacentes y que la arista es incidente con ambos; dos aristas con un extremo común son adyacentes entre sí. El número de vértices |V| es el orden del grafo y el número de aristas |E|, su tamaño. Salvo mención expresa se trabaja con grafos finitos, que son los que interesan a las aplicaciones y al aula.

Bajo esa definición se esconde una decisión conceptual que conviene subrayar desde el principio: 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 se cruzan al trazarlas. La 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, la fuente de la preconcepción más tenaz del alumnado, que atribuye significado a rasgos accidentales del dibujo, empezando por los cruces.

2.2. Variantes: multigrafos, dígrafos y grafos ponderados

Según lo que se permita en E se obtiene una tipología que hay que manejar con precisión. Un grafo simple no admite lazos —aristas que unen un vértice consigo mismo— ni aristas múltiples o paralelas entre el mismo par de vértices; cada arista es entonces un par no ordenado \{u,v\} con u\neq v. Un multigrafo sí admite aristas paralelas, que es lo que exigía Königsberg; si además se permiten lazos se habla de pseudografo. Un grafo dirigido o dígrafo sustituye las aristas por arcos, pares ordenados (u,v): la relación adquiere sentido, de origen a destino, y modeliza calles de dirección única, enlaces web o precedencias entre tareas. Un grafo ponderado añade una función de peso w:E\to\mathbb{R}, casi siempre positiva, que representa una distancia, un coste, un tiempo o una capacidad; prácticamente toda aplicación logística trabaja con grafos ponderados.

2.3. Familias con nombre propio, subgrafos e isomorfismo

Algunas familias reaparecen tanto que tienen nombre propio. El grafo completo K_n une entre sí todos sus n vértices y tiene por tanto

aristas, fórmula que conecta de inmediato con el recuento y que responde a la pregunta clásica de cuántos apretones de manos se dan en un grupo de n personas. El camino P_n y el ciclo C_n son, respectivamente, una sucesión abierta y una cerrada de vértices consecutivos. Un grafo es regular de grado k si todos sus vértices tienen exactamente k vecinos. 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 bipartitos modelizan los emparejamientos —personas y tareas, alumnado y proyectos— y admiten una caracterización muy útil: un grafo es bipartito si y solo si no contiene ciclos de longitud impar.

Un subgrafo de G se obtiene tomando parte de sus vértices y parte de sus aristas; si conserva todos los vértices se llama subgrafo generador o recubridor, noción imprescindible para el apartado 8. Dos grafos son isomorfos cuando existe una biyección entre sus vértices que conserva las adyacencias: son el mismo grafo con otras etiquetas o dibujado de otro modo. Decidir con eficiencia si dos grafos son isomorfos ha resistido durante décadas a la clasificación habitual de la complejidad, señal de que hasta las preguntas más elementales pueden esconder una dificultad formidable. Por último, el grafo complementario \overline{G} une exactamente los pares que en G no eran adyacentes, de manera que ambos se reparten todas las aristas de K_n; muchas propiedades se aclaran al mirarlo, y en el apartado 6 aparecerá un teorema profundo enunciado en esos términos.

3. El grado de un vértice y el lema del apretón de manos

El grado de un vértice v, que escribiremos \operatorname{gr}(v), es el número de aristas incidentes con él, con el convenio de que un lazo suma dos porque incide dos veces. Se llaman grado mínimo y grado máximo del grafo, y se denotan \delta(G) y \Delta(G), el menor y el mayor de esos valores. Un vértice de grado 0 es aislado y uno de grado 1 es una hoja, término que resultará central al hablar de árboles. En un dígrafo el grado se desdobla en grado de entrada y grado de salida, cuya suma total coincide en ambos casos con el número de arcos.

El primer teorema de la teoría es también el más rentable en un examen, por su brevedad y por la elegancia de su demostración:

Lema del apretón de manos. En todo grafo (o multigrafo) G=(V,E) se cumple \sum_{v\in V}\operatorname{gr}(v)=2\,|E|.

Demostración por doble conteo. Contamos de dos maneras el número de pares formados por una arista y uno de sus extremos, es decir, el número de incidencias. Recorriendo los vértices, cada v aporta exactamente \operatorname{gr}(v) incidencias, y la suma total es el miembro izquierdo. Recorriendo las aristas, cada una aporta exactamente dos incidencias —sus dos extremos, o dos veces el mismo vértice si es un lazo—, y la suma total es 2|E|. Ambos recuentos cuentan lo mismo, luego coinciden. \blacksquare

La consecuencia inmediata es el resultado que suele pedirse en el aula: el número de vértices de grado impar es siempre par. En efecto, si la suma de todos los grados es par y los vértices de grado par aportan una cantidad par, la suma de los grados impares restantes ha de ser par, lo que obliga a que haya una cantidad par de sumandos impares. De ahí se deducen sin esfuerzo hechos que parecen adivinanzas: es imposible construir una red en la que exactamente siete ordenadores tengan cada uno tres conexiones, porque habría siete vértices de grado impar. Es una excelente primera experiencia de demostración por imposibilidad para tercero y cuarto de la ESO: se razona sobre todos los casos a la vez, sin construir ninguno.

La sucesión de grados de un grafo es la lista de los grados de sus vértices ordenada de mayor a menor. No toda sucesión de números naturales es realizable: por el lema, su suma debe ser par, aunque esa condición no basta —la sucesión (3,3,3,1) suma par y no corresponde a ningún grafo simple—. El algoritmo de Havel-Hakimi decide constructivamente si una sucesión es gráfica, y el teorema de Erdos-Gallai da una caracterización cerrada mediante desigualdades.

Cuando el grafo describe una red del mundo real, lo interesante deja de ser cada grado y pasa a ser su distribución. Réka Albert y Albert-László Barabási descubrieron a finales de los años noventa que en muchas redes reales —enlaces web, redes de citas, redes metabólicas— esa distribución no se concentra alrededor de una media, como ocurriría si las conexiones fueran aleatorias, sino que sigue una ley potencial: muchísimos vértices de grado bajo y unos pocos concentradores de grado enorme. Su modelo de crecimiento con enganche preferencial, en el que los nodos nuevos se conectan con más probabilidad a los ya muy conectados, explica cómo emerge esa estructura y es hoy el punto de partida de la ciencia de redes.

Figura 2. Cada arista aporta dos incidencias, de modo que la suma de los grados duplica el tamaño del grafo; aquí hay además dos vértices de grado impar, nunca uno solo.

4. Representación de grafos: matrices y listas

Para trabajar con un grafo, y sobre todo para que lo procese una máquina, hace falta escribirlo sin dibujarlo. La matriz de adyacencia de un grafo con vértices numerados v_1,\dots,v_n es la matriz cuadrada A de orden n cuyo elemento a_{ij} vale 1 si v_i y v_j son adyacentes y 0 en caso contrario; en un multigrafo se anota directamente el número de aristas entre ambos. Para un grafo no dirigido la matriz es simétrica, y si el grafo es simple su diagonal es nula. La suma de cada fila es el grado del vértice correspondiente, con lo que el lema del apretón de manos se relee como que la suma de todos los elementos de A vale 2|E|. En un dígrafo la simetría se pierde, y las sumas por filas y por columnas dan los grados de salida y de entrada.

La matriz no es solo un almacén: es una herramienta de cálculo. Un resultado clásico y muy vistoso afirma que el elemento (i,j) de la potencia A^{k} cuenta el número de recorridos de longitud exactamente k que van de v_i a v_j. La demostración es una inducción limpia sobre k: el caso k=1 es la definición, y en el paso inductivo la regla del producto de matrices suma, sobre todos los vértices intermedios, los recorridos de longitud k-1 multiplicados por la existencia o no de la arista final. Así, el álgebra de matrices que el alumnado estudia en el bachillerato adquiere un significado combinatorio tangible.

Esa alianza entre matrices y grafos alcanza una profundidad notable en la teoría espectral de grafos, que estudia qué revela la estructura de un grafo a partir de los valores propios de su matriz de adyacencia o de su matriz laplaciana. Fan Chung es la autora del tratado de referencia en esta materia y una de las responsables de que el espectro se convirtiera en instrumento habitual para medir la conectividad y la velocidad con que se difunde la información en una red. En la misma línea algebraica se sitúa el teorema de Kirchhoff (1847), que cuenta los árboles generadores mediante un determinante y que reencontraremos en el apartado 8.

Frente a la matriz, la lista de adyacencia almacena para cada vértice la relación de sus vecinos. La elección entre ambas no es cosmética, y en el aula sirve para introducir el coste computacional con un ejemplo palpable. La matriz ocupa siempre n^{2} posiciones y responde en un solo paso si dos vértices concretos son adyacentes; la lista ocupa del orden de n+m posiciones, donde m es el número de aristas, y permite recorrer los vecinos de un vértice sin examinar los demás. En un grafo denso la matriz es razonable; en uno disperso, que es lo habitual en las redes reales —millones de personas de las que cada una conoce a unos cientos—, sería inabordable y la lista es la única opción sensata. Existe además la matriz de incidencia, con una fila por vértice y una columna por arista, menos usada en la práctica pero útil en el tratamiento algebraico.

Figura 3. Los dos dibujos comparten matriz de adyacencia y lista de vecinos: son el mismo grafo, y el cruce del segundo trazado no añade ningún vértice.

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

5.1. Recorridos, conexión y distancia

Un recorrido de u a v es una sucesión alternada de vértices y aristas que empieza en u, termina en v y en la que cada arista une los dos vértices que la flanquean. Si no repite aristas se llama camino o paseo; si además no repite vértices, camino simple. Un recorrido cerrado que no repite aristas es un circuito, y si tampoco repite vértices salvo el inicial, un ciclo; la longitud de un recorrido es su número de aristas. Un grafo es conexo si entre cada par de vértices existe un camino, y en otro caso se descompone de manera única en componentes conexas. La distancia entre dos vértices es la longitud del camino más corto que los une, y el diámetro, la mayor de esas distancias, mide lo compacta que es la red. Un vértice cuya supresión aumenta el número de componentes es un vértice de corte, y una arista con esa propiedad, un puente; ambos identifican los puntos frágiles de una red, y localizarlos es lo primero al evaluar la robustez de una infraestructura.

5.2. Grafos eulerianos: la respuesta de Königsberg

Un circuito euleriano recorre todas las aristas del grafo exactamente una vez y vuelve al punto de partida; si el recorrido no es cerrado se habla de camino euleriano. El teorema que Euler dejó planteado y que Hierholzer completó en 1873 se enuncia así:

Un multigrafo conexo admite un circuito euleriano si y solo si todos sus vértices tienen grado par, y admite un camino euleriano abierto si y solo si tiene exactamente dos vértices de grado impar, que serán forzosamente sus extremos.

La necesidad se expone en el aula en un minuto: cada vez que el paseo entra en un vértice por una arista debe salir por otra distinta, de modo que las aristas de cada vértice se emparejan y su grado ha de ser par; en el caso abierto quedan desemparejados el vértice de salida y el de llegada. La suficiencia exige un argumento constructivo —se toma un circuito cualquiera y, mientras queden aristas sin usar, se le injerta otro que parta de un vértice ya visitado—, esencia del algoritmo de Hierholzer. En Königsberg los cuatro vértices tenían grado impar, con lo que ni siquiera existía un camino abierto: la respuesta era doblemente negativa.

Este teorema sostiene los pasatiempos de «dibujar sin levantar el lápiz», que en el aula funcionan extraordinariamente bien: se reparten figuras, el alumnado descubre por ensayo cuáles se pueden y cuáles no, y al contar los vértices impares el criterio aparece solo. Es una tarea de bajo umbral y techo alto, accesible desde primero de la ESO y prolongable hasta la demostración formal.

5.3. Grafos hamiltonianos: un problema engañosamente parecido

Un ciclo hamiltoniano pasa por todos los vértices exactamente una vez y regresa al origen. El nombre procede del juego icosiano que William Rowan Hamilton comercializó en 1857, un dodecaedro de madera en el que había que recorrer todos los vértices. La definición se parece tanto a la anterior que el alumnado —y no pocos opositores— las confunde: la diferencia está en si se agotan las aristas o los vértices, y conviene decirlo así de crudo.

Y sin embargo el parecido es engañoso: no se conoce ninguna caracterización sencilla de los grafos hamiltonianos, y decidir si un grafo lo es es un problema NP-completo, computacionalmente duro en el peor caso. Solo se dispone de condiciones suficientes que exigen abundancia de aristas: el teorema de Dirac (1952) garantiza que si n\ge 3 y \delta(G)\ge n/2 el grafo es hamiltoniano, y el de Ore (1960) lo debilita pidiendo \operatorname{gr}(u)+\operatorname{gr}(v)\ge n para cada par de vértices no adyacentes. Ninguna de las dos es necesaria: el ciclo C_{10} es hamiltoniano y tiene todos los grados iguales a 2. La investigación sigue viva: Daniela Kühn y Deryk Osthus han demostrado en la última década viejas conjeturas sobre la descomposición de grafos densos y regulares en ciclos hamiltonianos.

El contraste Euler-Hamilton merece exponerse siempre, porque es una de las primeras ventanas honestas a la teoría de la complejidad: dos preguntas gemelas, una con criterio inmediato y otra sin criterio conocido. En su versión ponderada, la búsqueda del ciclo hamiltoniano más barato es el problema del viajante, omnipresente en logística, en el trazado de circuitos impresos y en la planificación de rutas de reparto.

Figura 4. Dos grafos pequeños que separan con nitidez ambas nociones: el de la izquierda agota las aristas pero no admite ciclo hamiltoniano; el de la derecha lo admite y no tiene circuito euleriano.

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

6.1. Grafos planos y la fórmula de Euler

Un grafo es plano si admite alguna representación en la que las aristas no se corten salvo en sus extremos. Que un dibujo tenga cruces no prueba nada: el grafo puede ser plano y estar mal dibujado, distinción en la que conviene insistir porque enlaza con la idea del apartado 2. Un dibujo plano divide el plano en regiones o caras, contando siempre la exterior no acotada. La joya del apartado es la relación descubierta por Euler en 1750 para los poliedros y válida para todo grafo plano conexo:

donde V es el número de vértices, A el de aristas y C el de caras. La demostración por inducción sobre el número de aristas es asequible: si el grafo no tiene ciclos es un árbol, con A=V-1 y una única cara, y la igualdad se cumple; si tiene un ciclo, al suprimir una de sus aristas se pierden una arista y una cara y la expresión no varía. Aplicarla a los poliedros convexos —contar caras, aristas y vértices de un cubo o de un dodecaedro construidos con cartulina— es un puente natural con el sentido espacial del currículo y una de las actividades más agradecidas de tercero y cuarto de la ESO.

De la fórmula se deducen cotas muy útiles. En un grafo plano simple con V\ge 3, cada cara está bordeada por al menos tres aristas y cada arista bordea a lo sumo dos caras, lo que da por doble conteo 2A\ge 3C y, sustituyendo,

Si además no tiene triángulos —por ejemplo si es bipartito—, cada cara necesita al menos cuatro aristas y la cota se afina a A\le 2V-4. Estas desigualdades son la manera más económica de demostrar que ciertos grafos no son planos.

6.2. Las dos obstrucciones: Kuratowski

El grafo completo K_5 tiene V=5 y A=10, mientras que 3V-6=9: incumple la cota y por tanto no es plano. El bipartito completo K_{3,3} tiene V=6 y A=9, y al carecer de triángulos debería cumplir A\le 2V-4=8: tampoco lo es. Este segundo caso es el célebre acertijo de las tres casas que han de conectarse a los suministros de agua, gas y electricidad sin que las conducciones se crucen: imposible, y ahora se sabe por qué. Lo notable es que estos dos grafos agotan el problema: el teorema de Kuratowski (1930) afirma que un grafo es plano si y solo si no contiene ninguna subdivisión de K_5 ni de K_{3,3}. Que una propiedad geométrica tan escurridiza se reduzca a la ausencia de dos configuraciones concretas es uno de los resultados más hermosos de la teoría.

6.3. Coloración y los cuatro colores

Colorear un grafo es asignar un color a cada vértice de manera que dos adyacentes nunca reciban el mismo; el mínimo número de colores necesario es el número cromático \chi(G), que vale 2 exactamente cuando el grafo es bipartito y n en K_n. La formulación es abstracta, pero los problemas que resuelve son cotidianos: repartir asignaturas en franjas horarias sin que coincidan dos de un mismo grupo, asignar frecuencias a antenas cercanas sin interferencias o distribuir tareas entre recursos incompatibles.

Colorear un mapa político de modo que dos países fronterizos reciban colores distintos equivale a colorear los vértices del grafo que tiene un vértice por país. En 1852 Francis Guthrie conjeturó que cuatro colores bastan siempre. La historia posterior es ejemplar: Kempe publicó en 1879 una demostración que la comunidad dio por buena once años, hasta que Heawood encontró el error en 1890; del argumento roto se rescató el teorema de los cinco colores, cuya demostración sí es elemental y cabe en una clase. El enunciado completo resistió hasta 1976, cuando Appel y Haken lo probaron reduciendo el problema a un conjunto finito de configuraciones inevitables y comprobándolas con ordenador. Fue la primera gran demostración asistida por máquina y desató un debate legítimo sobre qué es una demostración cuando nadie puede verificarla entera; en 1997 se simplificó y en 2005 Gonthier la formalizó por completo en un asistente de pruebas.

La coloración sigue siendo un terreno de investigación de primer nivel. Un hito reciente es el teorema fuerte de los grafos perfectos, conjeturado por Berge en 1961 y demostrado en 2002 por Maria Chudnovsky junto a Robertson, Seymour y Thomas: un grafo es perfecto —en él y en todos sus subgrafos inducidos el número cromático coincide con el tamaño de la mayor camarilla— si y solo si ni él ni su complementario contienen un ciclo impar inducido de longitud al menos cinco. Sirve para mostrar al alumnado que la matemática no es un edificio cerrado en el siglo XIX, sino una disciplina viva.

Figura 5. La fórmula de Euler comprobada sobre un dibujo plano y usada como cota para descartar la planaridad de los dos grafos que caracterizan la obstrucción.

7. Árboles: caracterizaciones y propiedades

Entre todos los grafos, los árboles ocupan un lugar privilegiado: son la frontera exacta entre la conexión y la ausencia de ciclos, la estructura más económica capaz de mantener unida una red. Un árbol es un grafo conexo y sin ciclos; un grafo sin ciclos pero no necesariamente conexo es un bosque, y cada una de sus componentes es un árbol.

7.1. Seis maneras equivalentes de decir lo mismo

La riqueza del concepto se aprecia en que admite varias definiciones equivalentes. Para un grafo G con n vértices, las siguientes afirmaciones dicen exactamente lo mismo:

• G es conexo y sin ciclos.
• Entre cada par de vértices de G existe un único camino simple.
• G es conexo y tiene exactamente n-1 aristas.
• G es acíclico y tiene exactamente n-1 aristas.
• G es minimalmente conexo: es conexo y al suprimir cualquier arista deja de serlo, de modo que todas sus aristas son puentes.
• G es maximalmente acíclico: es acíclico y al añadir cualquier arista entre dos vértices no adyacentes se crea exactamente un ciclo.

Conviene llevar preparada al menos una de las implicaciones. Que un árbol con n vértices tenga n-1 aristas se prueba por inducción apoyándose en un lema previo: todo árbol con al menos dos vértices tiene al menos dos hojas. Para verlo, tómese un camino simple de longitud máxima; sus dos extremos han de tener grado 1, porque cualquier arista adicional en un extremo llevaría a un vértice ya visitado —creando un ciclo— o permitiría alargar el camino, contra la maximalidad. Con ese lema la inducción es inmediata: si n=1 hay 0 aristas; si n>1, se poda una hoja con su arista, queda un árbol de n-1 vértices que por hipótesis tiene n-2 aristas, y al devolver la hoja se llega a n-1. Este argumento de poda de hojas reaparece constantemente.

7.2. Árboles con raíz

Un árbol con raíz es un árbol en el que se ha distinguido un vértice, la raíz, lo que orienta implícitamente todas las aristas alejándose de ella e induce un vocabulario familiar: el vecino más próximo a la raíz es el padre de un vértice y los restantes son sus hijos; los vértices sin hijos son las hojas y los demás, internos; el nivel de un vértice es su distancia a la raíz, y la altura del árbol, el nivel máximo. Un árbol binario es aquel en el que cada vértice tiene a lo sumo dos hijos, y sobre él se construyen los métodos de búsqueda y ordenación de datos más habituales. La observación clave es que un árbol binario de altura h tiene a lo sumo 2^{h+1}-1 vértices, de modo que uno equilibrado alcanza un número enorme de hojas con muy pocos niveles: es la razón matemática de que buscar en una lista ordenada de un millón de entradas exija unas veinte comparaciones y no un millón.

7.3. Cuántos árboles hay

Contar árboles conduce a una de las fórmulas más sorprendentes de la combinatoria. La fórmula de Cayley (1889) afirma que el número de árboles distintos que pueden construirse sobre n vértices etiquetados es

Con cuatro vértices salen 4^{2}=16 árboles y con diez, mil millones. La demostración más elegante, debida a Prüfer, establece una biyección entre los árboles etiquetados y las sucesiones de n-2 etiquetas: un ejemplo espléndido de la técnica de contar un conjunto poniéndolo en correspondencia con otro que ya se sabe contar.

Figura 6. Un árbol con raíz con su vocabulario jerárquico; nótese la relación entre el número de vértices y el de aristas, que caracteriza a todo árbol.

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

Un árbol generador de un grafo conexo G es un subgrafo que contiene todos sus vértices y que es un árbol. Existe siempre —basta ir eliminando aristas de ciclos hasta que no quede ninguno— y en general no es único: eso es justamente lo que cuenta el teorema de Kirchhoff. Interpretado sobre una red, un árbol generador es la selección de enlaces más económica que mantiene todo conectado: exactamente n-1 conexiones, sin bucles.

Esa lectura tiene una consecuencia práctica de primer orden en las redes de comunicaciones. Cuando varios conmutadores se conectan formando ciclos, un mensaje difundido circularía indefinidamente y colapsaría la red. La solución que Radia Perlman ideó en 1985, convertida después en el protocolo del árbol de expansión y en base del estándar IEEE 802.1D, consiste en que los conmutadores calculen entre todos, de forma distribuida, un árbol generador de la red y desactiven lógicamente las conexiones sobrantes, dejándolas como reserva por si falla un enlace. Es una de las traducciones más directas de un teorema de grafos a una infraestructura de uso diario.

8.1. El árbol generador mínimo

Si el grafo es ponderado, la pregunta se afina: entre todos sus árboles generadores, ¿cuál tiene la suma de pesos más pequeña? Ese es el árbol generador mínimo, y su enunciado modeliza sin retoques un problema de ingeniería recurrente: tender el cableado eléctrico, la fibra óptica o la red de riego que conecte un conjunto de puntos con la menor longitud total. No es casual que el primer algoritmo conocido lo publicara Otakar Boruvka en 1926 con una motivación aplicada: electrificar Moravia gastando el mínimo de cable. Ese origen convierte el tema en una ocasión honesta —no decorativa— para hablar de eficiencia en el uso de los recursos, porque minimizar material y obra civil es a la vez ahorro económico y menor impacto ambiental, en la línea de los objetivos de desarrollo sostenible sobre infraestructuras resilientes y consumo responsable (ODS 9 y ODS 12).

8.2. Dos algoritmos voraces

El algoritmo de Kruskal (1956) ordena todas las aristas de menor a mayor peso y las va aceptando una a una, descartando aquellas que cerrarían un ciclo con las ya elegidas; termina cuando ha aceptado n-1 aristas. El algoritmo de Prim (1957, anticipado por Jarník en 1930) hace crecer en cambio un único árbol: parte de un vértice cualquiera y en cada paso añade la arista más barata que une lo ya construido con un vértice todavía fuera.

Ambos son voraces: en cada paso toman la decisión localmente mejor sin reconsiderarla nunca. Que una estrategia tan miope alcance el óptimo global es sorprendente y necesita demostración; la clave es la propiedad de corte, según la cual, dada cualquier partición de los vértices en dos bloques, la arista de menor peso que los une pertenece a algún árbol generador mínimo. Añadirla a un árbol óptimo que no la contuviera crearía un ciclo del que podría retirarse otra arista del mismo corte, obteniendo un árbol de peso menor o igual: el clásico argumento de intercambio. El árbol mínimo es único si todos los pesos son distintos, pero puede no serlo si hay empates. En cuanto al coste, Kruskal trabaja en O(|E|\log|E|), dominado por la ordenación, y Prim en O(|E|\log|V|) con una cola de prioridad.

Hay un error de comprensión muy extendido que conviene anticipar en el aula: el árbol generador mínimo no contiene, en general, el camino más corto entre dos vértices dados. Optimiza el coste total de la red, no cada trayecto; para eso hace falta otro algoritmo, que se ve más adelante. Presentar los dos problemas seguidos y contrastarlos evita una confusión muy extendida.

Figura 7. Kruskal acepta las aristas por orden creciente de peso y descarta las que cerrarían un ciclo; se detiene al reunir una arista menos que vértices tiene el grafo.

9. Diagramas en árbol: recuento y probabilidad

Llegamos al segundo concepto del título, el de mayor presencia real en las aulas. Un diagrama en árbol es, sencillamente, un árbol con raíz que despliega de forma ordenada todas las posibilidades de un proceso que ocurre por etapas. De la raíz salen tantas ramas como opciones tenga la primera etapa; de cada una, las de la segunda, y así sucesivamente. Cada hoja es un resultado posible y cada camino de la raíz a una hoja, la secuencia de decisiones que lo produce. Su valor didáctico está en que materializa el proceso: lo que en una fórmula queda oculto, en el árbol se ve.

9.1. Contar por etapas

El número de hojas es el producto de las opciones de cada etapa, de modo que el diagrama es la representación visual del principio de multiplicación. Para formar números de dos cifras distintas con los dígitos 1, 2 y 3, el árbol tiene tres ramas iniciales y dos desde cada una, es decir 3\cdot 2=6 hojas: 12, 13, 21, 23, 31 y 32. Si se permitiera repetir cifra, cada nivel tendría tres ramas y saldrían 3^{2}=9.

Ese contraste, dibujado con los dos árboles uno junto a otro, resuelve la confusión más persistente del bloque de recuento: la de si importa el orden y si se puede repetir. Quien ha construido el árbol no necesita recordar qué fórmula corresponde a cada caso, porque puede reconstruirla: ve que al no repetir el número de ramas disminuye y aparece el factorial, y que al repetir se mantiene constante y aparece la potencia. Por eso el diagrama debe preceder a la fórmula y no al revés; usado así es además un recurso de diseño universal para el aprendizaje, porque ofrece una vía visual a quien no accede con comodidad al lenguaje simbólico, sin rebajar la exigencia matemática.

9.2. Probabilidad de experimentos compuestos

La potencia del diagrama se multiplica al etiquetar cada rama con su probabilidad. Dos reglas resuelven entonces casi cualquier problema de experimento compuesto. La regla del producto dice que la probabilidad de un camino completo es el producto de las probabilidades de sus ramas, y en las etapas posteriores esas probabilidades son ya condicionadas por lo ocurrido antes, de modo que el árbol incorpora la condicionalidad sin necesidad de nombrarla:

La regla de la suma dice que la probabilidad de un suceso alcanzable por varios caminos distintos es la suma de las probabilidades de esos caminos. Conviene exigir siempre una comprobación que detecta la mayoría de los errores: las probabilidades de las ramas que salen de un mismo nodo han de sumar 1, y también la suma de todas las hojas.

Considérese una urna con tres bolas rojas y dos azules de la que se extraen dos sin reemplazo. En la segunda etapa las probabilidades cambian, porque queda una bola menos y la composición depende de lo extraído antes. La probabilidad de sacar exactamente una bola roja es la suma de los dos caminos mixtos:

El mismo diagrama admite una lectura hacia atrás que encierra una de las ideas más finas de la probabilidad. Preguntarse, sabiendo que la segunda bola fue azul, cuál es la probabilidad de que la primera fuera roja invierte el sentido natural del árbol y conduce al teorema de Bayes: se divide la probabilidad del camino favorable entre la suma de todos los caminos compatibles con lo observado. Que ese razonamiento, que en el bachillerato se formaliza y sustenta desde el diagnóstico médico hasta los filtros de correo, pueda entenderse antes como un simple recorrido de ramas en sentido inverso es el mejor argumento para enseñar bien los diagramas en árbol.

9.3. La misma estructura, en todas partes

El diagrama en árbol es solo la cara más escolar de una idea universal. Los árboles de decisión organizan diagnósticos y clasificaciones y son un pilar del aprendizaje automático; los árboles de juego describen las jugadas del ajedrez y sostienen la estrategia minimax; los árboles sintácticos representan la estructura de una frase o de un programa; los árboles de Huffman comprimen ficheros asignando códigos más cortos a los símbolos más frecuentes. En todos late la misma estructura con raíz que el alumnado maneja con las bolas de una urna, y señalarlo en clase muestra que un concepto elemental bien comprendido abre la puerta a las ideas más avanzadas.

Figura 8. Cada camino se recorre multiplicando y cada suceso se calcula sumando caminos; la comprobación de que el total vale la unidad detecta casi todos los errores.

10. Algoritmos sobre grafos y panorama de aplicaciones

Si la teoría de grafos ha pasado de curiosidad decimonónica a herramienta imprescindible, es por sus algoritmos, capaces de responder preguntas sobre grafos gigantescos en fracciones de segundo. Llevarlos al aula es además la ocasión más natural para desarrollar el pensamiento computacional que el currículo vigente incorpora al sentido algebraico, porque permite pasar del razonamiento en papel a la programación de un procedimiento sin cambiar de problema.

Los dos recorridos básicos son la búsqueda en anchura y la búsqueda en profundidad. La primera explora el grafo por capas —primero los vecinos del vértice de partida, luego los vecinos de estos—, se implementa con una cola y proporciona de regalo los caminos más cortos en número de aristas, lo que la hace idónea para resolver laberintos o medir grados de separación en una red social. La segunda avanza todo lo que puede por una rama antes de retroceder, se implementa con una pila o con recursión, y es la base de la detección de ciclos, de la identificación de componentes y de la ordenación topológica de tareas con precedencias. Ambas recorren el grafo en tiempo O(|V|+|E|), proporcional al tamaño de la entrada.

Cuando las aristas tienen pesos, el camino con menos aristas deja de ser el más barato y hace falta el algoritmo de Dijkstra (1959), que mantiene una frontera de vértices con la mejor distancia provisional conocida y en cada paso cierra definitivamente el más cercano al origen. Es también voraz, y su corrección depende de una hipótesis que hay que enunciar siempre: los pesos no pueden ser negativos; si los hay, se recurre al algoritmo de Bellman-Ford. Dijkstra, junto con los refinamientos que orientan la búsqueda hacia el destino en lugar de expandirla en todas direcciones, es lo que ejecuta un navegador cada vez que calcula una ruta, y contarlo así en clase convierte una lista de pasos abstracta en algo que el alumnado lleva en el bolsillo.

El panorama de aplicaciones desborda cualquier enumeración, pero conviene llevar media docena de ejemplos sólidos. En internet, el algoritmo que ordenó los primeros buscadores interpretaba los enlaces entre páginas como votos y calculaba la importancia de cada una mediante el vector propio dominante de una matriz asociada al grafo: álgebra lineal y grafos otra vez de la mano. En redes sociales se estudian la centralidad, la formación de comunidades y la propagación de rumores. En logística conviven el problema del viajante y el del cartero chino, que busca el recorrido más corto que pase por todas las aristas y que, a diferencia del anterior, sí tiene solución eficiente apoyándose en el teorema de Euler. En planificación de proyectos, las técnicas de camino crítico calculan sobre un grafo dirigido acíclico la duración mínima de una obra. En biología, los árboles filogenéticos reconstruyen el parentesco entre especies. E incluso la asignación de turnos, aulas o tribunales se resuelve como una coloración o como un emparejamiento en un grafo bipartito.

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

Los ejes didácticos se han ido tejiendo a lo largo del desarrollo; conviene consolidarlos aquí con la vista puesta en la práctica de aula.

El anclaje curricular más firme está en el sentido estocástico, que recoge de manera explícita los diagramas de árbol como técnica de recuento sistemático en los primeros cursos de la ESO y como herramienta para el cálculo de probabilidades de experimentos compuestos en los últimos, con continuidad en el bachillerato a través de la probabilidad condicionada y el teorema de Bayes. Un segundo anclaje está en el sentido algebraico, que acoge el pensamiento computacional: los recorridos, el camino mínimo y el árbol generador son contextos idóneos para introducir la algoritmia. El tema irriga además el sentido espacial —la fórmula de Euler sobre poliedros—, el de las conexiones y el socioafectivo. En cuanto a las competencias específicas, la modelización es aquí la reina, porque traducir un mapa, una red o un torneo a un grafo es el gesto esencial del tema; el razonamiento y la prueba encuentran ejemplos cortos y elegantes —el lema del apretón de manos, las caracterizaciones del árbol, la imposibilidad de Königsberg—; y la comunicación se ejercita al justificar por qué una ruta no existe.

La experiencia docente ha identificado errores y preconcepciones frecuentes cuyo conocimiento permite intervenir antes de que se consoliden. El más profundo es confundir el grafo con su dibujo: creer que dos representaciones distintas son grafos distintos, o que un cruce del trazado es un vértice. Le siguen contar mal el grado cuando hay un lazo, confundir el recorrido euleriano con el hamiltoniano y suponer que el árbol generador mínimo contiene el camino más corto entre dos puntos. En los diagramas en árbol los tropiezos son otros: no ser sistemático y perder ramas, sumar cuando hay que multiplicar, no advertir que las probabilidades de la segunda etapa cambian si la extracción es sin reemplazo, y olvidar comprobar que las ramas de un mismo nodo suman uno. Provocar deliberadamente estos errores con un contraejemplo es más eficaz que corregirlos después.

Metodológicamente, el tema se presta como pocos al aprendizaje basado en problemas y proyectos. Una situación de aprendizaje de buen rendimiento para los últimos cursos de la ESO es la red de fibra de una localidad: el alumnado modeliza las calles como un grafo ponderado con distancias tomadas de un plano real, aplica Kruskal para diseñar el tendido de coste mínimo y discute después qué se optimiza y qué se sacrifica, lo que enlaza de forma natural con el uso responsable de los recursos. Otras propuestas de alto rendimiento son el clásico «¿se puede dibujar sin levantar el lápiz?», la coloración de un mapa real en colaboración con Geografía y el diseño de un torneo de aula, que es literalmente un grafo completo. La evaluación debe ser coherente: junto a la prueba escrita, observación del trabajo de modelización, portafolio del proceso y rúbricas que valoren el razonamiento y la comunicación tanto como el resultado.

En cuanto a la atención a la diversidad, el tema tiene una virtud poco común: su umbral de entrada es bajísimo —dibujar puntos y líneas— y su techo, altísimo, lo que permite plantear una misma tarea con varios niveles de reto sin segregar al grupo, que es el corazón del diseño universal para el aprendizaje. Conviene presentar cada idea por más de una vía —manipulativa con cuerdas y chinchetas, gráfica, simbólica y digital—, porque el alumnado con dificultades en el cálculo puede rendir aquí a alto nivel: razonar sobre grafos apenas exige destreza aritmética.

Merece mención aparte el sociograma, desarrollado en los años treinta por Jacob Moreno y Helen Hall Jennings, que representa como un grafo dirigido las relaciones de afinidad y rechazo dentro de un grupo. Es una herramienta valiosa de tutoría y convivencia para detectar liderazgos, subgrupos y, sobre todo, alumnado en riesgo de aislamiento: los vértices de grado de entrada nulo son exactamente los que hay que mirar. Que la misma estructura del tema sirva para cuidar el clima del aula permite trabajar el sentido socioafectivo y mostrar que las matemáticas también sirven para mirar a las personas.

12. Conclusión

Recorrer la teoría de grafos es asistir, en poco más de dos siglos y medio, al recorrido completo de una idea matemática: de un pasatiempo sobre siete puentes al lenguaje con el que hoy se describen las redes de comunicación, la logística mundial y el funcionamiento de una célula. Por el camino hemos fijado los fundamentos —qué es un grafo, cómo se clasifica, cómo se representa y qué gobierna su estructura a través del grado—, hemos revivido los grandes problemas clásicos —Euler y Hamilton, la planaridad, los cuatro colores—, hemos estudiado con detalle los árboles, esa frontera exacta entre la conexión y la aciclicidad, y hemos desplegado los diagramas en árbol que enlazan el tema con el recuento y la probabilidad del aula.

El valor formativo de este contenido no reside solo en los teoremas, sino en cuatro ideas transversales que el docente debe hacer visibles: la potencia de la modelización, pues buena parte del trabajo consiste en saber mirar un problema como un grafo; la distinción entre la estructura y sus representaciones, lección de abstracción aplicable mucho más allá de este tema; el contraste entre lo fácil y lo difícil —el criterio inmediato de Euler frente a la dureza del problema de Hamilton, el árbol mínimo frente al viajante—, primera ventana honesta a la teoría de la complejidad; y la constatación de que la disciplina sigue viva, con teoremas de primer orden demostrados en las últimas dos décadas. Dominar el tema con rigor y saber transponerlo al aula con sensibilidad hacia la diversidad y hacia el entorno permite presentar, ante el tribunal y después ante el alumnado, no una colección de definiciones, sino el relato de cómo unos puntos y unas líneas se convirtieron en una de las herramientas más poderosas para comprender el mundo.

13. Bibliografía y referencias

(a) Referencias técnicas y científicas

• Euler, L. (1736). «Solutio problematis ad geometriam situs pertinentis». Commentarii Academiae Scientiarum Petropolitanae, 8, 128-140.
• 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.
• Grimaldi, R. P. (1997). Matemática discreta y combinatoria. Addison-Wesley Iberoamericana.
• García Merayo, F. (2005). Matemática discreta. Thomson-Paraninfo.
• Chung, F. R. K. (1997). Spectral Graph Theory. American Mathematical Society.
• Chudnovsky, M., Robertson, N., Seymour, P. y Thomas, R. (2006). «The strong perfect graph theorem». Annals of Mathematics, 164(1), 51-229.
• Barabási, A.-L. y Albert, R. (1999). «Emergence of scaling in random networks». Science, 286(5439), 509-512.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L. y Stein, C. (2022). Introduction to Algorithms (4.ª ed.). MIT Press.
• Perlman, R. (1985). «An algorithm for distributed computation of a spanning tree in an extended LAN». ACM SIGCOMM Computer Communication Review, 15(4), 44-53.
• IEEE 802.1D. Media Access Control Bridges. Institute of Electrical and Electronics Engineers.
• Gardner, M. (1985). Circo matemático. Alianza Editorial.

(b) Recursos y webgrafía

• Instituto GeoGebra: construcciones interactivas de grafos, recorridos eulerianos y diagramas en árbol.
• Federación Española de Sociedades de Profesores de Matemáticas: monográficos de matemática discreta y de probabilidad en Secundaria en la revista Suma.
• Sociedad Española de Investigación en Educación Matemática: actas con investigaciones sobre errores del alumnado en probabilidad y recuento.
• NRICH, Universidad de Cambridge: colección de tareas de bajo umbral y techo alto sobre grafos, recorridos y coloración.
• Proyecto Divulgamat, Real Sociedad Matemática Española: materiales de historia de las matemáticas y del problema de los cuatro colores.

Orientaciones para el estudio

• Abra con Königsberg y cierre el círculo con el criterio de Euler: es el hilo narrativo que da unidad al tema y el tribunal lo agradece. Enuncie la condición con precisión —circuito si todos los grados son pares, camino abierto si hay exactamente dos impares— y explique en dos frases por qué es necesaria.
• Lleve el lema del apretón de manos con su demostración por doble conteo escrita y ensayada: es corta, elegante, se expone en tres minutos y demuestra soltura con la técnica de contar lo mismo de dos maneras. Remátelo con el corolario de los vértices de grado impar.
• Tenga muy preparado el contraste Euler frente a Hamilton. Es el punto donde más se distingue a quien ha comprendido el tema de quien lo ha memorizado: mismo aire, dificultad opuesta, y una primera puerta a la complejidad computacional.
• Memorice las caracterizaciones equivalentes del árbol y sepa demostrar la de las n-1 aristas por poda de hojas. Es el concepto que da título al tema junto con los diagramas, así que no puede quedar en una definición suelta.
• Prepare un ejemplo pequeño de Kruskal resuelto paso a paso, con la lista de aristas ordenada y las descartadas marcadas. Ocupa poco, se dibuja rápido y vale más que media página de prosa. Mencione a Prim, el carácter voraz, la propiedad de corte y el dato de Boruvka electrificando Moravia en 1926.
• Dedique tiempo real a los diagramas en árbol: es el contenido con presencia curricular más directa y el que un tribunal espera ver bien resuelto. Lleve un ejemplo de probabilidad con y sin reemplazo, las reglas del producto y de la suma, y la lectura inversa que conduce a Bayes.
• No se pierda enumerando aplicaciones. Media docena bien elegidas y explicadas en una línea rinden más que una lista de veinte: navegador y camino mínimo, buscador y enlaces, sociograma, cartero chino, filogenia y asignación de horarios por coloración.
• En la parte didáctica, no se limite a decir que el tema es motivador. Nombre una situación de aprendizaje concreta con su curso, dos o tres errores frecuentes del alumnado —el grafo no es su dibujo, sumar frente a multiplicar probabilidades, el árbol mínimo no da el camino más corto— y una idea de evaluación. Es la parte que más separa un notable de un sobresaliente y la que menos gente prepara.
• Reserve entre cinco y ocho minutos finales para el cierre. Un tema que se queda sin conclusión por mala gestión del tiempo pierde puntos que ya estaban ganados: cronometre al menos dos ensayos completos.
• Dibuje las figuras a mano mientras estudia, no solo las mire. En el examen se escriben con prisa y bajo presión, y un grafo mal trazado o un árbol torcido restan legibilidad a un contenido correcto.