Maksimal bipartitt matching

I bipartitte grafer ønsker vi en matching med flest mulig kant-par som ikke deler endepunkt. Problemet kan løses ved reduksjon til flyt eller med Hopcroft–Karp.

Test deg selv

Tar du quizen på kapittel 27?

5 spørsmål satt sammen til dette kapittelet — den beste måten å sjekke at det sitter.

Start quiz

Begreper & formler

5 begreper · 3 formler i kapittelet

Forrige

Flyt med minimumskostnad