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: enthält genau dann eine Paarung von wenn für alle .
Beweis: sei Matching, welches jede Ecke paart. Es existiert eine Paarung von wenn mindestens Nachbarn hat. für alle .
Es existiert Paarung von ganz A. Also zu jeder Paarung die eine Ecke ungepaart lässt existiert ein Verbesserungsweg.
Wir definieren: alternierende Wege, die in a beginnen''
Jeder alternierende Weg P_a1,...,an} endet in einer Kante aus M.
Definiere: Dann gilt: Es existiert ein wobei . alternierender Weg von a nach . Wäre gepaart durch . so ist ein alternierender Weg. Also . Widerspruch, da ungepaart Verbesserungsweg....
Ist das formal alles so in Ordnung?
|