Este temario corresponde en exclusiva a la especialidad de Matemáticas del Cuerpo de Profesores de Enseñanza Secundaria (código 590/512) — una de las aproximadamente 50 especialidades oficiales de este cuerpo. No cubre ninguna otra especialidad de Secundaria (Lengua Castellana y Literatura, Geografía e Historia, Física y Química, Biología y Geología, Inglés, Filosofía, Tecnología, Dibujo, Música...) ni los cuerpos de Maestros o de Profesores Técnicos de Formación Profesional, que tienen temarios propios y distintos, todavía no publicados en OpositaGratis. El cuestionario específico (Parte A) que se reproduce aquí es el fijado con carácter estatal por el entonces Ministerio de Educación y Ciencia, y sigue siendo, más de tres décadas después, el temario base que las distintas Administraciones educativas —las 17 comunidades autónomas más Ceuta y Melilla, cada una competente para convocar su propia oposición— citan y desarrollan en sus resoluciones de convocatoria anual, al no existir una versión posterior que lo haya derogado o sustituido con carácter general para esta especialidad. Cada convocatoria autonómica concreta puede añadir particularidades propias (requisitos lingüísticos en comunidades con lengua cooficial, la prueba de programación y unidad didáctica, u otras variaciones menores de redacción), que no están reflejadas en este índice.
La teoría de grafos es una de las incorporaciones más recientes al temario disciplinar de Matemáticas, y responde a la creciente presencia de las matemáticas discretas en el currículo de Secundaria y Bachillerato, especialmente en las materias de Matemáticas de Bachillerato. El tema exige dominar el vocabulario formal (vértices, aristas, grado, conexión), los resultados clásicos que dieron origen a la disciplina (Euler y los puentes de Königsberg), los algoritmos de optimización sobre grafos (Kruskal, Prim, Dijkstra) y el uso del diagrama en árbol como técnica de recuento y de cálculo de probabilidades, que es la aplicación con mayor peso didáctico en el aula.
Un grafo es una estructura matemática discreta que modela relaciones binarias entre objetos. Formalmente, un grafo G se define como un par ordenado G=(V,A), donde V es un conjunto finito no vacío de elementos llamados vértices o nodos, y A es un conjunto de pares de vértices llamados aristas, que representan la relación o conexión entre ellos. Cuando dos vértices están unidos por una arista se dice que son adyacentes, y la arista es incidente con ambos. Un grafo puede representarse gráficamente situando los vértices como puntos y las aristas como líneas o curvas que los unen, aunque la posición geométrica de los vértices es irrelevante para la estructura combinatoria del grafo: lo único que importa es qué pares de vértices están conectados. Se admiten variantes: un grafo simple no tiene lazos (aristas de un vértice a sí mismo) ni aristas múltiples entre el mismo par de vértices; un multigrafo sí las admite. El orden del grafo es el número de vértices, |V|, y el tamaño es el número de aristas, |A|. Esta formalización, desarrollada sobre todo en el siglo XX aunque con antecedentes en Euler, permite tratar de manera unificada problemas tan diversos como redes de transporte, circuitos eléctricos, relaciones sociales, moléculas químicas o la planificación de tareas, y constituye el punto de partida de toda la teoría de grafos que se desarrolla en el resto del tema.
Grafos dirigidos y no dirigidos
Un grafo no dirigido es aquel en que las aristas no tienen orientación: la arista {u,v} representa una relación simétrica, de modo que conecta a u con v exactamente igual que a v con u. Un grafo dirigido o dígrafo, en cambio, sustituye las aristas por arcos, es decir, pares ordenados (u,v), que representan una relación con sentido: del vértice u al vértice v, y no necesariamente al revés. Gráficamente los arcos se dibujan como flechas. Los dígrafos son el modelo natural para situaciones asimétricas: una calle de sentido único, una relación de precedencia entre tareas, un enlace web que apunta de una página a otra, o una relación de dominancia en un torneo. En un dígrafo se distingue el grado de salida de un vértice (número de arcos que parten de él) del grado de entrada (número de arcos que llegan a él). Todo grafo no dirigido puede verse como un caso particular de dígrafo en el que cada arista {u,v} se sustituye por los dos arcos (u,v) y (v,u), lo que permite unificar ambos marcos teóricos cuando conviene. La distinción entre ambos tipos es relevante en la resolución de problemas de aplicación: el problema del camino más corto, por ejemplo, admite versiones distintas según el grafo sea dirigido o no, y algoritmos como el de Dijkstra deben adaptarse a cada caso, ya que en un dígrafo la distancia de u a v puede no coincidir con la de v a u.
Grado de un vértice
El grado de un vértice v en un grafo no dirigido, denotado gr(v) o deg(v), es el número de aristas incidentes en él; un lazo (arista de v a sí mismo) se cuenta habitualmente dos veces, pues aporta dos extremos al mismo vértice. Un vértice de grado 0 se llama aislado, y uno de grado 1 se llama hoja o vértice pendiente, terminología especialmente relevante en el estudio de árboles. La secuencia de grados de un grafo es la lista de los grados de todos sus vértices, habitualmente ordenada de mayor a menor; dos grafos isomorfos tienen necesariamente la misma secuencia de grados, aunque el recíproco no es cierto en general. Un grafo se dice k-regular cuando todos sus vértices tienen el mismo grado k; el caso k=2 corresponde exactamente a una unión disjunta de ciclos. El concepto de grado es la base de resultados fundamentales como el lema del apretón de manos y del criterio de existencia de caminos y circuitos eulerianos, y tiene una interpretación intuitiva muy explotable en el aula: en un grafo que representa una red de amistades, el grado de un vértice es sencillamente el número de amigos de esa persona dentro de la red, lo que facilita introducir el concepto sin necesidad de formalismo excesivo en cursos de Secundaria.
Lema del apretón de manos
El lema del apretón de manos (handshaking lemma) establece que, en todo grafo no dirigido G=(V,A), la suma de los grados de todos los vértices es igual al doble del número de aristas: ∑_{v∈V} gr(v) = 2|A|. La demostración es inmediata por doble conteo: cada arista tiene exactamente dos extremos, de modo que al sumar los grados de todos los vértices cada arista se cuenta exactamente dos veces, una por cada uno de sus extremos. El nombre del lema proviene de una interpretación clásica: si en una reunión cada persona da la mano a algunas de las demás, la suma del número de manos dadas por cada persona es el doble del número total de apretones de manos, ya que cada apretón involucra a dos personas. Una consecuencia directa e importante del lema es que en todo grafo el número de vértices de grado impar es necesariamente par, puesto que la suma total de grados debe ser un número par (el doble de |A|), y una suma de grados sería impar si el número de sumandos impares fuera impar. Este resultado, aparentemente anecdótico, es una herramienta habitual para demostrar la no existencia de ciertos grafos con propiedades prescritas y aparece con frecuencia en problemas de oposición y en actividades de aula que introducen el razonamiento combinatorio de forma lúdica.
Caminos, circuitos y ciclos
Un camino en un grafo es una sucesión alternada de vértices y aristas v0, a1, v1, a2, ..., an, vn en la que cada arista ai conecta el vértice vi-1 con vi; la longitud del camino es el número de aristas que lo componen. Un camino es simple si no repite aristas, y elemental (o simple en el sentido más fuerte) si además no repite vértices. Un camino cerrado es aquel en que el vértice inicial coincide con el final (v0=vn). Un circuito es un camino cerrado que no repite aristas, y un ciclo es un circuito que además no repite vértices salvo el inicial y el final. Estas distinciones terminológicas, aunque varían ligeramente entre autores, son importantes porque de ellas dependen resultados clave: por ejemplo, un recorrido euleriano exige no repetir aristas (es un circuito o camino en sentido de no repetición de aristas), mientras que un circuito hamiltoniano exige no repetir vértices (es un ciclo). Un grafo sin ciclos se denomina acíclico, propiedad que caracteriza, junto con la conexión, a los árboles. La longitud del ciclo más corto de un grafo se llama cintura (girth); el estudio de caminos y ciclos es la base de multitud de algoritmos aplicados —como la búsqueda del camino más corto o la detección de dependencias circulares en la planificación de tareas— y del análisis de la conectividad de una red.
Grafos conexos y componentes conexas
Un grafo no dirigido se dice conexo si para todo par de vértices u, v existe al menos un camino que los une; en caso contrario, el grafo es disconexo. Todo grafo disconexo se descompone de manera única en componentes conexas: subgrafos maximales conexos, es decir, subconjuntos de vértices (junto con las aristas entre ellos) tales que dentro de cada uno hay camino entre cualquier par de vértices, pero no existe ninguna arista que conecte vértices de componentes distintas. El número de componentes conexas es un invariante estructural del grafo y tiene relevancia práctica inmediata: en una red de transporte, por ejemplo, dos ciudades en distinta componente conexa son inalcanzables entre sí utilizando exclusivamente esa red. Para grafos dirigidos la noción se refina en conexión débil (el grafo subyacente no dirigido es conexo) y conexión fuerte (existe camino dirigido de u a v y de v a u para todo par de vértices), distinción relevante, por ejemplo, en el análisis de enlaces de páginas web. El cálculo de las componentes conexas de un grafo puede hacerse de manera eficiente mediante algoritmos de recorrido como la búsqueda en anchura (BFS) o en profundidad (DFS), ambos de coste lineal en el número de vértices y aristas, lo que los hace aplicables incluso a redes de gran tamaño como las que modelan Internet o las redes sociales.
Grafos completos y grafos bipartitos
Un grafo completo de n vértices, denotado Kn, es aquel en que cada par de vértices distintos está unido por una arista; tiene por tanto n(n-1)/2 aristas, y todos sus vértices tienen grado n-1. Los grafos completos son el ejemplo extremo de densidad de conexiones y aparecen de forma natural en problemas de todos contra todos, como un torneo en el que cada participante se enfrenta a todos los demás. Un grafo bipartito es aquel cuyo conjunto de vértices puede partirse en dos subconjuntos disjuntos V1 y V2 de modo que toda arista del grafo une un vértice de V1 con uno de V2, sin que existan aristas dentro de un mismo subconjunto; se denota habitualmente Km,n cuando además es completo (todo vértice de V1 se une con todo vértice de V2), con |V1|=m y |V2|=n. Un resultado clásico caracteriza los grafos bipartitos: un grafo es bipartito si y solo si no contiene ningún ciclo de longitud impar. Los grafos bipartitos modelan de forma natural situaciones de emparejamiento entre dos tipos de elementos —trabajadores y tareas, alumnos y grupos, jugadores de fútbol y posiciones— y son la base de la teoría de emparejamientos (matching), con aplicaciones que van desde la asignación de plazas escolares hasta los algoritmos de recomendación, y constituyen un contenido con potencial didáctico alto por su cercanía a problemas cotidianos de reparto y asignación.
Isomorfismo de grafos
Dos grafos G1=(V1,A1) y G2=(V2,A2) son isomorfos si existe una biyección f: V1→V2 tal que dos vértices u, v son adyacentes en G1 si y solo si f(u) y f(v) son adyacentes en G2. Intuitivamente, dos grafos isomorfos son "el mismo grafo" salvo por el nombre o la disposición gráfica de sus vértices: tienen idéntica estructura de conexiones. El isomorfismo de grafos es una relación de equivalencia (reflexiva, simétrica y transitiva) sobre el conjunto de todos los grafos, y particiona dicho conjunto en clases de isomorfía. Determinar si dos grafos dados son isomorfos es, en general, un problema computacionalmente difícil —de hecho, no se conoce ningún algoritmo polinómico general (en 2015 László Babai anunció un algoritmo cuasipolinómico, resultado muy relevante pero distinto de uno polinómico), aunque tampoco se ha demostrado que sea NP-completo, situándolo en una clase de complejidad propia—, pero existen condiciones necesarias fáciles de comprobar que permiten descartar rápidamente el isomorfismo: dos grafos isomorfos deben tener el mismo número de vértices, el mismo número de aristas, y la misma secuencia de grados (ordenada). Sin embargo, estas condiciones no son suficientes: existen pares de grafos no isomorfos con la misma secuencia de grados. El concepto de isomorfismo permite trabajar con grafos "salvo el nombre de los vértices", lo que resulta esencial al clasificar estructuras (por ejemplo, existen exactamente 11 grafos no isomorfos con 4 vértices) y al reconocer que dos representaciones gráficas aparentemente distintas describen en realidad la misma red.
Grafo ponderado
Un grafo ponderado (o etiquetado) es un grafo en el que a cada arista se le asocia un número real, llamado peso o coste, mediante una función w: A→ℝ. El peso puede representar magnitudes muy diversas según el contexto de aplicación: una distancia física entre dos ciudades, un tiempo de desplazamiento, un coste económico, una capacidad de transporte o una probabilidad de transición. La introducción de pesos permite plantear problemas de optimización sobre la estructura combinatoria del grafo que carecerían de sentido en un grafo no ponderado, como determinar el camino de coste mínimo entre dos vértices (resuelto, por ejemplo, mediante el algoritmo de Dijkstra) o el árbol generador de coste mínimo de un grafo conexo (resuelto mediante los algoritmos de Kruskal o de Prim). El peso total de un camino, circuito o árbol se define como la suma de los pesos de las aristas que lo componen. Los grafos ponderados son el modelo estándar en la investigación operativa y la logística: una red de carreteras ponderada por distancias o tiempos permite calcular rutas óptimas (como hacen los sistemas de navegación GPS), y una red eléctrica ponderada por capacidades permite estudiar problemas de flujo máximo. En el aula, los grafos ponderados ofrecen un contexto muy natural para trabajar la optimización combinatoria con problemas cercanos a la experiencia del alumnado, como planificar la ruta más corta entre varios lugares de una ciudad.
Matriz de adyacencia
La matriz de adyacencia de un grafo G con n vértices numerados de 1 a n es una matriz cuadrada A de orden n en la que el elemento aij vale 1 si existe una arista entre el vértice i y el vértice j, y 0 en caso contrario (en un grafo ponderado, aij puede almacenar directamente el peso de la arista en lugar de un simple indicador binario). Para un grafo no dirigido la matriz de adyacencia es siempre simétrica (aij=aji), reflejando que la relación de adyacencia es simétrica; para un dígrafo, en cambio, no tiene por qué serlo. La diagonal principal es nula salvo que el grafo contenga lazos. La matriz de adyacencia no solo codifica completamente la estructura del grafo, sino que permite obtener información combinatoria mediante operaciones algebraicas: un resultado clásico establece que el elemento (i,j) de la matriz Ak (la k-ésima potencia de A) es igual al número de caminos distintos de longitud exactamente k que van del vértice i al vértice j. Esta propiedad conecta la teoría de grafos con el álgebra lineal y permite, por ejemplo, calcular de forma sistemática el número de caminos de una longitud dada, estudiar la conectividad de un grafo mediante el rango o los autovalores de su matriz de adyacencia (espectro del grafo), o implementar algoritmos de recorrido en un ordenador de forma eficiente, ya que la matriz es una estructura de datos natural para representar el grafo computacionalmente.
Matriz de incidencia
La matriz de incidencia de un grafo no dirigido con n vértices y m aristas es una matriz M de tamaño n×m en la que el elemento mij vale 1 si el vértice i es extremo de la arista j, y 0 en caso contrario; cada columna de la matriz tiene, por tanto, exactamente dos unos (los dos extremos de la arista correspondiente), salvo que existan lazos. Para un dígrafo, la convención habitual asigna -1 al vértice de origen del arco y +1 al vértice de destino (o viceversa), de modo que cada columna suma cero, lo que permite representar la orientación de cada arco. A diferencia de la matriz de adyacencia, cuyo tamaño depende solo del número de vértices, la matriz de incidencia depende también del número de aristas, y resulta especialmente útil cuando se necesita trabajar explícitamente con las aristas como objetos (por ejemplo, al plantear problemas de flujo en redes, donde cada arista representa una variable del problema de programación lineal asociado). La suma de los elementos de una fila de la matriz de incidencia de un grafo no dirigido coincide con el grado del vértice correspondiente, lo que ofrece una vía alternativa de comprobar el lema del apretón de manos sumando toda la matriz. Aunque en la práctica docente de Secundaria se emplea con menos frecuencia que la matriz de adyacencia, su mención es habitual en el temario de oposición como complemento formal a la representación matricial de un grafo.
Problema de los puentes de Königsberg (Euler, 1736)
El problema de los puentes de Königsberg es el origen histórico reconocido de la teoría de grafos. La ciudad de Königsberg (actual Kaliningrado), atravesada por el río Pregel, tenía dos islas conectadas entre sí y con las dos orillas mediante siete puentes; la pregunta popular era si resultaba posible dar un paseo que cruzara cada uno de los siete puentes exactamente una vez y regresara al punto de partida. Leonhard Euler resolvió el problema entre 1735 y 1736: presentó su solución a la Academia de Ciencias de San Petersburgo en 1735 y el artículo se publicó en 1741, demostrando que tal recorrido era imposible. Su aportación decisiva no fue solo la respuesta negativa, sino el método: Euler abstrajo el problema representando cada masa de tierra (las dos orillas y las dos islas) como un vértice y cada puente como una arista, despojando el problema de todo detalle geométrico irrelevante y reduciéndolo a una cuestión puramente combinatoria sobre la estructura resultante. Este paso de abstracción —sustituir un problema concreto por su esqueleto relacional— es precisamente el acto fundacional de la teoría de grafos como disciplina matemática autónoma, y por ello se considera a Euler su padre. El artículo de Euler, "Solutio problematis ad geometriam situs pertinentis", inauguró además lo que él mismo llamó geometría de la posición (geometria situs), antecedente directo de la topología. El problema es, además, un recurso didáctico extraordinariamente eficaz para introducir el pensamiento abstracto en el aula de Secundaria.
Condición de existencia de recorrido euleriano
Un camino euleriano es un camino que recorre todas las aristas del grafo exactamente una vez (pudiendo repetir vértices); si además el camino es cerrado (empieza y termina en el mismo vértice) se denomina circuito euleriano. Euler estableció, a raíz del problema de los puentes de Königsberg, las condiciones exactas de existencia: un grafo conexo (salvo vértices aislados) admite un circuito euleriano si y solo si todos sus vértices tienen grado par; admite un camino euleriano (no cerrado) si y solo si tiene exactamente dos vértices de grado impar, en cuyo caso el camino debe comenzar en uno de ellos y terminar en el otro. Si el grafo tiene más de dos vértices de grado impar, no existe ningún recorrido euleriano. La suficiencia de la condición (que si se cumple, el recorrido existe) fue demostrada rigurosamente por Carl Hierholzer en 1873, casi un siglo después de Euler, mediante un algoritmo constructivo que descompone el grafo en circuitos que se van fusionando. Aplicado al problema original: las cuatro masas de tierra de Königsberg tenían todas grado impar (3, 3, 3 y 5), muy lejos de la condición de a lo sumo dos vértices de grado impar, lo que confirma la imposibilidad del paseo. Este criterio es un ejemplo paradigmático de teorema de caracterización en matemática discreta: convierte una pregunta sobre la existencia de un objeto combinatorio complejo (un recorrido) en una comprobación aritmética trivial sobre los grados de los vértices.
Circuito hamiltoniano
Un ciclo hamiltoniano es un ciclo que visita cada vértice del grafo exactamente una vez (salvo el vértice inicial, que coincide con el final), sin necesidad de recorrer todas las aristas; si el recorrido no es cerrado se denomina camino hamiltoniano. El nombre honra a William Rowan Hamilton, quien en 1857 ideó el "juego icosiano", un rompecabezas basado en encontrar tales recorridos sobre las aristas de un dodecaedro. A pesar de la similitud superficial con el problema euleriano —ambos buscan un recorrido que use cada elemento del grafo una vez—, la naturaleza de ambos problemas es radicalmente distinta: mientras que la existencia de un recorrido euleriano se decide en tiempo polinómico mediante el sencillo criterio de la paridad de los grados, no se conoce ninguna caracterización simple y eficiente para la existencia de un ciclo hamiltoniano; de hecho, el problema de determinar si un grafo arbitrario posee un ciclo hamiltoniano es NP-completo, uno de los problemas computacionalmente más difíciles que se conocen. Existen condiciones suficientes parciales, como el teorema de Dirac (si todo vértice de un grafo simple con n≥3 vértices tiene grado al menos n/2, el grafo es hamiltoniano) o el teorema de Ore, pero ninguna caracteriza completamente el fenómeno. El problema del viajante de comercio (encontrar el ciclo hamiltoniano de coste mínimo en un grafo ponderado completo) es la aplicación práctica más célebre, con enorme relevancia en logística y planificación de rutas.
Árboles: definición y propiedades
Un árbol es un grafo no dirigido conexo y acíclico (sin ciclos). Los árboles son, en cierto sentido, los grafos conexos "mínimos": cualquier arista que se elimine de un árbol lo desconecta, y cualquier arista que se añada entre dos vértices no adyacentes crea exactamente un ciclo. Un resultado central caracteriza a los árboles mediante varias propiedades equivalentes, de modo que un grafo con n vértices es un árbol si y solo si se cumple cualquiera de las siguientes condiciones (que entonces implican todas las demás): es conexo y tiene exactamente n-1 aristas; es acíclico y tiene n-1 aristas; es conexo y toda arista es un puente (su eliminación lo desconecta); es acíclico y la adición de cualquier arista crea exactamente un ciclo; o existe un único camino entre cada par de vértices. Un vértice de grado 1 en un árbol se llama hoja, y todo árbol con al menos dos vértices tiene al menos dos hojas. Un bosque es una unión disjunta de árboles, es decir, un grafo acíclico no necesariamente conexo. Los árboles son omnipresentes en informática y matemáticas: estructuras de datos jerárquicas, árboles de decisión, árboles genealógicos, la representación de expresiones algebraicas o de derivaciones sintácticas en lingüística computacional se modelan todos mediante árboles, lo que convierte a este concepto en uno de los más transversales de la matemática discreta.
Árbol como grafo conexo y acíclico
La caracterización de un árbol como grafo simultáneamente conexo y acíclico merece un desarrollo propio por su papel de definición canónica. La conexión garantiza que el árbol está "todo unido" en una única pieza, mientras que la ausencia de ciclos garantiza que no hay redundancia en las conexiones: entre cualquier par de vértices existe un único camino, ni cero (porque es conexo) ni más de uno (porque un segundo camino distinto crearía un ciclo). Esta unicidad del camino es la propiedad más explotada en las aplicaciones: en un árbol genealógico, hay una única línea de descendencia entre un antepasado y un descendiente; en un árbol de decisión, hay una única secuencia de decisiones que lleva a cada resultado final; en la estructura de directorios de un sistema de archivos, hay una única ruta desde la raíz hasta cada archivo. Una consecuencia numérica directa de esta doble condición es la relación |A|=|V|-1, que puede demostrarse por inducción sobre el número de vértices: un árbol con un solo vértice tiene 0 aristas, y al añadir un nuevo vértice conectado por una única arista (la única forma de mantener la conexión sin crear un ciclo) el número de aristas aumenta exactamente en 1 cada vez que aumenta el número de vértices. Esta fórmula constituye un criterio de comprobación rápido, aunque no suficiente por sí solo, para verificar si un grafo dado podría ser un árbol.
Árbol generador (spanning tree)
Dado un grafo conexo G=(V,A), un árbol generador (o árbol de expansión, spanning tree) es un subgrafo de G que es un árbol y que contiene a todos los vértices de V. En otras palabras, un árbol generador conserva la totalidad de los vértices del grafo original pero conserva únicamente las aristas estrictamente necesarias para mantenerlo conexo, eliminando toda redundancia cíclica. Todo grafo conexo posee al menos un árbol generador, y en general posee varios: el número exacto de árboles generadores distintos de un grafo puede calcularse mediante el teorema de Kirchhoff (o teorema matriz-árbol), que lo expresa como un determinante relacionado con la matriz laplaciana del grafo; para el caso particular del grafo completo Kn, la fórmula de Cayley establece que el número de árboles generadores distintos es exactamente n^(n-2). Un árbol generador de un grafo con n vértices tiene siempre exactamente n-1 aristas, de acuerdo con la caracterización general de los árboles. La búsqueda de árboles generadores tiene una motivación práctica evidente: si G representa una red de comunicaciones o de suministro (eléctrico, de agua, de datos) y cada arista tiene un coste de instalación o mantenimiento, un árbol generador proporciona la red mínima de conexiones que mantiene todos los puntos comunicados, evitando duplicar caminos innecesarios; cuando además interesa minimizar el coste total, se plantea el problema del árbol generador de coste mínimo.
Árbol generador de coste mínimo
Dado un grafo conexo y ponderado G, el problema del árbol generador de coste mínimo (minimum spanning tree, MST) consiste en encontrar, de entre todos los árboles generadores posibles de G, aquel cuya suma de pesos de las aristas es mínima. Este problema tiene una motivación económica y logística directa: conectar un conjunto de instalaciones (ciudades, edificios, ordenadores) mediante la red de coste total mínimo que garantice que todas queden comunicadas entre sí, sin necesidad de que exista conexión directa entre cada par, sino solo de que exista algún camino. El problema es notable en la teoría de la optimización combinatoria porque, a diferencia de otros problemas de optimización sobre grafos que son computacionalmente intratables, admite algoritmos voraces (greedy) que garantizan la solución óptima en tiempo polinómico, un resultado nada trivial: en general, las estrategias voraces (tomar en cada paso la decisión localmente más ventajosa) no garantizan el óptimo global en problemas de optimización combinatoria, pero en el caso del árbol generador mínimo sí lo hacen, debido a la estructura matroidal subyacente del conjunto de aristas. Si todos los pesos de las aristas son distintos, el árbol generador de coste mínimo es único; si hay pesos repetidos, puede haber varios árboles óptimos de igual coste total. Los dos algoritmos clásicos para resolver este problema, ambos de origen anterior a la era de los ordenadores modernos, son el algoritmo de Kruskal y el algoritmo de Prim.
Algoritmo de Kruskal
El algoritmo de Kruskal, publicado por Joseph Kruskal en 1956, calcula un árbol generador de coste mínimo mediante una estrategia voraz basada en las aristas. El procedimiento ordena todas las aristas del grafo de menor a mayor peso y las examina una a una en ese orden, añadiendo cada arista al árbol en construcción siempre que no forme un ciclo con las aristas ya seleccionadas; si la arista crearía un ciclo, se descarta y se pasa a la siguiente. El proceso concluye cuando se han seleccionado n-1 aristas (siendo n el número de vértices), momento en el que se ha obtenido un árbol generador que conecta todos los vértices. La comprobación de si una arista formaría un ciclo se implementa habitualmente mediante una estructura de datos de conjuntos disjuntos (union-find), que permite determinar de forma muy eficiente si los dos extremos de la arista pertenecen ya a la misma componente conexa del árbol parcial. La corrección del algoritmo, es decir, la garantía de que la estrategia voraz produce efectivamente el árbol de coste mínimo y no solo un árbol razonable, se demuestra mediante el llamado "lema del corte", que afirma que la arista de menor peso que cruza cualquier partición del conjunto de vértices en dos partes pertenece a algún árbol generador mínimo. Kruskal resulta especialmente eficiente cuando el grafo tiene relativamente pocas aristas en comparación con el número de vértices (grafos dispersos).
Algoritmo de Prim
El algoritmo de Prim, desarrollado por Robert C. Prim en 1957 (aunque con un antecedente esencialmente idéntico debido a Vojtěch Jarník en 1930, por lo que en ocasiones se cita como algoritmo de Jarník-Prim), calcula igualmente un árbol generador de coste mínimo, pero mediante una estrategia voraz basada en los vértices en lugar de en las aristas. El procedimiento parte de un único vértice arbitrario, que constituye el árbol inicial, y en cada paso añade al árbol la arista de menor peso que conecta un vértice ya incluido en el árbol con un vértice todavía no incluido; este proceso se repite hasta que todos los vértices forman parte del árbol. A diferencia de Kruskal, en el algoritmo de Prim el árbol parcial es en todo momento conexo (crece añadiendo una rama cada vez), mientras que en Kruskal el conjunto de aristas seleccionadas puede formar, durante el proceso, varios fragmentos de árbol desconectados entre sí que se van fusionando progresivamente. Al igual que Kruskal, la corrección de Prim se apoya en el lema del corte. Desde el punto de vista de la eficiencia computacional, Prim resulta especialmente ventajoso cuando el grafo es denso (tiene muchas aristas en relación con el número de vértices), sobre todo si se implementa con una estructura de datos de cola de prioridad (montículo o heap), lo que reduce notablemente su coste. Ambos algoritmos, Kruskal y Prim, son un ejemplo canónico en el temario de estrategia voraz aplicada con éxito garantizado.
Diagramas en árbol para el recuento combinatorio
El diagrama en árbol es una representación gráfica que despliega de forma sistemática todas las posibilidades de un proceso que se desarrolla en varias etapas sucesivas, mostrando en cada nivel las ramas correspondientes a las distintas opciones disponibles en esa etapa. Formalmente, un diagrama de árbol de recuento es en realidad un árbol en el sentido de la teoría de grafos: un vértice raíz representa el inicio del proceso, y cada camino desde la raíz hasta una hoja representa una de las posibles secuencias completas de elecciones; el número total de hojas del árbol coincide con el número total de resultados posibles del proceso. Esta herramienta es, con diferencia, el recurso didáctico más potente para introducir la combinatoria en Secundaria, porque hace visible de manera intuitiva el principio del producto: si en la primera etapa hay m opciones y en la segunda hay n opciones para cada una de las anteriores, el árbol tendrá m ramas en el primer nivel y n ramas partiendo de cada una de ellas, de modo que el número total de hojas es m·n, sin necesidad de justificar la multiplicación mediante ninguna fórmula abstracta previa. El diagrama de árbol es igualmente la herramienta estándar para calcular probabilidades de sucesos compuestos (experimentos con varias etapas, con o sin reemplazamiento), asignando a cada rama la probabilidad condicionada correspondiente y multiplicando a lo largo de cada camino según la regla del producto de probabilidades.
Coloración de grafos y número cromático
Una coloración de vértices de un grafo consiste en asignar un color (o, más formalmente, un elemento de un conjunto finito de etiquetas) a cada vértice de modo que dos vértices adyacentes reciban siempre colores distintos. El número cromático de un grafo G, denotado χ(G), es el mínimo número de colores necesarios para conseguir una coloración válida. Determinar el número cromático exacto de un grafo arbitrario es, en general, un problema computacionalmente muy difícil (NP-difícil), aunque existen cotas y casos particulares bien conocidos: el número cromático de un grafo completo Kn es exactamente n (todos los vértices son adyacentes entre sí, luego todos necesitan colores distintos); el de un grafo bipartito no trivial es exactamente 2; y el de un ciclo de longitud impar es 3, mientras que el de un ciclo de longitud par es 2. La coloración de grafos modela de forma natural problemas de asignación de recursos con restricciones de incompatibilidad: la elaboración de horarios escolares o de exámenes (dos asignaturas con alumnado en común no pueden coincidir en el mismo turno), la asignación de frecuencias de radio (dos emisoras cercanas no pueden usar la misma frecuencia) o el problema clásico de colorear un mapa de modo que dos regiones fronterizas nunca compartan color, que fue precisamente el origen histórico del concepto y que condujo a uno de los teoremas más célebres de la teoría de grafos: el teorema de los cuatro colores.
Teorema de los cuatro colores
El teorema de los cuatro colores establece que el mapa de cualquier región plana dividida en subregiones conexas (por ejemplo, un mapa político) puede colorearse utilizando únicamente cuatro colores, de modo que dos subregiones que compartan una frontera común (no un simple punto) reciban siempre colores distintos. En términos de teoría de grafos, el enunciado equivale a afirmar que todo grafo planar (que puede dibujarse en el plano sin que sus aristas se crucen) tiene número cromático menor o igual que 4. La conjetura fue formulada en 1852 por Francis Guthrie, y resistió durante más de un siglo los intentos de demostración de algunos de los matemáticos más destacados, generando en el proceso avances importantes en teoría de grafos (como el propio concepto de grafo dual de un mapa). Fue finalmente demostrada en 1976 por Kenneth Appel y Wolfgang Haken, en la Universidad de Illinois, mediante un procedimiento que combinaba argumentos teóricos con una verificación exhaustiva por ordenador de cerca de 2000 configuraciones críticas irreducibles, lo que la convirtió en el primer teorema matemático de relevancia demostrado con ayuda esencial de un ordenador, hecho que suscitó en su momento un intenso debate filosófico sobre qué cuenta como demostración matemática válida al no poder ser verificada línea a línea por un ser humano. En 1997 Robertson, Sanders, Seymour y Thomas publicaron una demostración más sencilla (con menos configuraciones, también asistida por ordenador) y en 2005 Georges Gonthier la verificó formalmente con el asistente de pruebas Coq. Cabe precisar que cinco colores bastan siempre y son mucho más fáciles de demostrar (teorema de los cinco colores, de Percy Heawood, 1890); la dificultad extrema residía específicamente en reducir esa cota a cuatro.
Planaridad de un grafo
Un grafo es planar (o plano) si puede dibujarse en el plano de modo que ninguna de sus aristas se cruce con otra, salvo en los vértices comunes; nótese que la planaridad es una propiedad del grafo abstracto, no de un dibujo concreto, ya que un mismo grafo planar puede dibujarse también con cruces si se representa de forma poco cuidadosa. Un dibujo de un grafo planar sin cruces se denomina inmersión plana o mapa, y divide el plano en regiones llamadas caras, incluyendo una cara exterior no acotada. El teorema de Kuratowski (1930) caracteriza completamente los grafos planares: un grafo es planar si y solo si no contiene ningún subgrafo que sea una subdivisión de K5 (el grafo completo de 5 vértices) ni de K3,3 (el grafo bipartito completo de 3+3 vértices), los dos ejemplos más pequeños de grafos no planares. Existe una reformulación equivalente, el teorema de Wagner, en términos de menores de grafo en lugar de subdivisiones. La planaridad tiene consecuencias prácticas directas en el diseño de circuitos impresos, donde las pistas conductoras no pueden cruzarse sin un puente físico adicional, y en la cartografía y el diseño de redes de transporte urbano. Además, todo grafo planar cumple una acotación fuerte sobre su densidad: el número de aristas de un grafo planar simple con n≥3 vértices es siempre menor o igual que 3n-6, consecuencia directa de la fórmula de Euler para grafos planos.
Fórmula de Euler para grafos planos (V-A+C=2)
Para todo grafo planar conexo dibujado sin cruces en el plano, con V vértices, A aristas y C caras (incluida la cara exterior no acotada), se cumple la relación V - A + C = 2, conocida como fórmula de Euler para poliedros y grafos planos. Esta identidad, atribuida a Euler (1750, aunque con un caso particular ya conocido por Descartes), es uno de los resultados más elegantes y útiles de toda la teoría de grafos por su generalidad y sus numerosas consecuencias. Se demuestra habitualmente por inducción sobre el número de aristas: partiendo de un único vértice (V=1, A=0, C=1, se cumple 1-0+1=2), cada arista añadida al construir el grafo conexo puede ser de dos tipos: o bien une un vértice nuevo con uno ya existente (aumentan V y A en 1 y C no cambia, luego V-A+C se conserva), o bien une dos vértices ya existentes cerrando un ciclo (aumentan A y C en 1, porque la arista divide una cara en dos, y V no cambia, luego V-A+C se conserva). Si el grafo plano tiene k componentes conexas, la fórmula se generaliza a V-A+C=1+k. La fórmula tiene una aplicación inmediata en la clasificación de los poliedros regulares (sólidos platónicos): aplicada a la red de vértices, aristas y caras de cualquier poliedro convexo, permite demostrar que solo existen exactamente cinco poliedros regulares posibles (tetraedro, cubo, octaedro, dodecaedro e icosaedro), resultado ya conocido por los griegos pero que Euler proporcionó una vía puramente combinatoria de justificar. También permite deducir la cota 3n-6 sobre el número máximo de aristas de un grafo planar simple, mencionada al tratar la planaridad.
Algoritmo de Dijkstra del camino más corto
El algoritmo de Dijkstra, propuesto por Edsger W. Dijkstra en 1959, resuelve el problema del camino de coste mínimo entre un vértice origen y todos los demás vértices de un grafo ponderado, siempre que los pesos de las aristas sean no negativos. El algoritmo mantiene, para cada vértice, una etiqueta con la mejor distancia conocida hasta el momento desde el origen (inicializada a 0 para el propio origen y a infinito para el resto), y procede de forma voraz: en cada iteración selecciona, de entre los vértices aún no procesados definitivamente, aquel con menor etiqueta de distancia, lo marca como definitivo, y "relaja" las etiquetas de sus vecinos, actualizándolas si pasar por el vértice recién procesado ofrece un camino más corto que el conocido hasta entonces. El proceso concluye cuando todos los vértices alcanzables desde el origen han sido procesados. La condición de pesos no negativos es esencial para la corrección del algoritmo: si existieran aristas de peso negativo, la estrategia voraz podría fijar prematuramente como definitiva la distancia de un vértice que después resultara mejorable a través de un camino con una arista negativa; para grafos con pesos negativos (pero sin ciclos de peso negativo) se recurre en su lugar al algoritmo de Bellman-Ford, computacionalmente más costoso. El algoritmo de Dijkstra es, con diferencia, el más utilizado en la práctica para calcular rutas óptimas, y constituye el núcleo algorítmico de los sistemas de navegación GPS y de enrutamiento en redes de comunicaciones.
Aplicación a la organización de horarios y redes
La teoría de grafos proporciona el marco natural para modelar y resolver problemas de organización de horarios (scheduling), un tipo de aplicación con enorme relevancia práctica en centros educativos, hospitales o empresas. El problema típico de confección de horarios escolares puede plantearse como un problema de coloración de grafos: se construye un grafo cuyos vértices son las asignaturas (o los exámenes, en el caso de la planificación de convocatorias), uniendo con una arista a dos asignaturas cada vez que existe algún alumno matriculado en ambas (lo que impide que se impartan o examinen simultáneamente); una coloración válida de este grafo, en la que cada color representa una franja horaria distinta, garantiza automáticamente que ningún alumno tiene dos asignaturas o exámenes coincidentes, y el número cromático del grafo proporciona el número mínimo de franjas horarias necesarias. De manera similar, el diseño de redes de comunicaciones, de transporte o de suministro energético se apoya en conceptos de grafos ya vistos: la conectividad garantiza que todos los puntos de la red son alcanzables; el árbol generador de coste mínimo proporciona la infraestructura de coste mínimo que mantiene la red comunicada; y algoritmos como el de Dijkstra permiten calcular las rutas óptimas de tráfico o de datos dentro de la red ya construida. Estas aplicaciones muestran cómo un mismo aparato conceptual —vértices, aristas, grados, caminos, coloraciones— resuelve problemas de apariencia muy distinta en ámbitos profesionales diversos.
Grafos aplicados a itinerarios y transporte
Las redes de transporte —de carreteras, de líneas de autobús o metro, de rutas aéreas o marítimas— son uno de los ejemplos de aplicación de la teoría de grafos más cercanos a la experiencia cotidiana del alumnado, y por ello especialmente productivos en el aula. En estos modelos, los vértices representan localizaciones (ciudades, paradas, aeropuertos) y las aristas representan conexiones directas entre ellas (un tramo de carretera, un trayecto de autobús sin paradas intermedias, un vuelo directo); el peso de cada arista puede representar la distancia, el tiempo de viaje o el coste económico del trayecto. Sobre este modelo, preguntas cotidianas se traducen directamente en problemas de teoría de grafos ya estudiados: "¿cuál es la ruta más rápida entre dos ciudades?" es un problema de camino de coste mínimo, resoluble mediante el algoritmo de Dijkstra; "¿es posible llegar de una ciudad a otra usando esta red?" es una pregunta de conectividad; "¿cuál es la red de carreteras de coste mínimo que conecta todas estas poblaciones?" es un problema de árbol generador mínimo, resoluble mediante Kruskal o Prim. Las redes de transporte reales suelen ser dirigidas cuando existen restricciones de sentido (calles de sentido único, vuelos que no necesariamente tienen frecuencia idéntica en ambos sentidos), lo que ilustra en un contexto significativo la distinción entre grafos dirigidos y no dirigidos introducida al principio del tema, y ofrece al profesorado un contexto motivador para plantear problemas de optimización con sentido real en el aula.
Diagrama de árbol en probabilidad y sucesos compuestos
El diagrama en árbol es, junto con las tablas de contingencia, la herramienta más utilizada en el currículo de Secundaria para el cálculo de probabilidades de experimentos compuestos, es decir, experimentos que constan de varias etapas o pruebas sucesivas. En un diagrama de árbol probabilístico, cada rama que parte de un nodo representa uno de los posibles resultados de esa etapa del experimento, y se etiqueta con la probabilidad de ese resultado condicionada a haber llegado a ese nodo por el camino recorrido hasta entonces; la suma de las probabilidades de todas las ramas que parten de un mismo nodo debe ser siempre igual a 1, ya que representan todos los sucesos posibles en esa etapa. La probabilidad de un suceso compuesto, representado por un camino completo desde la raíz hasta una hoja, se calcula multiplicando las probabilidades de todas las ramas de ese camino (regla del producto para probabilidades condicionadas), lo que hace visible de forma muy intuitiva el teorema de la probabilidad compuesta o multiplicativa. Cuando interesa la probabilidad de un suceso que puede alcanzarse por varias hojas distintas (por ejemplo, "obtener exactamente una cara al lanzar dos monedas"), se suman las probabilidades de todos los caminos que llevan a ese resultado, ilustrando la regla de la suma para sucesos incompatibles. El diagrama de árbol resulta especialmente valioso para distinguir con claridad experimentos con reemplazamiento (probabilidades constantes en cada etapa) de experimentos sin reemplazamiento (probabilidades que cambian según lo ya extraído), un error conceptual muy frecuente en el alumnado de Secundaria y Bachillerato.
Uso didáctico de grafos y árboles en Secundaria
La teoría de grafos tiene presencia en el currículo de Matemáticas de Secundaria y Bachillerato (con un tratamiento más formal en Bachillerato, ligado al álgebra de matrices y a la matemática discreta, y una concreción que depende de cada normativa autonómica), por su capacidad para introducir el razonamiento matemático discreto y abstracto a través de contextos visuales, manipulativos y cercanos a la experiencia del alumnado, sin requerir un aparato algebraico previo complejo. Como recurso didáctico, los grafos permiten trabajar la resolución de problemas mediante representaciones que el alumnado puede dibujar, manipular y modificar directamente sobre el papel, favoreciendo un aprendizaje activo: problemas de itinerarios óptimos, de organización de torneos, de coloración de mapas o de resolución de acertijos clásicos (como el problema del lobo, la cabra y la col, o el de los puentes de Königsberg presentado como reto histórico) resultan motivadores y accesibles desde los primeros cursos de la ESO en forma simplificada, y se formalizan progresivamente en Bachillerato con la introducción de matrices de adyacencia, algoritmos de optimización y conceptos de conectividad. El diagrama en árbol, en particular, es una herramienta transversal que conecta este bloque con el de combinatoria y probabilidad, reforzando en el alumnado la idea de que un mismo esquema de representación —vértices y ramas conectando posibilidades sucesivas— sirve tanto para contar casos como para calcular probabilidades. Desde el punto de vista competencial, este bloque de contenidos es también un vehículo privilegiado para trabajar la modelización matemática de situaciones reales y el pensamiento computacional, dos de los ejes transversales más presentes en los currículos vigentes (LOMLOE).
Grafos dirigidos: grados de entrada y salida y recorridos eulerianos
En un dígrafo la suma de los grados de entrada de todos los vértices es igual a la suma de los grados de salida e igual al número de arcos: ∑gr⁺(v) = ∑gr⁻(v) = |A|. Un dígrafo conexo (débilmente) tiene un circuito euleriano si y solo si en cada vértice el grado de entrada coincide con el de salida; tiene un camino euleriano no cerrado si y solo si todos los vértices cumplen esa igualdad salvo dos: uno con grado de salida una unidad mayor que el de entrada (origen) y otro con grado de entrada una unidad mayor que el de salida (final). Un torneo es un dígrafo obtenido orientando cada arista de un grafo completo (cada pareja de participantes se enfrenta una vez); todo torneo posee un camino hamiltoniano (resultado de Rédei, 1934). Los dígrafos modelan relaciones de orden (diagrama de Hasse), precedencia de tareas (grafos de actividades, método del camino crítico), autómatas y redes de enlaces.
Subgrafos, complementario y familias notables de grafos
Un subgrafo de G=(V,A) es un grafo H=(V',A') con V'⊆V y A'⊆A (y las aristas de A' unen vértices de V'); es generador si V'=V e inducido si contiene todas las aristas de G entre los vértices de V'. El grafo complementario Ḡ de un grafo simple G tiene los mismos vértices y une dos vértices cuando G no los une; por tanto |A(G)|+|A(Ḡ)| = n(n−1)/2. Familias notables: el camino Pₙ (n vértices y n−1 aristas), el ciclo Cₙ (n vértices y n aristas, 2-regular), el completo Kₙ (n(n−1)/2 aristas), el bipartito completo Kₘ,ₙ (m·n aristas), la rueda Wₙ (un ciclo más un vértice central unido a todos), la estrella K₁,ₙ y el grafo de Petersen (10 vértices, 15 aristas, 3-regular, no planar y sin ciclo hamiltoniano, aunque sí con camino hamiltoniano). Entre las cifras de memoria: K₄ es planar y K₅ no lo es; K₂,ₙ es planar para cualquier n, mientras que K₃,₃ no lo es; el número de grafos simples etiquetados sobre n vértices es 2^(n(n−1)/2).
Recorridos de un grafo: búsqueda en anchura y en profundidad. Algoritmos de Fleury y Hierholzer
La búsqueda en anchura (BFS) explora el grafo por niveles de distancia al vértice inicial usando una cola; calcula distancias mínimas en número de aristas en un grafo no ponderado. La búsqueda en profundidad (DFS) avanza por una rama hasta agotarla y retrocede (backtracking), usando una pila o recursión; permite detectar ciclos, hallar componentes conexas y ordenar topológicamente un dígrafo acíclico. Ambas tienen coste lineal, O(V+A), con listas de adyacencia. Para construir efectivamente un circuito euleriano existen dos algoritmos clásicos: el de Fleury (1883), que recorre el grafo evitando atravesar un puente salvo que no haya alternativa, y el de Hierholzer (1873), más eficiente, que construye circuitos cerrados y los empalma hasta cubrir todas las aristas. El problema del cartero chino (Mei-Ko Kwan, 1960) busca el recorrido cerrado de coste mínimo que recorre todas las aristas de un grafo ponderado; se resuelve en tiempo polinómico duplicando aristas hasta que todos los grados sean pares, en contraste con el problema del viajante, que es NP-difícil.
Condiciones suficientes de hamiltonicidad: teoremas de Dirac y Ore
No existe una caracterización sencilla de los grafos hamiltonianos, pero sí condiciones suficientes. Teorema de Dirac (1952): si G es simple con n≥3 vértices y el grado de cada vértice es al menos n/2, entonces G es hamiltoniano. Teorema de Ore (1960): si en un grafo simple con n≥3 vértices se cumple gr(u)+gr(v) ≥ n para cada par de vértices no adyacentes u y v, entonces G es hamiltoniano; el teorema de Dirac es un caso particular. Ninguna de ambas condiciones es necesaria: el ciclo Cₙ es hamiltoniano con todos los grados iguales a 2, que es menor que n/2 cuando n>4. Condición necesaria sencilla: un grafo con un vértice de corte o con un vértice de grado 1 no puede ser hamiltoniano. Un grafo bipartito con partes de distinto tamaño no tiene ciclo hamiltoniano, resultado útil para descartar tableros (el recorrido del caballo de ajedrez sobre un tablero de ciertas dimensiones, por ejemplo). Euler y Hamilton: el euleriano se decide en tiempo polinómico; el hamiltoniano es NP-completo.
Árboles con raíz, árboles m-arios y recorridos de árboles
Un árbol con raíz es un árbol en el que se distingue un vértice (raíz) y se orienta cada arista desde la raíz; da lugar a la terminología de padre, hijo, hermanos, antecesores, descendientes, hoja (vértice sin hijos), vértice interno, nivel y altura (longitud del camino más largo desde la raíz a una hoja). Un árbol m-ario es aquel en que cada vértice interno tiene como máximo m hijos (binario si m=2); es completo si todos los vértices internos tienen exactamente m hijos. Un árbol m-ario completo con i vértices internos tiene n = m·i + 1 vértices en total y l = (m−1)·i + 1 hojas. Un árbol binario de altura h tiene como máximo 2^h hojas. Los tres recorridos clásicos de un árbol binario son preorden (raíz, izquierdo, derecho), inorden (izquierdo, raíz, derecho) y postorden (izquierdo, derecho, raíz); en un árbol de expresión aritmética el postorden da la notación polaca inversa. El código de Prüfer (1918) establece una biyección entre los árboles etiquetados sobre n vértices y las sucesiones de longitud n−2 con valores en {1,...,n}, de lo que resulta la fórmula de Cayley nⁿ⁻².
Algoritmos de caminos mínimos: complejidad y alternativas a Dijkstra
Con una implementación elemental (vector de distancias) el algoritmo de Dijkstra tiene coste O(V²); con una cola de prioridad (montículo binario) y listas de adyacencia, O((V+A) log V). Es un algoritmo voraz que fija la etiqueta de un vértice cuando es el de menor distancia provisional, y por eso exige pesos no negativos. El algoritmo de Bellman-Ford, de coste O(V·A), admite pesos negativos y detecta ciclos de peso negativo (en cuyo caso no existe camino mínimo). El algoritmo de Floyd-Warshall, de coste O(V³), calcula las distancias mínimas entre todos los pares de vértices mediante programación dinámica sobre la matriz de distancias y también admite pesos negativos sin ciclos negativos. En grafos no ponderados basta una búsqueda en anchura. Es útil recordar la diferencia con el árbol generador mínimo: el árbol de caminos mínimos desde un origen (obtenido con Dijkstra) no coincide en general con el árbol generador de coste mínimo (Kruskal, Prim), porque el primero minimiza distancias desde la raíz y el segundo el peso total.
Coloración: cotas del número cromático y coloración de aristas
Para un grafo simple G: χ(G) ≥ ω(G), siendo ω el tamaño de la mayor clique (subgrafo completo), y χ(G) ≤ Δ(G)+1, siendo Δ el grado máximo (basta colorear vértice a vértice con el primer color libre: algoritmo voraz). El teorema de Brooks (1941) afina la cota: χ(G) ≤ Δ(G) salvo que G sea completo o un ciclo impar. Un grafo es bipartito si y solo si χ(G) ≤ 2. Todo grafo planar es 4-coloreable (cuatro colores) y 5-coloreable con una demostración elemental (Heawood, 1890). La coloración de aristas asigna colores a las aristas de modo que las incidentes en un vértice difieran; su mínimo es el índice cromático χ'(G) y el teorema de Vizing (1964) asegura que Δ ≤ χ'(G) ≤ Δ+1. Aplicaciones: planificar un torneo de liga (en un grafo completo Kₙ con n par se necesitan n−1 jornadas, es decir, χ'(Kₙ) = n−1), asignar frecuencias, almacenar productos incompatibles y asignar registros en compiladores. El problema de decidir si un grafo es 3-coloreable es NP-completo.
Emparejamientos y flujos en redes (nociones)
Un emparejamiento (matching) de un grafo es un conjunto de aristas sin vértices comunes; es perfecto si cubre todos los vértices. El teorema de Hall (1935, «de los matrimonios») caracteriza cuándo un grafo bipartito con partes X e Y admite un emparejamiento que cubra X: si y solo si para todo subconjunto S⊆X el número de vecinos de S en Y es al menos |S|. Una red de flujo es un dígrafo ponderado con capacidades en los arcos, un origen y un sumidero; el teorema de flujo máximo-corte mínimo (Ford y Fulkerson, 1956) afirma que el valor del flujo máximo coincide con la capacidad mínima de un corte que separa origen y sumidero. Los emparejamientos en grafos bipartitos se reducen a un problema de flujo máximo. Aplicaciones: asignación de trabajadores a tareas, de alumnado a centros o prácticas, trasplantes de órganos cruzados, planificación de transporte y redes de tuberías.
Fórmulas y cifras de memoria sobre grafos
Resumen para examen: grafo simple de n vértices tiene como máximo n(n−1)/2 aristas; Kₙ tiene n(n−1)/2 aristas y es (n−1)-regular; Kₘ,ₙ tiene m·n aristas; Cₙ tiene n aristas; un árbol tiene n−1 aristas; un bosque con k componentes tiene n−k aristas; un grafo conexo tiene al menos n−1 aristas; un grafo con n vértices y más de (n−1)(n−2)/2 aristas es conexo; un grafo planar simple con n≥3 vértices tiene como máximo 3n−6 aristas (y 2n−4 si es además bipartito); el número de árboles generadores de Kₙ es nⁿ⁻² (Cayley); en un grafo planar conexo V−A+C=2; χ(Kₙ)=n, χ(Cₙ)=2 si n es par y 3 si n es impar, χ(bipartito)=2; el lema del apretón de manos da ∑gr(v)=2|A|. En Königsberg los grados eran 5, 3, 3 y 3. Fechas: Königsberg y Euler 1735-1736 (publicación 1741); Hierholzer 1873; Hamilton 1857; Kuratowski 1930; Kruskal 1956; Prim 1957 (Jarník 1930); Dijkstra 1959; Appel y Haken 1976.
Diagramas en árbol resueltos: recuento, extracciones y teorema de Bayes
Ejemplo de recuento: al lanzar tres veces una moneda el árbol tiene 2·2·2 = 8 hojas (resultados equiprobables), y la probabilidad de obtener exactamente dos caras es 3/8 (tres caminos favorables). Ejemplo de extracciones sin reemplazamiento: una urna con 3 bolas rojas y 2 azules, de la que se extraen dos bolas sucesivamente; la probabilidad de que las dos sean rojas es 3/5·2/4 = 3/10, la de una roja y una azul en cualquier orden es 3/5·2/4 + 2/5·3/4 = 3/5 y la de dos azules 2/5·1/4 = 1/10 (suman 1). Con reemplazamiento, las probabilidades serían 9/25, 12/25 y 4/25. Teorema de la probabilidad total y fórmula de Bayes: en un árbol de dos etapas, P(B) se obtiene sumando los productos de las ramas que terminan en B, y P(A|B) es el cociente entre el producto de la rama concreta y esa suma. Ejemplo: una enfermedad con prevalencia del 1%, una prueba con sensibilidad del 95% y 5% de falsos positivos; P(enfermo y positivo) = 0,01·0,95 = 0,0095 y P(sano y positivo) = 0,99·0,05 = 0,0495, de donde P(enfermo | positivo) = 0,0095/(0,0095+0,0495) ≈ 0,16, un resultado contraintuitivo que justifica el uso del árbol.
Ideas clave para el examen — memoriza esto
Un grafo es G=(V,A): vértices y aristas; dirigido si las aristas tienen sentido (arcos), no dirigido si no.
Lema del apretón de manos: ∑gr(v)=2|A|; consecuencia: el número de vértices de grado impar es siempre par.
Recorrido euleriano (recorre cada arista una vez): existe circuito si todos los grados son pares; existe camino si hay exactamente 2 vértices de grado impar (Euler, 1736, puentes de Königsberg).
Ciclo hamiltoniano (visita cada vértice una vez): no tiene criterio simple de existencia; el problema es NP-completo, a diferencia del euleriano.
Un árbol es un grafo conexo y acíclico; equivale a conexo con n-1 aristas; existe un único camino entre cada par de vértices.
Árbol generador mínimo: Kruskal (voraz por aristas, ordena y evita ciclos con union-find) y Prim (voraz por vértices, crece desde uno inicial) garantizan ambos la solución óptima.
Algoritmo de Dijkstra calcula caminos mínimos desde un origen, pero exige pesos no negativos (si hay negativos, se usa Bellman-Ford).
Fórmula de Euler para grafos planos conexos: V - A + C = 2; permite deducir que solo hay 5 poliedros regulares.
Teorema de Kuratowski: un grafo es planar si y solo si no contiene una subdivisión de K5 ni de K3,3.
Teorema de los cuatro colores (Appel-Haken, 1976): todo grafo planar tiene número cromático ≤4; fue el primer teorema demostrado con ayuda esencial de ordenador.
Un grafo es bipartito si y solo si no tiene ciclos de longitud impar.
La matriz de adyacencia elevada a k, Aᵏ, da en la posición (i,j) el número de caminos de longitud k entre i y j.
El diagrama en árbol es la herramienta central de recuento (principio del producto) y de cálculo de probabilidades compuestas (multiplicar a lo largo de cada rama, sumar entre hojas).
Dígrafos: en un dígrafo, la suma de grados de entrada = suma de grados de salida = nº de arcos; euleriano dirigido: grado de entrada = grado de salida en cada vértice.
Königsberg: Euler lo presentó en 1735 y se publicó en 1741; los cuatro vértices tenían grados 5, 3, 3 y 3; la suficiencia del criterio la demostró Hierholzer (1873).
Dirac (1952): gr(v)≥n/2 para todo v implica hamiltoniano; Ore (1960): gr(u)+gr(v)≥n en pares no adyacentes. Son condiciones suficientes, no necesarias.
Árbol m-ario completo con i vértices internos: n=m·i+1 vértices y (m−1)·i+1 hojas; árbol binario de altura h: como máximo 2^h hojas.
BFS y DFS cuestan O(V+A); Dijkstra O(V²) o O((V+A)log V); Bellman-Ford O(V·A); Floyd-Warshall O(V³).
12 preguntas sobre este tema, en orden aleatorio. Sin registro, sin límite de intentos.
Pregunta 1 de 120 aciertos
¿Cuántas aristas tiene el grafo completo K₅?
Preguntas frecuentes
¿De qué trata el Tema 2 de Secundaria?
La teoría de grafos es una de las incorporaciones más recientes al temario disciplinar de Matemáticas, y responde a la creciente presencia de las matemáticas discretas en el currículo de Secundaria y Bachillerato, especialmente en las materias de Matemáticas de Bachillerato. El tema exige dominar el vocabulario formal (vértices, aristas, grado, conexión), los resultados clásicos que dieron origen a la disciplina (Euler y los puentes de Königsberg), los algoritmos de optimización sobre grafos (Kruskal, Prim, Dijkstra) y el uso del diagrama en árbol como técnica de recuento y de cálculo de probabilidades, que es la aplicación con mayor peso didáctico en el aula.
¿Qué hay que memorizar del Tema 2 para el examen?
Un grafo es G=(V,A): vértices y aristas; dirigido si las aristas tienen sentido (arcos), no dirigido si no. Lema del apretón de manos: ∑gr(v)=2|A|; consecuencia: el número de vértices de grado impar es siempre par. Recorrido euleriano (recorre cada arista una vez): existe circuito si todos los grados son pares; existe camino si hay exactamente 2 vértices de grado impar (Euler, 1736, puentes de Königsberg). Ciclo hamiltoniano (visita cada vértice una vez): no tiene criterio simple de existencia; el problema es NP-completo, a diferencia del euleriano. Un árbol es un grafo conexo y acíclico; equivale a conexo con n-1 aristas; existe un único camino entre cada par de vértices. Árbol generador mínimo: Kruskal (voraz por aristas, ordena y evita ciclos con union-find) y Prim (voraz por vértices, crece desde uno inicial) garantizan ambos la solución óptima. Algoritmo de Dijkstra calcula caminos mínimos desde un origen, pero exige pesos no negativos (si hay negativos, se usa Bellman-Ford). Fórmula de Euler para grafos planos conexos: V - A + C = 2; permite deducir que solo hay 5 poliedros regulares. Teorema de Kuratowski: un grafo es planar si y solo si no contiene una subdivisión de K5 ni de K3,3. Teorema de los cuatro colores (Appel-Haken, 1976): todo grafo planar tiene número cromático ≤4; fue el primer teorema demostrado con ayuda esencial de ordenador. Un grafo es bipartito si y solo si no tiene ciclos de longitud impar. La matriz de adyacencia elevada a k, Aᵏ, da en la posición (i,j) el número de caminos de longitud k entre i y j. El diagrama en árbol es la herramienta central de recuento (principio del producto) y de cálculo de probabilidades compuestas (multiplicar a lo largo de cada rama, sumar entre hojas). Dígrafos: en un dígrafo, la suma de grados de entrada = suma de grados de salida = nº de arcos; euleriano dirigido: grado de entrada = grado de salida en cada vértice. Königsberg: Euler lo presentó en 1735 y se publicó en 1741; los cuatro vértices tenían grados 5, 3, 3 y 3; la suficiencia del criterio la demostró Hierholzer (1873). Dirac (1952): gr(v)≥n/2 para todo v implica hamiltoniano; Ore (1960): gr(u)+gr(v)≥n en pares no adyacentes. Son condiciones suficientes, no necesarias. Árbol m-ario completo con i vértices internos: n=m·i+1 vértices y (m−1)·i+1 hojas; árbol binario de altura h: como máximo 2^h hojas. BFS y DFS cuestan O(V+A); Dijkstra O(V²) o O((V+A)log V); Bellman-Ford O(V·A); Floyd-Warshall O(V³). Cotas de coloración: ω(G) ≤ χ(G) ≤ Δ+1; Brooks: χ ≤ Δ salvo grafo completo o ciclo impar; Vizing: Δ ≤ χ' ≤ Δ+1. En un grafo planar conexo V−A+C=2; con k componentes V−A+C=1+k; planar simple: A≤3n−6 (A≤2n−4 si es bipartito); K₅ y K₃,₃ no son planares. Teorema de Hall (1935) y flujo máximo-corte mínimo (Ford-Fulkerson, 1956): base de los problemas de asignación y de redes. Ejemplo con urna (3 rojas, 2 azules, sin reemplazo): P(dos rojas)=3/10; P(una de cada)=3/5; P(dos azules)=1/10.
¿Hay preguntas de test de este tema exacto?
Sí, 12 preguntas tipo test sobre este tema, en el apartado "Ponte a prueba" de esta misma página. Sin registro y sin límite de intentos.
¿De dónde sale el temario de este tema?
Del índice oficial de BOE núm. 226, de 21 de septiembre de 1993, páginas 27400 a 27438 (Orden de 9 de septiembre de 1993, del Ministerio de Educación y Ciencia, BOE-A-1993-23257), Anexo III — cuestionario específico (Parte A) de la especialidad Matemáticas del Cuerpo de Profesores de Enseñanza Secundaria (Temario oficial estatal de referencia — especialidad Matemáticas (Cuerpo de Profesores de Enseñanza Secundaria)).
Fuentes de este desarrollo
L. Euler, "Solutio problematis ad geometriam situs pertinentis" (presentado en 1735, publicado en 1741)
R. Diestel, "Graph Theory" (Springer)
F. Harary, "Graph Theory" (Addison-Wesley)
R.J. Wilson, "Introduction to Graph Theory"
T.H. Cormen, C.E. Leiserson, R.L. Rivest y C. Stein, "Introduction to Algorithms" (algoritmos de Kruskal, Prim, Dijkstra, Bellman-Ford y Floyd-Warshall)
K. Appel y W. Haken, "Every planar map is four colorable" (1976-1977)
Real Decreto 217/2022, de 29 de marzo, por el que se establecen la ordenación y las enseñanzas mínimas de la Educación Secundaria Obligatoria (BOE-A-2022-4975), bloques de Sentido estocástico y de Pensamiento computacional
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-A-2022-5521), materias de Matemáticas
Mientras tanto, practica con tests gratis de Secundaria.