En teoría de grafos , una parte de las matemáticas, un gráfico k -partito es un gráfico cuyos vértices están (o pueden ser) divididos en k conjuntos independientes diferentes . De manera equivalente, es un gráfico que se puede colorear con k colores, de modo que no hay dos puntos finales de una arista que tengan el mismo color. Cuando k = 2 estas son las gráficas bipartitas , y cuando k = 3 se llaman gráficas tripartitas .
Los gráficos bipartitos pueden reconocerse en tiempo polinómico pero, para cualquier k > 2, es NP-completo , dado un gráfico sin color, para probar si es k -partito. [1] Sin embargo, en algunas aplicaciones de la teoría de grafos, se puede proporcionar un gráfico k -partito como entrada para un cálculo con su coloración ya determinada; Esto puede suceder cuando los conjuntos de vértices del gráfico representan diferentes tipos de objetos. Por ejemplo, las folksonomías se han modelado matemáticamente mediante gráficos tripartitos en los que los tres conjuntos de vértices del gráfico 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]
Un gráfico k -partito completo es un gráfico k -partito en el que hay una arista entre cada par de vértices de diferentes conjuntos independientes. Estos gráficos se describen mediante notación con una letra K mayúscula subíndice por una secuencia de los tamaños de cada conjunto en la partición. Por ejemplo, K 2,2,2 es el gráfico tripartito completo de un octaedro regular , que se puede dividir en tres conjuntos independientes, cada uno de los cuales consta de dos vértices opuestos. Un gráfico multipartito completo es un gráfico que es k -partito completo para algunos k . [3] Los gráficos de Turán son el caso especial de gráficos multipartitos completos en los que cada dos conjuntos independientes difieren en tamaño como máximo en un vértice. Los gráficos k -partitos completos , los gráficos multipartitos completos y sus gráficos complementarios , los gráficos de conglomerados , son casos especiales de cografos y pueden reconocerse en tiempo polinomial incluso cuando la partición no se proporciona como parte de la entrada.