Grafo multipartito

En teoría de grafos , una rama de las matemáticas, un grafo k -partito es un grafo cuyos vértices se dividen (o pueden dividirse) en k conjuntos independientes distintos . De forma equivalente, es un grafo que puede colorearse con k colores, de modo que ningún par de extremos de una arista tenga el mismo color. Cuando k = 2, se denominan grafos bipartitos , y cuando k = 3, grafos tripartitos .

Los grafos bipartitos pueden reconocerse en tiempo polinomial , pero para cualquier k > 2 es NP-completo , dado un grafo sin color, probar si es k -partito. ^{[ 1 ]} Sin embargo, en algunas aplicaciones de la teoría de grafos, un grafo k -partito puede proporcionarse como entrada a un cálculo con su coloración ya determinada; esto puede ocurrir cuando los conjuntos de vértices del grafo representan diferentes tipos de objetos. Por ejemplo, las folksonomías se han modelado matemáticamente mediante grafos tripartitos en los que los tres conjuntos de vértices representan a los usuarios de un sistema, los recursos que los usuarios están etiquetando y las etiquetas que los usuarios han aplicado a los recursos. ^{[ 2 ]}

Ejemplo de grafos k -partitos completos

K _2,2,2 Gráfico de octaedro

K _3,3,3 Gráfico de octaedro generalizado complejo

K _2,2,2,2 Gráfico de 16 celdas

Un grafo k -partito completo es un grafo k -partito en el que existe una arista entre cada par de vértices de conjuntos independientes diferentes. Estos grafos se describen mediante una notación con la letra mayúscula K subíndice de una secuencia de tamaños de cada conjunto en la partición. Por ejemplo, K _2,2,2 es el grafo tripartito completo de un octaedro regular , que puede particionarse en tres conjuntos independientes, cada uno compuesto por dos vértices opuestos. Un grafo multipartito completo es un grafo que es k -partito completo para algún k . ^{[ 3 ]} Los grafos de Turán son el caso especial de grafos multipartitos completos en los que los conjuntos independientes difieren en tamaño en como máximo un vértice. Los grafos k -partitos completos, los grafos multipartitos completos y sus grafos complemento , los grafos de clúster , son casos especiales de cografos y pueden reconocerse en tiempo polinomial incluso cuando la partición no se proporciona como parte de la entrada.