Algebra

Analyse

Bewijzen

De grafische rekenmachine

Discrete wiskunde

Fundamenten

Hulpmiddelen

Meetkunde

Oppervlakte en inhoud

Plaatjes en verhalen

Rekenen

Schoolwiskunde

Statistiek en kansrekenen

Telproblemen

Toegepaste wiskunde

Van alles en nog wat

Wiskundeleraar


\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-2023 WisFaq