Hispanopedia Wiki
Articulo de referencia

Teorema de la estructura de grafos

En matemáticas , el teorema de la estructura de grafos es un resultado fundamental en el campo de la teoría de grafos . Este resultado establece una conexión profunda y esencial...

Hispanopedia WikiContenido en espanolLectura gratuita

En matemáticas , el teorema de la estructura de grafos es un resultado fundamental en el campo de la teoría de grafos . Este resultado establece una conexión profunda y esencial entre la teoría de 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 extensa y compleja. Kawarabayashi y Mohar (2007) y Lovász (2006) son obras de divulgación accesibles a no especialistas que describen el teorema y sus consecuencias.

Planteamiento y motivación del teorema

Un menor de un grafo G es cualquier grafo H que es isomorfo a un grafo que se puede obtener a partir de un subgrafo de G contrayendo algunas aristas . Si G no tiene un grafo H como menor, decimos que G es H -libre . Sea H un grafo fijo. Intuitivamente, si G es un grafo H -libre enorme , entonces debe haber una "buena razón" para ello. El teorema de la estructura de grafos proporciona dicha "buena razón" en forma de una descripción aproximada de la estructura de G. En esencia, todo grafo H -libre G sufre 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 demasiado simple para incrustar H. La primera razón se aplica si H es un grafo planar , y ambas razones se aplican si H no es planar. Primero precisaremos estas nociones.

Ancho del árbol

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 ancho de árbol uno si y solo si es un árbol, y G tiene ancho de árbol dos si y solo si es un grafo serie-paralelo . Intuitivamente, un grafo enorme G tiene ancho de árbol pequeño si y solo si G toma la estructura de un árbol enorme cuyos nodos y aristas han sido reemplazados por grafos pequeños. Damos una definición precisa de ancho de árbol en la subsección sobre sumas de cliques. 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 de grafos 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 todo 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 H (una excepción notable es cuando H = K⁴ , el grafo completo de 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 de grafos describe la "estructura aproximada" de los grafos libres de H.

Incrustaciones superficiales

En términos generales, una superficie es un conjunto de puntos con una estructura topológica local de 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 puede dibujarse sobre ella como un conjunto de puntos (vértices) y arcos (aristas) que no se cruzan ni se tocan, excepto donde las aristas y los vértices son incidentes o adyacentes. Un grafo es planar si se incrusta en la esfera. Si un grafo G se incrusta en una superficie particular, entonces todo 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 planar, el teorema de estructura de grafos puede considerarse una vasta generalización del teorema de Kuratowski. Una versión de este teorema, demostrada por Wagner (1937), establece que si un grafo G es libre de K 5 y K 3,3 , entonces G es planar. Este teorema proporciona una "buena razón" para que un grafo G no tenga K 5 ni 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 estructura de grafos. Se requieren dos nociones más: sumas de cliques y vórtices .

Sumas de camarilla

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 suma de k -camarillas 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, podemos generar un nuevo grafo uniendo la lista mediante sumas de k -cliques . Es decir, calculamos la suma de k -cliques de G 1 y G 2 , luego calculamos la suma de k -cliques de G 3 con el grafo resultante, y así sucesivamente. Un grafo tiene un ancho de árbol de como máximo k si se puede obtener mediante sumas de k -cliques 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 de k -cliques de grafos pequeños describen la estructura aproximada de los grafos libres de H cuando H es planar. Cuando H no es planar, también necesitamos considerar las sumas de k -cliques 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 planares. En particular, la suma de 3-cliques de cualquier lista de grafos planares resulta en 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 K 5- libre, entonces G se puede obtener mediante sumas de 3-cliques de una lista de grafos planares y copias de un grafo no planar especial que tiene 8 vértices.

Cabe destacar que el Teorema 2 es un teorema de estructura exacta, ya que determina la estructura precisa de los grafos libres de K⁵ . Estos resultados son poco comunes en 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 lo son.

Vórtices (descripción aproximada)

Uno podría verse tentado a conjeturar que un análogo del Teorema 2 se cumple para grafos H distintos de K 5 . Tal vez sea cierto que: para cualquier grafo no planar H , existe un entero positivo k tal que todo grafo libre de H puede obtenerse mediante k -clique-sums 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 vértices y aristas nuevos que pueden cruzarse entre sí de una manera de complejidad limitada . Dichas ubicaciones se llaman vórtices . La "complejidad" de un vórtice está limitada por un parámetro llamado su profundidad , estrechamente relacionado con el ancho del camino . 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 añada un número limitado de nuevos vértices a cada uno de los grafos incrustados con vórtices.

Vórtices (definición precisa)

Una cara de un grafo incrustado es una 2-celda abierta en la superficie que es disjunta del grafo, pero cuyo límite es la unión de algunas de las aristas del grafo incrustado. Sea F una cara de un grafo 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 , …, v a + s } donde a y s son 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 Λ 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 una v L con v M siempre que L y M tengan una intersección no vacía. Se dice que el grafo 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 Λ .

