91Ó°ÊÓ

Wege-Baum von \(a\) zu allen anderen Knoten in dem ungerichteten Graphen \(G\), der durch die Adjazensmatrix \(9.1\) gegeben ist. \begin{tabular}{c|c|c|c|c|c|c|c|c} & \(a\) & \(b\) & \(c\) & \(d\) & \(e\) & \(f\) & \(g\) & \(h\) \\ \hline\(a\) & & 11 & 2 & 5 & & & & \\ \hline\(b\) & 11 & & 9 & & 3 & 7 & & \\ \hline\(c\) & 2 & 9 & & 2 & & 3 & 1 & \\ \hline\(d\) & 5 & & 2 & & & & 2 & \\ \hline\(e\) & & 3 & & & & 2 & & 1 \\ \hline\(f\) & & 7 & 3 & & 2 & & 1 & 1 \\ \hline\(g\) & & & 1 & 2 & & 1 & & 3 \\ \hline\(h\) & & & & & 1 & 1 & 3 & \end{tabular}

\(w(e)<1\) für jede Kante \(e \in E\) und \(s, t \in V .\) Das Gewicht \(w(e)\) gibt an, wie hoch die Wahrscheinlichkeit ist, dass diese Kante nicht ausfällt. Gesucht ist nun ein \((s, t)\)-Weg \(p\) mit maximaler Zuverlässigkeit \(w(p)\), $$ w(p)=\prod_{e \in p} w(e) $$ Wie kann dieser Weg berechnet werden?

zesten Weg zu haben. Mit Perturbation, d.h. kleinen Veränderungen der Kantengewichte, kann dies erreicht werden. Formal ist Perturbation der Kostenfunktion folgendermaßen definiert: Sei \(G=(V, E)\) ein Graph mit ganzzahligen Kosten \(c: E \rightarrow \mathbb{N} .\) Sei \(e_{1}, \ldots, e_{m}\) eine beliebige Nummerierung der Kanten. Die perturbierte Kostenfunktion \(c^{\prime}: E \rightarrow \mathbb{R}\) ist dann definiert durch \(c^{\prime}\left(e_{i}\right):=c\left(e_{i}\right)+\left(\frac{1}{2}\right)^{i}\) Zeigen Sie: 1\. In \(G\) existiert immer ein eindeutiger kürzester Weg bzgl. \(c^{\prime}\). 2\. Ein kürzester Weg bzgl. \(c^{\prime}\) ist ebenfalls ein kürzester Weg bzgl. \(c\). 3\. Ein kürzester Weg bzgl. \(c\) muss kein kürzester Weg bzgl. \(c^{\prime}\) sein.