Koppeling (grafentheorie)

Als $G=(V,E)$ een niet-gerichte normale graaf is met knopenverzameling $V$ en zijdenverzameling $E$ , dan is de zijdenverzameling $M\subseteq E$ een koppeling (Engels: matching) als geen twee zijden van $M$ een gemeenschappelijke knoop hebben.

Twee knopen die verbonden zijn door een zijde uit een koppeling $M$ zijn gekoppeld en elkaars partner. De andere knopen zijn vrij of ongebonden.

Overige definities^[1]

Maximale koppeling

Een koppeling is maximaal als ze niet kan uitgebreid worden met een andere zijde, dus als ze geen echte deelverzameling is van een andere koppeling. Dat wil zeggen dat in een maximale koppeling $M$ van $G$ elke zijde van $G$ minstens een eindpunt gemeen heeft met een zijde van $M$ . In het algemeen zijn er meerdere maximale koppelingen mogelijk voor een gegeven graaf. In onderstaande figuur zijn in het rood enkele maximale koppelingen aangeduid:

Maximumkoppeling

Men noemt een koppeling een maximumkoppeling of een koppeling met maximale cardinaliteit als ze het grootst mogelijk aantal zijden bevat. Ook hier geldt dat er in het algemeen meerdere maximumkoppelingen kunnen bestaan. De volgende figuur geeft maximumkoppelingen aan in dezelfde grafen als hierboven:

Elke maximumkoppeling is een maximale koppeling, maar niet elke maximale koppeling is een maximumkoppeling.

Koppelingsgetal

Het koppelingsgetal $\nu (G)$ van graaf $G$ is het aantal zijden van een maximumkoppeling van $G$ . Uit de definitie van koppeling volgt dat een koppeling nooit meer dan de helft van het aantal knopen van de graaf kan bevatten. Dit is dus een bovengrens voor het koppelingsgetal.

Perfecte koppeling

Een koppeling die alle knopen van de graaf bevat is een perfecte koppeling of volmaakte koppeling: daarin zijn alle knopen gebonden en zijn er geen vrije knopen. De maximumkoppeling (b) in bovenstaande figuur is een perfecte koppeling. Een perfecte koppeling is een maximum- en een maximale koppeling. Een perfecte koppeling is tevens een minimum-kantenbedekking (edge covering).

Een perfecte koppeling is enkel mogelijk indien de graaf een even aantal knopen bevat; bij een oneven aantal is enkel een "bijna-perfecte" koppeling mogelijk, waarbij er een ongepaarde knoop overblijft.

Het minimum cost perfect matching-probleem is het optimaliseringsprobleem dat zoekt naar de perfecte koppeling met minimaal gewicht of kost; hierbij is elke zijde in de graaf voorzien van een kost of gewicht, zijnde een niet-negatief reëel getal. Dit probleem kan in polynomiale tijd opgelost worden voor eender welke graaf.

Wisselketen

Een wisselketen of wisselpad (alternating path) $C$ met betrekking tot een koppeling $M$ is een keten waarvan de zijden afwisselend wel en niet tot de koppeling $M$ behoren. Als de keten gesloten is spreekt men van een wisselkring. Een wisselkring heeft een even aantal zijden waarvan de helft behoort tot de koppeling.

Groeiketen

Een groeiketen of groeipad (augmenting path) is een wisselketen waarvan beide uiteinden vrije (ongebonden) knopen zijn. Een groeiketen heeft een oneven aantal zijden: $2p 1$ , waarvan $p$ zijden behoren tot de koppeling. Als er een groeiketen $C$ bestaat voor een koppeling $M$ , dan kan de koppeling altijd met een zijde uitgebreid worden. De stelling van Berge stelt dat een koppeling $M$ maximale cardinaliteit heeft als en slechts als er geen groeiketen met betrekking tot $M$ bestaat.

In bovenstaande figuur is (1 3 2 4 6 5) een wisselketen en tevens een groeiketen want knopen 1 en 5 zijn vrij. De in het vet aangeduide koppeling is dus geen maximumkoppeling.

In deze figuur is het pad (1 3 2 4 6 5) geen groeiketen meer en de aangeduide koppeling is een maximumkoppeling (tevens een perfecte koppeling).

Eigenschappen

Voor een samenhangende graaf zonder geïsoleerde knopen is het aantal knopen gelijk aan de som van het koppelingsgetal en het zijdenbedekkingsgetal (dit is het aantal zijden in een minimumzijdenbedekking). Als er een perfecte koppeling is, zijn die twee getallen gelijk aan de helft van het aantal knopen in de graaf.

Voorbeeld: sportcompetitie

Vele sportcompetities hebben een "round robin"-formaat, waarin iedereen tegen iedereen speelt, eenmaal (bijvoorbeeld in de eerste ronde van het wereldkampioenschap voetbal) of tweemaal (bij heen- en terugronden zoals in de meeste nationale voetbalcompetities). Alle mogelijke wedstrijden in zo een "round robin"-competitie kan men voorstellen door middel van een volledige graaf waarin elke deelnemer door een knoop wordt voorgesteld. Alle speelronden van de competitie samenstellen komt dan neer op het vinden van alle perfecte koppelingen in deze graaf. Als er een even aantal (n) deelnemers is, zijn er n-1 verschillende perfecte koppelingen in de graaf; elk daarvan komt overeen met een speelronde. Als er een oneven aantal deelnemers is kan men de competitie op dezelfde manier opstellen door een extra "fictieve" deelnemer toe te voegen. Deelnemers die tegen deze fictieve deelnemer uitkomen zijn dan vrij in de betreffende speelronde.

Een competitie tussen 4 ploegen voorgesteld als een volledige graaf
Eerste ronde: A speelt tegen B en C tegen D
Tweede ronde: B speelt tegen C en A tegen D
Derde ronde: A speelt tegen C en B tegen D