Enunciado del teorema de la estructura de grafos

Teorema de la estructura de grafos. Para cualquier grafo H , existe un entero positivo k tal que todo grafo libre de H se puede obtener de la siguiente manera:

  1. Comenzamos con una lista de grafos, donde cada grafo de la lista está incrustado en una superficie en la que H no está incrustado.
  2. A cada grafo incrustado en la lista, agregamos como máximo k vórtices, donde cada vórtice tiene una profundidad como máximo k.
  3. A cada grafo resultante le añadimos como máximo k nuevos vértices (llamados ápices ) y cualquier número de aristas, cada una de las cuales tiene al menos uno de sus extremos entre los ápices.
  4. Finalmente, unimos mediante sumas de k -cliques la lista de grafos resultante.

Tenga en cuenta que los pasos 1 y 2 dan como resultado un grafo vacío si H es planar, pero el número limitado de vértices añadidos en el paso 3 hace que la afirmación sea coherente con el Corolario 1.

Perfeccionamientos

Es posible obtener versiones reforzadas del teorema de la estructura de grafos dependiendo del conjunto H de menores prohibidos. Por ejemplo, cuando uno de los grafos en H es planar , entonces todo grafo H -libre de menores tiene una descomposición en árbol de ancho acotado; equivalentemente, puede representarse como una suma de cliques 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 H -libres de menores admiten una descomposición como una suma de cliques 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 ápice . [ 3 ]

Véase también

Notas

Referencias

Obtenido de " https://en.wikipedia.org/w/index.php?title=Graph_structure_theorem&oldid=1354296200 "
Lecturas relacionadas
6 articulos
MatemáticasMatemáticasLas matemáticas son un campo de estudio que descubre y organiza métodos, teorías y teoremas que se desarrollan y prueban para las necesidades de la...Teoría de grafosTeoría de grafosEn matemáticas , la teoría de grafos es el estudio de los grafos , que son estructuras matemáticas utilizadas para modelar relaciones por pares ent...gráfico HGráfico menorEn teoría de grafos , un grafo no dirigido H se denomina menor del grafo G si H puede formarse a partir de G eliminando aristas, vértices y contray...Incorporación de gráficosIncorporación de gráficosEn la teoría de grafos topológicos , una incrustación (también escrita imbedding ) de un grafo en una superficie es una representación de en la que...Estilo de visualización K_{6}}Neil Robertson (matemático)George Neil Robertson (nacido el 30 de noviembre de 1938) es un matemático que trabaja principalmente en teoría de grafos topológicos , actualmente...Paul Seymour (matemático)Paul Seymour (matemático)Paul D. Seymour FRS (nacido el 26 de julio de 1950) es un matemático británico conocido por su trabajo en matemáticas discretas , especialmente teo...