| Die letzten 2 Beiträge |
| ed209 |
Hi
Wie bei fast allen Aufgaben in der theoretischen Informatik ist es die halbe Miete die Problemstellung formal zu definieren.
Fangen wir mal bei 1. an:
Kannst Du folgende Dinge formal hinschreiben:
1. Was ist das Matchingproblem?
2. Was ist das Flussproblem?
3. Wie kann man Problem B auf Problem A zurueckfuehren?
Gruss,
ED |
| mathfoxx |
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 |
|
|
