Grafos bipartidos
Um grafo G diz-se bipartido de tipo
(p,q) se fôr um grafo simples de
ordem
p+q e existir uma partição do conjunto de
todos os vértices em dois subconjuntos V1
e V2, com p e q
elementos respectivamente, tal que nenhuma aresta
de G tenha ambas as extremidades em V1
nem ambas as extremidades em V2.
Se além disso se para todo o par de vértices
v1 em V1 e
v2 em V2
o grafo G contiver a aresta
{v1,v2}
então dizemos que
G é um grafo bipartido completo de tipo
(p,q).
Designa-se por Kp,qo grafo bipartido
completo de tipo (p,q) .
Veja mais alguns
exemplos.