Hall Bedingung, Satz von König < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 12:19 Fr 16.11.2012 | | Autor: | schneva |
| Aufgabe 1 | In einem bipartiten Graphen G mit der Zweiteilung V=S∪T ist die Hall Bedingung
|A|≤|N(A)| für alle A⊆S
notwendig und hinreichend für die Existenz einer vollständigen Paarung. |
| Aufgabe 2 | Für einen bipartiten Graphen G=(S∪T,E) gilt max|M|=min|C|
m(G)=c(G)
Die größte Mächtigkeit einer Paarung in G ist gleich der geringsten Mächtigkeit einer Eckenüberdeckung von E. |
Hallo zusammen,
ich schreibe gerade meine Bachelorarbeit zum Thema "Paarung in bipartiten Graphen". Hierzu soll ich die Hall Bedingung und den Satz von König beweisen.
Ich habe schon in sämtlichen Büchern Beweise von der Hall Bedingung nachgelesen, aber irgendwie kann ich mit diesen Beweisen nichts anfangen oder die Beweise werden ausgelassen, weil sie zu schwer sind.
Zum Satz von König hab ich folgenden Beweis in meinen Unterlagen:
Beweis des Heiratssatzes mit Hilfe des Satzes von König
Zeigen:
Es gibt kein Matching mit |S| Kanten
[mm] \Rightarrow [/mm] Es gibt eine Menge C [mm] \subseteq [/mm] S mit |N(C)| < |C|
Nach dem Satz von König gibt es einen Überdeckung A [mm] \cup [/mm] B, A [mm] \subseteq [/mm] S, B [mm] \subseteq [/mm] T mit
|A [mm] \cup [/mm] B|=|A|+|B|<|S|
[mm] \Rightarrow [/mm] |B|<|S|-|A|=|S-A|
[mm] \Rightarrow |N(S-A)|\le|B|<|S-A|
[/mm]
Da A [mm] \cup [/mm] B eine Überdeckung ist, gibt es keine Kante zwischen S-A und T-B
Es wäre nett wenn mir jemand weiterhelfen kann, so dass ich das auch verstehe.
Schöne Grüße und danke schonmal,
schneva
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:20 Fr 23.11.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
