Gráfico de ápice - Apex graph

Un gráfico de vértice. El subgrafo formado al eliminar el vértice rojo es plano .

En la teoría de grafos , una rama de las matemáticas, un gráfico de vértice es un gráfico que se puede hacer plano mediante la eliminación de un solo vértice. El vértice eliminado se denomina vértice del gráfico. Es un vértice, no el vértice porque un gráfico de vértice puede tener más de un vértice; por ejemplo, en las gráficas no planas mínimas K 5 o K 3,3 , cada vértice es un vértice. Los gráficos de vértice incluyen gráficos que son planos en sí mismos, en cuyo caso, de nuevo, cada vértice es un vértice. El gráfico nulo también se cuenta como un gráfico de vértice aunque no tenga vértices para eliminar.

Los gráficos de ápice se cierran bajo la operación de tomar menores y juegan un papel en varios otros aspectos de la teoría de gráficos menores: incrustación sin enlaces , conjetura de Hadwiger , gráficos YΔY reducibles y relaciones entre el ancho del árbol y el diámetro del gráfico .

Caracterización y reconocimiento

Los gráficos de ápice se cierran bajo la operación de tomar menores : contraer cualquier borde, o eliminar cualquier borde o vértice, conduce a otro gráfico de ápice. Porque, si G es un gráfico de vértice con vértice v , entonces cualquier contracción o remoción que no involucre a v preserva la planaridad del gráfico restante, al igual que cualquier remoción de borde de un borde incidente a v . Si se contrae un borde incidente av , el efecto en el gráfico restante es equivalente a la eliminación del otro extremo del borde. Y si se elimina v , se puede elegir cualquier otro vértice como vértice.

Según el teorema de Robertson-Seymour , debido a que forman una familia de gráficos menor cerrada, los gráficos de vértice tienen una caracterización de gráfico prohibida . Solo hay un número finito de gráficos que no son gráficos de vértice ni tienen otro gráfico que no sea de vértice como menor. Estos gráficos están prohibidos a menores de edad por la propiedad de ser un gráfico vértice. Cualquier otra gráfica G es un grafo vértice si y sólo si ninguno de los menores de edad prohibidos es menor de edad de G . Estos menores prohibidos incluyen los siete gráficos de la familia Petersen , tres gráficos desconectados formados a partir de las uniones inconexas de dos de K 5 y K 3,3 , y muchos otros gráficos. Sin embargo, se desconoce una descripción completa de ellos.

A pesar de que se desconoce el conjunto completo de menores prohibidos, es posible probar si un gráfico dado es un gráfico de vértice y, de ser así, encontrar un vértice del gráfico en tiempo lineal . De manera más general, para cualquier constante fija k , es posible reconocer en tiempo lineal los gráficos k- ápice , los gráficos en los que la eliminación de algún conjunto cuidadosamente elegido de como máximo k vértices conduce a un gráfico plano. Sin embargo, si k es variable, el problema es NP-completo .

Número cromático

Cada gráfico de vértice tiene un número cromático como máximo de cinco: el gráfico plano subyacente requiere como máximo cuatro colores según el teorema de los cuatro colores , y el vértice restante necesita como máximo un color adicional. Robertson, Seymour y Thomas (1993a) utilizaron este hecho en su demostración del caso k  = 6 de la conjetura de Hadwiger , el enunciado de que todo gráfico 6-cromático tiene el gráfico completo K 6 como menor: demostraron que cualquier contraejemplo mínimo para la conjetura tendría que ser un gráfico de ápice, pero como no hay gráficos de ápice de 6 cromáticos, tal contraejemplo no puede existir.

Problema no resuelto en matemáticas :

¿Es cada gráfico libre de menores conectados con 6 vértices un gráfico vértice?

(más problemas sin resolver en matemáticas)

Jørgensen (1994) conjeturó que cada grafo conectado a 6 vértices que no tenga a K 6 como menor debe ser un grafo de vértice. Si esto se probara, el resultado de Robertson-Seymour-Thomas sobre la conjetura de Hadwiger sería una consecuencia inmediata. La conjetura de Jørgensen sigue sin demostrarse. Sin embargo, si es falso, solo tiene un número finito de contraejemplos.

