Knm

Knm Concepto: Grafo bipartido completo cuyos n vértices en una de sus particiones están totalmente relacionados con los m de la otra.

K_n,m. Grafo bipartido completo cuyas particiones del conjunto de vértices cumplen que V₁=n y V₂=m respectivamente y que todos los vértices de V₁ tienen aristas a todos los de V₂.

Definición.

Una definición formal de K_n,m sería que siendo K_n,m=<V₁ U V₂,A>, donde V₁ y V₂ son las dos particiones del conjunto de vértices y A es la colección de aristas; si |V₁|=n,|V₂|=m y A=V₁xV₂ entonces K_n,m es un grafo bipartido completo de orden n y m .

A diferencia de un grafo bipartido común el conjunto de aristas es subconjunto no nulo de V₁xV₂.

Casos especiales.

Se sabe de un caso de grafo completo que es a su vez grafo bipartido completo: K₂=K_1,1.

• 

que es además el caso mas simple posible.

También uno de los grafos de Kuratowski es un grafo bipartido completo: K_3,3.

• 

usado en la definición formal del matemático de origen polaco Kazimierz Kuratowski de grafo planar.

Fuentes.

1. K. Ribnikov. Análisis Combinatorio. Editorial Mir Moscú. 1988.
2. Grafo bipartito completo en Wikipedia