En teoría de grafos , un grafo cociente Q de un grafo G es un grafo cuyos vértices son bloques de una partición de los vértices de G y donde el bloque B es adyacente al bloque C si algún vértice en B es adyacente a algún vértice en C con respecto al conjunto de borde de G . [1] En otras palabras, si G tiene un conjunto de aristas E y un conjunto de vértices V y R es la relación de equivalencia inducida por la partición, entonces el gráfico de cociente tiene un conjunto de vértices V/ R y conjunto de bordes {([ u ] R , [ v ] R ) | ( u , v ) ∈ E ( G )}.
Más formalmente, un gráfico de cociente es un objeto de cociente en la categoría de gráficos. La categoría de gráficos es concretizable - mapear un gráfico a su conjunto de vértices lo convierte en una categoría concreta - por lo que sus objetos se pueden considerar como "conjuntos con estructura adicional", y un gráfico de cociente corresponde al gráfico inducido en el conjunto de cocientes V / R de su conjunto de vértices V . Además, hay un homomorfismo de gráfico (un mapa de cociente ) de un gráfico a un gráfico de cociente, enviando cada vértice o borde a la clase de equivalencia a la que pertenece. Intuitivamente, esto corresponde a "pegar" (formalmente, "identificar") los vértices y los bordes del gráfico.
Ejemplos de
Un gráfico es trivialmente un gráfico de cociente de sí mismo (cada bloque de la partición es un único vértice), y el gráfico que consta de un solo punto es el gráfico del cociente de cualquier gráfico no vacío (la partición que consta de un solo bloque de todos los vértices ). El gráfico de cociente no trivial más simple es el que se obtiene identificando dos vértices ( identificación de vértices ); si los vértices están conectados, esto se llama contracción de borde .
Tipos especiales de cociente
La condensación de un gráfico dirigido es el gráfico de cociente donde los componentes fuertemente conectados forman los bloques de la partición. Esta construcción se puede utilizar para derivar un gráfico acíclico dirigido a partir de cualquier gráfico dirigido. [2]
El resultado de una o más contracciones de los bordes en un gráfico G no dirigido es un cociente de G , en el que los bloques son los componentes conectados del subgrafo de G formado por los bordes contraídos. Sin embargo, para los cocientes de manera más general, los bloques de la partición que dan lugar al cociente no necesitan formar subgrafos conectados.
Si G es un gráfico que cubre de otro gráfico H , entonces H es un gráfico cociente de G . Los bloques de la partición correspondiente son las imágenes inversas de los vértices de H debajo del mapa de cobertura. Sin embargo, los mapas de cobertura tienen un requisito adicional que no es cierto en general para los cocientes, que el mapa sea un isomorfismo local. [3]
Complejidad computacional
Es NP-completo , dado un gráfico cúbico de n - vértices G y un parámetro k , determinar si G puede obtenerse como un cociente de un gráfico plano con n + k vértices. [4]
Referencias
- ^ Sanders, Peter ; Schulz, Christian (2013), "Partición de gráficos de alta calidad", Partición de gráficos y agrupación de gráficos , Contemp. Math., 588 , Amer. Matemáticas. Soc., Providence, RI, págs. 1-17, doi : 10.1090 / conm / 588/11700 , MR 3074893.
- ^ Bloem, Roderick; Gabow, Harold N .; Somenzi, Fabio (enero de 2006), "Un algoritmo para el análisis de componentes fuertemente conectados en n log n pasos simbólicos", Métodos formales en el diseño de sistemas , 28 (1): 37–56, doi : 10.1007 / s10703-006-4341-z.
- ^ Gardiner, A. (1974), "Gráficos de cobertura de antípodas", Journal of Combinatorial Theory , Serie B, 16 : 255-273, doi : 10.1016 / 0095-8956 (74) 90072-0 , MR 0340090.
- ^ Faria, L .; de Figueiredo, CMH; Mendonça, CFX (2001), "El número de división es NP-completo", Matemáticas aplicadas discretas , 108 (1–2): 65–83, doi : 10.1016 / S0166-218X (00) 00220-1 , MR 1804713.