DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000
Beispiele zur bipartiten Graphen
Beim Moduswechsel ("Matching, E-V-Überdeckung, ...)
gibt es 4 Fälle, bei denen Sie aus einem optimalen
Gebilde automatisch eine optimales Gebilde erhalten
(es genügt also eines der vier Optimierungsaufgaben
zu lösen um alle zu lösen).
(Achten Sie darauf, daß Sie zuerst
nochmal "Matching" klicken, wenn Sie mit einem der beiden
Hilfsmittel ("Verbesserungsbaum", "Verbesserungsweg") ein
größtes Matching erzeugt haben.)
Dies entspricht den
Konstruktionen 3. - 6.
-
üEV ® u :
kleinste Kanten-Ecken-Überdeckung erzeugt
größte unabhängige Eckenmenge,
-
u ® üEV :
größte unabhängige Eckenmenge
erzeugt kleinste
Kanten-Ecken-Überdeckung,
-
üEV ® m :
kleinste Kanten-Ecken-Überdeckung erzeugt
größtes Matching,
-
m ® üEV :
größtes Matching erzeugt
kleinste Kanten-Ecken-Überdeckung.
Erich Prisner
erstellt im Juni 2000.