# Koppeling (grafentheorie)

Als $G=(V,E)$ een niet-gerichte graaf is met knopenverzameling $V$ en zijdenverzameling $E$, dan is de zijdenverzameling $M\subseteq E$ een koppeling 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
### 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 verschillende 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 kardinaliteit als ze het grootst mogelijk aantal zijden bevat. Er geldt ook hier dat er in het algemeen verschillende 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.
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 voor iedere mogelijke graaf in polynomiale tijd worden opgelost.

### Wisselketen

Een wisselketen of wisselpad $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 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 kardinaliteit heeft dan en slechts dan 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. Daarin spelen de deelnemende partijen eenmaal tegen elkaar, bijvoorbeeld in de eerste ronde van het wereldkampioenschap voetbal, of tweemaal zoals bij heen- en terugwedstrijden 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.
* Competitie tussen vier ploegen in 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
* ↑ Hier wordt zoveel mogelijk de terminologie gebruikt uit LCM Kallenberg. Grafentheorie, 2002, voor de Universiteit Leiden