Grafos Finitos e Infinitos Explicados

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. La definición nunca dijo finito

Vuelve a la definición de la guía de vértices y aristas y léela por lo que realmente dice:

G = (V, E)      with   E ⊆ [V]²

Un conjunto de vértices y un conjunto de subconjuntos de 2 elementos de él. Nada ahí menciona el tamaño. V puede ser las cuatro masas de tierra de Königsberg, los enteros, los reales o el conjunto de todas las cadenas binarias finitas, y la definición no se inmuta. Un grafo infinito es simplemente un grafo cuyo conjunto de vértices es infinito, y todo el tema de este artículo es qué deja de funcionar sin avisar cuando lo es.

No es un refinamiento moderno. El primer libro de teoría de grafos que se escribió es Theorie der endlichen und unendlichen Graphen de Dénes König, de 1936, cuyo título se traduce como Teoría de los grafos finitos e infinitos. Los grafos infinitos estaban en la disciplina desde su primer libro de texto, y Graph Theory de Diestel todavía les dedica un capítulo entero.

El paso importante es darse cuenta de que «finito» es una hipótesis que has estado usando sin verla. La mayoría de los enunciados de los libros tienen la forma «sea G un grafo finito», y la mayoría de las técnicas de demostración estándar la necesitan en silencio:

• La inducción sobre el número de vértices necesita un número de vértices sobre el que inducir.
• Los argumentos extremales («toma el vértice de grado máximo», «toma el camino más largo») necesitan que exista el máximo o el más largo.
• Los argumentos de conteo necesitan que los conteos sean números finitos y no cardinales.
• La terminación de un algoritmo necesita que la búsqueda se quede sin grafo.

Quita la finitud y cada una de esas cosas tiene que sustituirse por otra. Lo que las sustituye, en casi todos los casos, es la compacidad: la idea de que un enunciado sobre un objeto infinito a veces puede montarse a partir de enunciados sobre todas sus piezas finitas. Las secciones 5 y 6 tratan los dos teoremas clásicos que hacen exactamente eso.

2. Cuán grande: numerable, no numerable, localmente finito

«Infinito» no es un único tamaño, y hay tres medidas distintas que importan. Confundirlas es la primera fuente de confusión.

Un grafo es localmente finito cuando todo vértice tiene grado finito. Es una condición realmente independiente de la numerabilidad, y ambas se combinan de las cuatro maneras posibles:

• El rayo doble, un camino infinito en ambas direcciones, es numerable y localmente finito: todos los grados son 2.
• La retícula cuadrada infinita sobre ℤ² es numerable y localmente finita: todos los grados son 4. Es el grafo sobre el que viven realmente una hoja de cálculo, un autómata celular o un mundo de juego con casillas.
• La estrella infinita, un centro unido a una cantidad numerable de hojas, es numerable pero no localmente finita: el centro tiene grado infinito.
• El grafo completo sobre un conjunto no numerable de vértices es no numerable y no localmente finito.
• Una colección no numerable de rayos dobles disjuntos es no numerable y aun así localmente finita: hay una cantidad no numerable de vértices, y cada uno sigue teniendo grado 2. Esta es la cuarta combinación, y muestra que ninguna de las dos condiciones implica nada sobre la otra.

Merece la pena enunciar una consecuencia porque confunde a la gente: un grafo localmente finito puede ser infinito, y un grafo infinito puede tener todos sus grados pequeños. La finitud local acota cada vértice por separado; no dice nada sobre el tamaño del grafo.

3. Lo que la finitud te daba sin que lo notaras

Aquí está el inventario honesto. Son resultados y técnicas estándar, y cada uno falla en grafos infinitos por una razón concreta.

Dos filas merecen un comentario inmediato porque son las que más sorprenden.

«Algún vértice tiene grado máximo» falla, y falla por la razón más mundana del análisis: un conjunto infinito de números naturales no tiene por qué contener un elemento mayor. Construye un grafo cuyos vértices tengan grados 1, 2, 3 y así sin cota, y la cantidad Δ(G) sencillamente no está definida. Todo argumento extremal que empieza con «sea v un vértice de grado máximo» ha supuesto por tanto, en silencio, la finitud, o al menos una cota.

