Grafo bipartido: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Terceira linha do texto. ímpar para par. |
nao tem ciclos de tamanho impar |
||
Linha 1:
[[Image:Simple-bipartite-graph.svg|200px|thumb|Exemplo de um grafo bipartido]]
No campo da [[matemática]] da [[teoria dos grafos]], um '''grafo bipartido''' ou '''bigrafo''' é um [[grafo]] cujos [[vértice (teoria dos grafos)|vértices]] podem ser divididos em dois [[conjuntos disjuntos]] ''U'' e ''V'' tais que toda [[aresta (teoria dos grafos)|aresta]] conecta um vértice em ''U'' a um vértice em ''V'';<ref>{{citar livro|autor=SZWARCFITER, Jayme Luiz|título=Grafos e algoritmos computacionais|subtítulo=|idioma=|edição=|local=Rio de Janeiro|editora=Campus|ano=1988|página=|volumes=|volume=|id=ISBN 85-7001-341-8}}</ref> ou seja, ''U'' e ''V'' são [[Conjunto independente|conjuntos independentes]]. Equivalentemente, um grafo bipartido é um grafo que não contém qualquer [[ciclo (teoria dos grafos)|ciclo]] de comprimento
Os dois conjuntos ''U'' e ''V'' podem ser pensados como uma [[coloração de grafos|coloração]] do grafo com duas cores: se nós colorirmos todos os nodos em ''U'' de azul, e todos os nodos em ''V'' de verde, cada aresta tem terminações de cores diferentes, como é exigido no problema de coloração de grafos. Em contrapartida, tal coloração é impossível no caso de um grafo que não é bipartido, como um [[Galeria de grafos nomeados|triângulo]]: depois de um nó ser colorido de cor azul e outro de verde, o terceiro vértice do triângulo é ligado a vértices de ambas as cores, impedindo que seja atribuída qualquer cor.
| |||