En teoría de grafos, un grafo bipartito completo es un grafo bipartito en el que todos los vértices de uno de los subconjuntos de la partición están conectados a todos los vértices del segundo subconjunto, y viceversa.
Este concepto se puede generalizar al de grafo s-bipartito completo, como un grafo cuyo conjunto de vértices se puede particionar en s subconjuntos, de modo que todos los pares de vértices pertenecientes a subconjuntos diferentes son adyacentes.
Definición Un grafo bipartito completo es un grafo bipartito tal que Es decir, un grafo bipartito completo está formado por dos conjuntos disjuntos de vértices y todas las posibles aristas que unen esos vértices.
El grafo completo bipartito con particiones de tamaño y es denotado como .
Ejemplos
Propiedades Sea un grafo bipartito con y , se verifica:
posee árboles de expansión.
Véase también Grafo bipartito Grafo completo
Referencias
Bibliografía
Categoría:Optimización Categoría:Investigación operativa Categoría:Familias paramétricas de grafos