En teoría de grafos , una rama de las matemáticas , un grafo de conglomerados es un grafo formado a partir de la unión disjunta de grafos completos . De manera equivalente, un grafo es un grafo de conglomerados si y solo si no tiene un camino inducido de tres vértices ; por esta razón, los grafos de conglomerados también se denominan grafos P 3 -libres . Son los grafos complementarios de los grafos multipartitos completos [1] y las potencias de 2 hojas . [2] Los grafos de conglomerados son transitivamente cerrados , y todo grafo no dirigido transitivamente cerrado es un grafo de conglomerados. [3]
Los gráficos de conglomerados son los gráficos para los cuales la adyacencia es una relación de equivalencia , y sus componentes conectados son las clases de equivalencia para esta relación.
Cada grafo de conglomerados es un grafo de bloques , un cografo y un grafo sin garras . [1] Cada conjunto independiente maximal en un grafo de conglomerados elige un único vértice de cada conglomerado, por lo que el tamaño de dicho conjunto siempre es igual al número de conglomerados; debido a que todos los conjuntos independientes maximales tienen el mismo tamaño, los grafos de conglomerados están bien cubiertos . Los grafos de Turán son grafos complementarios de grafos de conglomerados, con todos los subgrafos completos de tamaño igual o casi igual. El grafo agrupado localmente (grafos en los que cada vecindario es un grafo de conglomerados) son los grafos sin diamantes , otra familia de grafos que contiene los grafos de conglomerados.
Cuando un grafo de conglomerados se forma a partir de camarillas que son todas del mismo tamaño, el grafo general es un grafo homogéneo , lo que significa que cada isomorfismo entre dos de sus subgrafos inducidos se puede extender a un automorfismo de todo el grafo. Con solo dos excepciones, los grafos de conglomerados y sus complementos son los únicos grafos homogéneos finitos, [4] y los grafos de conglomerados infinitos también forman uno de los pocos tipos diferentes de grafos homogéneos infinitos numerables . [5]
Una subcoloración de un grafo es una partición de sus vértices en grafos de agrupamiento inducidos . Por lo tanto, los grafos de agrupamiento son exactamente los grafos del número subcromático 1. [6]
El problema computacional de encontrar un pequeño conjunto de aristas para agregar o quitar de un gráfico para transformarlo en un gráfico de conglomerados se llama edición de conglomerados. Es NP-completo [7] pero manejable con parámetros fijos . [8]
Dado un gráfico completo con costos de aristas (positivos y negativos), el problema de partición de camarillas solicita un subgráfico que sea un gráfico de conglomerados tal que la suma de los costos de las aristas del gráfico de conglomerados sea mínima. [9] Este problema está estrechamente relacionado con el problema de agrupamiento por correlación .