\require{AMSmath}

Minimale koppeling

Gegeven is een ongerichte graaf G met knopen V en kanten E, en een knopenbedekking X. Gevraagd is om een koppeling K te vinden van minimale kardinaliteit waarbij de eindpunten van de kanten in de koppeling een superset vormen van C. Bovendien moet K worden gevonden in polynomiale tijd in de grootte van de invoer.

Ik heb geprobeerd om hier een recursieve formule van te maken, waarbij ik alle deelverzamelingen van E bekijk. Namelijk, door voor elke knoop in C uit te proberen welke aangrenzende kant ik neem. Aangezien ik nog niet weet wat optimaal is, probeer ik alle aangrenzende kanten. Dit is echter exponentieel in E, aangezien ik alle deelverzamelingen van E moet bekijken. Er lijkt een veel eenvoudigere oplossing voor dit probleem aangezien een koppeling en bedekking erg gerelateerd zijn aan elkaar. Echter loop ik hierop vast. Hulp is gewenst.

Richar
Student universiteit - vrijdag 25 maart 2022

Antwoord

Zoals het nu geformuleerd is zal het niet lukken: een koppeling pakt een even aantal knopen. Als $C$ uit alle knopen bestaat, dus $C=V$, en als er een oneven aantal knopen is dan pakt de koppeling zeker niet alle knopen mee.

Er moeten dus voorwaarden bij: over de aard van de overdekking, over de aard van de graaf, ...

kphart
vrijdag 25 maart 2022

Re: Minimale koppeling

©2001-2024 WisFaq