Kantenbedekking

In de grafentheorie is een kantenbedekking (ook wel bogenbedekking, bogenoverdekking en kantenoverdekking) (Engels: edge cover) van een graaf G een deelverzameling C van de kanten uit de graaf waarvoor geldt dat elke knoop van G het begin- of eindpunt is van minstens een kant uit de verzameling C. Men zegt dan dat C de knopen van G bedekt. De volgende figuur toont twee voorbeelden van kantenbedekkingen:

Een minimum-kantenbedekking is een kantenbedekking met het kleinst mogelijk aantal kanten. Dat aantal noemt men het kantenbedekkingsgetal (Engels: edge covering number) $\rho (G)$. De volgende figuur toont twee minimum-kantenbedekkingen:

Merk op dat de figuur rechts tevens een koppeling voorstelt, en wel een perfecte koppeling M, waarin elke knoop van de graaf begin- of eindpunt is van exact een kant van M. Een perfecte koppeling is altijd een minimum-kantenbedekking.

Het vinden van een minimum-kantenbedekking en dus van het kantenbedekkingsgetal is een probleem dat in polynomiale tijd kan opgelost worden door eerst een maximumkoppeling te vinden en daaraan kanten toe te voegen naar de zogenaamde onverzadigde knopen (die geen deel uitmaken van de koppeling). In tegenstelling hiermee is het verwante probleem van het vinden van een minimum-knopenbedekking een NP-moeilijk probleem.

Voorbeelden

• De verzameling van alle kanten van G is een kantenbedekking, op voorwaarde dat er geen geïsoleerde knopen (met graad nul) zijn.
• De volledige bipartiete graaf K_m,n heeft als kantenbedekkingsgetal max(m,n).

Zie ook

• Knopenbedekking