WisFaq!

\require{AMSmath} geprint op donderdag 28 maart 2024

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.

Richard
25-3-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
25-3-2022


© 2001-2024 WisFaq
WisFaq - de digitale vraagbaak voor het wiskunde onderwijs - http://www.wisfaq.nl

#93488 - Grafen - Student universiteit