En teoría de grafos , el teorema de Robertson-Seymour (también llamado teorema del grafo menor [1] ) establece que los grafos no dirigidos , parcialmente ordenados por la relación del grafo menor , forman un cuasiordenamiento bien . [2] De manera equivalente, cada familia de grafos que está cerrada bajo menores puede definirse por un conjunto finito de menores prohibidos , de la misma manera que el teorema de Wagner caracteriza a los grafos planos como los grafos que no tienen el grafo completo K 5 o el gráfico bipartito completo K 3,3 como menores.
El teorema de Robertson-Seymour lleva el nombre de los matemáticos Neil Robertson y Paul D. Seymour , quienes lo demostraron en una serie de veinte artículos que abarcan más de 500 páginas entre 1983 y 2004. [3] Antes de su demostración, el enunciado del teorema se conocía como Conjetura de Wagner en honor al matemático alemán Klaus Wagner , aunque Wagner dijo que nunca la conjeturó. [4]
Un resultado más débil para los árboles está implícito en el teorema del árbol de Kruskal , que fue conjeturado en 1937 por Andrew Vázsonyi y demostrado en 1960 de forma independiente por Joseph Kruskal y S. Tarkowski. [5]
Un menor de un gráfico no dirigido G es cualquier gráfico que pueda obtenerse de G mediante una secuencia de cero o más contracciones de aristas de G y eliminaciones de aristas y vértices de G. La relación menor forma un orden parcial en el conjunto de todos los grafos finitos no dirigidos distintos, ya que obedece a los tres axiomas de órdenes parciales: es reflexiva (cada grafo es menor de sí mismo), transitiva (un menor de un menor de G es en sí mismo un menor de G ), y antisimétrico (si dos gráficos G y H son menores entre sí, entonces deben ser isomorfos ). Sin embargo, si los grafos que son isomórficos pueden considerarse objetos distintos, entonces el ordenamiento menor en los grafos forma un preorden , una relación que es reflexiva y transitiva pero no necesariamente antisimétrica. [6]
Se dice que un preorden forma un cuasiordenamiento si no contiene ni una cadena descendente infinita ni una anticadena infinita . [7] Por ejemplo, el orden habitual de los números enteros no negativos es un cuasi ordenamiento, pero el mismo orden en el conjunto de todos los números enteros no lo es, porque contiene la cadena descendente infinita 0, −1, −2. , −3... Otro ejemplo es el conjunto de los números enteros positivos ordenados por divisibilidad , que no tiene cadenas descendentes infinitas, pero donde los números primos constituyen una anticadena infinita.
El teorema de Robertson-Seymour establece que los gráficos finitos no dirigidos y los gráficos menores forman un cuasiordenamiento bien. La relación menor del gráfico no contiene ninguna cadena descendente infinita, porque cada contracción o eliminación reduce el número de aristas y vértices del gráfico (un número entero no negativo). [8] La parte no trivial del teorema es que no hay anticadenas infinitas, conjuntos infinitos de gráficos que no están relacionados entre sí por el orden menor. Si S es un conjunto de gráficos y M es un subconjunto de S que contiene un gráfico representativo para cada clase de equivalencia de elementos mínimos (gráficos que pertenecen a S pero para los cuales ningún menor propio pertenece a S ), entonces M forma una anticadena; por lo tanto, una forma equivalente de enunciar el teorema es que, en cualquier conjunto infinito S de gráficos, debe haber sólo un número finito de elementos mínimos no isomorfos.
Otra forma equivalente del teorema es que, en cualquier conjunto infinito S de gráficos, debe haber un par de gráficos, uno de los cuales es menor del otro. [8] La afirmación de que todo conjunto infinito tiene un número finito de elementos mínimos implica esta forma del teorema, ya que si solo hay un número finito de elementos mínimos, entonces cada uno de los gráficos restantes debe pertenecer a un par de este tipo con uno de los mínimos. elementos. Y en la otra dirección, esta forma del teorema implica la afirmación de que no puede haber anticadenas infinitas, porque una anticadena infinita es un conjunto que no contiene ningún par relacionado por la relación menor.
Una familia F de grafos se dice cerrada bajo la operación de tomar menores si cada menor de un grafo en F también pertenece a F. Si F es una familia menor cerrada, entonces sea S la clase de grafos que no están en F (el complemento de F ). Según el teorema de Robertson-Seymour, existe un conjunto finito H de elementos mínimos en S. Estos elementos mínimos forman una caracterización gráfica prohibida de F : las gráficas en F son exactamente las gráficas que no tienen ninguna gráfica en H como menor. [9] Los miembros de H se denominan menores excluidos (o menores prohibidos , o menores-obstrucciones mínimas ) de la familia F.
Por ejemplo, los gráficos planos son cerrados tomando menores: contraer una arista en un gráfico plano, o eliminar aristas o vértices del gráfico, no puede destruir su planaridad. Por lo tanto, las gráficas planas tienen una caracterización menor prohibida, que en este caso viene dada por el teorema de Wagner : el conjunto H de gráficas no planas mínimas menores contiene exactamente dos gráficas, la gráfica completa K 5 y la gráfica bipartita completa K 3,3 , y las gráficas planas son exactamente las gráficas que no tienen menor en el conjunto { K 5 , K 3,3 }.
La existencia de caracterizaciones menores prohibidas para todas las familias de grafos cerrados menores es una forma equivalente de enunciar el teorema de Robertson-Seymour. Porque, supongamos que cada familia cerrada de menores F tiene un conjunto finito H de menores mínimos prohibidos, y sea S cualquier conjunto infinito de gráficos. Defina F de S como la familia de gráficos que no tienen menor en S. Entonces F es menor cerrado y tiene un conjunto finito H de menores mínimos prohibidos. Sea C el complemento de F . S es un subconjunto de C ya que S y F son disjuntos, y H son las gráficas mínimas en C. Considere una gráfica G en H . G no puede tener una menor adecuada en S ya que G es mínima en C. Al mismo tiempo, G debe tener un menor en S , ya que de lo contrario G sería un elemento en F. Por lo tanto, G es un elemento en S , es decir, H es un subconjunto de S , y todos los demás gráficos en S tienen un menor entre los gráficos en H , por lo que H es el conjunto finito de elementos mínimos de S.
Para la otra implicación, supongamos que cada conjunto de gráficas tiene un subconjunto finito de gráficas mínimas y dejemos que se dé un conjunto cerrado menor F. Queremos encontrar un conjunto H de gráficas tal que una gráfica esté en F si y solo si no tiene menor en H. Sean E las gráficas que no son menores de ninguna gráfica en F y sea H el conjunto finito de gráficas mínimas en E. Ahora, dejemos que se dé una gráfica arbitraria G. Supongamos primero que G está en F . G no puede tener un menor en H ya que G está en F y H es un subconjunto de E. Ahora supongamos que G no está en F. Entonces G no es menor de ningún gráfico en F , ya que F es menor-cerrado. Por lo tanto, G está en E , por lo que G tiene menor en H.
Los siguientes conjuntos de gráficos finitos son cerrados menores y, por lo tanto (según el teorema de Robertson-Seymour) tienen caracterizaciones menores prohibidas:
Algunos ejemplos de conjuntos de obstrucción finitos ya se conocían para clases específicas de gráficos antes de que se demostrara el teorema de Robertson-Seymour. Por ejemplo, el obstáculo para el conjunto de todos los bosques es el gráfico de bucle (o, si nos limitamos a gráficos simples , el ciclo con tres vértices). Esto significa que un gráfico es un bosque si y sólo si ninguno de sus menores es el bucle (o el ciclo con tres vértices, respectivamente). La única obstrucción para el conjunto de caminos es el árbol de cuatro vértices, uno de los cuales tiene grado 3. En estos casos, el conjunto de obstrucciones contiene un solo elemento, pero en general no es así. El teorema de Wagner establece que una gráfica es plana si y sólo si no tiene ni K 5 ni K 3,3 como menores. En otras palabras, el conjunto { K 5 , K 3,3 } es un conjunto de obstrucción para el conjunto de todos los gráficos planos y, de hecho, el único conjunto de obstrucción mínimo. Un teorema similar establece que K 4 y K 2,3 son los menores prohibidos para el conjunto de grafos planos externos.
Aunque el teorema de Robertson-Seymour extiende estos resultados a familias arbitrarias de grafos cerrados menores, no es un sustituto completo de estos resultados, porque no proporciona una descripción explícita del conjunto de obstrucciones para ninguna familia. Por ejemplo, nos dice que el conjunto de gráficos toroidales tiene un conjunto de obstrucciones finito, pero no proporciona dicho conjunto. Se desconoce el conjunto completo de menores prohibidos para los gráficos toroidales, pero contiene al menos 17.535 gráficos. [11]
El teorema de Robertson-Seymour tiene una consecuencia importante en la complejidad computacional, debido a la prueba de Robertson y Seymour de que, para cada gráfico fijo h , existe un algoritmo de tiempo polinomial para probar si un gráfico tiene h como menor. El tiempo de ejecución de este algoritmo es cúbico (en el tamaño del gráfico a comprobar), aunque con un factor constante que depende superpolinómicamente del tamaño del menor h . Kawarabayashi, Kobayashi y Reed han mejorado el tiempo de ejecución a cuadrático. [12] Como resultado, para cada familia cerrada menor F , existe un algoritmo de tiempo polinomial para probar si un gráfico pertenece a F : simplemente verifique si el gráfico dado contiene h para cada menor prohibido h en el conjunto de obstrucción de F. [13]
Sin embargo, este método requiere un conjunto de obstrucciones finitas específico para funcionar, y el teorema no proporciona uno. El teorema demuestra que existe un conjunto de obstrucciones finito y, por lo tanto, el problema es polinómico debido al algoritmo anterior. Sin embargo, el algoritmo sólo puede utilizarse en la práctica si se proporciona dicho conjunto de obstrucciones finito. Como resultado, el teorema demuestra que el problema se puede resolver en tiempo polinomial, pero no proporciona un algoritmo concreto en tiempo polinomial para resolverlo. Estas pruebas de polinomialidad no son constructivas : prueban la polinomialidad de problemas sin proporcionar un algoritmo explícito de tiempo polinomial. [14] En muchos casos específicos, comprobar si una gráfica pertenece a una determinada familia menor cerrada se puede hacer de manera más eficiente: por ejemplo, verificar si una gráfica es plana se puede hacer en tiempo lineal.
Para invariantes de gráficos con la propiedad de que, para cada k , los gráficos con invariantes como máximo k son cerrados menores, se aplica el mismo método. Por ejemplo, según este resultado, el ancho del árbol, el ancho de la rama y el ancho de la ruta, la cobertura de vértices y el género mínimo de una incrustación son todos susceptibles de este enfoque, y para cualquier k fijo existe un algoritmo de tiempo polinomial para probar si estas invariantes son como máximo k , en el que el exponente en el tiempo de ejecución del algoritmo no depende de k . Un problema con esta propiedad, que puede resolverse en tiempo polinomial para cualquier k fijo con un exponente que no dependa de k , se conoce como tratable de parámetros fijos .
Sin embargo, este método no proporciona directamente un único algoritmo manejable con parámetros fijos para calcular el valor del parámetro para un gráfico dado con k desconocido , debido a la dificultad de determinar el conjunto de menores prohibidos. Además, los grandes factores constantes involucrados en estos resultados los hacen muy poco prácticos. Por lo tanto, el desarrollo de algoritmos explícitos de parámetros fijos para estos problemas, con una mayor dependencia de k , ha seguido siendo una importante línea de investigación.
Friedman, Robertson y Seymour (1987) demostraron que el siguiente teorema exhibe el fenómeno de la independencia al no ser demostrable en varios sistemas formales que son mucho más fuertes que la aritmética de Peano , pero sí demostrable en sistemas mucho más débiles que ZFC :
(Aquí, el tamaño de un gráfico es el número total de sus vértices y aristas, y ≤ denota el orden menor).