Laufzeit Ford Fulkerson < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 15:30 Mo 13.04.2009 | | Autor: | fin129 |
| Aufgabe | Wir betrachten Netzwerke, in denen jeder Knoten außer der
Quelle und der Senke Ingrad 1 hat. Zeigen Sie, dass der Ford-Fulkerson-Algorithmus
auf solchen Netzwerken polynomielle Laufzeit hat. |
Mein Ansatz führt leider ins Leere:
Allgemeine worst case Laufzeit von FF auf einem Netzwerk (Graphen) $G=(V;E;c: E [mm] \mapsto \mathbb{N})$ [/mm] mit Quelle $q$ und Senke $s$ laut Vorlesung:
[m]
T_{worst}=O((\vert E \vert + \vert V \vert) \cdot \sum_{e\in q\rightarrow} c(e))
[/m]
nämlich [mm] $O(\vert [/mm] E [mm] \vert [/mm] + [mm] \vert [/mm] V [mm] \vert)$ [/mm] für die Suche eines beliebigen q-s-Weges als "Kosten eines Schrittes" und maximal [mm] $\sum_{e\in q\rightarrow} [/mm] c(e)$ Schritte, d.h. im worst case Flusserhöhungen um je 1 bis maximal die ausgehende Kapazitätsgrenze der Quelle erreicht ist.
Soweit ist mir das noch klar.
Ingrad 1 macht aus dem Graphen eine Art Baum [mm] ($\vert [/mm] E [mm] \vert [/mm] = [mm] \vert [/mm] V [mm] \vert [/mm] - 1$), bei dem jedes Blatt mit der Senke verbunden ist [mm] ($\exists$ [/mm] maximal $ [mm] \vert [/mm] V [mm] \vert [/mm] - 1$ Blattknoten mit je einer Kante), es gilt also
[m]
\vert E \vert = O(2 \vert V \vert)
[/m]
In Konsequenz erhalte ich eine wc-Laufzeit von
[m]
T_{worst}=O((3 \vert V \vert) \cdot \sum_{e\in q\rightarrow} c(e))
[/m]
was bei einer zugrundeliegenden Eingabe von
[m]
S=O(\vert E \vert + \vert V \vert + \sum_{e \in E} \log c(e))
[/m]
nicht polynomiell ist.
Hat jemand einen Tipp wie es weitergeht / was falsch ist?
-------------------------------------------------------------------------
Achso, der knappe Lösungsweg seitens der Professur:
Suche Weg:
[m]
O(\vert E \vert + \vert V \vert)
[/m]
worst case
[m]
O(\vert E \vert \cdot (\vert E \vert + \vert V \vert))
[/m]
sogar:
[m]
O(\vert V \vert \cdot (\vert E \vert + \vert V \vert))
[/m]
Eingabegröße:
[m]
O(\vert E \vert + \vert V \vert)=O(l)
[/m]
mit
[m]
\vert V \vert < l
[/m]
also
[m]
\Longrightarrow O(l \cdot l) = O(l^2) \square
[/m]
-------------------------------------------------------------------------
Diesen verstehe ich allein schon deswegen nicht, weil doch zur Eingabe eines Netzwerks nicht nur alle Knoten und Kanten gehören, sondern auch die Kapazitäten der Kanten.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 Mi 15.04.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
