Grafo bipartido: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m Checkwiki + ajustes |
|||
Linha 3:
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 ímpar
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
Frequentemente se escreve ''G'' = (''U'', ''V'', ''E'') para denotar um grafo bipartido cuja partição tem as partes ''U'' e ''V''. Se |''U''| =|''V''|, ou seja, se os dois subconjuntos tem igual [[cardinalidade]], então ''G'' é chamado um grafo bipartido ''balanceado''.
| |||