La estrella infinita rompe el lema de König, y por eso la finitud local aparece en su enunciado. La estrella es infinita y conexa, pero su camino más largo tiene longitud 2: hoja, centro, hoja. No hay ningún rayo en ella. Un solo vértice de grado infinito basta para destruir la conclusión, lo que indica que la hipótesis hace un trabajo real y no es higiene técnica.

4. Un contraejemplo de una línea al corolario del apretón de manos

El lema del apretón de manos es el teorema más antiguo de la disciplina, y su corolario es el que todo el mundo recuerda: el número de vértices de grado impar es par. En los grafos infinitos es falso, y el contraejemplo se dibuja en una línea.

Toma el rayo: vértices v0, v1, v2, … con una arista entre cada dos consecutivos.

v0 ── v1 ── v2 ── v3 ── v4 ── ⋯

deg(v0) = 1        impar
deg(vi) = 2        par, para todo i ≥ 1

vértices de grado impar: exactamente uno.  El corolario finito dice que su número debe ser par.

Conviene precisar qué sobrevive, porque la respuesta es más interesante que un simple «falla».

La ecuación ∑ deg(v) = 2|E| no se vuelve falsa; se vuelve vacía. Ambos lados son números cardinales, y para un cardinal infinito κ tenemos 2κ = κ, así que la identidad se cumple trivialmente y no dice nada. Lo que de verdad se rompe es el argumento de paridad construido sobre ella. Ese argumento divide una suma finita en partes impares y pares y concluye que la parte impar tiene un número par de términos, y es la finitud de la suma, no la ecuación, lo que hace legítimo el paso.

La lección se generaliza: cuando un teorema finito falla en grafos infinitos, normalmente no se rompe el enunciado sino la técnica de demostración, y esa técnica suele ser el conteo.

5. El lema de infinitud de König: el primer puente

Si la finitud es aquello en lo que se apoyan la mayoría de las demostraciones, la pregunta interesante es qué puede sustituirla. La primera y más útil respuesta es un lema que König publicó en 1927, nueve años antes de su libro de texto.

Lema de infinitud de König. Todo grafo infinito, conexo y localmente finito contiene un rayo, es decir, un camino infinito v0, v1, v2, … sin vértices repetidos.

La demostración es un argumento del palomar repetido infinitas veces, y vale la pena verla porque su forma reaparece en toda la combinatoria infinita.

Empieza en cualquier vértice v0. El grafo es infinito y conexo, así que desde él se alcanzan infinitos vértices. El grafo es localmente finito, así que v0 solo tiene finitos vecinos. Eliminar v0 reparte esos infinitos vértices restantes entre finitas piezas, así que por el principio del palomar al menos una pieza es infinita. Entra en ella y estarás exactamente en la situación de partida. Repitiendo para siempre se obtiene v0, v1, v2, …, y como cada paso entra en una región aún no visitada, ningún vértice se repite.

Ambas hipótesis hacen su trabajo, y quitar cualquiera de ellas mata la conclusión:

• Quita la finitud local y la estrella infinita es un contraejemplo: infinita, conexa, y su camino más largo tiene 3 vértices.
• Quita la infinitud y no hay nada que demostrar.

El lema llega mucho más allá de la teoría de grafos. En su forma de árbol, «un árbol infinito con ramificación finita tiene una rama infinita», es el núcleo combinatorio de los argumentos de compacidad en lógica, y es lo que permite concluir que un cómputo con infinitos estados finitos debe tener una ejecución infinita. Es la misma idea que subyace al teorema de compacidad de la lógica proposicional, que es de donde viene la siguiente sección.

6. De Bruijn y Erdős: la coloración se transfiere

El segundo gran puente toma una propiedad que puede comprobarse en piezas finitas y la eleva a todo el grafo infinito.

Teorema de De Bruijn-Erdős (1951). Para un k finito, un grafo infinito es k-coloreable si y solo si cada uno de sus subgrafos finitos es k-coloreable.

La dirección «solo si» es trivial: una coloración del grafo entero se restringe a cada subgrafo. El contenido está en la otra dirección, y es realmente sorprendente. Dice que la colorabilidad, que es una restricción global sobre infinitos vértices a la vez, queda totalmente determinada por lo que ocurre en ventanas finitas. Nada nuevo puede salir mal «en el infinito».

