Recuento de ápices

En la teoría de grafos, un grafo de vértice es un grafo que puede volverse plano quitando un vértice. El vértice eliminado se llama la parte superior del gráfico. Tenga en cuenta que puede haber más de un vértice. Por ejemplo, en un gráfico mínimo no plano K 5 o K 3,3 , cada vértice es un vértice. Los gráficos de vértice incluyen gráficos inicialmente planos en los que cada vértice es un vértice. Un grafo nulo también se considera apical, aunque no tiene vértices que eliminar.

Los gráficos de vértice se cierran bajo la operación de generar menores y juegan un papel importante en varios otros aspectos de la teoría de gráficos menores, incluida la incrustación no vinculada [1] , la conjetura de Hadwiger [2] , los gráficos reducibles YΔY [3] y la relación entre ancho del árbol y diámetro del gráfico [4] [5] .

Descripción y reconocimiento

Los gráficos de vértice se cierran bajo la operación de generar menores : reducir cualquier borde o eliminar un vértice o borde conduce a otro gráfico de vértice. De hecho, si G es un grafo de vértices con vértice v , entonces una contracción o eliminación que no afecta al vértice v conserva la planaridad del resto del gráfico (sin vértice v ). lo mismo ocurre cuando se elimina cualquier incidente de borde con v . Si se contrae una arista incidente con v , el efecto es equivalente a quitar el extremo opuesto de la arista. Si se elimina el vértice v , cualquier otro vértice puede considerarse un vértice [6] .

Dado que los grafos de vértice son cerrados por la operación de generar menores, por el teorema de Robertson-Seymour tienen una caracterización por grafos prohibidos . Solo hay un número finito de gráficos que no son gráficos de vértice y no contienen como menor otro gráfico que no sea de vértice. Estos grafos son menores prohibidos por la propiedad de grafos de vértices. Cualquier otro grafo G es vértice si y solo si ninguno de los menores prohibidos es menor de G . Los menores prohibidos incluyen siete gráficos de la familia Petersen , tres gráficos desconectados formados a partir de uniones disjuntas de K 5 y K 3,3 , y muchos otros gráficos. Una lista completa de todos los menores prohibidos sigue siendo incompleta [6] [7] .

A pesar de que no se conoce la lista completa de menores prohibidos, es posible comprobar en tiempo lineal si un grafo dado es vértice, y si lo es, encontrar el vértice del gráfico. De manera más general, para cualquier k constante fija, los gráficos de k -vértices (gráficos en los que la eliminación de un conjunto cuidadosamente elegido que contiene como máximo k vértices conduce a un gráfico plano [8] ) pueden reconocerse en tiempo lineal . Sin embargo, si k no es fijo, el problema se vuelve NP-completo [9] .

Número cromático

Cualquier gráfico de vértice tiene un número cromático que no exceda de cinco: un gráfico plano sin vértice requiere como máximo cuatro colores según el teorema de los cuatro colores , y un color adicional es suficiente para un vértice. Robertson, Seymour y Thomas [2] usaron este hecho para probar el caso k  = 6 de la conjetura de Hadwiger , la afirmación de que cualquier grafo 6-cromático tiene un grafo completo K 6 como menor; demostraron que cualquier contraejemplo mínimo para la conjetura debe ser un gráfico de vértice, pero no hay gráficos cromáticos de vértice 6, por lo que no existe tal contraejemplo.

Problemas no resueltos en matemáticas : ¿Todos los gráficos conectados por 6 vértices no tienen vértice menor?

Jorgensen [10] conjeturó que cualquier grafo conexo con 6 vértices que no tenga K 6 como menores debe ser vértice. Si esto se probara, el resultado de Robertson-Seymour-Thomas para la conjetura de Hadwiger sería una consecuencia directa de [2] . La conjetura de Jorgensen aún no ha sido probada [11] . Sin embargo, si la conjetura es falsa, solo tiene un número finito de contraejemplos [12] .

Ancho del árbol local

