submodulare Funktionen < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 12:15 Mo 15.12.2008 | | Autor: | Schobbi |
| Aufgabe | Sei [mm] f:2^{E} \to \IR [/mm] submodular mit [mm] f(\emptyset)=0. [/mm] Weiter sei
[mm] \gamma_{e} [/mm] := [mm] f(E\backslash\{e\})-f(E) \ge [/mm] 0 für alle e [mm] \in [/mm] E und
[mm] \overline{f}(A) [/mm] := f(A) + [mm] \gamma(A) [/mm] für alle Mengen A [mm] \subseteq [/mm] E.
Beweise: [mm] \overline{f} [/mm] ist submodular und monoton wachsend mit [mm] \overline{f}(\emptyset)=0 [/mm] |
Guten Morgen zusammen! Ich habe eine Frage zur Lösung der obigen Aufgabe. Mein Ansatz lautet wie folgt.
zzg: [mm] \overline{f}(A)+\overline{f}(B)\ge\overline{f}(A \cap B)+\overline{f}(A \cup [/mm] B)
[mm] \overline{f}(A)+\overline{f}(B) [/mm]
= [mm] f(A)+\gamma(A)+f(B)+\gamma(B)
[/mm]
= [mm] f(A)+f(B)+\gamma(A)+\gamma(B)
[/mm]
[mm] \ge [/mm] f(A [mm] \cap [/mm] B)+f(A [mm] \cup B)+\gamma(A)+\gamma(B)
[/mm]
= f(A [mm] \cap [/mm] B)+f(A [mm] \cup B)+f(E\backslash A)-f(E)+f(E\backslash [/mm] B)-f(E)
Mein Problem besteht nun darin die [mm] \gamma [/mm] 's bzw. [mm] f(E\backslash [/mm] A) so aufzuschlüsseln und wieder zusammenzufassen, dass ich meine Behauptung zeigen kann. Vielleicht könntet ihr mir dabei helfen. DANKE!
Viele Grüße Schobbi
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:22 Mo 15.12.2008 | | Autor: | pelzig |
> Sei [mm]f:2^{E} \to \IR[/mm] submodular mit [mm]f(\emptyset)=0.[/mm] Weiter
> sei
> [mm]\gamma_{e}[/mm] := [mm]f(E\backslash\{e\})-f(E) \ge[/mm] 0 für alle e [mm]\in[/mm]
> E und
> [mm]\overline{f}(A)[/mm] := f(A) + [mm]\gamma(A)[/mm] für alle Mengen A [mm]\subseteq[/mm] E.
Was ist denn [mm] $\gamma(A)$?
[/mm]
Gruß, Robert
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:23 Di 16.12.2008 | | Autor: | Schobbi |
Ich denke, dass mit [mm] \gamma(A) [/mm] gemeint ist, dass nicht nur ein Element e [mm] \in [/mm] E wie in obiger Definition betrachtet wird, sondern alle Elemente in [mm] A\subseteq [/mm] E. Somit würde dann gelten:
[mm] \gamma(A)=f(E\backslash [/mm] A)-f(E)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:20 Do 18.12.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
