Grafo bipartido completo

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Grafo bipartido completo
Biclique K 3 5.svg

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 K_{m,n}

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.

Definição[editar | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]

Ver também[editar | editar código-fonte]

Referências

  1. BOAVENTURA NETTO, Paulo Oswaldo. Grafos. São Paulo: Edgard Blücher, 2001. ISBN 85-212-0292-X.