Gráfico multipartito - Multipartite graph
En la teoría de grafos , una parte de las matemáticas, un grafo de k -partitas es un grafo cuyos vértices están o pueden dividirse en k conjuntos independientes diferentes . De manera equivalente, es un gráfico que se puede colorear con k colores, de modo que no haya dos extremos de un borde que tengan el mismo color. Cuando k = 2, estos son los gráficos bipartitos , y cuando k = 3 se denominan gráficos tripartitos .
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. Sin embargo, en algunas aplicaciones de la teoría de grafos, se puede dar un grafo de k -partitas 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.
| K 2,2,2 | K 3,3,3 | K 2,2,2,2 |
|---|---|---|
 Gráfico de octaedro |
 Gráfico de octaedro generalizado complejo |
 Gráfico de 16 celdas |
Una completa k -partite gráfico es un k -partite gráfico en el que hay un borde entre cada par de vértices de diferentes conjuntos independientes. Estos gráficos se describen mediante notación con una letra K mayúscula subindicada 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. Una gráfica multipartita completa es una gráfica que es k -partita completa para algunos k . Los gráficos de Turán son el caso especial de los 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 cografías y pueden reconocerse en tiempo polinomial incluso cuando la partición no se proporciona como parte de la entrada.