Índice:
Definição - O que significa Gráfico Bipartido?
Um gráfico bipartido é um gráfico no qual um conjunto de vértices do gráfico pode ser dividido em dois conjuntos independentes e nenhum dois vértices do gráfico no mesmo conjunto é adjacente. Em outras palavras, gráficos bipartidos podem ser considerados iguais a dois gráficos coloridos. Gráficos bipartidos são usados principalmente em relacionamentos de modelagem, especialmente entre duas classes separadas inteiras de objeto.
Um gráfico bipartido também é conhecido como bigraph.
Techopedia explica o gráfico bipartido
Um gráfico bipartido possui dois conjuntos de vértices, por exemplo, A e B, com a possibilidade de que, quando uma aresta for desenhada, a conexão possa conectar-se 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ário para colorir os vértices sem vértices adjacentes que compartilham as mesmas cores, precisa ser menor ou igual a dois no caso de um gráfico bipartido. Todos os tipos de gráficos acíclicos (gráficos que não possuem ciclos gráficos) são exemplos de gráficos bipartidos. Um gráfico cíclico é considerado bipartido se todos os ciclos envolvidos tiverem uma duração uniforme. De acordo com o teorema de coloração de linha de Koning, todos os gráficos bipartidos são gráficos de classe 1.
Os gráficos bipartidos são amplamente utilizados na teoria moderna de codificação, além de serem usados nas relações de modelagem.
