En matemáticas , el teorema de la estructura de grafos es un resultado importante en el área de la teoría de grafos . El resultado establece una conexión profunda y fundamental entre la teoría de los menores de grafos y las incrustaciones topológicas . El teorema se enuncia en el decimoséptimo de una serie de 23 artículos de Neil Robertson y Paul Seymour . Su demostración es muy larga y compleja. Kawarabayashi & Mohar (2007) y Lovász (2006) son estudios accesibles para los no especialistas, que describen el teorema y sus consecuencias.
Un menor de un grafo G es cualquier grafo H que sea isomorfo a un grafo que se puede obtener de un subgrafo de G contrayendo algunas aristas. Si G no tiene un grafo H como menor , entonces decimos que G es H -libre . Sea H un grafo fijo. Intuitivamente, si G es un grafo enorme H -libre, entonces debería haber una "buena razón" para esto. El teorema de la estructura del grafo proporciona esa "buena razón" en forma de una descripción aproximada de la estructura de G. En esencia, cada grafo H -libre G sufre de una de dos deficiencias estructurales: o bien G es "demasiado delgado" para tener H como menor, o bien G puede estar (casi) topológicamente incrustado en una superficie que es demasiado simple para incrustar H en ella. La primera razón se aplica si H es un grafo plano , y ambas razones se aplican si H no es plano. Primero precisamos estas nociones.
El ancho de árbol de un grafo G es un entero positivo que especifica la "delgadez" de G . Por ejemplo, un grafo conexo G tiene un ancho de árbol de uno si y solo si es un árbol, y G tiene un ancho de árbol de dos si y solo si es un grafo serie-paralelo . Intuitivamente, un grafo enorme G tiene un ancho de árbol pequeño si y solo si G adopta la estructura de un árbol enorme cuyos nodos y aristas han sido reemplazados por grafos pequeños. Damos una definición precisa del ancho de árbol en la subsección sobre sumas de clique. Es un teorema que si H es un menor de G , entonces el ancho de árbol de H no es mayor que el de G . Por lo tanto, una "buena razón" para que G sea libre de H es que el ancho de árbol de G no es muy grande. El teorema de la estructura del grafo implica que esta razón siempre se aplica en caso de que H sea planar.
Corolario 1. Para cada grafo planar H , existe un entero positivo k tal que cada grafo libre de H tiene un ancho de árbol menor que k .
Es lamentable que el valor de k en el Corolario 1 sea generalmente mucho mayor que el ancho del árbol de H (una excepción notable es cuando H = K 4 , el gráfico completo en cuatro vértices, para el cual k = 3 ). Esta es una de las razones por las que se dice que el teorema de la estructura del gráfico describe la "estructura aproximada" de los gráficos sin H.
En términos generales, una superficie es un conjunto de puntos con una estructura topológica local de un disco. Las superficies se dividen en dos familias infinitas: las superficies orientables incluyen la esfera , el toro , el doble toro , etc.; las superficies no orientables incluyen el plano proyectivo real , la botella de Klein , etc. Un grafo se incrusta en una superficie si el grafo se puede dibujar en la superficie como un conjunto de puntos (vértices) y arcos (aristas) que no se cruzan ni se tocan entre sí, excepto cuando las aristas y los vértices son incidentes o adyacentes. Un grafo es plano si se incrusta en la esfera. Si un grafo G se incrusta en una superficie particular, entonces cada menor de G también se incrusta en esa misma superficie. Por lo tanto, una "buena razón" para que G sea libre de H es que G se incrusta en una superficie en la que H no se incrusta.
Cuando H no es plana, el teorema de la estructura del grafo puede considerarse como una amplia generalización del teorema de Kuratowski. Una versión de este teorema probada por Wagner (1937) establece que si un grafo G es tanto libre de K 5 como libre de K 3,3 , entonces G es plana. Este teorema proporciona una "buena razón" para que un grafo G no tenga K 5 o K 3,3 como menores; específicamente, G se incrusta en la esfera, mientras que ni K 5 ni K 3,3 se incrustan en la esfera. Desafortunadamente, esta noción de "buena razón" no es lo suficientemente sofisticada para el teorema de la estructura del grafo. Se requieren dos nociones más: sumas de clique y vórtices .
Una camarilla en un grafo G es cualquier conjunto de vértices que son adyacentes por pares en G . Para un entero no negativo k , una k -camarilla-suma de dos grafos G y K es cualquier grafo obtenido al seleccionar un entero no negativo m ≤ k , seleccionar una camarilla de tamaño m en cada uno de G y K , identificar las dos camarillas en una sola camarilla de tamaño m y luego eliminar cero o más de las aristas que unen vértices en la nueva camarilla.
Si G 1 , G 2 , …, G n es una lista de grafos, entonces podemos producir un nuevo grafo uniendo la lista de grafos mediante sumas k -clique . Es decir, tomamos una suma k -clique de G 1 y G 2 , luego tomamos una suma k -clique de G 3 con el grafo resultante, y así sucesivamente. Un grafo tiene un ancho de árbol como máximo k si se puede obtener mediante sumas k -clique a partir de una lista de grafos, donde cada grafo de la lista tiene como máximo k + 1 vértices.
El corolario 1 nos indica que las sumas k -clique de grafos pequeños describen la estructura aproximada de los grafos libres de H cuando H es plano. Cuando H no es plano, también necesitamos considerar las sumas k -clique de una lista de grafos, cada uno de los cuales está incrustado en una superficie. El siguiente ejemplo con H = K 5 ilustra este punto. El grafo K 5 se incrusta en todas las superficies excepto en la esfera. Sin embargo, existen grafos libres de K 5 que están lejos de ser planos. En particular, la suma 3-clique de cualquier lista de grafos planos da como resultado un grafo libre de K 5. Wagner (1937) determinó la estructura precisa de los grafos libres de K 5 , como parte de un conjunto de resultados conocido como el teorema de Wagner :
Teorema 2. Si G es libre de K 5 , entonces G puede obtenerse mediante sumas de 3 cliques a partir de una lista de gráficos planares y copias de un gráfico no planar especial que tiene 8 vértices.
Señalamos que el Teorema 2 es un teorema de estructura exacta ya que se determina la estructura precisa de los grafos libres de K 5 . Tales resultados son raros dentro de la teoría de grafos. El teorema de estructura de grafos no es preciso en este sentido porque, para la mayoría de los grafos H , la descripción estructural de los grafos libres de H incluye algunos grafos que no son libres de H .
Uno podría verse tentado a conjeturar que un análogo del Teorema 2 es válido para grafos H distintos de K 5 . Tal vez sea cierto que: para cualquier grafo no plano H , existe un entero positivo k tal que cada grafo libre de H puede obtenerse mediante sumas de k -clique de una lista de grafos, cada uno de los cuales tiene como máximo k vértices o se incrusta en alguna superficie en la que H no se incrusta . Desafortunadamente, esta afirmación aún no es lo suficientemente sofisticada como para ser cierta. Debemos permitir que cada grafo incrustado G i "haga trampa" de dos maneras limitadas. Primero, debemos permitir un número limitado de ubicaciones en la superficie en las que podemos agregar algunos nuevos vértices y aristas a las que se les permite cruzarse entre sí de una manera de complejidad limitada . Tales ubicaciones se llaman vórtices . La "complejidad" de un vórtice está limitada por un parámetro llamado profundidad , estrechamente relacionado con el ancho del camino . El lector puede preferir aplazar la lectura de la siguiente descripción precisa de un vórtice de profundidad k . En segundo lugar, debemos permitir que se agregue un número limitado de nuevos vértices a cada uno de los gráficos integrados con vórtices.
Una cara de un grafo embebido es una celda abierta de 2 celdas en la superficie que está disjunta del grafo, pero cuyo límite es la unión de algunas de las aristas del grafo embebido. Sea F una cara de un grafo embebido G y sean v 0 , v 1 , ..., v n – 1 , v n = v 0 los vértices que se encuentran en el límite de F (en ese orden circular). Un intervalo circular para F es un conjunto de vértices de la forma { v a , v a +1 , …, v a + s donde a y s son números enteros y donde los subíndices se reducen módulo n . Sea Λ una lista finita de intervalos circulares para F . Construimos un nuevo grafo de la siguiente manera. Para cada intervalo circular L en Λ añadimos un nuevo vértice v L que se une a cero o más de los vértices en L . Finalmente, para cada par { L , M } de intervalos en Λ , podemos añadir una arista que una v L a v M siempre que L y M tengan intersección no vacía. Se dice que el grafo resultante se obtiene a partir de G añadiendo un vórtice de profundidad como máximo k (a la cara F ) siempre que ningún vértice en el límite de F aparezca en más de k de los intervalos en Λ .
Teorema de la estructura de grafos. Para cualquier grafo H , existe un entero positivo k tal que todo grafo libre de H puede obtenerse de la siguiente manera:
Nótese que los pasos 1 y 2 dan como resultado un gráfico vacío si H es planar, pero el número limitado de vértices agregado en el paso 3 hace que la afirmación sea consistente con el Corolario 1.
Son posibles versiones reforzadas del teorema de estructura de grafos dependiendo del conjunto H de menores prohibidos. Por ejemplo, cuando uno de los grafos en H es plano , entonces cada grafo sin menores H tiene una descomposición en árbol de ancho acotado; equivalentemente, puede representarse como una suma de clique de grafos de tamaño constante. [1] Cuando uno de los grafos en H puede dibujarse en el plano con un solo cruce , entonces los grafos sin menores H admiten una descomposición como una suma de clique de grafos de tamaño constante y grafos de género acotado, sin vórtices. [2] También se conoce un fortalecimiento diferente cuando uno de los grafos en H es un grafo de vértice . [3]