Satz von Hall < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:29 Do 05.09.2013 | | Autor: | AntonK |
| Aufgabe | Sei G=(S [mm] \cup [/mm] T,E) ein bipartiter Graph. Dann erlaubt G genau dann ein perfektes Matching wenn |N(U)| [mm] \ge [/mm] |U| für alle U [mm] \subseteq [/mm] S und alle U [mm] \subseteq [/mm] T.
N(U) sind die Nachbarn. |
Hallo Leute,
bei uns im Skript ist der Satz von Hall so definiert, aber ich verstehe nicht ganz was |U| sein soll, nehme ich mir die beliebige Teilmengen raus oder wie?
Bei Wikipedia gab es ein Beispiel für ein perfektes Matching mit dem [mm] K_{3,3}
[/mm]
Wie habe ich mir das dort vorzustellen beispielsweise, was ist |U|?
Danke schonmal!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:55 Fr 06.09.2013 | | Autor: | Marcel |
Hallo,
> Sei G=(S [mm]\cup[/mm] T,E) ein bipartiter Graph. Dann erlaubt G
> genau dann ein perfektes Matching wenn |N(U)| [mm]\ge[/mm] |U| für
> alle U [mm]\subseteq[/mm] S und alle U [mm]\subseteq[/mm] T.
>
> N(U) sind die Nachbarn.
> Hallo Leute,
>
> bei uns im Skript ist der Satz von Hall so definiert,
Sätze sind keine Definitionen - der Satz wurde höchstens so formuliert,
denn das ist eine beweisbare Aussage.
> aber
> ich verstehe nicht ganz was |U| sein soll, nehme ich mir
Ich habe keine Ahnung mehr, um was genau es da geht, aber rein
mathematisch:
$|U|$ ist die Anzahl der Elemente von [mm] $U\,.$
[/mm]
(Entsprechend: Wenn [mm] $N(U)\,$ [/mm] die Menge der Nachbarn ist, dann ist $|N(U)|$
die Anzahl der Nachbarn.)
> die beliebige Teilmengen raus oder wie?
Steht oben: Für alle $U [mm] \subseteq [/mm] S$ und alle $U [mm] \subseteq T\,.$
[/mm]
Also: "Durchlaufe" alle $U [mm] \subseteq [/mm] S$ und alle $U [mm] \subseteq T\,.$
[/mm]
> Bei Wikipedia gab es ein Beispiel für ein perfektes Matching mit dem $ [mm] K_{3,3} [/mm] $
Am besten mal den Link nachliefern!
P.S. Lies' doch mal hier
![[]](/images/popup.gif) http://de.wikipedia.org/wiki/Heiratssatz
den Abschnitt "Problemstellung".
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 01:40 Fr 06.09.2013 | | Autor: | AntonK |
Erst einmal danke für deine Antwort!
Ich bezog mich auf diesen Link:
http://de.wikipedia.org/wiki/Matching_%28Graphentheorie%29
Nehmen wir mal diese 6 Knoten und den Graph dazu:
2---4
| |
6---1---5
|
3
Das heißt die Teilmengen S und T sind die folgenden:
S=[1,2,3], T=[4,5,6]
Alle möglichen Teilmengen U sind:
[1],[2],[3],[1,2],[1,3],[2,3]
[4],[5],[6],[4,5],[4,6],[5,6]
Nun schaue ich mir |N(U)| an:
|N([1])|=3 [mm] \ge [/mm] |U|=1 (Weil die 1 drei Nachbarn hat)
|N([2])|=2 [mm] \ge [/mm] 1
|N([3])|=1 [mm] \ge [/mm] 1
|N([1,2]|=3+2 [mm] \ge [/mm] 2
.
.
.
Wenn ich nun alle prüfe und die Gleichung erfüllt ist, dann gibt es ein perfektes Matching?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:40 Fr 06.09.2013 | | Autor: | Marcel |
Hallo,
> Erst einmal danke für deine Antwort!
>
> Ich bezog mich auf diesen Link:
>
> http://de.wikipedia.org/wiki/Matching_%28Graphentheorie%29
>
> Nehmen wir mal diese 6 Knoten und den Graph dazu:
>
> 2---4
> | |
> 6---1---5
> |
> 3
> Das heißt die Teilmengen S und T sind die folgenden:
>
> S=[1,2,3], T=[4,5,6]
sind die zwangsläufig eindeutig? Jedenfalls kannst Du sicher mal diese
betrachten... (Übrigens finde ich die "Mengennotation" hier doch sehr
eigen - aber das ist sicher eine Sache der Konvention...)
> Alle möglichen Teilmengen U sind:
>
> [1],[2],[3],[1,2],[1,3],[2,3]
>
> [4],[5],[6],[4,5],[4,6],[5,6]
>
> Nun schaue ich mir |N(U)| an:
>
> |N([1])|=3 [mm]\ge[/mm] |U|=1 (Weil die 1 drei Nachbarn hat)
> |N([2])|=2 [mm]\ge[/mm] 1
> |N([3])|=1 [mm]\ge[/mm] 1
> |N([1,2]|=3+2 [mm]\ge[/mm] 2
> .
> .
> .
>
> Wenn ich nun alle prüfe und die Gleichung erfüllt ist,
Alle "Un-Gleichungen" müssen erfüllt sein.
> dann gibt es ein perfektes Matching?
So verstehe ich die Aussage des Satzes jedenfalls. Aber: Ich bin in der
Graphentheorie nicht mehr so wirklich ganz fit - wäre vielleicht gut, wenn
noch jemand anderes mal drüberguckt.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:34 Fr 13.09.2013 | | Autor: | AntonK |
Danke, habs verstanden!
|
|
|
|
