Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » Heiratssatz (Beweis)

Heiratssatz (Beweis)

Universität / Fachhochschule

Graphentheorie

Tags: Graphentheorie

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
Salasah

Salasah aktiv_icon

03:03 Uhr, 21.07.2013

Antworten
Hi, ich habe in 2 Wochen eine mündliche Prüdung in Graphentheorie und wollte fragen ob der Beweis für den Heiratssatz so passt:

Behauptung:
G=(V=(AB,E) enthält genau dann eine Paarung von A, wenn |N(S)||S| für alle SA.

Beweis:
,,=>''
M sei Matching, welches jede Ecke XX paart.
Es existiert eine Paarung von SA, wenn S mindestens |S| Nachbarn hat.
|N(S)||S| für alle SA.

,,<=''
z.z.:|N(S)||S| Es existiert Paarung von ganz A. Also zu jeder Paarung M, die eine Ecke aA ungepaart lässt existiert ein Verbesserungsweg.

Wir definieren: ,,Pa1,...,Pan'' alternierende Wege, die in a beginnen''
A':={xA|xPi,xa,i=1,...,n}
B':={yB|yPi,i=1,...,n}

Jeder alternierende Weg P_{a1,...,an} endet in einer Kante aus M.
|A'|=|B'|

Definiere: S=A'{a}
Dann gilt: |N(S)|=|N(A'{a})||A'{a}|>|A'|=|B'|
Es existiert ein vA'{a}:{v,b}E,bB/B'
vPk, wobei 1kn.
Pkb alternierender Weg von a nach b.
Wäre b gepaart durch {a',b}M. so ist Pk,b,a' ein alternierender Weg.
Also a'A',b'B'. Widerspruch, da bB'b ungepaart Verbesserungsweg....

Ist das formal alles so in Ordnung?
Online-Nachhilfe in Mathematik
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.