En la teoría de grafos , una rama de las matemáticas, un gráfico de vértice es un gráfico que puede hacerse plano mediante la eliminación de un solo vértice. El vértice eliminado se llama 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 del vértice incluyen gráficos que son planos, en cuyo caso nuevamente cada vértice es un vértice. El gráfico nulo también se cuenta como un gráfico de vértice a pesar de que no tiene vértice para eliminar.
Los gráficos Apex se cierran bajo la operación de tomar menores y desempeñan un papel en varios otros aspectos de la teoría menor de gráficos: incrustación sin enlaces , [1] conjetura de Hadwiger , [2] gráficos reducibles YΔY, [3] y relaciones entre el ancho del árbol y el diámetro del gráfico .
Caracterización y reconocimiento [ editar ]
Los gráficos de Apex 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 eliminación que no implique v conserva la planaridad del gráfico restante, al igual que cualquier eliminación de borde de un incidente de borde a v . Si se contrae un borde incidente a v , el efecto en el gráfico restante es equivalente a la eliminación del otro punto final del borde. Y si se elimina v , se puede elegir cualquier otro vértice como vértice. [5]
Según el teorema de Robertson-Seymour , debido a que forman una familia de gráficos cerrados menores, los gráficos de vértice tienen una caracterización de gráfico prohibida . Solo hay muchos gráficos que no son gráficos de ápice ni tienen otro gráfico que no sea de ápice como menor. Estos gráficos están prohibidos a los menores por la propiedad de ser un gráfico de 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 por las uniones disjuntas de dos de K 5 y K 3,3, y muchos otros gráficos. Sin embargo, una descripción completa de ellos sigue siendo desconocida. [5] [6]
A pesar de que el conjunto completo de menores prohibidos sigue siendo desconocido, es posible probar si un gráfico dado es un gráfico de vértice y, de ser así, encontrar un vértice para el gráfico, en tiempo lineal . De manera más general, para cualquier constante constante 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 a lo sumo k vértices conduce a un gráfico plano. [7] Si k es variable, sin embargo, el problema es NP-completo . [8]
Número cromático [ editar ]
Cada gráfico de vértice tiene un número cromático como máximo cinco: el gráfico plano subyacente requiere como máximo cuatro colores por el teorema de cuatro colores , y el vértice restante necesita como máximo un color adicional. Robertson, Seymour y Thomas (1993a) utilizaron este hecho en su prueba del caso k = 6 de la conjetura de Hadwiger , la afirmación de que cada gráfico de 6 cromáticos tiene el gráfico completo K 6 como menor: mostraron que cualquier contraejemplo mínimo para la conjetura tendría que ser un gráfico de vértice, pero como no hay gráficos de ápice cromático 6, tal contraejemplo no puede existir.
 | Problema no resuelto en matemáticas :
