mathfoxx
Grünschnabel
Dabei seit: 03.10.2015
Beiträge: 1
 |
|
Meine Frage:
Hallo Liebe Community,
möchte mich gerne für eine Klausur vorbereiten.. Leider fehlen mir die Lösungen zu wichtigen, meiner Ansicht nach, relevanten Aufgaben.
Freue mich über jede Lösung oder Hilfe
Hier die Aufgaben:
1)
Beh: In einem bipartiten Graphen G=(S u T, E) ist das Matchingproblem auf das Flussproblem zurückzuführen.
2)
Sei G ein Baum.
Beh: Es existiert höchstens ein perfektes Matching
3)Sei G ein Graph ohne perf. Matching.
Beh: Es existiert v e V : jede mit v induzierte Kante in einem max. Matching enthalten ist.
4)Beh: Der Komplementgraph eines Intervallgraphen ist transitiv orientierbar
5)Beh: chordale Graphen sind perfekt
(man darf ohne Beweis annehmen, dass chordale Graphen eine simlizialen Knoten haben)
Meine Ideen:
... leider noch keine brauchbaren Ansätze
|
|
