Algorithmik mündlich

1.) \(B_0 = \{u\}\)

2.) Nach Schritt \(i\) ist \(B_i\) berechnet,so dass für jedes \(w \in B_i, d(u,w)\) und ein zugehöriger kürzester Pfad von \(u\) und \(w\) bekannt sind. Weiterhin gilt für alle \(w'\in B_i\) und alle \(z \in V\backslash B_i:d(u,w')\le d(u,z)\).

• \((x\in B_{i_1}, y\notin B_{i-1})\)
• \(\forall (x',y')\in E: x' \in B_{i-1} \wedge y' \notin B_{i-1}: d(u.x) + \gamma(x,y) \le d(u,x') + \gamma(x',y')\)
• Nach diesem Schritt: \(B_i := B_{i-1}\cup \{ y \}\) und \(d(u,y)=d(u,x)+\gamma(x,y)\)

• Nach dem i-ten Durchlauf ist \(B=B_i\).
• Jeder Schritt vergrößert \(B_i\) und ernthält nu rdie vom Startknoten aus erreichbaren Knoten

\(\mathcal{O}(|V|^2+|E|)=\mathcal{O}(|V|^2)\)

und

\(\mathcal{O}(\underbrace{|E|}_{\text{Anzahl decrease-key}}+\underbrace{|V|}_{\text{Anzahl insert}}\underbrace{\log(|V|}_{\text{Anzahl delete_min}})\)

Wenn je zwei Knoten durch einen Pfad verbunden sind.

Ein Baum ist ein zusammenhängender, kreisfreier, ungerichteter Graph.

n - 1 Kanten

Beweis über Induktion:

IA: Ein Baum mit n=1 Knoten: 1-1=0

IS: n+1 Knoten:

Ein Baum mit n+1 Knoten ist ein Baum mit n Knoten und 1er Kanten angehängt. Nach Induktionsvorraussetzung hat der Baum n-1 Kanten + 1 angehängte Kante = n-1+1 = n

ISS: Behauptung ist wahr.

Ein Baum \(B=(V,F,\gamma|_F)\) mit \(F \subseteq E\) mit minimalen Gewicht, also \(\gamma(B):=\sum_{e \in F} \gamma(e)\) zu einem gewichteten Graphen \(G=(V,E,\gamma)\)