Kann mir bitte jemand helfen?!
Betrachte folgendes Problem:
Geg: Matroid [E,U] , e Element E mit {e} Element U.
Ges: Eine MEnge V Elemnet U mit e Element V und card V möglichst gross.
Beweisen sie(ohne Verwendung von Satz Greedy) das dem Problem wiederum ein Matroid zugrundeliegt.
(Satz Greedy: Sei [e,U] beliebiges Teilmengensystem.Dann gilt :Kanonischer GreddyAlgorithmus liefert für jede Funktion
w:E->N eine optimale Lösung(E,U,w) genau dann wenn [E,U] ist MAtroid.)
Eine Def matroid (vielleicht nicht Deine)
Unabhängigkeitssystem, leere Menge unhabhaengig +
A,B in U und |B| > |A| folgt exists b in (B ohne A) so dass
A + {b} auch in U.
Betrachte U’ = Mengen in U, die e enthalten.
konstruiere (E’,U’’) indem aus E und U’ überall e entfernt wird.
Ist immer noch US.
{e} war in U, alsi ist {} in U’’
A’,B’ in U’’ |B’|>|A’|, betrachte A=A’+{e}, B analog, dann
|B|>|A| also gibts b in B ohne A. Das kann nicht e sein, da
A e enthaelt. Also ist A+{b} in U und somit A+{b} ohne e
in U’’.
MFG
ML