Aplicaciones de la teoría de grafos
Gráficos planos
Se dice que un gráfico G es plano si se puede representar en un plano de tal manera que los vértices sean puntos distintos, los bordes sean curvas simples y no haya dos bordes que se encuentren entre sí, excepto en sus terminales. Por ejemplo, K 4, el gráfico completo en cuatro vértices, es plano, como lo muestra la Figura 4A.
Se dice que dos gráficos son homeomórficos si ambos se pueden obtener del mismo gráfico por subdivisiones de bordes. Por ejemplo, los gráficos en la Figura 4A y la Figura 4B son homeomórficos.
El gráfico K m, n es un gráfico para el cual el conjunto de vértices se puede dividir en dos subconjuntos, uno con m vértices y el otro con n vértices. Dos vértices del mismo subconjunto no son adyacentes, mientras que dos vértices de diferentes subconjuntos son adyacentes. El matemático polaco Kazimierz Kuratowski en 1930 demostró el siguiente famoso teorema:
Una condición necesaria y suficiente para que un gráfico G sea plano es que no contiene un subgrafo homeomorfo a K 5 o K 3,3 que se muestra en la Figura 5.
Una contracción elemental de un gráfico G es una transformación de G a un nuevo gráfico G 1, de modo que dos vértices adyacentes u y υ de G se reemplazan por un nuevo vértice w en G 1 yw es adyacente en G 1 a todos los vértices para que u u u son adyacentes en G. Se dice que un gráfico G * es una contracción de G si G * puede obtenerse de G mediante una secuencia de contracciones elementales. La siguiente es otra caracterización de un gráfico plano debido al matemático alemán K. Wagner en 1937.
Un gráfico es plano si y solo si no es contraíble a K 5 o K 3,3.
El problema del mapa de cuatro colores
Durante más de un siglo, la solución del problema del mapa de cuatro colores eludió a todos los analistas que lo intentaron. El problema puede haber llamado la atención de Möbius, pero la primera referencia escrita parece ser una carta de un tal Francis Guthrie a su hermano, un estudiante de Augustus De Morgan, en 1852.
El problema se refiere a mapas planos, es decir, subdivisiones del plano en regiones no superpuestas delimitadas por simples curvas cerradas. En los mapas geográficos se ha observado empíricamente, en tantos casos especiales como se ha intentado, que, como máximo, se necesitan cuatro colores para colorear las regiones, de modo que dos regiones que comparten un límite común siempre se colorean de manera diferente, y en ciertos casos que son necesarios al menos cuatro colores. (No se considera que las regiones que se encuentran solo en un punto, como los estados de Colorado y Arizona en los Estados Unidos, tengan un límite común). Una formalización de esta observación empírica constituye lo que se llama "el teorema de los cuatro colores". El problema es probar o refutar la afirmación de que este es el caso para cada mapa plano. Que tres colores no serán suficientes se demuestra fácilmente, mientras que la matemática británica PJ Heawood demostró la suficiencia de cinco colores en 1890.
En 1879, AB Kempe, un inglés, propuso una solución al problema de los cuatro colores. Aunque Heawood demostró que el argumento de Kempe era defectuoso, dos de sus conceptos resultaron fructíferos en una investigación posterior. Uno de estos, llamado inevitable, indica correctamente la imposibilidad de construir un mapa en el que no exista cada una de las cuatro configuraciones (estas configuraciones consisten en una región con dos vecinos, uno con tres, uno con cuatro y uno con cinco). El segundo concepto, el de reducibilidad, toma su nombre de la prueba válida de Kempe de que si hay un mapa que requiere al menos cinco colores y que contiene una región con cuatro (o tres o dos) vecinos, entonces debe haber un mapa que requiera cinco colores para un menor número de regiones. El intento de Kempe de demostrar la reducibilidad de un mapa que contiene una región con cinco vecinos fue erróneo, pero fue rectificado en una prueba publicada en 1976 por Kenneth Appel y Wolfgang Haken de los Estados Unidos. Su prueba atrajo algunas críticas porque requería la evaluación de 1,936 casos distintos, cada uno de los cuales involucraba hasta 500,000 operaciones lógicas. Appel, Haken y sus colaboradores diseñaron programas que hicieron posible que una computadora digital grande manejara estos detalles. La computadora requirió más de 1,000 horas para realizar la tarea, y la prueba formal resultante es de varios cientos de páginas.
Ciclos eulerianos y el problema del puente de Königsberg
Un G multigráfico consiste en un conjunto no vacío V (G) de vértices y un subconjunto E (G) del conjunto de pares desordenados de elementos distintos de V (G) con una frecuencia f ≥ 1 unida a cada par. Si el par (x 1, x 2) con frecuencia f pertenece a E (G), entonces los vértices x 1 y x 2 están unidos por f bordes.
Un ciclo euleriano de una G multigráfica es una cadena cerrada en la que cada borde aparece exactamente una vez. Euler demostró que un multigrafo posee un ciclo euleriano si y solo si está conectado (aparte de puntos aislados) y el número de vértices de grado impar es cero o dos.
Este problema surgió primero de la siguiente manera. El río Pregel, formado por la confluencia de sus dos ramas, atraviesa la ciudad de Königsberg y fluye a ambos lados de la isla de Kneiphof. Había siete puentes, como se muestra en la Figura 6A. La gente del pueblo se preguntaba si era posible salir a caminar y cruzar cada puente una sola vez. Esto es equivalente a encontrar un ciclo euleriano para el multigrafo en la Figura 6B. Euler demostró que era imposible porque hay cuatro vértices de orden impar.
