Bipartities begrijpen in de grafentheorie

In de grafentheorie is een bipartie van een grafiek een verdeling van de hoekpuntenset in twee onsamenhangende sets (deelverzamelingen genoemd), zodat alle randen hoekpunten van verschillende deelverzamelingen met elkaar verbinden. Met andere woorden, er zijn geen randen tussen hoekpunten in dezelfde deelverzameling. Beschouw bijvoorbeeld een grafiek met 4 hoekpunten {a,b,c,d} en we verdelen de hoekpuntenset in twee delen: {a,b} en {CD}. De grafiek is bipartiet omdat alle randen hoekpunten uit verschillende delen met elkaar verbinden. Bipartitie kan worden gebruikt om de complexiteit van algoritmen voor grafiekproblemen zoals het doorlopen van grafieken, het vinden van het kortste pad en het matchen van grafieken te verminderen.