29 lines
1.1 KiB
TeX
29 lines
1.1 KiB
TeX
|
\section{Leichteste Kreise}
|
||
|
|
\begin{tasks}
|
||
|
|
\item
|
||
|
|
Wir wenden Dijkstra auf den Graphen $G$ mit Startknoten $s$ an (\autoref{fig:edsger}).
|
||
|
|
Das geht in $\Oh(n \log n)$ da Dijkstra in $\Oh(E + V \log V)$ läuft und die Kanten $m$ im planaren Graphen mit $m \leq 3n-6$ beschränkt sind.
|
||
|
|
|
||
|
|
Einen Kreis der $s$ enthält existiert, wenn es in einem Teilbaum von $s$ des
|
||
|
|
Kürzeste-Wege-Baums eine Rückwärtskante zu $s$ gibt.
|
||
|
|
|
||
|
|
Haben wir eine Rückwärtskante in einem Teilbaum gefunden, lesen wir den kürzesten
|
||
|
|
Weg von $s$ zu dem Knoten $a$ von dem die Rückwärtskante ausgeht, aus dem
|
||
|
|
Kürzeste-Wege-Baum ab. Das Gewicht des Kreises erhalten wir, durch $a_d + \abs{as}$, wobei $a_d$ die Länge des kürzesten $s-a$-Weges ist und $\abs{as}$ das Kantengewicht der Kante $as$.
|
||
|
|
|
||
|
|
Es reicht, die erste Rückwärtskante die wir finden zu nehmen.
|
||
|
|
|
||
|
|
Das müssen wir nun für alle Teilbäume machen.
|
||
|
|
Da der durchschnittliche Knotengrad im Graphen
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
\end{tasks}
|
||
|
|
|
||
|
|
\begin{figure}
|
||
|
|
\centering
|
||
|
|
\includegraphics{edsger.png}
|
||
|
|
\caption{Let's go Edsger! Shortest Path!}
|
||
|
|
\label{fig:edsger}
|
||
|
|
\end{figure}
|