¿Está cada 6 vértices conectados -grave sin gráficos un gráfico de ápice?
(Más problemas no resueltos en matemáticas) |
Jørgensen (1994) conjeturó que cada gráfico conectado a 6 vértices que no tiene K 6 como menor debe ser un gráfico de vértice. Si esto se probara, el resultado de Robertson-Seymour-Thomas sobre la conjetura de Hadwiger sería una consecuencia inmediata. [2] La conjetura de Jørgensen sigue sin probarse. [9] Sin embargo, si es falso, solo tiene muchos contraejemplos finitos. [10]
Ancho de árbol local [ editar ]
Una familia de gráficos F ha delimitado el ancho de árbol local si los gráficos en F obedecen a una relación funcional entre el diámetro y el 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 acotado: los gráficos de vértice formados conectando un vértice de vértice a cada vértice de un gráfico de cuadrícula n × n tienen un ancho de árbol ny diámetro 2, por lo que el ancho del árbol no está limitado por una función de diámetro para estos gráficos. Sin embargo, los gráficos de ápice están íntimamente conectados al ancho de árbol local limitado: las familias de gráficos menores cerrados F que tienen ancho de árbol local limitado son exactamente las familias que tienen un gráfico de ápice como uno de sus menores prohibidos. [4] Una familia de gráficos cerrados menores que tiene un gráfico de vértice como uno de sus menores prohibidos se conoce como ápice libre de menores . Con esta terminología, la conexión entre los gráficos de ápice y el ancho de árbol local se puede restablecer como el hecho de que las familias de gráficos libres de ápice menor son las mismas que las familias de gráficos de menor tamaño 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 libres de ápice menor se resuelvan exactamente mediante un algoritmo de tiempo polinómico o un algoritmo manejable de parámetro fijo , o se aproximen utilizando un esquema de aproximación de tiempo polinómico . [11] Las familias gráficas libres de ápice-menor obedecen a una versión reforzada del teorema de la estructura gráfica , lo que lleva a algoritmos de aproximación adicionales para colorear el gráfico y el problema del vendedor ambulante . [12]Sin embargo, algunos de estos resultados también pueden extenderse a familias arbitrarias de gráficos menores cerrados a través de teoremas de estructura que los relacionan con gráficos libres de ápices menores. [13]
Incrustaciones [ editar ]
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 a todos los vecinos de v en una incrustación plana de G \ { v }, entonces G puede incrustarse en una superficie bidimensional del género τ - 1: simplemente agregue ese número de puentes a la incrustación plana, conectando todas las caras en las que v debe conectarse. 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 a 3, su límite está dentro de un factor constante óptimo: cada incrustación de superficie deG 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 del vértice, minimizando el número total de cruces, en polinomios. hora. [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 al agregar un solo borde a un gráfico plano. [dieciséis]
Los gráficos de Apex también se pueden incorporar sin vínculo en el espacio tridimensional: se pueden incrustar de tal manera que cada ciclo en el gráfico sea el límite de un disco que no esté atravesado por ninguna otra característica del gráfico. [17] Se puede obtener un dibujo de este tipo 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 a cada uno de sus vecinos. Los gráficos integrables sin vínculo forman una familia cerrada menor con los siete gráficos de la familia Petersen como sus menores prohibidos mínimos; [1] por lo tanto, estos gráficos también están prohibidos como menores para los gráficos de ápice. Sin embargo, existen gráficos incrustables sin enlaces que no son gráficos de ápice.
YΔY-reducibilidad [ editar ]
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 auto-loop 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 bordes vecinos por un solo borde. [3]
Al igual que los gráficos de ápice y los gráficos incrustables sin enlace, los gráficos reducibles YΔY se cierran bajo gráficos menores. Y, al igual que los gráficos integrables sin enlace, los gráficos reducibles YΔY tienen los siete gráficos de la familia Petersen como menores prohibidos, lo que plantea la pregunta de si estos son los únicos menores prohibidos y si los gráficos reducibles YΔY son los mismos que los integrables sin enlace gráficos Sin embargo, Neil Robertson proporcionó un ejemplo de un gráfico de vértice que no es reducible en YΔY. Dado que cada gráfico de ápice es incrustable sin enlace, esto muestra que hay gráficos que son incrustables sin enlace pero no reducibles YΔY y, por lo tanto, hay menores prohibidos adicionales para los gráficos reducibles YΔY. [3]
El gráfico del ápice de Robertson se muestra en la figura. Se puede obtener conectando un vértice de 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 libre de triángulos con un grado mínimo de cuatro, por lo que no puede modificarse mediante ninguna reducción YΔY. [3]
Gráficos casi planos [ editar ]
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 las gráficas no planas menores-mínimas K 5 y K 3,3 , cualquiera de los vértices se puede elegir como el vértice. Wagner ( 1967 , 1970 ) definió un gráfico casi plano como un gráfico de ápice no plano con la propiedad de que todos los vértices pueden ser el vértice del gráfico; así, 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 ) pueden integrarse en la tira de Möbiusde tal manera que el borde único de la tira coincida con un ciclo hamiltoniano de la gráfica. Antes de la prueba del teorema de los cuatro colores , demostró que cada gráfico casi plano puede ser coloreado como máximo con cuatro colores, excepto los gráficos formados a partir de un gráfico de rueda con un ciclo externo extraño al reemplazar el vértice del cubo con dos vértices adyacentes, que requieren cinco colores. Además, demostró que, con una sola excepción (el gráfico del 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 ápice, [18] gráficos formados agregando un borde a un gráfico plano, [19] y gráficos formados a partir de un gráfico plano incrustado por la sustitución de un número limitado de caras por "vórtices" de acotada pathwidth , [20] , así como para otros conjuntos menos definidos con precisión de gráficos.
Clases gráficas relacionadas [ editar ]
Se dice que un gráfico abstracto es n- ápice si puede hacerse plano eliminando n o menos vértices. También se dice que un gráfico de 1 ápice es el ápice.
De acuerdo con Lipton et al. (2016) , un gráfico es edge-apex si hay algún borde en el gráfico que se puede eliminar para hacer que el gráfico sea plano. Un gráfico es contracción-ápice si hay algún borde en el gráfico que se puede contraer para hacer que el gráfico sea plano.
En la teoría de grafos , un vértice universal es un vértice de un gráfico no dirigido que está adyacente a todos los demás vértices del gráfico. También se le puede llamar vértice dominante , ya que forma un conjunto dominante de un elemento en el gráfico.
Un gráfico que contiene un vértice universal puede llamarse cono . En este contexto, el vértice universal también puede llamarse el vértice del cono. [1] Sin embargo, esta terminología entra en conflicto con la terminología de los gráficos de vértice , en el que un vértice es un vértice cuya eliminación deja un subgrafo plano.
En familias especiales de gráficos [ editar ]
Las estrellas son exactamente los árboles que tienen un vértice universal, y pueden construirse agregando un vértice universal a un conjunto independiente . Los gráficos de rueda , de manera similar, pueden formarse agregando un vértice universal a un gráfico de ciclo . [2] En geometría, las pirámides tridimensionales tienen gráficos de ruedas como sus esqueletos , y más generalmente el gráfico de cualquier pirámide de dimensiones superiores tiene un vértice universal como el vértice de la pirámide.
Los gráficos trivialmente perfectos (los gráficos de comparabilidad de los árboles de la teoría del orden ) siempre contienen un vértice universal, la raíz del árbol, y más fuertemente pueden caracterizarse como los gráficos en los que cada subgrafo inducido conectado contiene un vértice universal. [3] Los gráficos de umbral conectados forman una subclase de los gráficos trivialmente perfectos, por lo que también contienen un vértice universal; se pueden definir como los gráficos que se pueden formar mediante la adición repetida de un vértice universal o un vértice aislado (uno sin bordes incidentes). [4]
Cada gráfico con un vértice universal es un gráfico desmontable , y casi todos los gráficos desmontables tienen un vértice universal. [5]
Otras propiedades [ editar ]
En un gráfico con n vértices, un vértice universal es un vértice cuyo grado es exactamente n - 1 . Por lo tanto, al igual que los gráficos divididos , los gráficos con un vértice universal pueden reconocerse únicamente por sus secuencias de grados , sin mirar la estructura del gráfico.
No hay comentarios:
Publicar un comentario