Geschrieben von mathfoxx am 03.10.2015 um 16:01:
Graphentheorie
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