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 siendoK_n,m=<V₁ U V₂,A>, donde V₁ y V₂ son las dos particiones del conjunto de vértices de K_nm 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.

• 

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

• 

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

Fuentes.

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