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; que es además el caso más simple posible. K₂=K_1,1.

También uno de los grafos de Kuratowski es un grafo bipartido completo; usado en la definición formal del matemático de origen polaco Kazimierz Kuratowski de grafo planar. K_3,3.

Fuentes

• Ribnikov. Análisis Combinatorio. Moscú: Editorial Mir. 1988
• Artículo. Grafo bipartito completo. Disponible: en "es.wikipedia.org". Consultado: 29 de noviembre de 2011.