Vereinigung minimaler Schnitte < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 19:29 So 02.12.2012 | | Autor: | Aiphi |
| Aufgabe | | Seien [mm] $(S_1,\overline{S_1})$ [/mm] und [mm] $(S_2,\overline{S_2})$ [/mm] zwei minimale (s,t)-Schnitte in einem Netzwerk. Zeige, dass [mm] $(S_1 \cup S_2,\overline{S_1}\cap\overline{S_2})$ [/mm] auch ein minimaler (s,t)-Schnitt ist. |
Bewiesen hab ich schon, dass es ein (s,t)-Schnitt ist:
[mm] $(S_1 \cup S_2,\overline{S_1}\cap\overline{S_2}) [/mm] = [mm] (S_1 \cup S_2,\overline{S_1 \cup S_2}) [/mm] $. Somit ist es ein Schnitt, da es disjunkt ist und vereinigt den Graphen/das Netzwerk aufspannt.
Da [mm] $s\in S_1$ [/mm] und [mm] $s\in S_2$ [/mm] ist [mm] $s\in S_1\cup S_2$.
[/mm]
Da [mm] $t\in \overline{S_1}$ [/mm] und [mm] $t\in \overline{S_2}$ [/mm] ist [mm] $t\in \overline{S_1}\cap \overline{S_2}$.
[/mm]
Somit ist es ein (s,t)-Schnitt.
Jetzt scheitere ich aber daran, dass der Schnitt ebenfalls minimal sein soll.
Eine Idee war bisher, die Kantensummen der beiden Schnitte zu addieren und nach ein paar Umformungen hoffentlich auf 2 mal der Kantenbewertung des Vereinigungs-Schnittes zu kommen. Also in etwa so:
[mm] $\summe_{i\in S_1, j\in \overline{S_1}}c(i,j) [/mm] + [mm] \summe_{i\in S_2, j\in \overline{S_2}}c(i,j) [/mm] = ... = 2 * [mm] (\summe_{i\in S_1\cup S_2, j\in \overline{S_1}\cap\overline{S_2}}c(i,j) [/mm] )$
Ein anderer Ansatz (oder eher eine Auffälligkeit) wäre vielleicht, dass die Kanten des Vereinigungsschnittes eine Teilmenge der Kanten der beiden Schnitte sind. Ich bin mir dabei aber zum Einen nicht sicher, ob das überhaupt immer gilt, und zum Anderen weiß ich nicht, ob mir das irgendwie hilft.
Ich würde mich sehr über Hilfe und Ansätze freuen.
Liebe Grüße
Aiphi
P.S.: Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Do 06.12.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
