Gráfico de cociente

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 conjunto de aristas E y conjunto de vértices V y R es la relación de equivalencia inducida por la partición, entonces el grafo cociente tiene conjunto de vértices V / R y conjunto de aristas {([ u ] _R ,  [ v ] _R )  |  ( u , v ) ∈ E ( G )}.  

De forma más formal, un grafo cociente es un objeto cociente en la categoría de grafos. La categoría de grafos es concretizable : al asignar un grafo a su conjunto de vértices, se convierte en una categoría concreta . Por lo tanto, 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 ) que asigna a cada vértice o arista la clase de equivalencia a la que pertenece. Intuitivamente, esto corresponde a "unir" (formalmente, "identificar") los vértices y las 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 consta de un solo punto es el grafo cociente de cualquier grafo no vacío (la partición que consta de un único bloque de todos los vértices). El grafo cociente no trivial más simple es el que se obtiene al identificar dos vértices ( identificación de vértices ); si los vértices están conectados, esto se denomina contracción de aristas .

La condensación de un grafo dirigido es el grafo cociente, donde los componentes fuertemente conexos forman los bloques de la partición. Esta construcción puede utilizarse para derivar un grafo dirigido acíclico 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 las componentes conexas del subgrafo de G formado por las aristas contraídas. Sin embargo, en el caso de los cocientes en general, los bloques de la partición que da origen 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 la aplicación de recubrimiento. Sin embargo, las aplicaciones de recubrimiento tienen un requisito adicional que no se cumple de forma más general para los cocientes: que la aplicación sea un isomorfismo local. ^{[ 3 ]}

Dado un grafo cúbico G de n vértices y un parámetro k , la complejidad computacional de determinar si G puede obtenerse como cociente de un grafo planar con n + k vértices es NP-completa . ^{[ 4 ]}

5. Alain Bretto, Alain Faisant y François Hennecart, Elementos de la teoría de grafos: Del concepto básico a la teoría moderna, European Mathematical Society Press, 2022.