Gráfica de factores

Un grafo cociente Q de un grafo G  es un grafo cuyos vértices son bloques de partición de los vértices del grafo G , y un bloque B es adyacente a un bloque C si algún vértice en B es adyacente a algún vértice en C [1] . En otras palabras, si G tiene un conjunto de aristas E y un conjunto de vértices V y R es una relación de equivalencia generada por una partición, entonces el gráfico del cociente tiene un conjunto de vértices V / R y un conjunto de aristas .

Más formalmente, un gráfico de cociente es un objeto de cociente en la categoría de gráficos. La categoría de grafos es instanciable :  el mapeo de un gráfico a su conjunto de vértices lo convierte en una categoría concreta , de modo que sus objetos pueden considerarse como "conjuntos con estructura adicional", y el gráfico de cociente corresponde al gráfico generado en el cociente . conjunto V / R por su vértice conjunto V . Luego hay un homomorfismo de gráfico ( asignación de cociente ) de un gráfico a un gráfico de cociente que asigna 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 las aristas del gráfico.

Ejemplos

Un gráfico es trivialmente un factorgraph de sí mismo (cada bloque de partición es un vértice separado), y un gráfico que consta de un solo punto es un factorgraph de cualquier gráfico no vacío (la partición consta de un bloque que contiene todos los vértices). El gráfico de cociente no trivial más simple se obtiene pegando dos vértices ( identificación de vértices ), pero si dos vértices son adyacentes, esto se denomina contracción de borde .

Tipos especiales de factorgraphs

La condensación de un gráfico dirigido es un gráfico de cociente cuando los componentes fuertemente conectados forman bloques de partición. Esta construcción se puede utilizar para obtener 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 grafo no dirigido G es un grafo cociente de G en el que los bloques son los componentes conectados del subgrafo de G formado por la contracción de aristas. Sin embargo, los bloques de partición que conducen a un gráfico de cociente no necesariamente forman subgráficos conectados.

Si G es una gráfica que cubre a otra gráfica H , entonces H es una gráfica cociente de G. Los bloques de la partición correspondiente son las imágenes inversas de los vértices de H bajo el mapeo de cobertura. Sin embargo, las aplicaciones de cobertura tienen requisitos adicionales que generalmente no se cumplen para los gráficos de cocientes, a saber, que la aplicación sea un isomorfismo local [3] .

A menudo, especialmente cuando se trabaja con gráficos periódicos , uno considera factorgraphs cuyos vértices corresponden a las órbitas de los vértices del gráfico original bajo la acción del grupo de automorfismos del gráfico (o algunos de sus subgrupos).

Complejidad computacional

Dado un gráfico cúbico G de n vértices y un parámetro k , determinar si el gráfico G se puede obtener como un gráfico cociente de un gráfico plano con n + k vértices es un problema NP-completo [4] .

Notas

  1. ↑ Sanders, Schulz, 2013 , pág. 1–17.
  2. ↑ Bloem, Gabow, Somenzi, 2006 , pág. 37–56.
  3. ↑ Gardiner, 1974 , pág. 255–273.
  4. ↑ Faria, de Figueiredo, Mendonça, 2001 , p. 65–83.

Literatura