Dos matices que importan y que las explicaciones divulgativas suelen omitir:

• El número de colores debe ser finito. El teorema trata de un k finito fijo. No dice que un grafo cuyos subgrafos finitos son todos coloreables con finitos colores sea coloreable con finitos colores.
• Necesita un principio de elección. Las demostraciones estándar pasan por el teorema de Tychonoff para espacios de Hausdorff compactos, el lema de Zorn o el lema del ultrafiltro. En la teoría de conjuntos de Zermelo-Fraenkel sin ninguna forma de elección, el teorema no es demostrable. De Bruijn y Erdős trabajaron con el axioma de elección disponible, como casi todo el mundo.

La lectura práctica para quien modela un sistema no acotado: si tu restricción puede expresarse como una coloración con una paleta finita fija, puedes verificarla en fragmentos finitos y concluirla para el todo. Es exactamente la licencia que da un argumento de compacidad, y es la razón por la que la verificación de modelos finita a veces puede decir algo sobre ejecuciones no acotadas.

7. Rayos, rayos dobles y fines

La teoría de grafos finitos no tiene vocabulario para «cómo se ve el grafo a lo lejos», porque un grafo finito no tiene lejanía. La teoría de grafos infinitos lo necesita, y la construcción estándar se debe a Halin.

• Un rayo es un camino infinito en un sentido v0, v1, v2, …. El lema de König dice que todo grafo infinito, conexo y localmente finito tiene uno.
• Un rayo doble es un camino infinito en ambos sentidos, indexado por todo ℤ. Es un árbol infinito sin ninguna hoja, que es justamente lo que ningún árbol finito puede ser.
• Un fin es una clase de equivalencia de rayos, donde dos rayos cuentan como equivalentes cuando ningún conjunto finito de vértices los separa. Los fines son la respuesta formal a «en cuántas direcciones distintas se aleja este grafo hacia el infinito».

La noción se capta mejor con ejemplos que con la definición:

La entrada de la retícula es la instructiva. Intuitivamente un plano se aleja en todas las direcciones, así que esperarías muchos fines, pero la definición pregunta si los rayos pueden separarse quitando finitos vértices, y en una retícula no pueden: si te alejas lo suficiente, siempre puedes rodear cualquier agujero finito. Un fin es la respuesta correcta, y es la definición, no el dibujo, la que lo decide.

8. Árboles de expansión y el axioma de elección

Todo grafo finito conexo tiene un árbol de expansión, y la demostración es un argumento voraz de dos líneas: ve eliminando una arista que esté en un ciclo hasta que no quede ninguno. Termina porque hay finitas aristas.

El enunciado infinito sigue siendo cierto, pero por una razón distinta y mucho más profunda:

Todo grafo conexo tiene un árbol de expansión. Para grafos infinitos esto requiere el axioma de elección, y de hecho el enunciado es equivalente a él.

La demostración habitual aplica el lema de Zorn a la familia de subgrafos acíclicos ordenada por inclusión, que es un principio de elección disfrazado. Que la implicación vaya en ambos sentidos, de modo que «todo grafo conexo tiene un árbol de expansión» no sea solo una consecuencia de la elección sino igual de fuerte, es un resultado realmente llamativo: un enunciado de apariencia inocente sobre grafos resulta ser una de las muchas formas equivalentes de un axioma de la teoría de conjuntos.

La importancia práctica es pequeña y la conceptual es grande. Ningún algoritmo que escribas se verá afectado, porque los grafos que toca un programa son finitos o al menos están presentados de forma computable. Pero marca con precisión dónde la teoría de grafos infinitos deja de ser combinatoria y empieza a ser teoría de conjuntos, y explica por qué los libros sobre grafos infinitos precisan con cuidado qué principios de elección asumen.

El mismo patrón aparece en otros sitios. Varios enunciados rutinarios para grafos finitos resultan, en sus versiones infinitas, depender de la elección o ser independientes de los axiomas básicos, y por eso De Bruijn-Erdős también lleva una hipótesis de elección.

9. El grafo de Rado: un grafo para dominarlos a todos

Los grafos infinitos no son simplemente grafos finitos con más de todo. Algunos se comportan de maneras que no tienen ningún análogo finito, y el ejemplo más limpio es el grafo de Rado.

