Förstå bipartitioner i grafteori
I grafteorin är en bipartition av en graf en uppdelning av dess vertexuppsättning i två disjunkta uppsättningar (kallade partituppsättningar) så att alla kanter förbinder hörn från olika partituppsättningar. Med andra ord, det finns inga kanter mellan hörn i samma partitmängd.
Betrakta till exempel en graf med 4 hörn {a,b,c,d} och vi delar upp vertexmängden i två delar: {a,b} och {CD}. Grafen är tvådelad eftersom alla kanter förbinder hörn från olika delar.
Bipartition kan användas för att reducera komplexiteten hos algoritmer för grafproblem som t.ex. grafkorsning, kortaste vägsökning och grafmatchning.
Jag gillar det här
Jag gillar inte det här
Rapportera ett innehållsfel
Aktie
