En teoría de grafos , un gráfico cociente Q de un gráfico G es un gráfico 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 aristas 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 cocientes tiene un conjunto de vértices V / R y un conjunto de aristas {([ u ] R , [ v ] R ) | ( tu , v ) ∈ mi ( GRAMO )}.
Más formalmente, un gráfico cociente es un objeto cociente en la categoría de gráficos. La categoría de gráficos es concretizable (asignar un gráfico a su conjunto de vértices lo convierte en una categoría concreta ), por lo que sus objetos pueden considerarse como "conjuntos con estructura adicional", y un gráfico cociente corresponde al gráfico inducido en el conjunto cociente V / R de su conjunto de vértices V . Además, existe un homomorfismo de gráfico (un mapa de cociente ) de un gráfico a un gráfico de cociente, enviando cada vértice o arista a la clase de equivalencia a la que pertenece. Intuitivamente, esto corresponde a "pegar" (formalmente, "identificar") los vértices y aristas del gráfico.
Un gráfico es trivialmente un gráfico cociente de sí mismo (cada bloque de la partición es un solo vértice), y el gráfico que consta de un solo punto es el gráfico 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 cocientes 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 aristas .
La condensación de un gráfico dirigido es el gráfico 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 aristas en un gráfico no dirigido G es un cociente de G , en el que los bloques son los componentes conectados del subgrafo de G formado por las aristas contraídas. Sin embargo, para los cocientes en 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 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 bajo el mapa de cobertura. Sin embargo, los mapas de cobertura tienen un requisito adicional que no se aplica de manera más general a los cocientes: que el mapa sea un isomorfismo local. [3]
Es NP-completo , dado un gráfico cúbico de n -vértices G y un parámetro k , determinar si G se puede obtener como cociente de un gráfico plano con n + k vértices. [4]