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 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 grafo cociente tiene un conjunto de vértices V / R y un conjunto de aristas {([ u ] R , [ v ] R ) | ( u , v ) ∈ E ( G )}.
Más formalmente, un grafo cociente es un objeto cociente en la categoría de grafos. La categoría de grafos es concretizable –la aplicación de un grafo 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 grafo cociente corresponde al grafo inducido en el conjunto cociente V / R de su conjunto de vértices V. Además, existe un homomorfismo de grafos (una aplicación cociente ) de un grafo a un grafo cociente, enviando cada vértice o arista a la clase de equivalencia a la que pertenece. Intuitivamente, esto corresponde a “pegar” (formalmente, “identificar”) vértices y aristas del grafo.
Un grafo es trivialmente un grafo cociente de sí mismo (cada bloque de la partición es un único vértice), y el grafo que consiste en un único punto es el grafo cociente de cualquier grafo no vacío (la partición que consiste en un único bloque de todos los vértices). El grafo cociente no trivial más simple es aquel 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 grafo dirigido es el grafo cociente donde los componentes fuertemente conectados forman los bloques de la partición. Esta construcción se puede utilizar para derivar un grafo acíclico dirigido a partir de cualquier grafo dirigido. [2]
El resultado de una o más contracciones de aristas en un grafo no dirigido G es un cociente de G , en el que los bloques son los componentes conexos del subgrafo de G formado por las aristas contraídas. Sin embargo, para cocientes más generales, los bloques de la partición que da lugar al cociente no necesitan formar subgrafos conexos.
Si G es un grafo de recubrimiento de otro grafo H , entonces H es un grafo 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 recubrimiento. Sin embargo, los mapas de recubrimiento tienen un requisito adicional que no es cierto de manera más general para los cocientes, que el mapa sea un isomorfismo local. [3]
Es NP-completo , dado un grafo cúbico de n vértices G y un parámetro k , determinar si G puede obtenerse como cociente de un grafo plano con n + k vértices. [4]