Menor (teoría de grafos)
En teoría de grafos, un grafo H se denomina menor del grafo G si se puede formar H a partir de G eliminando aristas y vértices y mediante la contracción de aristas.
[2] Para cada grafo fijo H, es posible probar si H es un menor de un grafo de entrada G en complejidad temporal;[3] junto con la caracterización menor prohibida, esto implica que cada propiedad del grafo preservada por eliminaciones y contracciones puede reconocerse en tiempo polinomial.
Un grafo H es un menor de otro grafo no dirigido G si se puede obtener un grafo isomorfo a H de partir de G 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 G no afecta al grafo resultante H. Los grafos menores a menudo se estudian en el contexto más general de los menores matroides.
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):
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 (G1, G2, …), entonces siempre existen dos índices i < j tales que Gi es un menor de Gj.
[6] 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.
Además, los H grafos sin menores tienen un teorema separador similar al teorema separador plano para grafos planos: para cualquier H fijo y para cualquier grafo G de n-vértices sin menores de H, es posible encontrar un subconjunto de
[13] El caso k= 5 es una reformulación del teorema de los cuatro colores.
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.
Por ejemplo, en cualquier grafo plano, o en cualquier embebido 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 del embebido; por lo tanto, los grafos planos y los grafos embebibles en cualquier superficie fija forman familias cerradas de menores.
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,[16] 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,[17] 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).
[22] La relación topológica menor no es un buen cuasi-ordenamiento en el conjunto de grafos finitos[23] y, por lo tanto, el resultado de Robertson y Seymour no se aplica a los menores topológicos.
De lo contrario, se dice que G está libre de menores inducidos por H.[24] Una operación gráfica llamada levantamiento es central en un concepto llamado inmersiones.
Un grafo H es un menor bipartito de otro grafo G siempre que se pueda obtener H de G eliminando vértices, eliminando aristas y colapsando pares de vértices que estén a distancia dos uno del otro en un ciclo periférico del grafo.
[30] El problema de decisión de si un grafo G contiene H como menor es NP-completo en general; por ejemplo, si H es un grafo ciclo con el mismo número de vértices que G, entonces H es un menor de G si y solo si G contiene un camino hamiltoniano.
Sin embargo, cuando G es parte de la entrada pero H es fijo, se puede resolver en tiempo polinomial.
Este resultado no se usa en la práctica, ya que la constante oculta es tan grande (necesita tres capas en la notación flecha de Knuth para expresarse) que descarta cualquier aplicación, convirtiéndola en un algoritmo galáctico.
[4] En algunos casos, los menores prohibidos son conocidos, o pueden computarse.
[33] En el caso de que H sea un grafo plano fijo, entonces se puede probar en tiempo lineal en un grafo de entrada G si H es un menor de G.[34] En los casos en que H no es fija, se conocen algoritmos más rápidos en el caso en que G es plano.