Una familia de gráficos F tiene un ancho de árbol local acotado si los gráficos en F obedecen a una relación funcional entre el diámetro y el ancho del árbol : existe una función ƒ tal que el ancho del árbol de un gráfico en F con diámetro d no excede ƒ( d ). Los gráficos superiores no tienen un ancho de árbol local acotado: el gráfico formado al conectar un vértice a cada vértice de una red n  ×  n tiene un ancho de árbol n y un diámetro de 2, por lo que el ancho del árbol no está limitado por alguna función del diámetro de estos gráficos. . Sin embargo, los gráficos de vértice están estrechamente relacionados con los gráficos con un ancho de árbol local acotado: las familias de gráficos F cerrados menores que tienen un ancho de árbol local acotado son exactamente familias cuyos menores prohibidos son algún gráfico de ápice [4] [5] . Se sabe que las familias de gráficos cerrados por menor que tienen un gráfico de vértice como su menor están libres de vértice menor . De acuerdo con esta terminología, la relación entre grafos de vértice y ancho de árbol local se puede reformular de la siguiente manera: familias de grafos libres de vértices menores coinciden con familias de grafos cerrados en menores con ancho de árbol local acotado.

El concepto de ancho de árbol local acotado forma la base de la teoría de la bidimensionalidad y permite resolver muchos problemas algorítmicos en gráficos libres de menores superiores exactamente mediante un algoritmo de tiempo polinomial, o mediante un algoritmo solucionable de parámetro fijo , o el problema se puede aproximar usando un tiempo polinomial de esquema aproximado [4] [13] [14] . Para familias de grafos libres de menores apicales, se cumple una versión reforzada del teorema del grafico estructural , lo que conduce a algoritmos de aproximación adicionales para la coloración de grafos y para el problema del viajante de comercio [15] . Sin embargo, algunos de estos resultados pueden extenderse a familias arbitrarias de grafos menores cerrados mediante el uso de teoremas de estructura para grafos asociados con familias que están libres de vértices menores [16] .

Adjuntos

Si un gráfico G es un gráfico de vértice con vértice v y es igual al número mínimo de caras requeridas para cubrir todos los vecinos del vértice v bajo una incrustación plana G \{ v }, entonces G puede estar incrustado en una superficie de género bidimensional agregando tantos puentes a la incrustación plana conectando así todas las caras a las que se va a conectar v . Por ejemplo, agregar un vértice a un gráfico plano exterior (un gráfico con un ) produce un gráfico plano. Si el gráfico G \{ v } es conexo en 3, su límite no difiere del óptimo en más de un factor constante: cualquier incrustación de G en una superficie requiere género al menos . Sin embargo, el problema de determinar el género óptimo para una superficie de incrustación para gráficos de vértices es un problema NP-difícil [17] .

Cuando se usan árboles SPQR para codificar posibles incrustaciones de la parte plana del vértice del gráfico, es posible calcular en tiempo polinomial la incrustación del gráfico en un plano en el que las intersecciones son causadas solo por bordes que emanan del vértice del ápice, y el total el número de intersecciones es mínimo [18] . Si se permiten intersecciones arbitrarias, el problema de minimizar el número de intersecciones se vuelve NP-difícil, incluso en el caso especial de los gráficos de vértices formados al agregar un solo borde a un gráfico plano [19] .

Los gráficos de vértices se pueden incrustar sin vincularse en el espacio tridimensional: se pueden incrustar de tal manera que cualquier ciclo en el gráfico sea el límite de un disco que no se intersecta con ninguna otra parte del gráfico [20] . Se puede obtener un dibujo de este tipo dibujando la parte plana del gráfico en un plano, colocando la parte superior del gráfico sobre el plano y conectándolo a sus vecinos con segmentos. Los gráficos integrables sin enlaces forman una familia cerrada de menores con siete gráficos de la familia Petersen como menores prohibidos mínimos [1] . Por lo tanto, estos gráficos también son menores prohibidos para los gráficos de vértices. Sin embargo, hay gráficos que se pueden integrar sin un enlace y no son vértice.

Reducibilidad YΔY

Un gráfico conectado es YΔY-reducible si se puede reducir a un solo vértice mediante una secuencia de pasos, cada uno de los cuales es una transformación Δ-Y o Y-Δ , eliminando un bucle o varios bordes, eliminando un vértice con un vecino, y reemplazando un vértice de grado dos y sus dos aristas adyacentes por una arista [3] .