Se dice que un grafo numerable tiene la propiedad de extensión si, para todo par de conjuntos finitos disjuntos de vértices U y W, existe un vértice unido a todos los vértices de U y a ninguno de W. Entonces:

Unicidad. Dos grafos numerables cualesquiera con la propiedad de extensión son isomorfos. Hay, salvo isomorfismo, exactamente un grafo así: el grafo de Rado, también llamado grafo aleatorio R.

Y la razón por la que se llama grafo aleatorio es la segunda mitad de la historia. Erdős y Rényi demostraron que si construyes un grafo numerable infinito decidiendo cada arista posible de forma independiente con probabilidad 1/2, el resultado cumple la propiedad de extensión con probabilidad 1. Así que:

Lanza una moneda equilibrada por cada par de vértices de un conjunto numerable infinito.
Con probabilidad 1, el grafo que obtienes es el grafo de Rado.
Hazlo otra vez, de otra manera. Vuelves a obtener el grafo de Rado, salvo isomorfismo.

Hay esencialmente un solo grafo aleatorio numerable infinito. Nada remotamente parecido ocurre con los grafos finitos, donde los grafos aleatorios de n vértices son muy variados y las preguntas interesantes tratan de qué propiedades se cumplen con alta probabilidad. El grafo de Rado contiene además todo grafo finito y todo grafo numerable como subgrafo inducido, lo que lo hace universal para los grafos numerables.

Para quien trabaja con grafos, lo importante no es la construcción sino la advertencia que encierra: las intuiciones calibradas con grafos finitos no solo fallan cuantitativamente en el infinito, fallan cualitativamente. «Aleatorio» deja de significar «variado» y pasa a significar «canónico».

10. Cuando lo infinito es más fácil

Sería razonable suponer que los grafos infinitos son siempre más difíciles. A veces ocurre lo contrario, y la teoría de Ramsey es el ejemplo clásico.

Ramsey demostró ambos en su artículo de 1930. La versión infinita es más fácil precisamente porque no pide una cota: nunca tienes que decir a qué distancia aparece la estructura monocromática, solo que aparece. Es posible extraer la versión finita de la infinita mediante un argumento de compacidad de la misma familia que el lema de König, pero las cotas que produce son pésimas, y por eso la teoría de Ramsey finita es una materia aparte y mucho más difícil.

La moraleja general: los enunciados infinitos suelen ser más limpios porque no son cuantitativos. Cuando un teorema finito es difícil por sus cotas, su análogo infinito puede ser mucho más sencillo y aun así decirte algo útil.

11. Grafos infinitos en computación

Los grafos infinitos no son un capricho puramente matemático. Aparecen constantemente en informática, normalmente de forma implícita y siempre bajo el mismo disfraz: un grafo que nunca construyes.

• Espacios de estados. El grafo de configuraciones de una máquina de Turing, de un programa con enteros no acotados o de un protocolo con colas no acotadas es infinito. Verificar un sistema así es exactamente estudiar un grafo infinito presentado mediante una descripción finita.
• Retículas y cuadrículas. La búsqueda de rutas en un mapa de casillas sin límites, los autómatas celulares y las retículas de imágenes viven todos sobre ℤ², un grafo infinito localmente finito.
• Árboles de juego. El árbol completo de un juego sin límite de jugadas es infinito; los algoritmos de búsqueda exploran un prefijo finito de él.
• Grafos de Cayley. Un grupo infinito con un conjunto generador elegido da un grafo infinito transitivo en vértices, y la teoría geométrica de grupos estudia los grupos precisamente a través de estos grafos y sus fines.
• Estructuras definidas recursivamente. El grafo de todas las cadenas finitas bajo «añadir un carácter» es un árbol infinito, y es el objeto al que suele aplicarse el lema de König en computabilidad.

La consecuencia de ingeniería es una única distinción tajante:

En un grafo infinito localmente finito , la búsqueda se vuelve semidecidible. Una búsqueda en anchura desde s encontrará un camino a t si existe, y se ejecutará para siempre si no existe. La finitud local es lo que hace finito cada nivel, de modo que la búsqueda alcanza cada distancia en tiempo finito. Puede confirmar la alcanzabilidad, pero nunca refutarla.