Ancho de árbol local

Una familia de gráficos F tiene un ancho de árbol local acotado si los gráficos de F obedecen a una relación funcional entre diámetro y ancho de árbol : existe una función ƒ tal que el ancho de árbol de un gráfico de diámetro d en F es como máximo ƒ ( d ). Los gráficos de vértice no tienen un ancho de árbol local limitado: los gráficos de vértice formados al conectar un vértice de vértice a cada vértice de un gráfico de cuadrícula n  ×  n tienen un ancho de árbol n y un diámetro 2, por lo que el ancho de árbol no está limitado por una función de diámetro para estos gráficos . Sin embargo, los gráficos de vértice están íntimamente conectados al ancho de árbol local limitado: las familias de gráficos menores cerrados F que tienen un ancho de árbol local limitado son exactamente las familias que tienen un gráfico de vértice como uno de sus menores prohibidos. Una familia de gráficos menor-cerrada que tiene un gráfico de vértice como uno de sus menores prohibidos se conoce como libre de vértice-menor . Con esta terminología, la conexión entre los gráficos de ápice y el ancho de árbol local se puede reformular como el hecho de que las familias de gráficos sin ápice menores son las mismas que las familias de gráficos menores cerrados con ancho de árbol local limitado.

El concepto de ancho de árbol local acotado forma la base de la teoría de la bidimensionalidad y permite que muchos problemas algorítmicos en gráficos sin ápice menor se resuelvan exactamente mediante un algoritmo de tiempo polinomial o un algoritmo manejable de parámetros fijos , o que se aproximen mediante un algoritmo de tiempo polinomial. esquema de aproximación polinomial-temporal . Las familias de grafos sin ápice menor obedecen a una versión reforzada del teorema de la estructura de grafos , lo que lleva a algoritmos de aproximación adicionales para colorear grafos y el problema del viajante . Sin embargo, algunos de estos resultados también pueden extenderse a familias arbitrarias de grafos menores cerrados mediante teoremas de estructura que los relacionan con grafos sin ápices menores.

Embeddings

Si G es un gráfico de vértice con vértice v , y τ es el número mínimo de caras necesarias para cubrir todos los vecinos de v en una incrustación plana de G \ { v }, entonces G puede incrustarse en una superficie bidimensional de género τ - 1: simplemente agregue ese número de puentes a la incrustación plana, conectando todas las caras en las que se debe conectar v . Por ejemplo, agregar un solo vértice a un gráfico plano exterior (un gráfico con τ = 1) produce un gráfico plano. Cuando G \ { v } está conectado en 3, su límite está dentro de un factor constante de óptimo: cada incrustación superficial de G requiere un género al menos τ / 160. Sin embargo, es NP-difícil determinar el género óptimo de una superficie incrustada de un gráfico de vértice.

Al utilizar árboles SPQR para codificar las posibles incrustaciones de la parte plana de un gráfico de vértice, es posible calcular un dibujo del gráfico en el plano en el que los únicos cruces involucran el vértice del vértice, minimizando el número total de cruces, en polinomio. hora. Sin embargo, si se permiten cruces arbitrarios, se vuelve NP-difícil minimizar el número de cruces, incluso en el caso especial de los gráficos de vértice formados al agregar un solo borde a un gráfico plano.

Los gráficos Apex también se pueden incrustar sin vínculos en un espacio tridimensional: se pueden incrustar de tal manera que cada ciclo en el gráfico sea el límite de un disco que no sea atravesado por ninguna otra característica del gráfico. Un dibujo de este tipo puede obtenerse dibujando la parte plana del gráfico en un plano, colocando el vértice sobre el plano y conectando el vértice mediante bordes en línea recta con cada uno de sus vecinos. Los gráficos integrables sin enlaces forman una familia cerrada de menores con los siete gráficos de la familia Petersen como sus menores mínimos prohibidos; por lo tanto, estos gráficos también están prohibidos como menores para los gráficos de vértice. Sin embargo, existen gráficos integrables sin enlaces que no son gráficos de vértice.

