\require{AMSmath}

Dit is een reactie op vraag 93487

Re: Minimale koppeling

Excuses, ik ben erbij vergeten te vermelden: als een dergelijke koppeling K onmogelijk is om te vinden (bijvoorbeeld omdat C bestaat uit geïsoleerde knopen), dan moeten we dat ook aangeven. Over de vorm van de gegeven graaf of aard van de gegeven knoppendekking mogen verder geen assumpties worden gemaakt.

Richar
Student universiteit - vrijdag 25 maart 2022

Antwoord

De ultieme methode ken ik niet maar je kunt dit soort problemen als een stromingsprobleem zien, bijvoorbeeld voor tweedelingsgrafen door van alle lijnen pijlen te maken die allemaal dezelfde kant op wijzen, en een bron en een put toe te voegen.

Een maximale stroom geeft je dan een maximum koppeling. Zie ook de Stelling van Konig-Egervary.

Je zou je probleem tot dit probleem kunnen proberen te reduceren door twee kopieën, $V\times\{0\}$ en $V\times\{1\}$, van $V$ naast elkaar te zetten en een pijl van $(v,0)$ naar $(w,1)$ te trekken als er een lijn van $v$ naar $w$ loopt.
Voro het vinden van maximale stromen zijn polynomiale algoritmen beschikbaar.

kphart
vrijdag 25 maart 2022

©2001-2024 WisFaq