bipartiteparitukset

Bipartiteparitus (bipartite matching) är en term inom grafteori som beskriver hur ett graf G = (V,E) kan delas in i två disjunkta delmängder U och W så att varje kant har ena änden i U och den andra i W. En mängd M ⊆ E kallad bipartiteparitus är en samling kanter där inga två kanter delar ett gemensamt hörn. En maximal bipartiteparitus har maximal möjliga storlek bland sådana mängder. En perfekt bipartiteparitus täcker alla hörn i grafen, vilket kräver att de två delmängderna har samma storlek eller att varje hörn faktiskt kan paras i en sådan maximal uppsättning.

Hall-s sats och existensvillkor: För varje delmängd S ⊆ U låter N(S) denote hörnatkomsten i W. Hall’s krav säger att en bipartiteparitus som täcker U finns om och endast om |N(S)| ≥ |S| för alla S ⊆ U. Paritus som täcker båda sidorna kallas ibland perfekt, och dess existens kräver att både U och W kan parares respektive.

Algoritmer: För att hitta en maximal eller maximalisparad bipartiteparitus används ofta augmenting path-metoder. Kuhn’s algoritm (DFS-baserad) hittar en maximal paritus i ungefär O(|V|·|E|). Hopcroft–Karp-algoritmen förbättrar detta till O(E√V). Dessa metoder kan också omvandlas till max-flödesproblem, där bipartiteparitus motsvarar ett flöde i ett nätverk.

Användningar: Bipartiteparitus tillämpas i uppgiftsfördelning (assignment problems), arbetsplanering, matchning mellan två typer av enheter, och som del i lösningar av max-flödesproblem i nätverk. Ett litet exempel omfattar ett tvådelat uppsättning av jobb och arbetare med angivna färdigheter; en maximal eller perfekt paritus motsvarar en optimal uppgiftsfördelning.