matchingprobleem

Het matchingprobleem is een klassieke vraag uit de grafentheorie en datastructuren. Gegeven is een graf G = (V,E), eventueel met gewichten op de randen. Een matching is een verzameling randen M ⊆ E waarbij geen twee randen een gemeenschappelijk knooppunt hebben. Het maximale doel is een matching met zo veel mogelijk randen, oftewel een maximale of maximum matching. In een bipartiet graf geldt hetzelfde idee, maar met de extra structuur dat de knopen in twee disjuncte delen zijn verdeeld en alle randen tussen de delen lopen.

Een belangrijke eigenschap van maximum matching is de augmenting path-theorie: een matching is maximaal als er geen augmenterend pad bestaat, een pad dat begint en eindigt bij onbeetelde knopen en afwisselend door niet-gewenste en gewenste randen loopt. Deze karakterisering maakt het computeren van maximum matching mogelijk via iteratief zoeken naar augmenterende paden.

Algoritmisch gezien zijn er verschillende benaderingen. Voor bipartiete grafen leveren algoritmen zoals de Kuhn-algoritme en de Hopcroft–Karp-algoritme veel efficiënte methoden op; Hopcroft–Karp draait in tijd O(E√V). Voor algemene grafen bestaan er blossom-algoritmen die maximum matching in poly tijd vinden, met klassieke implementaties die ruwweg O(V^3) tijd kosten. Daarnaast bestaan er ook gewogen varianten, waarbij men niet alleen de grootte van de matching, maar de som van de gewichten van de randen wil maximaliseren (maximum weight matching). Voor bipartiete gewogen matching wordt veelal de Hungarian-algoritme gebruikt, met tijdscomplexiteit O(n^3).

Toepassingen van het matchingprobleem zijn onder meer taak- en werktoewijzing, netwerkontwerp, resource-allocation en combinatoriële optimalisatie in logistiek. In meer geavanceerde standen komen varianten zoals maximum-weight en perfect matching voor, met diverse praktische en theoretische toepassingen.