Esa asimetría es la razón por la que BFS y no DFS es la elección correcta en un grafo infinito: BFS explora por orden de distancia y alcanza cualquier vértice alcanzable en tiempo finito, mientras que DFS puede descender por una sola rama infinita y no volver nunca. Es la misma razón por la que existe la profundización iterativa. Para garantizar la terminación hace falta algo más, como la finitud local más una cota, una medida monótona decreciente o una abstracción finita del espacio de estados.

12. Errores comunes

• Suponer que existe un máximo o un mínimo. «Toma el vértice de grado máximo» y «toma el camino más largo» presuponen finitud o una cota explícita. En un grafo infinito pueden no designar nada.
• Usar el corolario de los grados impares. El rayo tiene exactamente un vértice de grado impar, como muestra la sección 4 .
• Inducir sobre el número de vértices. No existe tal número. La inducción transfinita está disponible, pero necesita un buen orden, que es otro recurso a la elección.
• Olvidar la finitud local en el lema de König. La estrella infinita es infinita, conexa y no contiene ningún rayo. La hipótesis no es decorativa.
• Esperar terminación. La búsqueda en un grafo infinito es semidecidible, así que una respuesta «no hay camino» nunca llega. Acota la búsqueda explícitamente o trabaja con una abstracción finita.
• Ejecutar DFS en un grafo infinito. Una sola rama infinita se lo traga. Usa BFS o profundización iterativa.
• Aplicar resultados de conteo finitos. Todo lo demostrado contando vértices, aristas o incidencias necesita revisarse; lo demostrado por compacidad suele sobrevivir.
• Tratar «infinito» como una sola cosa. Numerable frente a no numerable y localmente finito frente a no localmente finito son independientes, y casi todo teorema depende de qué combinación tengas.

13. Glosario

15. Referencias

Las definiciones, teoremas y atribuciones anteriores proceden de estas fuentes, ordenadas cronológicamente.

1. König, D. (1927). "Über eine Schlussweise aus dem Endlichen ins Unendliche." Acta Litterarum ac Scientiarum Regiae Universitatis Hungaricae Francisco-Josephinae, Sectio Scientiarum Mathematicarum (Szeged) 3, 121 a 130. El lema de infinitud.
2. Ramsey, F. P. (1930). "On a Problem of Formal Logic." Proceedings of the London Mathematical Society s2-30, 264 a 286. Contiene los teoremas de Ramsey finito e infinito.
3. König, D. (1936). Theorie der endlichen und unendlichen Graphen. Leipzig: Akademische Verlagsgesellschaft. El primer libro de teoría de grafos, cuyo título ya nombra ambos casos.
4. de Bruijn, N. G. and Erdős, P. (1951). "A Colour Problem for Infinite Graphs and a Problem in the Theory of Relations." Indagationes Mathematicae 13, 369 a 373.
5. Erdős, P. y Rényi, A. (1963). "Asymmetric Graphs." Acta Mathematica Academiae Scientiarum Hungaricae 14, 295 a 315. Contiene la observación de que el grafo aleatorio numerable está determinado salvo isomorfismo.
6. Halin, R. (1964). "Über unendliche Wege in Graphen." Mathematische Annalen 157, 125 a 137. La teoría de los fines de un grafo.
7. Rado, R. (1964). "Universal Graphs and Universal Functions." Acta Arithmetica 9, 331 a 340. La construcción explícita del grafo numerable universal.
8. Cameron, P. J. (1997). "The Random Graph." En R. L. Graham y J. Nešetřil (eds.), The Mathematics of Paul Erdős II, 333 a 351. Berlín: Springer. Un panorama del grafo de Rado y sus propiedades.
9. Bollobás, B. (1998). Modern Graph Theory. Graduate Texts in Mathematics 184. Nueva York: Springer.
10. West, D. B. (2001). Introduction to Graph Theory, 2.ª edición. Upper Saddle River: Prentice Hall.
11. Bondy, J. A. y Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. Londres: Springer.
12. Diestel, R. (2017). Graph Theory, 5.ª edición. Graduate Texts in Mathematics 173. Berlín: Springer. El capítulo 8 está dedicado a los grafos infinitos, los rayos y los fines.