matchingsgraad

Matchingsgraad is een maat in de grafentheorie die de dekking van een grafiek door een maximum matching beschrijft. Voor een grafiek G met n knopen en ν(G) gelijk aan de grootste possible aantal randen in een matching, wordt de matchingsgraad g(G) gedefinieerd als g(G) = ν(G) / floor(n/2). Hierdoor ligt g(G) steeds tussen 0 en 1.

Interpretatie en betekenis: de matchingsgraad geeft aan in hoeverre een grafiek optimaal kan worden bedekt door paren knopen die geen gemeenschappelijke knoop delen. Een waarde van 1 wijst op een bijna-perfekte (bij een oneven aantal knopen) of perfecte (bij een even aantal knopen) matching. Waarden kleiner dan 1 duiden aan dat er knopen zijn die niet in een maximale matching kunnen worden opgenomen zonder conflicten.

Voorbeelden: een pad met vijf knopen heeft ν(G)=2 en floor(n/2)=2, dus g(G)=1. Een ster met vijf knopen (K1,4) heeft ν(G)=1 en floor(n/2)=2, dus g(G)=0,5. Een lege grafiek of een grafiek zonder randen heeft g(G)=0.

Eigenschappen en toepassingen: de matchingsgraad geeft een genormeerde maat voor de aanwezigheid van nearly-perfecte of perfecte matchings en kan worden gebruikt om de kwaliteit van toewijzings- of pairing-problemen te evalueren. Berekening van ν(G) gebeurt in polynomial tijd voor bipartiete grafen ( Hopcroft-Karp) en voor algemene grafen via het blossom-algoritme.

Notitie: literatuur kan verschillende normalisaties gebruiken; de juridische definities kunnen licht uiteenlopen. De hierboven gegeven definitie is een gangbare keuze.