Koppeling (grafentheorie)

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Definities[1][bewerken]

koppeling[bewerken]

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

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

maximale koppeling[bewerken]

Een koppeling is maximaal als ze niet kan uitgebreid worden met een andere kant, dus als ze geen echte deelverzameling is van een andere koppeling. Dat wil zeggen dat in een maximale koppeling M van G elke kant van G minstens een eindpunt gemeen heeft met een kant 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:

Maximal-matching.svg


maximumkoppeling[bewerken]

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

Maximum-matching-labels.svg

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

koppelingsgetal[bewerken]

Het koppelingsgetal \nu(G) van graaf G is het aantal kanten 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[bewerken]

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 kant 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[bewerken]

Een wisselketen of wisselpad (alternating path) C met betrekking tot een koppeling M is een keten waarvan de kanten 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 kanten waarvan de helft behoort tot de koppeling.

groeiketen[bewerken]

Een groeiketen of groeipad (augmenting path) is een wisselketen waarvan beide uiteinden vrije (ongebonden) knopen zijn. Een groeiketen heeft een oneven aantal kanten: 2p + 1, waarvan p kanten behoren tot de koppeling. Als er een groeiketen C bestaat voor een koppeling M, dan kan de koppeling altijd met een kant 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.

Aug.svg

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.

Aug2.svg

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[bewerken]

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

Voorbeeld: sportcompetitie[bewerken]

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.

Bronnen, noten en/of referenties
  1. Hier wordt zoveel mogelijk de terminologie gebruikt uit "Grafentheorie", L.C.M. Kallenberg, Universiteit Leiden, 2002