En teoría de grafos , el teorema de Robertson-Seymour (también llamado teorema de los menores de grafos [1] ) establece que los grafos no dirigidos , parcialmente ordenados por la relación de menores de grafos , forman un buen cuasiordenamiento . [2] De manera equivalente, cada familia de grafos que está cerrada bajo los menores puede definirse por un conjunto finito de menores prohibidos , de la misma manera que el teorema de Wagner caracteriza a los grafos planares como los grafos que no tienen como menores al grafo completo K 5 o al grafo bipartito completo K 3,3 .
El teorema de Robertson-Seymour debe su nombre a 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 desde 1983 hasta 2004. [3] Antes de su demostración, el enunciado del teorema se conocía como la conjetura de Wagner en honor al matemático alemán Klaus Wagner , aunque Wagner dijo que nunca la conjeturaba. [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 independientemente por Joseph Kruskal y S. Tarkowski. [5]
Un menor de un grafo no dirigido G es cualquier grafo que puede obtenerse a partir 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 de menor forma un orden parcial en el conjunto de todos los grafos no dirigidos finitos distintos, ya que obedece los tres axiomas de órdenes parciales: es reflexiva (cada grafo es un menor de sí mismo), transitiva (un menor de un menor de G es en sí mismo un menor de G ), y antisimétrica (si dos grafos G y H son menores entre sí, entonces deben ser isomorfos ). Sin embargo, si los grafos que son isomorfos pueden no obstante considerarse como objetos distintos, entonces el ordenamiento de menores 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 buen cuasiordenamiento si no contiene ni una cadena descendente infinita ni una anticadena infinita . [7] Por ejemplo, el ordenamiento habitual en los números enteros no negativos es un buen cuasiordenamiento, pero el mismo ordenamiento 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 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 grafos finitos no dirigidos y los menores de grafos forman un cuasiordenamiento correcto. La relación de menores de grafos no contiene ninguna cadena descendente infinita, porque cada contracción o eliminación reduce el número de aristas y vértices del grafo (un entero no negativo). [8] La parte no trivial del teorema es que no hay anticadenas infinitas, conjuntos infinitos de grafos que no están relacionados entre sí por el ordenamiento de menores. Si S es un conjunto de grafos y M es un subconjunto de S que contiene un grafo representativo para cada clase de equivalencia de elementos mínimos (grafos 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 grafos, debe haber solo un número finito de elementos mínimos no isomorfos.
Otra forma equivalente del teorema es que, en cualquier conjunto infinito S de grafos, debe haber un par de grafos, uno de los cuales sea 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, pues si sólo hay un número finito de elementos mínimos, entonces cada uno de los grafos restantes debe pertenecer a un par de este tipo con uno de los elementos mínimos. 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.
Se dice que una familia F de grafos está 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 cerrada por menores, entonces sea S la clase de grafos que no están en F (el complemento de F ). De acuerdo con el teorema de Robertson-Seymour, existe un conjunto finito H de elementos mínimos en S . Estos elementos mínimos forman una caracterización de grafo prohibido de F : los grafos en F son exactamente los grafos que no tienen ningún grafo en H como menor. [9] Los miembros de H se denominan menores excluidos (o menores prohibidos u obstrucciones de menores mínimos ) para la familia F .
Por ejemplo, los grafos planares son cerrados bajo la toma de menores: contraer una arista en un grafo planar, o quitar aristas o vértices del grafo, no puede destruir su planaridad. Por lo tanto, los grafos planares tienen una caracterización de menor prohibido, que en este caso viene dada por el teorema de Wagner : el conjunto H de grafos no planares menores-minimalistas contiene exactamente dos grafos, el grafo completo K 5 y el grafo bipartito completo K 3,3 , y los grafos planares son exactamente los grafos que no tienen un menor en el conjunto { K 5 , K 3,3 }.
La existencia de caracterizaciones de menores prohibidos para todas las familias de grafos menores-cerrados es una forma equivalente de enunciar el teorema de Robertson-Seymour. Pues, supongamos que cada familia menor-cerrada F tiene un conjunto finito H de menores prohibidos mínimos, y sea S cualquier conjunto infinito de grafos. Definamos F a partir de S como la familia de grafos que no tienen un menor en S . Entonces F es menor-cerrada y tiene un conjunto finito H de menores prohibidos mínimos. Sea C el complemento de F . S es un subconjunto de C ya que S y F son disjuntos, y H son los grafos mínimos en C . Considérese un grafo G en H . G no puede tener un menor propio en S ya que G es mínimo 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 de S , es decir, H es un subconjunto de S , y todos los demás grafos de S tienen un menor entre los grafos de 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 grafos tiene un subconjunto finito de grafos minimales y sea dado un conjunto menor-cerrado F. Queremos encontrar un conjunto H de grafos tales que un grafo esté en F si y solo si no tiene un menor en H. Sean E los grafos que no son menores de ningún grafo en F , y sea H el conjunto finito de grafos mínimos en E. Ahora, sea dado un grafo arbitrario 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 un menor de ningún grafo en F , ya que F es menor-cerrado. Por lo tanto, G está en E , por lo que G tiene un menor en H.
Los siguientes conjuntos de grafos finitos son menores cerrados y, por lo tanto (según el teorema de Robertson-Seymour) tienen caracterizaciones menores prohibidas:
Algunos ejemplos de conjuntos de obstrucciones finitas ya se conocían para clases específicas de grafos antes de que se demostrara el teorema de Robertson-Seymour. Por ejemplo, la obstrucción para el conjunto de todos los bosques es el grafo de bucle (o, si uno se restringe a grafos simples , el ciclo con tres vértices). Esto significa que un grafo es un bosque si y solo 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 con cuatro vértices, uno de los cuales tiene grado 3. En estos casos, el conjunto de obstrucciones contiene un solo elemento, pero en general este no es el caso. El teorema de Wagner establece que un grafo es planar si y solo si no tiene ni K 5 ni K 3,3 como menor. En otras palabras, el conjunto { K 5 , K 3,3 } es un conjunto de obstrucciones para el conjunto de todos los grafos planares, y de hecho el único conjunto de obstrucciones minimal. Un teorema similar establece que K 4 y K 2,3 son los menores prohibidos para el conjunto de grafos exteriores-planares.
Aunque el teorema de Robertson-Seymour extiende estos resultados a familias arbitrarias de grafos menores cerrados, 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 grafos toroidales tiene un conjunto de obstrucciones finito, pero no proporciona ningún conjunto de ese tipo. El conjunto completo de menores prohibidos para grafos toroidales sigue siendo desconocido, pero contiene al menos 17.535 grafos. [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 grafo fijo h , existe un algoritmo de tiempo polinomial para probar si un grafo tiene h como menor. El tiempo de ejecución de este algoritmo es cúbico (en el tamaño del grafo a comprobar), aunque con un factor constante que depende superpolinomialmente del tamaño del menor h . El tiempo de ejecución ha sido mejorado a cuadrático por Kawarabayashi, Kobayashi y Reed. [12] Como resultado, para cada familia menor-cerrada F , existe un algoritmo de tiempo polinomial para probar si un grafo pertenece a F : simplemente verifique si el grafo dado contiene h para cada menor prohibido h en el conjunto de obstrucciones de F. [ 13]
Sin embargo, este método requiere un conjunto finito específico de obstrucciones para funcionar, y el teorema no proporciona uno. El teorema prueba que existe tal conjunto finito de obstrucciones y, por lo tanto, el problema es polinomial debido al algoritmo anterior. Sin embargo, el algoritmo se puede utilizar en la práctica solo si se proporciona tal conjunto finito de obstrucciones. Como resultado, el teorema prueba que el problema se puede resolver en tiempo polinomial, pero no proporciona un algoritmo concreto en tiempo polinomial para resolverlo. Tales pruebas de polinomio no son constructivas : prueban la polinomio de los problemas sin proporcionar un algoritmo explícito en tiempo polinomial. [14] En muchos casos específicos, verificar si un grafo está en una familia menor cerrada dada se puede hacer de manera más eficiente: por ejemplo, verificar si un grafo es planar se puede hacer en tiempo lineal.
Para los invariantes de grafos con la propiedad de que, para cada k , los grafos con invariante como máximo k son menores cerrados, se aplica el mismo método. Por ejemplo, por este resultado, el ancho del árbol, el ancho de la rama y el ancho del camino, 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 hay un algoritmo de tiempo polinomial para probar si estos 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 se puede resolver en tiempo polinomial para cualquier k fijo con un exponente que no depende de k , se conoce como manejable con 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 altamente imprácticos. Por lo tanto, el desarrollo de algoritmos explícitos de parámetros fijos para estos problemas, con una dependencia mejorada de k , ha seguido siendo una línea de investigación importante.
Friedman, Robertson y Seymour (1987) demostraron que el siguiente teorema exhibe el fenómeno de independencia al ser indemostrable en varios sistemas formales que son mucho más fuertes que la aritmética de Peano , pero siendo 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).