![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/e/e8/Simple-bipartite-graph.svg/langpt-640px-Simple-bipartite-graph.svg.png&w=640&q=50)
Grafo bipartido
De Wikipedia, a enciclopédia encyclopedia
No campo da matemática da teoria dos grafos, um grafo bipartido ou bigrafo é um grafo cujos vértices podem ser divididos em dois conjuntos disjuntos U e V tais que toda aresta conecta um vértice em U a um vértice em V;[1] ou seja, U e V são conjuntos independentes. Equivalentemente, um grafo bipartido é um grafo que não contém qualquer ciclo de comprimento ímpar.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e8/Simple-bipartite-graph.svg/320px-Simple-bipartite-graph.svg.png)
Os dois conjuntos U e V podem ser pensados como uma 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 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.
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.