En la teoría de grafos , una rama de las matemáticas, un gráfico de conglomerados es un gráfico formado a partir de la unión disjunta de gráficos completos . De manera equivalente, un gráfico es un gráfico de conglomerados si y solo si no tiene una trayectoria inducida por tres vértices ; por esta razón, los gráficos de conglomerados también se denominan gráficos libres de P 3 . Son los gráficos complementarios de los gráficos multipartitos completos [1] y las potencias de 2 hojas . [2]
Clases de grafos relacionados
Cada gráfico de conglomerados es un gráfico de bloques , un cográfico y un gráfico sin garras . [1] Cada conjunto máximo independiente en un gráfico de conglomerados elige un solo 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 máximos tienen el mismo tamaño, los gráficos de conglomerados están bien cubiertos . Los gráficos de Turán son gráficos complementarios de gráficos de conglomerados, con todos los subgráficos completos de igual o casi igual tamaño. El gráfico agrupado localmente (gráficos en los que cada vecindario es un gráfico de grupo) son los gráficos sin rombo , otra familia de gráficos que contiene los gráficos de grupo.
Cuando un gráfico de conglomerados se forma a partir de grupos que son todos del mismo tamaño, el gráfico general es un gráfico homogéneo , lo que significa que cada isomorfismo entre dos de sus subgrafos inducidos puede extenderse a un automorfismo de todo el gráfico. Con sólo dos excepciones, los gráficos de conglomerados y sus complementos son los únicos gráficos finitos homogéneos, [3] y los gráficos de conglomerados infinitos también forman uno de los pocos tipos diferentes de gráficos homogéneos infinitos numerables . [4]
Problemas computacionales
Una subcoloración de un gráfico es una partición de sus vértices en gráficos de conglomerados inducidos . Por lo tanto, los gráficos de conglomerados son exactamente los gráficos del número subcromático 1. [5]
El problema computacional de encontrar un pequeño conjunto de bordes para agregar o eliminar de un gráfico para transformarlo en un gráfico de conglomerados se llama edición de conglomerados . Es NP-completo [6] pero manejable con parámetros fijos . [7]
Referencias
- ^ a b Cluster graphs , Information System on Graph Classes and its Inclusions, consultado el 26 de junio de 2016.
- ↑ Nishimura, N .; Ragde, P .; Thilikos, DM (2002), "Sobre potencias gráficas para árboles etiquetados con hojas", Journal of Algorithms , 42 : 69–108, doi : 10.1006 / jagm.2001.1195.
- ^ Gardiner, A. (1976), "Gráficos homogéneos", Journal of Combinatorial Theory , Serie B, 20 (1): 94-102, doi : 10.1016 / 0095-8956 (76) 90072-1 , MR 0419293.
- ^ Lachlan, AH; Woodrow, Robert E. (1980), "Gráficos no dirigidos ultrahomogéneos contables", Transactions of the American Mathematical Society , 262 (1): 51–94, doi : 10.2307 / 1999974 , MR 0583847.
- ^ Albertson, MO; Jamison, RE; Hedetniemi, ST; Locke, SC (1989), "El número subcromático de una gráfica", Matemáticas discretas , 74 (1–2): 33–49, doi : 10.1016 / 0012-365X (89) 90196-9.
- ^ Shamir, Ron; Sharan, Roded; Tsur, Dekel (2004), "Problemas de modificación de gráficos de conglomerados", Matemáticas aplicadas discretas , 144 (1–2): 173–182, doi : 10.1016 / j.dam.2004.01.007 , MR 2095392.
- ^ Böcker, Sebastian; Baumbach, Jan (2013), "Edición de clústeres", La naturaleza de la computación , Lecture Notes in Comput. Sci., 7921 , Springer, Heidelberg, págs. 33-44, doi : 10.1007 / 978-3-642-39053-1_5 , MR 3102002.