Graphentheorie

Neue Frage »

Auf diesen Beitrag antworten »
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 Hilfesmile

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
 
Auf diesen Beitrag antworten »
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
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »