Edmonds-Karp bipartite Graphen < Algorithm. Geometrie < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 15:40 Mo 13.01.2014 | | Autor: | Klass |
| Aufgabe 1 | | Woran erkennt man am minimalen Schnitt (S,T) welche Knoten zu S und welche zu T gehören? |
| Aufgabe 2 | Sei G ein bipartiter Graph G = (V,E) und sei m(G) die Matchingzahl, c(G) die Knotenüberdeckungszahl und M das Matching von G.
a) Dann gilt immer |M|+1 <= m(G)
b) und es gilt immer c(G) <= m(G) |
Hallo,
zu Aufgabe 1:
Woran erkennt man das? Wüsste das jetzt nicht, wo man das erkennen soll. Sind eventuell die zu erst genannten immer S zugehörig und die zuletzt genannten T zugehörig?
zu Aufgabe 2:
Meiner Meinung nach, müsste beides FALSCH sein, oder? Denn a) gilt nicht, da m(G) = max(|M| : M ist ein Matching von G), also m(G)=M, daher ist M+1 größer als m(G). und b) gilt nicht, da für alle biparten Graphen gilt: m(G) = c(G) laut Satz von König. Also kann m(G) NIE kleiner als c(G) sein. Zudem gilt für alle anderen Graphen m(G) kleiner gleich c(G) und nicht c(G) kleiner gleich m(G).
Oder habe ich jetzt irgendwo einen Denkfehler?
Danke im Voraus für hilfreiche Antworten.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 Mi 15.01.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