Al igual que los gráficos de vértices y los gráficos incrustables sin enlaces, los gráficos reducibles YΔY se cierran bajo la operación de generación de menores. Al igual que los gráficos incrustables sin vincular, los gráficos reducibles YΔY tienen siete gráficos de la familia Petersen como menores prohibidos mínimos, lo que plantea la cuestión de si estos gráficos son los únicos menores prohibidos y si las familias de gráficos reducibles YΔY y gráficos incrustables sin vincular coinciden. . Sin embargo, Neil Robertson dio un ejemplo de un gráfico de vértice que no es reducible por YΔY. Dado que cualquier gráfico de vértice es incrustable sin un enlace, esto muestra que hay gráficos incrustables sin un enlace que no son reducibles con YΔY y, por lo tanto, hay menores prohibidos adicionales para los gráficos reducibles con YΔY [3] .

El gráfico del vértice de Robertson se muestra en la figura. Se puede obtener conectando el vértice con todos los vértices del dodecaedro rómbico de grado tres o fusionando dos vértices opuestos del gráfico de hipercubo de cuatro dimensiones . Debido a que la gráfica del dodecaedro rómbico es plana, la gráfica de Robertson es vértice. El gráfico no contiene triángulos y tiene un grado mínimo de cuatro, por lo que no se le puede aplicar ninguna operación de reducción YΔY [3] .

Gráficos casi planos

Si un gráfico es un vértice, no necesariamente tiene un solo vértice. Por ejemplo, en grafos no planos menores-mínimos K 5 y K 3,3 se puede elegir cualquier vértice como vértice. Wagner [21] [22] definió un gráfico casi plano como un gráfico de vértice no plano en el que cualquier vértice puede servir como vértice. Así , K 5 y K 3,3 son gráficos casi planos. Dio una clasificación de tales gráficos, dividiéndolos en cuatro familias. Una familia consta de gráficos que (como las escaleras de Möbius ) se pueden incrustar en una tira de Möbius de tal manera que el borde de la tira coincida con el ciclo hamiltoniano del gráfico. Incluso antes de probar el teorema de los cuatro colores , demostró que cualquier gráfico casi plano puede colorearse con no más de cuatro colores, con la excepción de los gráficos formados a partir de una rueda con un ciclo exterior impar reemplazando el vértice central con dos vértices adyacentes: tal gráfico necesita cinco colores. Además, demostró que, con una excepción (el complemento de ocho vértices de un cubo ), cualquier gráfico casi plano tiene una incrustación en el plano proyectivo .

Sin embargo, la frase "gráfico casi plano" es muy ambigua: el mismo término se ha utilizado para gráficos de vértices [20] [4] , gráficos formados al agregar un solo borde a un gráfico plano [23] , gráficos formados a partir de una incrustación plana de un gráfico reemplazando un número limitado de caras "torbellinos" de ancho de camino limitado [24] , así como algunos otros conjuntos de gráficos menos estrictamente definidos.

Notas

  1. ↑ 12 Robertson, Seymour, Thomas, 1993b .
  2. ↑ 1 2 3 Robertson, Seymour, Thomas, 1993a .
  3. ↑ 1 2 3 4 Truemper, 1992 .
  4. ↑ 1 2 3 4 Eppstein, 2000 .
  5. ↑ 1 2 Demaine, Hajiaghayi, 2004 .
  6. ↑ 1 2 Gupta, Impagliazzo, 1991 .
  7. ↑ Perforar, 2014 .
  8. ↑ Kawarabayashi, 2009 .
  9. ↑ Lewis, Yannakakis, 1980 .
  10. ↑ Jorgensen, 1994 .
  11. ↑ Conjetura de Jorgensen , < http://www.openproblemgarden.org/op/jorgensens_conjecture > . Consultado el 13 de noviembre de 2016. Archivado el 14 de noviembre de 2016 en Wayback Machine . 
  12. ↑ Kawarabayashi, Norine, Thomas, Wollan, 2012 .
  13. ↑ Frick, Grohe, 2001 .
  14. ↑ Demaine, Hajiaghayi, 2005 .
  15. ↑ Demaine, Hajiaghayi, Kawarabayashi, 2009 .
  16. ↑ Grohe, 2003 .
  17. ↑ Mohar, 2001 .
  18. ↑ Chimani, Gutwenger, Mutzel, Wolf, 2009 .
  19. ↑ Cabello, Mohar, 2010 .
  20. ↑ 12 Robertson, Seymour, Thomas, 1993c .
  21. ↑ Wagner, 1967 .
  22. ↑ Wagner, 1970 .
  23. ↑ Archidiácono, Bonnington, 2004 .
  24. ↑ Abraham, Gavoille, 2006 .

Literatura