mini|450px|En el lado izquierdo, se muestra el grafo completo con tres vértices . Es creado por contracción de aristas a partir del grafo , que a su vez está contenido en . Entonces es un menor de
En teoría de grafos, un grafo se denomina menor del grafo si se puede formar a partir de eliminando aristas y vértices y mediante la contracción de aristas.
La teoría de los menores de grafo comenzó con el teorema de Wagner, que afirma que un grafo es plano si y solo si sus menores no incluyen ni el grafo completo ni el grafo bipartito completo ., p. 77;. El teorema de Robertson-Seymour implica que existe una caracterización de menores prohibidos análogo para cada propiedad de los grafos que se conserva mediante eliminaciones y contracciones de arista., theorem 4, p. 78;.
Para cada grafo fijo , es posible probar si es un menor de un grafo de entrada en complejidad temporal; junto con la caracterización menor prohibida, esto implica que cada propiedad del grafo preservada por eliminaciones y contracciones puede reconocerse en tiempo polinomial.
Otros resultados y conjeturas que involucran grafos menores incluyen el teorema de la estructura del grafo, según el cual los grafos que no tienen como menor pueden formarse pegando piezas más simples, y la conjetura de Hadwiger que relaciona la incapacidad de colorear un grafo con la existencia de un gran grafo completo como menor. Las variantes importantes de los menores de grafos incluyen los menores topológicos y los menores de inmersión.
Definiciones Una contracción de arista es una operación que elimina una arista de un grafo mientras fusiona simultáneamente los dos vértices que estaba conectando. Un grafo es un menor de otro grafo no dirigido si se puede obtener un grafo isomorfo a de partir de contrayendo algunas aristas, eliminando algunas aristas y eliminando algunos vértices aislados. El orden en que se realiza una secuencia de dichas contracciones y eliminaciones en no afecta al grafo resultante .
Los grafos menores a menudo se estudian en el contexto más general de los menores matroides. En este contexto, es común suponer que todos los grafos están conectados, estando permitidos bucles y aristas múltiples (es decir, son multigrafos en lugar de grafos simples); la contracción de un bucle y la eliminación de una arista de corte son operaciones prohibidas. Este punto de vista tiene la ventaja de que las eliminaciones de arista dejan el rango de un grafo sin cambios, y las contracciones de arista siempre reducen el rango en uno.
En otros contextos (como en el estudio de pseudobosques) tiene más sentido permitir la eliminación de una arista de corte y permitir grafos desconectados, pero prohibir los multigrafos. En esta variación de la teoría de grafos menores, un grafo siempre se simplifica después de cualquier contracción de arista para eliminar sus bucles propios y aristas múltiples. is inconsistent about whether to allow self-loops and multiple adjacencies: he writes on p. 76 that "parallel edges and loops are allowed" but on p. 77 he states that "a graph is a forest if and only if it does not contain the triangle as a minor", true only for simple graphs.
Una función se denomina monótona menor si, siempre que sea menor de , se tiene que .
Ejemplo En el siguiente ejemplo, el grafo H es menor del grafo G:
H.
G.
El siguiente diagrama ilustra esto. Primero se construye un subgrafo de G eliminando las aristas discontinuas (y el vértice aislado resultante), y luego se contrae la arista gris (fusionando los dos vértices que conecta):
Principales resultados y conjeturas Es sencillo verificar que la relación ser grafo menor forma un conjunto parcialmente ordenado sobre las clases de isomorfismos de grafos finitos no dirigidos: es transitiva (un menor de un menor de es un menor del propio ), y y solo pueden ser menores entre sí si son isomorfos, porque cualquier operación menor no trivial elimina aristas o vértices. Un resultado profundo hallado por Neil Robertson y Paul Seymour establece que este orden parcial es en realidad un casi buen orden: si se da una lista infinita de grafos finitos , entonces siempre existen dos índices tales que es un menor de . Otra forma equivalente de afirmar esto es que cualquier conjunto de grafos puede tener solo un número finito de elementos mínimos bajo el orden menor., Chapter 12: Minors, Trees, and WQO;. Este resultado demostró una conjetura anteriormente conocida como la conjetura de Wagner, en honor a Klaus Wagner; quien la había planteado mucho antes, aunque se publicó en 1970., p. 76.
En el curso de su demostración, Seymour y Robertson también probaron el teorema de la estructura de grafo, en el que determinaron para cualquier grafo fijo la estructura aproximada de cualquier grafo que no tenga como menor. El enunciado del teorema es en sí largo y complicado, pero en resumen establece que tal grafo debe tener la estructura de una suma de cliques de grafos más pequeños que se modifican ligeramente a partir de grafos embebidos en superficies de genus acotados.
Así, su teoría establece conexiones fundamentales entre grafos menores y embebidos topológicos de grafos., pp. 80–82;.
Para cualquier grafo , los grafos libres de menores simples de deben ser densos, lo que significa que el número de aristas es menor que algún múltiplo constante del número de vértices.. Más específicamente, si tiene vértices, entonces un grafo simple de -vértices sin menores puede tener como máximo aristas, y algunos grafos sin menores tienen al menos esta cantidad de aristas.;;;. Por lo tanto, si tiene vértices, entonces los grafos sin menores tienen grado medio y, además degenerados. Además, los grafos sin menores tienen un teorema separador similar al teorema separador plano para grafos planos: para cualquier fijo y para cualquier grafo de -vértices sin menores de , es posible encontrar un subconjunto de vértices cuya eliminación divide en dos subgrafos (posiblemente desconectados) con como máximo vértices por subgrafo.;;. Aún más fuerte, para cualquier fijo, los grafos sin menores de tienen ancho de árbol .
La conjetura de Hadwiger en la teoría de grafos propone que si un grafo no contiene un isomorfo menor al grafo completo en vértices, entonces tiene un coloreado propio con colores.. El caso es una reformulación del teorema de los cuatro colores. La conjetura de Hadwiger ha sido probada para ,. pero se desconoce en el caso general. lo calificó como "uno de los problemas sin resolver más profundos en la teoría de grafos". Otro resultado que relaciona el teorema de los cuatro colores con grafos menores es el teorema del snark anunciado por Robertson, Sanders, Seymour y Thomas, un refuerzo del teorema de los cuatro colores conjeturado por W. T. Tutte y que establece que cualquier grafo 3-regular sin puentes que requiera cuatro colores en un coloreado de aristas debe tener el grafo de Petersen como menor.;.
Familias de grafos cerrados menores
Muchas familias de grafos tienen la propiedad de que todo menor de un grafo en F también está en F; se dice que dicha clase es menor cerrada. Por ejemplo, en cualquier grafo plano, o en cualquier incrustación de un grafo en una superficie topológica fija, ni la eliminación de aristas ni la contracción de aristas permiten aumentar el genus de la incrustación; por lo tanto, los grafos planos y los grafos incrustables en cualquier superficie fija forman familias cerradas de menores.
Si F es una familia cerrada de menores, entonces (debido a la propiedad de buen cuasi-ordenamiento de los menores) entre los grafos que no pertenecen a F hay un conjunto finito X de grafos menores mínimo. Estos grafos son menores prohibidos para F: un grafo pertenece a F si y solo si no contiene como menor ningún grafo de X. Es decir, toda familia cerrada de menores F se puede caracterizar como la familia de grafos sin los menores de X para algún conjunto finito X de menores prohibidos.
El ejemplo más conocido de una caracterización de este tipo es el teorema de Wagner que caracteriza los grafos planos como aquellos que no tienen K5 ni K3,3 como menores.
En algunos casos, las propiedades de los grafos en una familia cerrada de menores pueden estar estrechamente relacionadas con las propiedades de sus menores excluidos. Por ejemplo, una familia de grafos cerrados menores F tiene acotado su ancho de ruta si y solo si sus elementos menores prohibidos incluyen un bosque,. F tiene acotada su profundidad de árbol si y solo si sus elementos menores prohibidos incluyen una unión disjunta de grafos camino, F tiene ancho de árbol acotado si y solo si sus menores prohibidos incluyen un grafo plano,, Theorem 9, p. 81;. y F tiene un ancho de árbol local acotado (una relación funcional entre su diámetro y el ancho del árbol) si y solo si sus menores prohibidos incluyen un grafo de ápice (un grafo que puede volverse plano eliminando un solo vértice).;. Si H se puede dibujar en el plano con un solo cruce (es decir, tiene número de cruce uno), entonces los grafos de H sin menores tienen un teorema de estructura simplificado en el que se forman como suma de cliques de grafos planos y grafos de ancho de árbol acotado.;. Por ejemplo, tanto K5 como K3,3 tienen número de cruces uno, y como Wagner demostró, los grafos sin K5 son exactamente las sumas de 3-cliques de grafos planares y el grafo de Wagner de ocho vértices, mientras que los grafos sin K3,3 son exactamente las sumas de 2-cliques de grafos planos y K5.;;.
Variaciones Menores topológicos Un grafo H se denomina menor topológico de un grafo G si una subdivisión de H es isomorfa a un subgrafo de G. Es fácil ver que todo menor topológico también es un menor. Sin embargo, lo contrario no es cierto en general (por ejemplo, el grafo completo K5 en el grafo de Petersen es menor pero no topológico), pero es válido para grafos con un grado máximo no superior a tres.
La relación topológica menor no es un buen cuasi-ordenamiento en el conjunto de grafos finitos y, por lo tanto, el resultado de Robertson y Seymour no se aplica a los menores topológicos. Sin embargo, es sencillo construir caracterizaciones topológicas secundarias prohibidas finitas a partir de caracterizaciones secundarias prohibidas finitas reemplazando cada conjunto de ramas con k aristas salientes por un árbol de k hojas que tiene un grado de descenso de al menos dos.
Menores inducidos Un grafo H se denomina menor inducido de un grafo G si puede obtenerse a partir de un subgrafo inducido de G contrayendo aristas. De lo contrario, se dice que G está libre de menores inducidos por H.
Inmersión menor Una operación gráfica llamada levantamiento es central en un concepto llamado inmersiones. El levantamiento es una operación sobre aristas adyacentes. Dados tres vértices v, u y w, donde (v,u) y (u,w) son aristas en el grafo, el levantamiento de vuw, o equivalentemente de (v,u), (u,w) es la operación que borra las dos aristas (v,u) y (u,w) y agrega la arista (v,w). En el caso de que (v,w) ya estuviera presente, v y w ahora estarán conectados por más de una arista y, por lo tanto, esta operación es intrínsecamente una operación de grafos múltiples.
En el caso de que se pueda obtener un grafo H a partir de un grafo G mediante una secuencia de operaciones de elevación (sobre G) y luego encontrar un subgrafo isomorfo, se dice que H es una inmersión menor de G.
Hay otra forma de definir los menores de inmersión, que es equivalente a la operación de levantamiento. Se dice que H es una inmersión menor de G si existe una aplicación inyectiva de vértices en H a vértices en G donde las imágenes de elementos adyacentes de H están conectadas en G por caminos disjuntos en las aristas.