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 & Mohar (2007) y Lovász (2006) son encuestas accesibles a no especialistas, que describen el teorema y sus consecuencias.
Configuración y motivación del teorema
A menor de un gráfico G es cualquier gráfico H que es isomorfo a un gráfico que se puede obtener a partir de un subgrafo de G por contraer algunos bordes. Si G no no tiene una gráfica H como un menor de edad, entonces se dice que G es H exento . Sea H una gráfica fija. Intuitivamente, si G es un gran gráfico libre de H , entonces debería haber una "buena razón" para ello. La estructura gráfica teorema proporciona una "buena razón" tal en la forma de una descripción aproximada de la estructura de G . En esencia, cada gráfico libre de H G sufre de una de dos deficiencias estructurales: o G es "demasiado delgado" para tener a H como menor, o G puede estar (casi) incrustado topológicamente en una superficie que es demasiado simple para incrustar H sobre. 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.
Ancho del árbol
La anchura de árbol de un gráfico G es un número entero positivo que especifica el "delgadez" de G . Por ejemplo, un gráfico conectado 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 en serie-paralelo . Intuitivamente, un gran gráfico G tiene un ancho de árbol pequeño si y solo si G toma la estructura de un gran árbol cuyos nodos y bordes han sido reemplazados por pequeños gráficos. Damos una definición precisa del ancho del árbol en la subsección con respecto a las sumas de camarillas. Es un teorema que si H es menor de edad de G , entonces el ancho á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 del grafo implica que esta razón siempre se aplica en el caso de que H sea plano.
Corolario 1. Para cada grafo plano 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 los cuales k = 3). Ésta 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 libres de H.
Incrustaciones de superficie
Aproximadamente, 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 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 donde los bordes y vértices son incidentes o adyacentes. Un gráfico es plano si se incrusta en la esfera. Si un gráfico G se incrusta en una superficie particular, 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 verse como una vasta generalización del teorema de Kuratowski. Una versión de este teorema probada por Wagner (1937) establece que si un gráfico G es tanto libre de K 5 como libre 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 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 camarillas y vórtices .
Sumas de camarillas
A clique en una gráfica G es cualquier conjunto de vértices que son pares adyacentes en G . Para un entero no negativo k , una k -clique-suma de dos gráficos G y K es cualquier gráfico obtenido seleccionando un entero no negativo m ≤ k , seleccionando clique 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 -clique-suma de G 1 y G 2 , luego tomamos una k -clique-suma 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 en la lista tiene como máximo k + 1 vértices.
Corolario 1 nos indica que k -clique-sumas de gráficos pequeños describen la estructura en bruto H gráficos -free cuando H es plana. Cuando H no es plano, también necesitamos considerar k -clique-sumas 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 K 5 gráficos -free que están lejos de planar. En particular, la suma de 3 clique 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 grupo de resultados conocido como teorema de Wagner :
Teorema 2. Si G está libre de K 5 , entonces G puede obtenerse mediante sumas de 3 clique de una lista de gráficos planos y copias de un gráfico especial no plano 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 las gráficas libres de K 5 . Estos resultados son raros dentro de la teoría de grafos. El teorema de la estructura del gráfico 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 están libres de H.
Vórtices (descripción aproximada)
Uno podría tener la tentación de conjeturar que un análogo del teorema 2 es válido 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-clique-sums 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 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 trampas de dos formas 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 . 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 la 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.
Vórtices (definición precisa)
Una cara de un gráfico incrustado es una celda abierta de 2 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 una , v un 1 , ..., v un + s } donde un y s son números enteros y donde los subíndices se reducen modulo n . Deje que Λ ser una lista finita de intervalos circulares para F . Construimos una nueva gráfica de la siguiente manera. Para cada intervalo de circular L en Λ añadimos un nuevo vértice V L que une a cero o más de los vértices en L . Finalmente, para cada par { L , M } de intervalos en Λ, podemos agregar un borde que une v L con v M siempre que L y M tengan una intersección no vacía. El gráfico resultante se dice que es obtenido a partir de G por la adición de un vórtice de profundidad como máximo k (a la cara F ) a condición de que ningún vértice en el límite de F aparece en más de k de los intervalos en Λ.
Declaración del teorema de la estructura de la gráfica
Teorema de 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:
- Comenzamos con una lista de gráficos, donde cada gráfico de la lista está incrustado en una superficie en la que H no se incrusta
- a cada gráfico incrustado en la lista, agregamos como máximo k vórtices, donde cada vórtice tiene profundidad como máximo k
- a cada gráfico resultante agregamos como máximo k nuevos vértices (llamados vértices ) y agregamos cualquier número de aristas, cada una con al menos uno de sus puntos finales entre los vértices.
- finalmente, unimos a través de k-clique-sums la lista resultante de gráficos.
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 agregado en el paso 3. hace que la declaración sea consistente con el Corolario 1.
Refinamientos
Las versiones reforzadas del teorema de la estructura del gráfico son posibles dependiendo del conjunto H de menores prohibidos. Por ejemplo, cuando una de las gráficas en H es plana , entonces cada gráfica libre de H -menor tiene una descomposición de árbol de ancho acotado; de manera equivalente, se puede representar como una pandilla de gráficos de tamaño constante. [1] Cuando una de las gráficas de H se puede dibujar en el plano con un solo cruce , las gráficas libres de H -minor admiten una descomposición como una clique-suma 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 uno de los gráficos de H es un gráfico de vértice . [3]
Ver también
Notas
- ^ Grafica Menores V.
- ^ Robertson y Seymour (1993) ; Demaine, Hajiaghayi y Thilikos (2002) ).
- ^ Demaine, Hajiaghayi y Kawarabayashi (2009) .
Referencias
- Demaine, Erik D .; Hajiaghayi, Mohammad Taghi; Kawarabayashi, Ken-ichi (2009), "Algoritmos de aproximación a través de resultados estructurales para gráficos sin ápice menor", Proc. 36th International Colloquium Automata, Languages and Programming (ICALP '09) (PDF) , Lecture Notes in Computer Science, 5555 , Springer-Verlag, pp. 316–327, doi : 10.1007 / 978-3-642-02927-1_27 , MR 2544855.
- Demaine, Erik D .; Hajiaghayi, Mohammad Taghi; Thilikos, Dimitrios M. (2002), "1.5-Aproximación para el ancho de árbol de gráficos excluyendo un gráfico con un cruce como menor", Proc. 5to Taller internacional sobre algoritmos de aproximación para la optimización combinatoria (APPROX 2002) , Lecture Notes in Computer Science, 2462 , Springer-Verlag, págs. 67–80, doi : 10.1007 / 3-540-45753-4_8 , hdl : 2117/97497 , Señor 2091577.
- Kawarabayashi, Ken-ichi ; Mohar, Bojan (2007), "Algunos avances y aplicaciones recientes en la teoría de grafos menores", Gráficos y combinatoria , 23 (1): 1–46, doi : 10.1007 / s00373-006-0684-x , MR 2292102.
- Lovász, László (2006), "Graph minor theory", Bulletin of the American Mathematical Society , 43 (1): 75–86, doi : 10.1090 / S0273-0979-05-01088-8 , MR 2188176.
- Robertson, Neil ; Seymour, PD (1983), "Graph minors. I. Excluyendo un bosque", Journal of Combinatorial Theory , Serie B, 35 (1): 39–61, doi : 10.1016 / 0095-8956 (83) 90079-5 , MR 0723569.
- Robertson, Neil ; Seymour, PD (1986), "Graph menores. II. Aspectos algorítmicos del ancho del árbol", Journal of Algorithms , 7 (3): 309–322, doi : 10.1016 / 0196-6774 (86) 90023-4 , MR 0855559.
- Robertson, Neil ; Seymour, PD (1984), "Graph minors. III. Planar tree-width", Journal of Combinatorial Theory , Serie B, 36 (1): 49-64, doi : 10.1016 / 0095-8956 (84) 90013-3 , Señor 0742386.
- Robertson, Neil ; Seymour, PD (1990), "Graph minors. IV. Tree-width and well-cuasi-ordering", Journal of Combinatorial Theory , Serie B, 48 (2): 227-254, doi : 10.1016 / 0095-8956 (90 ) 90120-O , MR 1046757.
- Robertson, Neil ; Seymour, PD (1986), "Graph minors. V. Excluyendo un gráfico plano", Journal of Combinatorial Theory , Serie B, 41 (1): 92-114, doi : 10.1016 / 0095-8956 (86) 90030-4 , Señor 0854606.
- Robertson, Neil ; Seymour, PD (1986), "Graph menores. VI. Caminos disjuntos a través de un disco", Journal of Combinatorial Theory , Serie B, 41 (1): 115-138, doi : 10.1016 / 0095-8956 (86) 90031-6 , MR 0854607.
- Robertson, Neil ; Seymour, PD (1988), "Graph minors. VII. Disjoint Path on a surface", Journal of Combinatorial Theory , Serie B, 45 (2): 212–254, doi : 10.1016 / 0095-8956 (88) 90070-6 , MR 0961150.
- Robertson, Neil ; Seymour, PD (1990), "Graph menores. VIII. Un teorema de Kuratowski para superficies generales", Journal of Combinatorial Theory , Serie B, 48 (2): 255-288, doi : 10.1016 / 0095-8956 (90) 90121- F , MR 1046758.
- Robertson, Neil ; Seymour, PD (1990), "Graph minors. IX. Disjoint cruzado", Journal of Combinatorial Theory , Serie B, 49 (1): 40–77, doi : 10.1016 / 0095-8956 (90) 90063-6 , MR 1056819.
- Robertson, Neil ; Seymour, PD (1991), "Graph menores. X. Obstrucciones a la descomposición de árboles", Journal of Combinatorial Theory , Serie B, 52 (2): 153-190, doi : 10.1016 / 0095-8956 (91) 90061-N , MR 1110468.
- Robertson, Neil ; Seymour, PD (1993), "Excluyendo un gráfico con un cruce", en Robertson, Neil; Seymour, Paul (eds.), Teoría de la estructura de grafos: Proc. Conferencia de investigación conjunta de verano AMS-IMS-SIAM sobre Graph Minors , Contemporary Mathematics, 147 , American Mathematical Society, págs. 669–675, doi : 10.1090 / conm / 147/01206 , MR 1224738.
- Robertson, Neil ; Seymour, PD (1994), "Graph minors. XI. Circuits on a surface", Journal of Combinatorial Theory , Serie B, 60 (1): 72–106, doi : 10.1006 / jctb.1994.1007 , MR 1256585.
- Robertson, Neil ; Seymour, PD (1995), "Graph minors. XII. Distancia sobre una superficie", Journal of Combinatorial Theory , Serie B, 64 (2): 240–272, doi : 10.1006 / jctb.1995.1034 , MR 1339851.
- Robertson, Neil ; Seymour, PD (1995), "Graph minors. XIII. El problema de los caminos disjuntos", Journal of Combinatorial Theory , Serie B, 63 (1): 65-110, doi : 10.1006 / jctb.1995.1006 , MR 1309358.
- Robertson, Neil ; Seymour, PD (1995), "Graph minors. XIV. Extendiendo una incrustación", Journal of Combinatorial Theory , Serie B, 65 (1): 23–50, doi : 10.1006 / jctb.1995.1042 , MR 1347339.
- Robertson, Neil ; Seymour, PD (1996), "Graph minors. XV. Giant steps", Journal of Combinatorial Theory , Serie B, 68 (1): 112–148, doi : 10.1006 / jctb.1996.0059 , MR 1405708
- Robertson, Neil ; Seymour, PD (2003), "Graph minors. XVI. Excluyendo un gráfico no plano", Journal of Combinatorial Theory , Serie B, 89 (1): 43–76, doi : 10.1016 / S0095-8956 (03) 00042- X , MR 1999736.
- Robertson, Neil ; Seymour, PD (1999), "Graph minors. XVII. Domando un vórtice", Journal of Combinatorial Theory , Serie B, 77 (1): 162–210, doi : 10.1006 / jctb.1999.1919 , MR 1710538.
- Robertson, Neil ; Seymour, Paul (2003), "Graph menores. XVIII. Descomposiciones de árboles y cuasi-ordenamiento de pozos", Journal of Combinatorial Theory , Serie B, 89 (1): 77-108, doi : 10.1016 / S0095-8956 (03 ) 00067-4 , MR 1999737.
- Robertson, Neil ; Seymour, PD (2004), "Graph minors. XIX. Well-cuasi-ordering on a surface", Journal of Combinatorial Theory , Serie B, 90 (2): 325–385, doi : 10.1016 / j.jctb.2003.08. 005 , MR 2034033.
- Robertson, Neil ; Seymour, PD (2004), "Graph minors. XX. Conjetura de Wagner", Journal of Combinatorial Theory , Serie B, 92 (2): 325–357, doi : 10.1016 / j.jctb.2004.08.001 , MR 2099147.
- Robertson, Neil ; Seymour, Paul (2009), "Graph minors. XXI. Gráficos con vínculos únicos", Journal of Combinatorial Theory , Serie B, 99 (3): 583–616, doi : 10.1016 / j.jctb.2008.08.003 , MR 2507943.
- Robertson, Neil ; Seymour, Paul (2012), "Graph minors. XXII. Vértices irrelevantes en problemas de vinculación", Journal of Combinatorial Theory , Serie B, 102 (2): 530–563, doi : 10.1016 / j.jctb.2007.12.007 , MR 2885434.
- Robertson, Neil ; Seymour, Paul (2010), "Graph minors XXIII. Conjetura de inmersión de Nash-Williams", Journal of Combinatorial Theory , Serie B, 100 (2): 181-205, doi : 10.1016 / j.jctb.2009.07.003 , MR 2595703.
- Wagner, Klaus (1937), "Über eine Erweiterung des Satzes von Kuratowski", Deutsche Mathematik , 2 : 280–285.