Definição - o que significa gráfico bipartido?
Um grafo bipartido é um grafo no qual um conjunto de vértices de gráfico pode ser dividido em dois conjuntos independentes, e nenhum dos dois vértices de gráfico dentro do mesmo conjunto são adjacentes. Em outras palavras, os gráficos bipartidos podem ser considerados iguais a dois gráficos coloridos. Os gráficos bipartidos são usados principalmente na modelagem de relacionamentos, especialmente entre duas classes de objetos inteiras e separadas.
Um gráfico bipartido também é conhecido como bigraph.
Definirtec explica o gráfico bipartido
Um grafo bipartido tem dois conjuntos de vértices, por exemplo A e B, com a possibilidade de que quando uma aresta é desenhada, a conexão deve ser capaz de conectar entre qualquer vértice em A a qualquer vértice em B. Se o gráfico não contiver nenhum ciclo ímpar (o número de vértices no gráfico é ímpar), então seu espectro é simétrico. O número cromático, que é o número mínimo de cores necessárias para colorir os vértices sem vértices adjacentes compartilhando as mesmas cores, deve ser menor ou igual a dois no caso de um grafo bipartido. Todos os tipos de grafos acíclicos (grafos que não possuem ciclos de grafos) são exemplos de grafos bipartidos. Um gráfico cíclico é considerado bipartido se todos os ciclos envolvidos forem de comprimento uniforme. De acordo com o teorema da coloração de linhas de Koning, todos os grafos bipartidos são grafos de classe 1.
Grafos bipartidos são amplamente usados na teoria da codificação moderna, além de serem usados na modelagem de relacionamentos.