Comprendere le bipartizioni nella teoria dei grafi

Nella teoria dei grafi, una bipartizione di un grafo è una divisione del suo insieme di vertici in due insiemi disgiunti (chiamati insiemi partiti) in modo tale che tutti gli spigoli connettono i vertici di diversi insiemi partiti. In altre parole, non ci sono archi tra i vertici nello stesso insieme partite.

Ad esempio, consideriamo un grafo con 4 vertici {a,b,c,d} e dividiamo l'insieme dei vertici in due parti: {a,b} e {CD}. Il grafico è bipartito perché tutti gli spigoli collegano vertici di parti diverse.

La bipartizione può essere utilizzata per ridurre la complessità degli algoritmi per problemi sui grafici come l'attraversamento del grafico, la ricerca del percorso più breve e la corrispondenza del grafico.