matchningsproblem

Matchningsproblem är inom grafteori och kombinatorisk optimering problem som handlar om att hitta ett lämpligt urval av parningar mellan objekt under vissa regler. I praktiken innebär det ofta att välja ett antal kanter (parningar) i en graf så att inga två kanter delar en gemensam vertex. Ett vanligt fall är bipartita grafer där två uppsättningar av objekt, till exempel arbetstagare och uppgifter, står i kontakt via kanter. En maximal eller maximal kardinalitetsmatchning har så många kanter som möjligt, medan en perfekt matchning täcker alla vertikaler i grafen om sådana finns.

Variantformer inkluderar kardinalitetsbaserade problem (maximal eller perfekt matchning) och viktade problem där varje kant har en kostnad och målet är att minimera total kostnad. Speciellt fall är uppgiftsproblemet (assignment problem) där antalet objekt i de två uppsättningarna är lika och målet är en kostnadseffektiv parbildning som täcker alla objekt.

Algoritmer och komplexitet: Maximal matchning i bipartita grafer kan lösas med högerorienterade flödsalgoritmer och med Hopcroft–Karp-algoritmen i O(E√V). För viktade problem används Hungarianska algoritmen (Hungarian algorithm) som löser minimum weight perfect matching i en n×n kostnadsmatris i O(n^3). För generella grafer används Edmonds’ blossom-algoritm för maximal matchning i polynomtid. Genom reduktioner kan maxflödsmetoder användas för olika varianter.

Tillämpningar: uppgiftstilldelning, rekrytering och projektallokering, skolval, organtransplantationer och nätverksdesign. Matchningsproblem utgör en central del av teorin och har brett tillämpade lösningar i ekonomi, datorvetenskap och operationsanalys.