De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  gastenboek |  wie is wie? |  verhalen |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ
links
twitter
boeken
help

inloggen

colofon

  \require{AMSmath}

Re: Minimale koppeling

 Dit is een reactie op vraag 93487 
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
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
Vragen naar aanleiding van dit antwoord? Klik rechts..!
vrijdag 25 maart 2022



klein |  normaal |  groot

home |  vandaag |  bijzonder |  gastenboek |  statistieken |  wie is wie? |  verhalen |  colofon

©2001-2022 WisFaq - versie 3