prev up inhalt next


10.1 Maximum/maximales Matching

Ein maximales Matching ist ein Matching, welches nicht mehr erweitert werden kann. Ein Maximum Matching ist ein Matching mit maximaler Kantenkardinalität.

Dabei gilt: M ist ein Maximum Matching. $\Rightarrow$ M ist ein maximales Matching. (Die Umkehrung ist i. a. falsch !)


Beispiel:




prev up inhalt next