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 grafos menores y las incrustaciones topológicas . El teorema se establece en el decimoséptimo de una serie de 23 artículos de Neil Robertson y Paul Seymour . Su prueba es muy larga y complicada. Kawarabayashi y Mohar (2007) y Lovász (2006) son estudios accesibles a no especialistas que describen el teorema y sus consecuencias.
Un gráfico menor de un gráfico G es cualquier gráfico H que sea isomorfo a un gráfico que se pueda obtener a partir de un subgrafo de G contrayendo algunas aristas . Si G no tiene un gráfico H como menor, entonces decimos que G está libre de H. Sea H una gráfica fija. Intuitivamente, si G es un enorme gráfico libre de H , entonces debería haber una "buena razón" para ello. El teorema de la estructura del grafo proporciona una "buena razón" en forma de una descripción aproximada de la estructura de G. En esencia, todo gráfico G libre de H sufre de una de dos deficiencias estructurales: o G es "demasiado delgado" para tener H como menor, o G puede estar (casi) topológicamente incrustado en una superficie que es demasiado simple para incrustar H. al. La primera razón se aplica si H es un gráfico plano , y ambas razones se aplican si H no es plano. Primero precisamos estas nociones.
El ancho del árbol de un gráfico G es un número entero positivo que especifica la "delgadez" de G . Por ejemplo, un gráfico conexo G tiene un ancho de árbol uno si y solo si es un árbol, y G tiene un ancho de árbol dos si y solo si es un gráfico serie-paralelo . Intuitivamente, un gráfico enorme G tiene un ancho de árbol pequeño si y sólo si G toma la estructura de un árbol enorme cuyos nodos y aristas han sido reemplazados por gráficos pequeños. Damos una definición precisa del ancho del árbol en la subsección sobre sumas de camarillas. Es un teorema que si H es menor de G , entonces el ancho del árbol de H no es mayor que el de G. Por lo tanto, una "buena razón" para que G esté libre de H es que el ancho del árbol de G no es muy grande. El teorema de la estructura gráfica implica que esta razón siempre se aplica en el caso de que H sea plano.
Corolario 1. Para cada gráfico plano H , existe un entero positivo k tal que cada gráfico libre de H tiene un ancho de árbol menor que k .
Es desafortunado 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 ). Ésta es una de las razones por las que se dice que el teorema de la estructura de los grafos describe la "estructura aproximada" de los gráficos libres de H.
A grandes rasgos, una superficie es un conjunto de puntos con una estructura topológica local de un disco. Las superficies se dividen en dos infinitas familias: las superficies orientables incluyen la esfera , el toroide , el doble toroide , etc.; las superficies no orientables incluyen el plano proyectivo real , la botella de Klein , etc. Un gráfico se incrusta en una superficie si el gráfico se puede dibujar en la superficie como un conjunto de puntos (vértices) y arcos (bordes) que no se cruzan ni se tocan entre sí, excepto cuando los bordes y vértices son incidentes o adyacentes. Una gráfica es plana si se incrusta en la esfera. Si un gráfico 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 esté libre de H es que G se incrusta en una superficie en la que H no se incrusta.
Cuando H no es plano, el teorema de la estructura del grafo puede considerarse como una amplia generalización del teorema de Kuratowski. Una versión de este teorema demostrada por Wagner (1937) establece que si un gráfico G está libre de K 5 y de K 3,3 , entonces G es plano. Este teorema proporciona una "buena razón" para que un gráfico G no tenga K 5 o K 3,3 como menores; específicamente, G está incrustado en la esfera, mientras que ni K 5 ni K 3,3 están incrustados en la esfera. Desafortunadamente, esta noción de "buena razón" no es lo suficientemente sofisticada para el teorema de la estructura gráfica. Se requieren dos nociones más: sumas de camarillas y vórtices .
Una camarilla en un gráfico G es cualquier conjunto de vértices que son adyacentes por pares en G. Para un entero no negativo k , una k -suma de camarilla de dos gráficos G y K es cualquier gráfico obtenido seleccionando un entero no negativo m ≤ k , seleccionando una camarilla de tamaño m en cada uno de G y K , identificando los dos camarillas en una sola camarilla de tamaño m , luego eliminando cero o más de los bordes que unen los vértices en la nueva camarilla.
Si G 1 , G 2 ,…, G n es una lista de gráficos, entonces podemos producir un nuevo gráfico uniendo la lista de gráficos mediante k -clique-sums . Es decir, tomamos una k -suma-clique de G 1 y G 2 , luego tomamos una k -suma-clique de G 3 con la gráfica resultante, y así sucesivamente. Un gráfico tiene un ancho de árbol como máximo k si se puede obtener mediante k -clique-sums de una lista de gráficos, donde cada gráfico de la lista tiene como máximo k + 1 vértices.
El corolario 1 nos indica que k -sumas de clique de gráficos pequeños describen la estructura aproximada H -gráficos libres cuando H es plano. Cuando H no es plano, también debemos considerar k -sumas de camarillas de una lista de gráficos, cada uno de los cuales está incrustado en una superficie. El siguiente ejemplo con H = K 5 ilustra este punto. El gráfico K 5 se incrusta en todas las superficies excepto en la esfera. Sin embargo, existen gráficos libres de K 5 que están lejos de ser planos. En particular, la suma de 3 camarillas de cualquier lista de gráficos planos da como resultado un gráfico libre de K 5 . Wagner (1937) determinó la estructura precisa de los gráficos libres de K 5 , como parte de un conjunto de resultados conocido como teorema de Wagner :
Teorema 2. Si G no tiene K 5 , entonces G se puede obtener mediante sumas de 3 camarillas a partir de una lista de gráficos planos y copias de un gráfico no plano 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 gráficos libres de K 5 . Estos resultados son raros dentro de la teoría de grafos. El teorema de la estructura de grafos no es preciso en este sentido porque, para la mayoría de los gráficos H , la descripción estructural de los gráficos libres de H incluye algunos gráficos que no lo son .
Uno podría verse tentado a conjeturar que una analogía del teorema 2 es válida para gráficos H distintos de K 5 . Quizás sea cierto que: para cualquier gráfico no plano H , existe un entero positivo k tal que cada gráfico libre de H se puede obtener mediante k sumas de camarillas de una lista de gráficos, cada uno de los cuales tiene como máximo k vértices o incrustaciones 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 gráfico 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 vértices y aristas nuevos a los que se les permite cruzarse entre sí de una manera de complejidad limitada . Estos lugares se denominan vórtices . La "complejidad" de un vórtice está limitada por un parámetro llamado profundidad , estrechamente relacionado con el ancho de ruta . El lector puede preferir posponer 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 incrustados con vórtices.
Una cara de un gráfico incrustado es una celda abierta de 2 celdas en la superficie que está separada del gráfico, pero cuyo límite es la unión de algunos de los bordes del gráfico incrustado. Sea F una cara de un gráfico incrustado 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 ,…, va + s } donde a y s son números enteros y donde los subíndices se reducen en módulo n . Sea Λ una lista finita de intervalos circulares para F . Construimos un nuevo gráfico de la siguiente manera. Para cada intervalo circular L en Λ agregamos 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 agregar una arista que une v L con v M siempre que L y M tengan una intersección no vacía. Se dice que el gráfico resultante se obtiene de G agregando 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 gráfico H , existe un entero positivo k tal que cada gráfico libre de H se puede obtener de la siguiente manera:
Tenga en cuenta que los pasos 1 y 2 dan como resultado un gráfico vacío si H es plano, pero el número acotado de vértices agregados en el paso 3 hace que la afirmación sea consistente con el Corolario 1.
Son posibles versiones reforzadas del teorema de la estructura gráfica dependiendo del conjunto H de menores prohibidos. Por ejemplo, cuando uno de los gráficos en H es plano , entonces cada gráfico libre de H -menor tiene una descomposición en árbol de ancho acotado; de manera equivalente, se puede representar como una suma camarilla de gráficos de tamaño constante. [1] Cuando una de las gráficas en H se puede dibujar en el plano con un solo cruce , entonces las gráficas libres de H -menor admiten una descomposición como una suma de camarillas de gráficas de tamaño constante y gráficas de género acotado, sin vórtices. [2] También se conoce un fortalecimiento diferente cuando una de las gráficas en H es una gráfica de vértices . [3]