YΔY-reducibilidad

Ejemplo de Robertson de un gráfico de vértice no reducible en 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 transformada Δ-Y o Y-Δ , la eliminación de un bucle propio o adyacencia múltiple, la eliminación de un vértice con un vecino, y la sustitución de un vértice de grado dos y sus dos aristas vecinas por una sola arista.

Al igual que los gráficos de vértice y los gráficos integrables sin enlaces, los gráficos reducibles de YΔY se cierran en gráficos menores. Y, al igual que los gráficos integrables sin enlaces, los gráficos YΔY reducibles tienen los siete gráficos de la familia Petersen como menores prohibidos, lo que genera la pregunta de si estos son los únicos menores prohibidos y si los gráficos reducibles YΔY son los mismos que los gráficos integrables sin enlaces. gráficos. Sin embargo, Neil Robertson proporcionó un ejemplo de un gráfico de vértice que no es YΔY-reducible. Dado que cada gráfico de vértice es integrable sin enlaces, esto muestra que hay gráficos que son incrustables sin enlaces pero no reducibles en YΔY y, por lo tanto, hay menores prohibidos adicionales para los gráficos reducibles en YΔY.

El gráfico de vértice de Robertson se muestra en la figura. Puede obtenerse conectando un vértice del vértice con cada uno de los vértices de grado tres de un dodecaedro rómbico , o fusionando dos vértices diametralmente opuestos de un gráfico hipercubo de cuatro dimensiones . Debido a que la gráfica del dodecaedro rómbico es plana, la gráfica de Robertson es una gráfica de vértice. Es un gráfico sin triángulos con un grado mínimo de cuatro, por lo que no se puede cambiar mediante ninguna reducción YΔY.

Gráficos casi planos

La escalera de Möbius de 16 vértices , un ejemplo de un gráfico casi plano.

Si un gráfico es un gráfico de vértice, no es necesariamente el caso de que tenga un vértice único. Por ejemplo, en los gráficos no planos menor-mínimo K 5 y K 3,3 , se puede elegir cualquiera de los vértices como vértice. Wagner ( 1967 , 1970 ) definió un grafo casi plano como un grafo de vértice no plano con la propiedad de que todos los vértices pueden ser el vértice del grafo; por tanto, K 5 y K 3,3 son casi planos. Proporcionó una clasificación de estos gráficos en cuatro subconjuntos, uno de los cuales consiste en los gráficos que (como las escaleras de Möbius ) se pueden incrustar en la tira de Möbius de tal manera que el borde único de la tira coincida con un ciclo hamiltoniano del grafico. Antes de la demostración del teorema de los cuatro colores , demostró que cada gráfico casi plano se puede colorear con un máximo de cuatro colores, excepto los gráficos formados a partir de un gráfico de rueda con un ciclo externo impar al reemplazar el vértice del eje con dos vértices adyacentes, que requieren cinco colores. Además, demostró que, con una sola excepción (el gráfico de complemento de ocho vértices del cubo ), cada gráfico casi plano tiene una incrustación en el plano proyectivo .

Sin embargo, la frase "gráfico casi plano" es muy ambigua: también se ha utilizado para referirse a gráficos de vértice, gráficos formados al agregar un borde a un gráfico plano y gráficos formados a partir de un gráfico incrustado plano reemplazando un número limitado de caras. por "vórtices" de ancho de ruta acotado , así como por otros conjuntos de gráficos definidos con menor precisión.

Clases de grafos relacionados

Se dice que un gráfico abstracto es n- ápice si se puede hacer plano eliminando n o menos vértices. También se dice que un gráfico de 1 vértice es vértice.

Según Lipton et al. (2016) , un gráfico es borde-ápice si hay algún borde en el gráfico que se puede eliminar para hacer el gráfico plano. Un gráfico tiene vértice de contracción si hay algún borde en el gráfico que se puede contraer para hacer el gráfico plano.

Ver también

Notas

Referencias