Sommario:
Definizione - Cosa significa grafico bipartito?
Un grafico bipartito è un grafico in cui un insieme di vertici di grafico può essere diviso in due insiemi indipendenti e non vi sono due vertici di grafico all'interno dello stesso insieme adiacenti. In altre parole, i grafici bipartiti possono essere considerati uguali a due grafici colorabili. I grafici bipartiti sono utilizzati principalmente nelle relazioni di modellazione, in particolare tra due intere classi di oggetti separate.
Un grafico bipartito è anche noto come bigraph.
Techopedia spiega il grafico bipartito
Un grafico bipartito ha due serie di vertici, ad esempio A e B, con la possibilità che quando viene disegnato un bordo, la connessione dovrebbe essere in grado di connettersi tra qualsiasi vertice in A a qualsiasi vertice in B. Se il grafico non contiene alcun ciclo dispari (il numero di vertici nel grafico è dispari), quindi il suo spettro è simmetrico. Il numero cromatico, che è il numero minimo di colori richiesto per colorare i vertici senza vertici adiacenti che condividono gli stessi colori, deve essere inferiore o uguale a due nel caso di un grafico bipartito. Tutti i tipi di grafici aciclici (grafici che non hanno cicli di grafici), sono esempi di grafici bipartiti. Un grafico ciclico è considerato bipartito se tutti i cicli coinvolti sono di lunghezza pari. Secondo il teorema di colorazione della linea di Koning, tutti i grafici bipartiti sono grafici di classe 1.
I grafici bipartiti sono ampiamente utilizzati nella moderna teoria dei codici oltre ad essere utilizzati nelle relazioni di modellazione.
