En la teoría de grafos y la optimización combinatoria , el cierre de un grafo dirigido es un conjunto de vértices sin bordes salientes. Es decir, el gráfico no debe tener bordes que comiencen dentro del cierre y terminen fuera del cierre. El problema del cierre es la tarea de encontrar el cierre de peso máximo o mínimo en un gráfico dirigido ponderado por vértice. [1] [2] Se puede resolver en tiempo polinómico usando una reducción al problema de flujo máximo . Se puede usar para modelar varios problemas de aplicación de elegir un subconjunto óptimo de tareas para realizar, con dependencias entre pares de tareas, un ejemplo es la minería a cielo abierto .
Algoritmos [ editar ]
Condensación [ editar ]
El cierre de peso máximo de un gráfico G dado es el mismo que el complemento del cierre de peso mínimo en el gráfico de transposición de G , por lo que los dos problemas son equivalentes en complejidad computacional. Si dos vértices del gráfico pertenecen al mismo componente fuertemente conectado , deben comportarse de la misma manera con respecto a todos los cierres: no es posible que un cierre contenga un vértice sin contener el otro. Por esta razón, el gráfico de entrada a un problema de cierre puede reemplazarse por su condensación , en la que cada componente fuertemente conectado se reemplaza por un solo vértice. La condensación es siempre un gráfico acíclico dirigido .
Reducción al flujo máximo [ editar ]
Como Picard (1976) mostró, [2] [3] un cierre máximo peso se puede obtener de G por la solución de un problema de flujo máximo en un gráfico H construido a partir de G mediante la adición a ella dos vértices adicionales s y t . Para cada vértice v con peso positivo en G , el gráfico aumentada H contiene un borde de s a v con capacidad igual al peso de v , y para cada vértice v con peso negativo en G , el gráfico aumentada Hcontiene una arista de v a t cuya capacidad es la negación del peso de v . Todas las aristas en G se dan capacidad infinita en H . [1]
Un corte mínimo que separa s de t en este gráfico no puede tener bordes de G que pasen en la dirección hacia adelante a través del corte: un corte con dicho borde tendría una capacidad infinita y no sería mínimo. Por lo tanto, el conjunto de vértices en el mismo lado del corte como s automáticamente forma un cierre C . La capacidad del corte es igual al peso de todos los vértices de peso positivo menos el peso de los vértices en C , que se minimiza cuando el peso de C se maximiza. Mediante el teorema de corte mínimo de flujo máximo, se puede encontrar un corte mínimo y el cierre óptimo derivado de él resolviendo un problema de flujo máximo.[1]
Algoritmos alternativos [ editar ]
También se han estudiado algoritmos alternativos para el problema de cierre máximo que no calculan los flujos. [4] [5] [6] Su tiempo de ejecución es similar al de los algoritmos de flujo más rápidos conocidos. [4]
Aplicaciones [ editar ]
Minería a cielo abierto [ editar ]
Una mina a cielo abierto puede modelarse como un conjunto de bloques de material que pueden eliminarse extrayéndolos una vez que se hayan eliminado todos los bloques directamente encima de ella. Un bloque tiene un valor total, igual al valor de los minerales que se pueden extraer de él menos el costo de extracción y extracción; en algunos casos, un bloque no tiene valor de extracción, pero aún debe eliminarse para alcanzar otros bloques, dándole un valor negativo. Se puede definir una red acíclica que tenga como vértices los bloques de una mina, con un borde de cada bloque a los bloques por encima que debe eliminarse antes. El peso de cada vértice en esta red es el valor total de su bloque, y el plan más rentable para la minería se puede determinar encontrando un cierre de peso máximo y luego formando un orden topológicode los bloques en este cierre. [1] [5] [7]
Ataque militar [ editar ]
En las operaciones militares, los objetivos de alto valor, como los centros de comando, con frecuencia están protegidos por capas de sistemas de defensa, que a su vez pueden estar protegidos por otros sistemas. Para alcanzar un objetivo, todas sus defensas deben ser derribadas, convirtiéndolo en un objetivo secundario. Cada objetivo necesita que se le asigne una cierta cantidad de recursos para realizar un ataque exitoso. El conjunto óptimo de objetivos para atacar, para obtener el mayor valor por los recursos gastados, puede modelarse como un problema de cierre. [1] [8]
Diseño de red de transporte [ editar ]
El problema de planificar un sistema de entrega de carga puede ser modelado por una red en la cual los vértices representan ciudades y los bordes (no dirigidos) representan posibles rutas de entrega de carga entre pares de ciudades. Cada ruta puede lograr una cierta ganancia, pero solo se puede usar si se construyen depósitos de carga en ambos extremos, con un cierto costo. El problema de diseñar una red que maximice la diferencia entre las ganancias y los costos puede resolverse como un problema de cierre, subdividiendo cada borde no dirigido en dos bordes dirigidos, ambos dirigidos hacia afuera desde el punto de subdivisión. El peso de cada punto de subdivisión es un número positivo, el beneficio de la ruta correspondiente y el peso de cada vértice gráfico original es un número negativo, el costo de construir un depósito en esa ciudad. [1] [9]Junto con la minería a cielo abierto, esta fue una de las aplicaciones motivadoras originales para estudiar el problema del cierre; fue originalmente estudiado en 1970, en dos artículos independientes publicados en el mismo número de la misma revista por JMW Rhys y Michel Balinski . [9] [10] [11]
Programación de trabajos [ editar ]
Sidney (1975) y Lawler (1978) describen una aplicación del problema de cierre a una versión de la programación del taller de trabajo en la que se le da una colección de tareas que se programarán para que se realicen, una por una. Cada tarea tiene dos números asociados: un peso o prioridad, y un tiempo de procesamiento, la cantidad de tiempo que lleva realizar esa tarea. Además, las tareas tienen restricciones de precedencia: ciertas tareas deben realizarse antes que otras. Estas restricciones de precedencia se pueden describir mediante un gráfico acíclico dirigido G en el que un borde de una tarea a otra indica que la primera tarea debe realizarse antes que la segunda. El objetivo es elegir un orden que sea consistente con estas restricciones (unordenamiento topológico de G ) que minimiza el tiempo de finalización ponderado total de las tareas. [12] [13]
Aunque (como muestra Lawler) este problema de programación es NP-completo en general, Sidney describe un método de descomposición que puede ayudar a resolver el problema reduciéndolo a varios problemas más pequeños del mismo tipo. En particular, si S es un subconjunto de las tareas que (entre todos los subconjuntos) tiene la mayor relación posible de su peso total a su tiempo de procesamiento total, y además S es mínimo entre todos los conjuntos con la misma relación, entonces existe un Programa óptimo en el que todas las tareas en S se realizan antes que todas las demás tareas. Mientras S no sea el conjunto completo de tareas, esta partición de las tareas divide el problema de programación en dos problemas más pequeños, uno de programación Sy uno de programar las tareas restantes. [12] Aunque S es un cierre (para un gráfico con bordes invertidos de G ), el problema de encontrar S no es exactamente un problema de cierre de peso máximo, porque el valor de S es una relación en lugar de una suma de pesos. Sin embargo, Lawler muestra que S puede encontrarse en el tiempo polinomial mediante un algoritmo de búsqueda binaria en el que cada paso de la búsqueda utiliza una instancia del problema de cierre como una subrutina.
En la teoría de grafos , el complemento o inversa de un gráfico G es un gráfico H en los mismos vértices de tal manera que dos vértices distintos de H son adyacentes si y sólo si no son adyacentes en G . Es decir, para generar el complemento de un gráfico, se rellenan todos los bordes faltantes necesarios para formar un gráfico completo y se eliminan todos los bordes que estaban previamente allí. [1] Sin embargo, no es el conjunto de complemento del gráfico; solo se complementan los bordes.
Definición [ editar ]
Supongamos que G = ( V , E ) sea un gráfico simple y que K consista en todos los subconjuntos de V de 2 elementos . Entonces H = ( V , K \ E ) es el complemento de G , [2] donde K \ E es el complemento relativa de E en K . Para gráficos dirigidos , el complemento se puede definir de la misma manera, como un gráfico dirigido en el mismo conjunto de vértices, utilizando el conjunto de todos los pares ordenados de 2 elementosde V en lugar del conjunto K en la fórmula anterior.
El complemento no está definido para multigrafos . En los gráficos que permiten bucles automáticos (pero no adyacencias múltiples), el complemento de G puede definirse agregando un bucle automático a cada vértice que no tenga uno en G y, de lo contrario, utilizando la misma fórmula que la anterior. Sin embargo, esta operación es diferente de la de los gráficos simples, ya que aplicarla a un gráfico sin bucles automáticos daría como resultado un gráfico con bucles automáticos en todos los vértices.
Aplicaciones y ejemplos [ editar ]
Varios conceptos teóricos de gráficos están relacionados entre sí a través de gráficos complementarios:
- El complemento de un gráfico sin bordes es un gráfico completo y viceversa.
- Cualquier subgrafo inducido de la gráfica complemento de un gráfico G es el complemento de la subgrafo inducido correspondiente en G .
- Un conjunto independiente en un gráfico es una camarilla en el gráfico del complemento y viceversa. Este es un caso especial de las dos propiedades anteriores, ya que un conjunto independiente es una subgrafía inducida sin bordes y una camarilla es una subgrafía inducida completa.
- El grupo de automorfismo de un gráfico es el grupo de automorfismo de su complemento.
- El complemento de cada gráfico sin triángulo es un gráfico sin garras , [3] aunque lo contrario no es cierto.
Gráficos autocomplementarios y clases de gráficos [ editar ]
Un gráfico autocomplementario es un gráfico que es isomorfo a su propio complemento. [1] Los ejemplos incluyen el gráfico de ruta de cuatro vértices y el gráfico de ciclo de cinco vértices .
Varias clases de gráficos son autocomplementarios, en el sentido de que el complemento de cualquier gráfico en una de estas clases es otro gráfico en la misma clase.
- Los gráficos perfectos son aquellos en los que, para cada subgrafo inducido, el número cromático es igual al tamaño de la camarilla máxima. El hecho de que el complemento de una gráfica perfecta también sea perfecto es el teorema de la gráfica perfecta de László Lovász . [4]
- Los cográficos se definen como los gráficos que se pueden construir a partir de vértices únicos mediante operaciones de unión y complementación disjuntas . Forman una familia de gráficos autocomplementarios: el complemento de cualquier cografía es otra cografía diferente. Para los cogramas de más de un vértice, se conecta exactamente un gráfico en cada par complementario, y una definición equivalente de los cogramas es que cada uno de sus subgrafos inducidos conectados tiene un complemento desconectado. Otra definición autocomplementaria es que son los gráficos sin subgrafo inducido en forma de una ruta de cuatro vértices. [5]
- Otra clase de gráficos autocomplementarios es la clase de gráficos divididos , los gráficos en los que los vértices se pueden dividir en una camarilla y un conjunto independiente. La misma partición da un conjunto independiente y una camarilla en el gráfico del complemento. [6]
- Los gráficos de umbral son los gráficos formados al agregar repetidamente un vértice independiente (uno sin vecinos) o un vértice universal (adyacente a todos los vértices agregados previamente). Estas dos operaciones son complementarias y generan una clase de gráficos autocomplementarios. [7]
Aspectos algorítmicos [ editar ]
En el análisis de algoritmos en gráficos, la distinción entre un gráfico y su complemento es importante, porque un gráfico escaso (uno con un pequeño número de aristas en comparación con el número de pares de vértices) en general no tendrá un complemento escaso y, por lo tanto, un algoritmo que lleva un tiempo proporcional al número de aristas en un gráfico dado puede tomar una cantidad de tiempo mucho mayor si se ejecuta el mismo algoritmo en una representación explícita del gráfico del complemento. Por lo tanto, los investigadores han estudiado algoritmos que realizan cálculos gráficos estándar en el complemento de un gráfico de entrada, utilizando una representación gráfica implícita que no requiere la construcción explícita del gráfico complementario. En particular, es posible simularbúsqueda en profundidad o búsqueda en amplitud en el gráfico del complemento, en una cantidad de tiempo que es lineal en el tamaño del gráfico dado, incluso cuando el gráfico del complemento puede tener un tamaño mucho mayor. [8] También es posible utilizar estas simulaciones para calcular otras propiedades relacionadas con la conectividad del gráfico del complemento.
En matemáticas , el teorema de los cuatro colores , o el teorema del mapa de cuatro colores , establece que, dada cualquier separación de un plano en regiones contiguas , produciendo una figura llamada mapa , no se requieren más de cuatro colores para colorear las regiones del mapa. que no hay dos regiones adyacentes que tengan el mismo color. Adyacente significa que dos regiones comparten un segmento de curva de límite común, no simplemente una esquina donde se encuentran tres o más regiones. [1] Fue el primer teorema importante que se probó usando una computadora . Inicialmente, esta prueba no fue aceptada por todos los matemáticos porque la prueba asistida por computadoraera inviable que un humano lo revisara a mano . [2] Desde entonces, la prueba ha ganado una gran aceptación, aunque algunos dudan. [3]
El teorema de los cuatro colores fue probado en 1976 por Kenneth Appel y Wolfgang Haken después de muchas pruebas falsas y contraejemplos (a diferencia del teorema de los cinco colores , un teorema que establece que cinco colores son suficientes para colorear un mapa, que se demostró en el siglo XIX). Para disipar cualquier duda restante sobre la prueba Appel-Haken, Robertson, Sanders, Seymour y Thomas publicaron en 1997 una prueba más simple que utilizaba las mismas ideas y seguía confiando en las computadoras. Además, en 2005, Georges Gonthier probó el teorema con un software de prueba de teoremas de propósito general .
Formulación precisa del teorema [ editar ]
En términos de teoría de grafos, el teorema establece que para planar sin bucle , el número cromático de su gráfico dual es.
La declaración intuitiva del teorema de los cuatro colores, es decir, "dada cualquier separación de un plano en regiones contiguas, las regiones se pueden colorear usando como máximo cuatro colores para que no haya dos regiones adyacentes que tengan el mismo color", debe interpretarse de manera apropiada para ser correcto.
Primero, las regiones son adyacentes si comparten un segmento límite; dos regiones que comparten solo puntos límite aislados no se consideran adyacentes. Segundo, no se permiten regiones extrañas, como aquellas con área finita pero perímetro infinitamente largo; Los mapas con tales regiones pueden requerir más de cuatro colores. [4] (Para estar seguros, podemos restringir a las regiones cuyos límites consisten en un número finito de segmentos de línea recta. Se permite que una región rodee por completo una o más regiones). Tenga en cuenta que la noción de "región contigua" (técnicamente: el subconjunto abierto conectado del avión) no es lo mismo que el de un "país" en los mapas regulares, ya que los países no necesitan ser contiguos (por ejemplo, la provincia de Cabinda como parte de Angola ,Nakhchivan como parte de Azerbaiyán , Kaliningrado como parte de Rusia y Alaska como parte de los Estados Unidos no son contiguos). Si requerimos que todo el territorio de un país reciba el mismo color, entonces cuatro colores no siempre son suficientes. Por ejemplo, considere un mapa simplificado:
En este mapa, las dos regiones etiquetadas A pertenecen al mismo país. Si quisiéramos que esas regiones recibieran el mismo color, se requerirían cinco colores, ya que las dos regiones A juntas son adyacentes a otras cuatro regiones, cada una de las cuales es adyacente a todas las demás. Una construcción similar también se aplica si se usa un solo color para todos los cuerpos de agua, como es habitual en los mapas reales. Para los mapas en los que más de un país puede tener múltiples regiones desconectadas, se pueden requerir seis o más colores.
Una declaración más simple del teorema utiliza la teoría de grafos . El conjunto de regiones de un mapa se puede representar de manera más abstracta como un gráfico no dirigido que tiene un vértice para cada región y un borde para cada par de regiones que comparten un segmento de límite. Este gráfico es plano: se puede dibujar en el plano sin cruces colocando cada vértice en una ubicación elegida arbitrariamente dentro de la región a la que corresponde, y dibujando los bordes como curvas sin cruces que conducen desde el vértice de una región, a través de un segmento de límite compartido, hasta vértice de una región adyacente. Por el contrario, cualquier gráfico plano puede formarse a partir de un mapa de esta manera. En la terminología teórica de grafos, el teorema de cuatro colores establece que los vértices de cada gráfico plano pueden colorearse como máximo con cuatro colores para que no haya dos vértices adyacentes que reciban el mismo color, o para abreviar:
- Cada gráfico plano es de cuatro colores . [5]
Historia [ editar ]
Intentos de prueba tempranos [ editar ]
Hasta donde se sabe, [6] la conjetura se propuso por primera vez el 23 de octubre de 1852 [7] cuando Francis Guthrie , mientras intentaba colorear el mapa de los condados de Inglaterra, notó que solo se necesitaban cuatro colores diferentes. En ese momento, el hermano de Guthrie, Frederick, era estudiante de Augustus De Morgan (el ex asesor de Francis) en el University College de Londres . Francis preguntó a Frederick al respecto, quien luego se lo llevó a De Morgan (Francis Guthrie se graduó más tarde en 1852 y luego se convirtió en profesor de matemáticas en Sudáfrica). De acuerdo con De Morgan:
"FG", quizás uno de los dos Guthries, publicó la pregunta en The Athenaeum en 1854, [8] y De Morgan volvió a plantear la pregunta en la misma revista en 1860. [9] Otra referencia publicada por Arthur Cayley ( 1879 ) a su vez atribuye la conjetura a De Morgan.
Hubo varios intentos fallidos de probar el teorema. De Morgan creía que se debía a un hecho simple sobre cuatro regiones, aunque no creía que ese hecho pudiera derivarse de hechos más elementales.
Una supuesta prueba fue dada por Alfred Kempe en 1879, que fue ampliamente aclamada; [10] otro fue dado por Peter Guthrie Tait en 1880. No fue hasta 1890 que la prueba de Kempe se demostró incorrecta por Percy Heawood , y en 1891, la prueba de Tait se demostró incorrecta por Julius Petersen falsa prueba -cada se paró sin respuesta desde hace 11 años. [11]
En 1890, además de exponer el defecto en la prueba de Kempe, Heawood probó el teorema de los cinco colores y generalizó la conjetura de los cuatro colores a superficies de género arbitrario. [12]
Tait, en 1880, mostró que el teorema de los cuatro colores es equivalente a la afirmación de que cierto tipo de gráfico (llamado snark en la terminología moderna) debe ser no plano . [13]
En 1943, Hugo Hadwiger formuló la conjetura de Hadwiger , [14] una generalización de gran alcance del problema de los cuatro colores que aún no se ha resuelto.
Prueba por computadora [ editar ]
Durante las décadas de 1960 y 1970, el matemático alemán Heinrich Heesch desarrolló métodos para usar computadoras para buscar una prueba. Cabe destacar que fue el primero en utilizar la descarga para probar el teorema, que resultó ser importante en la parte inevitable de la prueba posterior de Appel-Haken. También amplió el concepto de reducibilidad y, junto con Ken Durre, desarrolló una prueba de computadora para ello. Desafortunadamente, en esta coyuntura crítica, no pudo obtener el tiempo necesario de la supercomputadora para continuar su trabajo. [15]
Otros adoptaron sus métodos y su enfoque asistido por computadora. Mientras otros equipos de matemáticos competían para completar pruebas, Kenneth Appel y Wolfgang Haken de la Universidad de Illinois anunciaron, el 21 de junio de 1976 [16], que habían demostrado el teorema. Fueron asistidos en algún trabajo algorítmico por John A. Koch . [15]
Si la conjetura de cuatro colores fuera falsa, habría al menos un mapa con el menor número posible de regiones que requiera cinco colores. La prueba mostró que un contraejemplo tan mínimo no puede existir, mediante el uso de dos conceptos técnicos: [17]
- Un conjunto inevitable es un conjunto de configuraciones de modo que cada mapa que satisfaga algunas condiciones necesarias para ser una triangulación mínima no colorable en 4 (como tener un grado mínimo 5) debe tener al menos una configuración de este conjunto.
- Una configuración reducible es una disposición de países que no puede ocurrir en un contraejemplo mínimo. Si un mapa contiene una configuración reducible, entonces el mapa puede reducirse a un mapa más pequeño. Este mapa más pequeño tiene la condición de que si se puede colorear con cuatro colores, entonces el mapa original también. Esto implica que si el mapa original no puede colorearse con cuatro colores, el mapa más pequeño tampoco puede hacerlo, por lo que el mapa original no es mínimo.
Utilizando reglas y procedimientos matemáticos basados en propiedades de configuraciones reducibles, Appel y Haken encontraron un conjunto inevitable de configuraciones reducibles, lo que demuestra que no podría existir un contraejemplo mínimo para la conjetura de cuatro colores. Su prueba redujo la infinitud de mapas posibles a 1.834 configuraciones reducibles (luego reducidas a 1.482) que tuvieron que verificarse una por una por computadora y tomaron más de mil horas. Esta parte del trabajo de reducibilidad se verificó de forma independiente con diferentes programas y computadoras. Sin embargo, la parte inevitable de la prueba se verificó en más de 400 páginas de microfichas , que tuvieron que verificarse a mano con la ayuda de la hija de Haken, Dorothea Blostein ( Appel & Haken 1989 ).
El anuncio de Appel y Haken fue ampliamente informado por los medios de comunicación de todo el mundo, y el departamento de matemáticas de la Universidad de Illinois utilizó un matasellos que decía "Cuatro colores son suficientes". Al mismo tiempo, la naturaleza inusual de la prueba —fue el primer teorema importante que se demostró con una amplia asistencia informática— y la complejidad de la parte verificable por los humanos suscitó una gran controversia ( Wilson 2014 ).
A principios de la década de 1980, se difundieron rumores de una falla en la prueba Appel-Haken. Ulrich Schmidt en RWTH Aachen había examinado las pruebas de Appel y Haken para su tesis de maestría publicada en 1981 ( Wilson 2014 , 225). Había verificado aproximadamente el 40% de la porción inevitable y encontró un error significativo en el procedimiento de descarga ( Appel y Haken 1989 ). En 1986, el editor de Mathematical Intelligencer les pidió a Appel y Haken que escribieran un artículo que abordara los rumores de fallas en su prueba. Respondieron que los rumores se debían a una "mala interpretación de los resultados [de Schmidt]" y se vieron obligados con un artículo detallado ( Wilson 2014 , 225–226). Su obra magna ,Cada Planar Map es Four-Colorable , un libro que reclama una prueba completa y detallada (con un suplemento de microfichas de más de 400 páginas), apareció en 1989; explicó y corrigió el error descubierto por Schmidt, así como varios otros errores encontrados por otros ( Appel y Haken 1989 ).
Simplificación y verificación [ editar ]
Desde la demostración del teorema, se han encontrado algoritmos eficientes para mapas de 4 colores que requieren solo el tiempo O ( n 2 ), donde n es el número de vértices. En 1996, Neil Robertson , Daniel P. Sanders , Paul Seymour , y Robin Thomas crearon un tiempo cuadrática algoritmo, mejorando en un cuártica algoritmo basado en la prueba -tiempo Appel y Haken de. [18]Esta nueva prueba es similar a la de Appel y Haken, pero es más eficiente porque reduce la complejidad del problema y requiere verificar solo 633 configuraciones reducibles. Tanto las partes de inevitabilidad como de reducibilidad de esta nueva prueba deben ejecutarse por computadora y no es práctico verificarlas a mano. [19] En 2001, los mismos autores anunciaron una prueba alternativa, probando el teorema de snark . [20]
En 2005, Benjamin Werner y Georges Gonthier formalizaron una prueba del teorema dentro del asistente de pruebas Coq . Esto eliminó la necesidad de confiar en los diversos programas de computadora utilizados para verificar casos particulares; solo es necesario confiar en el núcleo Coq. [21]
Resumen de ideas de prueba [ editar ]
La siguiente discusión es un resumen basado en la introducción de Cada mapa plano es cuatro colorable ( Appel y Haken 1989 ). Aunque defectuoso, la supuesta prueba original de Kempe del teorema de los cuatro colores proporcionó algunas de las herramientas básicas que luego se usaron para probarlo. La explicación aquí se reformula en términos de la formulación moderna de la teoría de grafos anterior.
El argumento de Kempe es el siguiente. Primero, si las regiones planas separadas por el gráfico no están trianguladas , es decir, no tienen exactamente tres bordes en sus límites, podemos agregar bordes sin introducir nuevos vértices para hacer que cada región sea triangular, incluida la región externa sin límites. Si este gráfico triangulado se puede colorear con cuatro colores o menos, también lo es el gráfico original, ya que el mismo color es válido si se eliminan los bordes. Por lo tanto, es suficiente probar el teorema de cuatro colores para gráficos triangulados para probarlo para todos los gráficos planos, y sin pérdida de generalidad asumimos que el gráfico es triangulado.
Supongamos que v , e y f son el número de vértices, aristas y regiones (caras). Como cada región es triangular y cada borde es compartido por dos regiones, tenemos que 2 e = 3 f . Esto, junto con la fórmula de Euler , v - e + f = 2, se puede usar para mostrar que 6 v - 2 e = 12. Ahora, el grado de un vértice es el número de aristas contiguas. Si v n es el número de vértices de grado n , y D es el grado máximo de cualquier vértice,
Pero como 12> 0 y 6 - i ≤ 0 para todo i ≥ 6, esto demuestra que hay al menos un vértice de grado 5 o menos.
Si hay un gráfico que requiere 5 colores, entonces hay un gráfico mínimo , donde eliminar cualquier vértice lo hace de cuatro colores. Llame a este gráfico G . Entonces G no puede tener un vértice de grado 3 o menos, porque si d ( v ) ≤ 3, podemos eliminar v de G , colorear cuatro veces el gráfico más pequeño, luego agregar de nuevo v y extender el color de cuatro eligiendo un color diferente de sus vecinos.
Kempe también mostró correctamente que G no puede tener vértices de grado 4. Al igual que antes, eliminamos el vértice v y aplicamos cuatro colores a los vértices restantes. Si los cuatro vecinos de v son de diferentes colores, por ejemplo, rojo, verde, azul y amarillo en el sentido de las agujas del reloj, buscamos una ruta alterna de vértices de color rojo y azul que se unan a los vecinos rojo y azul. Tal camino se llama cadena Kempe. Puede haber una cadena Kempe uniendo los vecinos rojo y azul, y puede haber una cadena Kempe uniendo los vecinos verde y amarillo, pero no ambos, ya que estos dos caminos necesariamente se cruzan, y el vértice donde se cruzan no puede ser coloreado. Supongamos que son los vecinos rojos y azules los que no están encadenados. Explore todos los vértices unidos al vecino rojo por caminos alternos rojo-azul, y luego invierta los colores rojo y azul en todos estos vértices. El resultado sigue siendo un color cuatro válido, y v ahora se puede volver a agregar y colorear en rojo.
Esto deja solo el caso donde G tiene un vértice de grado 5; pero el argumento de Kempe fue defectuoso para este caso. Heawood notó el error de Kempe y también observó que si uno estaba satisfecho con probar que solo se necesitaban cinco colores, uno podría pasar por el argumento anterior (cambiando solo que el contraejemplo mínimo requiere 6 colores) y usar cadenas de Kempe en la situación de grado 5 para probar el Teorema de cinco colores .
En cualquier caso, para tratar este caso de vértice de grado 5 se requiere una noción más complicada que la eliminación de un vértice. Más bien, la forma del argumento se generaliza a considerar configuraciones , que son subgrafías conectadas de G con el grado de cada vértice (en G) especificado. Por ejemplo, el caso descrito en el grado 4 situación vértice es la configuración que consiste en un solo vértice etiquetado como que tiene un grado 4 en G . Como se indicó anteriormente, es suficiente demostrar que si se elimina la configuración y el gráfico restante tiene cuatro colores, entonces el color puede modificarse de tal manera que cuando se vuelve a agregar la configuración, el color cuatro se puede extender a él como bien. Una configuración para la que esto es posible se denomina configuración reducible. Si al menos uno de un conjunto de configuraciones debe ocurrir en algún lugar de G, ese conjunto se llama inevitable . El argumento anterior comenzó dando un conjunto inevitable de cinco configuraciones (un solo vértice con grado 1, un solo vértice con grado 2, ..., un solo vértice con grado 5) y luego pasó a mostrar que los primeros 4 son reducibles; exhibir un conjunto inevitable de configuraciones donde cada configuración en el conjunto es reducible probaría el teorema.
Debido a que G es triangular, se conoce el grado de cada vértice en una configuración, y se conocen todos los bordes internos de la configuración, el número de vértices en G adyacentes a una configuración dada es fijo, y se unen en un ciclo. Estos vértices forman el anillo de la configuración; una configuración con k vértices en su anillo es una configuración de anillo k , y la configuración junto con su anillo se llama configuración anillada . Como en los casos simples anteriores, uno puede enumerar todos los cuatro colores distintos del anillo; cualquier coloración que se pueda extender sin modificación a una coloración de la configuración se llama inicialmente buena. Por ejemplo, la configuración de un solo vértice anterior con 3 o menos vecinos fue inicialmente buena. En general, el gráfico circundante debe volverse a colorear sistemáticamente para convertir el color del anillo en uno bueno, como se hizo en el caso anterior donde había 4 vecinos; Para una configuración general con un anillo más grande, esto requiere técnicas más complejas. Debido a la gran cantidad de cuatro colores distintos del anillo, este es el paso principal que requiere asistencia informática.
Finalmente, queda por identificar un conjunto inevitable de configuraciones susceptibles de reducción mediante este procedimiento. El método principal utilizado para descubrir dicho conjunto es el método de descarga . La idea intuitiva que subyace a la descarga es considerar el gráfico plano como una red eléctrica. Inicialmente, la "carga eléctrica" positiva y negativa se distribuye entre los vértices para que el total sea positivo.
Recuerde la fórmula anterior:
A cada vértice se le asigna una carga inicial de 6 grados ( v ). Luego, uno "fluye" la carga redistribuyendo sistemáticamente la carga desde un vértice a sus vértices vecinos de acuerdo con un conjunto de reglas, el procedimiento de descarga . Como se conserva la carga, algunos vértices todavía tienen carga positiva. Las reglas restringen las posibilidades de configuraciones de vértices cargados positivamente, por lo que enumerar todas estas configuraciones posibles proporciona un conjunto inevitable.
Mientras algún miembro del conjunto inevitable no sea reducible, el procedimiento de descarga se modifica para eliminarlo (al introducir otras configuraciones). El procedimiento de descarga final de Appel y Haken fue extremadamente complejo y, junto con una descripción del conjunto de configuración inevitable resultante, llenó un volumen de 400 páginas, pero las configuraciones que generó podrían verificarse mecánicamente para ser reducibles. La verificación por pares durante varios años verificó el volumen que describe la configuración inevitable en sí.
Un detalle técnico no discutido aquí pero requerido para completar la prueba es la reducibilidad de inmersión .
Falsas distorsiones [ editar ]
El teorema de los cuatro colores ha sido conocido por atraer una gran cantidad de pruebas falsas y refutaciones en su larga historia. Al principio, The New York Times se negó por política a informar sobre la prueba Appel-Haken, temiendo que la prueba se mostrara falsa como las anteriores ( Wilson 2014 ). Algunas presuntas pruebas, como las de Kempe y Tait mencionadas anteriormente, estuvieron bajo escrutinio público durante más de una década antes de ser refutadas. Pero muchos más, escritos por aficionados, nunca fueron publicados.
En general, los contraejemplos más simples, aunque inválidos, intentan crear una región que toque todas las demás regiones. Esto obliga a las regiones restantes a colorearse con solo tres colores. Debido a que el teorema de los cuatro colores es verdadero, esto siempre es posible; sin embargo, debido a que la persona que dibuja el mapa está enfocada en una región grande, no se dan cuenta de que las regiones restantes pueden ser coloreadas con tres colores.
Este truco puede generalizarse: hay muchos mapas en los que si los colores de algunas regiones se seleccionan de antemano, es imposible colorear las regiones restantes sin exceder los cuatro colores. Un verificador casual del contraejemplo puede no pensar en cambiar los colores de estas regiones, por lo que el contraejemplo aparecerá como si fuera válido.
Quizás un efecto subyacente a esta idea errónea común es el hecho de que la restricción de color no es transitiva : una región solo tiene que tener un color diferente de las regiones que toca directamente, no las regiones que tocan las regiones que toca. Si esta fuera la restricción, las gráficas planas requerirían arbitrariamente grandes cantidades de colores.
Otras falsas distorsiones violan los supuestos del teorema de maneras inesperadas, como el uso de una región que consta de múltiples partes desconectadas, o no permiten que regiones del mismo color se toquen en un punto.
Tres colores [ editar ]
Si bien cada mapa plano puede colorearse con cuatro colores, es NP-completo en complejidad decidir si un mapa plano arbitrario puede colorearse con solo tres colores. [22]
Generalizaciones [ editar ]
El teorema de los cuatro colores se aplica no solo a los gráficos planos finitos, sino también a los gráficos infinitos que se pueden dibujar sin cruces en el plano, y aún más generalmente a los gráficos infinitos (posiblemente con un número incontable de vértices) para los que cada subgrafo finito es plano Para probar esto, se puede combinar una prueba del teorema para gráficos planos finitos con el teorema de De Bruijn-Erd que establece que, si cada subgrafo finito de un gráfico infinito es k -colorable, entonces todo el gráfico también es k -polorable Nash- Williams (1967) . Esto también puede ser visto como una consecuencia inmediata de Kurt Godel 's teorema de compacidad para la lógica de primer orden, simplemente expresando la capacidad de coloración de un gráfico infinito con un conjunto de fórmulas lógicas.
También se puede considerar el problema de coloración en superficies distintas al plano ( Weisstein ). El problema en la esfera o el cilindro es equivalente al del plano. Para cerrada (orientable o no orientable) superficies con positivos género , el número máximo p de colores necesarios depende de la superficie característica de Euler χ acuerdo con la fórmula
Alternativamente, para una superficie orientable , la fórmula se puede dar en términos del género de una superficie, g :
-
- ( Weisstein )
Esta fórmula, la conjetura de Heawood , fue conjeturada por PJ Heawood en 1890 y probada por Gerhard Ringel y JWT Youngs en 1968. La única excepción a la fórmula es la botella de Klein , que tiene la característica de Euler 0 (por lo tanto, la fórmula da p = 7) y requiere solo 6 colores, como lo muestra P. Franklin en 1934 ( Weisstein ).
Por ejemplo, el toro tiene la característica de Euler χ = 0 (y el género g = 1) y, por lo tanto, p = 7, por lo que no se requieren más de 7 colores para colorear cualquier mapa en un toro. Este límite superior de 7 es nítido: ciertos poliedros toroidales como el poliedro Szilassi requieren siete colores.
Una tira de Möbius requiere seis colores ( Tietze 1910 ) al igual que los gráficos de 1 plano (gráficos dibujados con como máximo un cruce simple por borde) ( Borodin 1984 ). Si tanto los vértices como las caras de un gráfico plano están coloreados, de tal manera que no haya dos vértices adyacentes, caras o pares de vértices-caras que tengan el mismo color, entonces nuevamente se necesitan seis colores como máximo ( Borodin 1984 ).
No hay una extensión obvia del resultado de coloración a regiones sólidas tridimensionales. Al usar un conjunto de n varillas flexibles, se puede hacer que cada varilla toque a cualquier otra varilla. El conjunto requeriría n colores, o n +1 si considera el espacio vacío que también toca cada barra. Se puede tomar el número n como cualquier número entero, tan grande como se desee. Tales ejemplos fueron conocidos por Fredrick Guthrie en 1880 ( Wilson 2014 ). Incluso para los cuboides paralelos al eje (considerados adyacentes cuando dos cuboides comparten un área límite bidimensional) puede ser necesario un número ilimitado de colores ( Reed y Allwright 2008 ; Magnant y Martin (2011) ).
No hay comentarios:
Publicar un comentario