Grafo bipartido completo

No campo da matemática da teoria dos grafos, um grafo bipartido completo ou biclique é um tipo especial de grafo bipartido onde cada vértice do primeiro conjunto está associado a cada vértice do segundo conjunto.

Grafo bipartido completo


Um grafo bipartido completo com m = 5 n = 3
vértices n + m
arestas mn
Cintura 4
Automorfismos 2m!n! se m=n, caso contrário m!n!
Número cromático 2
Índice cromático max{m, n}
Notação

Definição

editar

Um grafo bipartido completo, G := (V1 + V2, E), é um grafo bipartido tal que para quaisquer dois vértices, v1V1 e v2V2, v1v2 é uma aresta em G. O grafo bipartido completo com partições de tamanho |V1|=m e |V2|=n, é denotado Km,n.

Exemplos

editar
 
Os grafos estrela S3, S4, S5 e S6.
 
O grafo de utilidade K3,3
  • Para qualquer k, K1,k é chamado uma estrela. Todos os grafos bipartidos completos que são árvores são estrelas.
  • O grafo K1,3 é chamado uma garra, e é usado para definir os grafos sem garra.
  • O grafo K3,3 é chamado de grafo de utilidade. Esta prática vem de um quebra-cabeça matemático tradicional, no qual três utilidades devem ser ligadas a cada três edifícios; é impossível de resolver sem cruzamentos, devido à não-planaridade de K3,3.

Propriedades

editar

Ver também

editar

Referências

  1. BOAVENTURA NETTO, Paulo Oswaldo (2001). Grafos. Teoria, Modelos Algoritmos. São Paulo: Edgard Blücher. p. 263. ISBN 85-212-0292-X