Caracterización de gráfico prohibido - Forbidden graph characterization
En la teoría de grafos , una rama de las matemáticas, muchas familias importantes de grafos pueden describirse mediante un conjunto finito de grafos individuales que no pertenecen a la familia y además excluyen todos los grafos de la familia que contengan cualquiera de estos grafos prohibidos como (inducidos) subgrafo o menor. Un ejemplo prototípico de este fenómeno es el teorema de Kuratowski , que establece que un gráfico es plano (se puede dibujar sin cruces en el plano) si y solo si no contiene ninguno de los dos gráficos prohibidos, el gráfico completo K 5 y el bipartito completo. gráfico K 3,3 . Para el teorema de Kuratowski, la noción de contención es la de homeomorfismo gráfico , en el que una subdivisión de un gráfico aparece como un subgrafo del otro. Por lo tanto, cada gráfico tiene un dibujo plano (en cuyo caso pertenece a la familia de gráficos planos) o tiene una subdivisión de uno de estos dos gráficos como un subgráfico (en cuyo caso no pertenece a los gráficos planos).
Definición
De manera más general, una caracterización de grafos prohibidos es un método para especificar una familia de estructuras de grafos , o hipergrafos , especificando subestructuras que tienen prohibido existir dentro de cualquier grafo de la familia. Las diferentes familias varían en la naturaleza de lo que está prohibido . En general, una estructura G es un miembro de una familia si y sólo si una subestructura prohibido es no contenido en G . La subestructura prohibida podría ser una de las siguientes:
- subgráficos , gráficos más pequeños obtenidos de subconjuntos de los vértices y aristas de un gráfico más grande,
- subgráficos inducidos , gráficos más pequeños obtenidos seleccionando un subconjunto de los vértices y usando todos los bordes con ambos extremos en ese subconjunto,
- Subgrafos homeomorfos (también llamados topológicos menores ), grafos más pequeños obtenidos de subgrafos colapsando caminos de vértices de grado dos a bordes simples, o
- grafos menores , grafos más pequeños obtenidos de subgrafos mediante contracciones arbitrarias de los bordes .
El conjunto de estructuras que tienen prohibido pertenecer a una familia de gráficos determinada también se puede denominar un conjunto de obstrucciones para esa familia.
Las caracterizaciones de gráficos prohibidas se pueden utilizar en algoritmos para probar si un gráfico pertenece a una familia determinada. En muchos casos, es posible probar en tiempo polinómico si un gráfico dado contiene alguno de los miembros del conjunto de obstrucciones y, por lo tanto, si pertenece a la familia definida por ese conjunto de obstrucciones.
Para que una familia tenga una caracterización gráfica prohibida, con un tipo particular de subestructura, la familia debe estar cerrada bajo subestructuras. Es decir, cada subestructura (de un tipo determinado) de un gráfico de la familia debe ser otro gráfico de la familia. De manera equivalente, si un gráfico no es parte de la familia, todos los gráficos más grandes que lo contengan como subestructura también deben excluirse de la familia. Cuando esto es cierto, siempre existe un conjunto de obstrucción (el conjunto de gráficos que no están en la familia pero cuyas subestructuras más pequeñas pertenecen todas a la familia). Sin embargo, para algunas nociones de lo que es una subestructura, este conjunto de obstrucciones podría ser infinito. El teorema de Robertson-Seymour demuestra que, para el caso particular de grafos menores , una familia que está cerrada bajo menores siempre tiene un conjunto de obstrucciones finito.
Lista de caracterizaciones prohibidas para gráficos e hipergráficos
| Familia | Obstrucciones | Relación | Referencia |
|---|---|---|---|
| Bosques | bucles, pares de bordes paralelos y ciclos de todas las longitudes | subgrafo | Definición |
| un bucle (para gráficos múltiples) o un triángulo K 3 (para gráficos simples) | grafica menor | Definición | |
| Gráficos sin garras | estrella K 1,3 | subgrafo inducido | Definición |
| Gráficos de comparabilidad | subgrafo inducido | ||
| Gráficos sin triángulos | triángulo K 3 | subgrafo inducido | Definición |
| Gráficos planos | K 5 y K 3,3 | subgrafo homeomorfo | Teorema de Kuratowski |
| K 5 y K 3,3 | grafica menor | Teorema de wagner | |
| Gráficos planos exteriores | K 4 y K 2,3 | grafica menor | Diestel (2000) , pág. 107 |
| Gráficos exteriores de 1 plano | seis menores prohibidos | grafica menor | Auer y col. (2013) |
| Gráficos de género fijo | un conjunto de obstrucción finito | grafica menor | Diestel (2000) , pág. 275 |
| Gráficos de Apex | un conjunto de obstrucción finito | grafica menor | |
| Gráficos integrables sin enlaces | La familia Petersen | grafica menor | |
| Gráficos bipartitos | ciclos impares | subgrafo | |
| Gráficos de cuerdas | ciclos de 4 o más de duración | subgrafo inducido | |
| Gráficos perfectos | ciclos de duración impar 5 o más o sus complementos | subgrafo inducido | |
| Gráfico lineal de gráficos | nueve subgrafos prohibidos (enumerados aqui ) | subgrafo inducido | |
| Uniones gráficas de gráficas de cactus | el gráfico de diamante de cuatro vértices formado al eliminar un borde del gráfico completo K 4 | grafica menor | |
| Gráficos de escalera | K 2,3 y su gráfico dual | subgrafo homeomorfo | |
| Gráficos divididos | subgrafo inducido | ||
| Serie de 2 conexiones : paralelo ( ancho de árbol ≤ 2, ancho de rama ≤ 2) | K 4 | grafica menor | Diestel (2000) , pág. 327 |
| Ancho de árbol ≤ 3 | K 5 , octaedro , prisma pentagonal , gráfico de Wagner | grafica menor | |
| Ancho de rama ≤ 3 | K 5 , octaedro , cubo , gráfico de Wagner | grafica menor | |
| Gráficos complementarios reducibles (cographs) | Ruta de 4 vértices P 4 | subgrafo inducido | |
| Gráficos trivialmente perfectos | Ruta de 4 vértices P 4 y ciclo de 4 vértices C 4 | subgrafo inducido | |
| Gráficos de umbral | Ruta de 4 vértices P 4 , ciclo de 4 vértices C 4 y complemento de C 4 | subgrafo inducido | |
| Gráfico de líneas de hipergráficos lineales uniformes de 3 | una lista finita de subgrafos inducidos prohibidos con un grado mínimo de al menos 19 | subgrafo inducido | |
| Gráfico lineal de k- hipergráficos lineales uniformes, k > 3 | una lista finita de subgrafos inducidos prohibidos con un grado de borde mínimo de al menos 2 k 2 - 3 k + 1 | subgrafo inducido | |
| Grafica ΔY-reducible a un solo vértice | una lista finita de al menos 68 mil millones de sumas distintas (1,2,3) -clique | grafica menor | |
| Teoremas generales | |||
| Una familia definida por una propiedad inducida-hereditaria | un conjunto de obstrucciones, posiblemente no finito | subgrafo inducido | |
| Una familia definida por una propiedad hereditaria menor | un conjunto de obstrucción finito | grafica menor | Teorema de Robertson-Seymour |
