Una relación de equivalencia en un conjunto de vértices finitos puede representarse mediante un gráfico no dirigido que es una unión disjunta de camarillas. El conjunto de vértices representa los elementos y un borde representa que dos elementos son equivalentes.
Si tengo un gráfico y gráficos G 1 , ... , G k , decimos que G está cubierto por G 1 , ... , G k si el conjunto de bordes de G es igual a la unión de los conjuntos de bordes de G 1 , ... , G k . Los conjuntos de bordes de G 1 , ... , G k no necesitan ser disjuntos. Tenga en cuenta que cualquier gráfico G no dirigido puede estar cubierto por un número finito de relaciones de equivalencia (es decir, unión disjunta de gráficos de camarillas).
Tengo varias preguntas
- ¿Qué se puede decir sobre el número mínimo de relaciones de equivalencia requeridas para cubrir un gráfico ?
- ¿Cómo podemos calcular este número mínimo?
- ¿Cómo podemos calcular una cobertura mínima explícita de , es decir, un conjunto de relaciones de equivalencia cuyo tamaño es mínimo y que cubren G ?
- ¿Este problema tiene alguna aplicación aparte de la lógica de partición (la dual de la lógica de los subconjuntos )?
- ¿Este problema tiene un nombre bien establecido?
Dados los diversos malentendidos indicados por los comentarios, aquí hay algunas imágenes para ilustrar estos conceptos. Si tiene una idea para una terminología más fácil de entender (en lugar de "cobertura", "relación de equivalencia", "unión disuelta de camarillas" y unión "no necesariamente disjunta" de conjuntos de bordes), no dude en hacérmelo saber.
Aquí hay una imagen de un gráfico y una relación de equivalencia que lo cubre:
Aquí hay una imagen de un gráfico y dos relaciones de equivalencia que lo cubren:
debería ser bastante obvio que se requieren al menos dos relaciones de equivalencia.
Aquí hay una imagen de un gráfico y tres relaciones de equivalencia que lo cubren:
es menos obvio que se requieren al menos tres relaciones de equivalencia. Lemma 1.9 de Dual of the Logic of Subsets se puede utilizar para mostrar que esto es cierto. La generalización de este lema a las operaciones nand con más de dos entradas fue la motivación para esta pregunta.
fuente
Respuestas:
Hay clases especiales de gráficos donde se conoce el valor exacto o un buen límite superior para cualquier número. En general, que yo sepa, Alon [1] da los mejores límites:
[1] Alon, Noga. "Cubriendo gráficos por el número mínimo de relaciones de equivalencia". Combinatorica 6.3 (1986): 201-206.
[2] Blokhuis, Aart y Ton Kloks. "Sobre la equivalencia que cubre el número de divisores". Cartas de procesamiento de información 54.5 (1995): 301-304.
[3] Kučera, Luděk, Jaroslav Nešetřil y Aleš Pultr. "Complejidad de la dimensión tres y algunas características relacionadas de los bordes que cubren los gráficos". Informática teórica 11.1 (1980): 93-106.
fuente
Aunque no sé el nombre de tal problema, puedo mostrar que este problema es NP-hard.
Para un gráfico libre de triángulos, todas las clases de equivalencia deben coincidir. El número mínimo de clases de equivalencia que cubre el gráfico es igual al índice cromático del gráfico.
De acuerdo con este artículo , encontrar el índice cromático para un gráfico libre de triángulos es NP-completo.
fuente