En la teoría de grafos , una rama de las matemáticas, un grafo de vértice es un grafo que se puede hacer plano mediante la eliminación de un solo vértice . El vértice eliminado se llama vértice del grafo. Es un vértice, no el vértice porque un grafo de vértice puede tener más de un vértice; por ejemplo, en los grafos no planos mínimos K 5 o K 3,3 , cada vértice es un ápice. Los grafos de vértice incluyen grafos que son en sí mismos planos, en cuyo caso nuevamente cada vértice es un ápice. El grafo nulo también se cuenta como un grafo de vértice aunque no tenga ningún vértice para eliminar.
Los gráficos de vértice 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 , [1] la conjetura de Hadwiger , [2] gráficos YΔY-reducibles, [3] y relaciones entre el ancho del árbol y el diámetro del gráfico . [4]
Los grafos de vértice se cierran bajo la operación de tomar menores : contraer cualquier arista, o eliminar cualquier arista o vértice, conduce a otro grafo de vértice. Porque, si G es un grafo de vértice con vértice v , entonces cualquier contracción o eliminación que no involucre a v preserva la planaridad del grafo restante, al igual que cualquier eliminación de una arista incidente a v . Si una arista incidente a v se contrae, el efecto en el grafo restante es equivalente a la eliminación del otro punto final de la arista. Y si se elimina v mismo, cualquier otro vértice puede ser elegido como el vértice. [5]
Por el teorema de Robertson-Seymour , debido a que forman una familia de grafos cerrada menor, los grafos de vértice tienen una caracterización de grafo prohibido . Solo hay un número finito de grafos que no son grafos de vértice ni tienen otro grafo no de vértice como menor. Estos grafos son menores prohibidos por la propiedad de ser un grafo de vértice. Cualquier otro grafo G es un grafo de vértice si y solo si ninguno de los menores prohibidos es un menor de G . Estos menores prohibidos incluyen los siete grafos de la familia Petersen , tres grafos desconectados formados a partir de las uniones disjuntas de dos de K 5 y K 3,3 , y muchos otros grafos. Sin embargo, sigue sin conocerse una descripción completa de ellos. [5] [6]
A pesar de que el conjunto completo de menores prohibidos permanece desconocido, es posible probar si un grafo dado es un grafo de vértice, y si es así, encontrar un vértice para el grafo, en tiempo lineal . De manera más general, para cualquier constante fija k , es posible reconocer en tiempo lineal los grafos de k -ápices , los grafos en los que la eliminación de un conjunto cuidadosamente elegido de como máximo k vértices conduce a un grafo plano. [7] Sin embargo, si k es variable, el problema es NP-completo . [8]
Cada grafo de vértice tiene un número cromático de cinco como máximo: el grafo planar 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 , la afirmación de que todo grafo 6-cromático tiene como menor al grafo completo K 6 : demostraron que cualquier contraejemplo mínimo de la conjetura tendría que ser un grafo de vértice, pero como no hay grafos de vértice 6-cromáticos, tal contraejemplo no puede existir.
Jørgensen (1994) conjeturó que todo grafo conexo de 6 vértices que no tenga K 6 como menor debe ser un grafo de vértice. Si esto se demostrara, el resultado de Robertson–Seymour–Thomas sobre la conjetura de Hadwiger sería una consecuencia inmediata. [2] La conjetura de Jørgensen sigue sin demostrarse. [9] Sin embargo, si es falsa, solo tiene un número finito de contraejemplos. [10]
Una familia de grafos F tiene un ancho de árbol local acotado si los grafos en F obedecen a una relación funcional entre diámetro y ancho de árbol : existe una función f tal que el ancho de árbol de un grafo de diámetro- d en F es como máximo f ( d ) . Los grafos de vértice no tienen un ancho de árbol local acotado: los grafos de vértice formados al conectar un vértice de vértice a cada vértice de un grafo de cuadrícula n × n tienen un ancho de árbol n y diámetro 2, por lo que el ancho de árbol no está acotado por una función de diámetro para estos grafos. Sin embargo, los grafos de vértice están íntimamente conectados con el ancho de árbol local acotado: las familias de grafos menores-cerradas F que tienen un ancho de árbol local acotado son exactamente las familias que tienen un grafo de vértice como uno de sus menores prohibidos. [4] Una familia de grafos menores-cerrada que tiene un grafo de vértice como uno de sus menores prohibidos se conoce como apex-minor-free . Con esta terminología, la conexión entre los gráficos de vértice y el ancho de árbol local se puede reformular como el hecho de que las familias de gráficos libres de menores de vértice son las mismas que las familias de gráficos cerrados de menores con ancho de árbol local acotado.
El concepto de ancho de árbol local acotado constituye la base de la teoría de la bidimensionalidad y permite que muchos problemas algorítmicos en grafos libres de menores apéndices se resuelvan exactamente mediante un algoritmo de tiempo polinomial o un algoritmo manejable con parámetros fijos , o se aproximen utilizando un esquema de aproximación de tiempo polinomial . [11] Las familias de grafos libres de menores apéndices obedecen a una versión reforzada del teorema de estructura de grafos , lo que conduce a algoritmos de aproximación adicionales para la coloración de grafos y el problema del viajante de comercio . [12] Sin embargo, algunos de estos resultados también se pueden extender a familias de grafos menores cerrados arbitrarios a través de teoremas de estructura que los relacionan con grafos libres de menores apéndices. [13]
Si G es un grafo 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 entre sí todas las caras en las que v debe estar conectado. Por ejemplo, agregar un solo vértice a un grafo exterior-planar (un grafo con τ = 1 ) produce un grafo planar. Cuando G \ { v } es 3-conexo, su límite está dentro de un factor constante de óptimo: cada incrustación de superficie de G requiere género al menos τ/160 . Sin embargo, es NP-difícil determinar el género óptimo de una incrustación superficial de un gráfico de vértice. [14]
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, minimizando el número total de cruces, en tiempo polinomial. [15] 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 agregando un solo borde a un gráfico plano. [16]
Los grafos de vértice también se pueden incrustar sin enlaces en el espacio tridimensional: se pueden incrustar de tal manera que cada ciclo del grafo sea el límite de un disco que no sea atravesado por ninguna otra característica del grafo. [17] Se puede obtener un dibujo de este tipo dibujando la parte plana del grafo en un plano, colocando el vértice sobre el plano y conectando el vértice mediante aristas rectas a cada uno de sus vecinos. Los grafos incrustables sin enlaces forman una familia cerrada menor con los siete grafos de la familia Petersen como sus menores prohibidos mínimos; [1] por lo tanto, estos grafos también están prohibidos como menores para los grafos de vértice. Sin embargo, existen grafos incrustables sin enlaces que no son grafos de vértice.
Un gráfico conexo es YΔY-reducible si se puede reducir a un único 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 el reemplazo de un vértice de grado dos y sus dos aristas vecinas por una única arista. [3]
Al igual que los grafos de vértice y los grafos integrables sin enlaces, los grafos YΔY-reducibles están cerrados bajo los menores de grafos. Y, al igual que los grafos integrables sin enlaces, los grafos YΔY-reducibles tienen los siete grafos de la familia Petersen como menores prohibidos, lo que plantea la pregunta de si estos son los únicos menores prohibidos y si los grafos YΔY-reducibles son los mismos que los grafos integrables sin enlaces. Sin embargo, Neil Robertson proporcionó un ejemplo de un grafo de vértice que no es YΔY-reducible. Dado que cada grafo de vértice es integrable sin enlaces, esto demuestra que hay grafos que son integrables sin enlaces pero no YΔY-reducibles y, por lo tanto, que hay menores prohibidos adicionales para los grafos YΔY-reducibles. [3]
El gráfico de vértice de Robertson se muestra en la figura. Se puede obtener conectando un vértice a 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 de hipercubo de cuatro dimensiones . Debido a que el gráfico del dodecaedro rómbico es plano, el gráfico de Robertson es un gráfico 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. [3]
Si un grafo es un grafo de vértice, no es necesariamente el caso de que tenga un vértice único. Por ejemplo, en los grafos no planos mínimos menores K 5 y K 3,3 , cualquiera de los vértices puede elegirse como el 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 lo tanto, K 5 y K 3,3 son casi planos. Proporcionó una clasificación de estos grafos en cuatro subconjuntos, uno de los cuales consiste en los grafos que (como las escaleras de Möbius ) pueden incrustarse en la banda de Möbius de tal manera que el borde único de la banda coincida con un ciclo hamiltoniano del grafo. Antes de la prueba del teorema de los cuatro colores , demostró que todo grafo casi plano puede colorearse con cuatro colores como máximo, excepto los grafos formados a partir de un grafo de rueda con un ciclo exterior impar reemplazando el vértice central con dos vértices adyacentes, que requieren cinco colores. Además, demostró que, con una única excepción (el grafo de complemento de ocho vértices del cubo ), todo grafo 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, [18] gráficos formados añadiendo una arista a un gráfico plano, [19] y gráficos formados a partir de un gráfico plano incrustado reemplazando un número limitado de caras por "vórtices" de ancho de trayectoria limitado , [20] así como para otros conjuntos de gráficos definidos con menor precisión.
Se dice que un grafo abstracto tiene n vértices si se puede convertir en plano eliminando n vértices o menos. Un grafo con 1 vértice también se dice que tiene ápices.
Según Lipton et al. (2018), un grafo es de arista-vértice si hay alguna arista en el grafo que se puede eliminar para hacer que el grafo sea plano. Un grafo es de contracción-vértice si hay alguna arista en el grafo que se puede contraer para hacer que el grafo sea plano.
En general, si X es una clase de grafos, un grafo "ápice- X " es un grafo que se puede incorporar a la clase X eliminando algún vértice. Por ejemplo, un ápice- cografo es un grafo G que tiene un vértice v tal que G―v es un cografo.
