Ψ Die Informatikseite

Menü
Informatik » Bachelor » Algorithmen der Informatik » Bäume
Dijkstra-Beweis Algorithmen der Informatik Ungerichtete Graphen
Unterabschnitte

Bäume

Definition

  • Jeder Graph ohne Knoten und folglich auch ohne Kanten ist ein Baum
  • Für genau einen Knoten gilt $Pre(v_{0})=\emptyset$. Für alle anderen Knoten gilt: $v$ ist genau über einen Pfad von $v_{0}$ erreichbar.
  • $\Leftrightarrow$ Für genau einen Knoten gilt $Pre(v_{0})=\emptyset$. Für alle anderen Knoten gilt $\vert Pre(v)\vert=1$.

Höhe und Tiefe

Die Höhe des leeren Baumes ist $-1$. Die Höhe des Baumes mit nur dem Wurzelknoten ist $0$ usw.
Tiefe wird gesagt, wenn man die Entfernung eines Knoten zur Wurzel angibt. Der Wurzelknoten selbst hat die Tiefe $0$.

Regeln

  • $n=\vert V\vert$ Knotenanzahl
  • $h=H(T)$ Höhe

Allgemeine

  • Hat der Baum den Grad $k$, so ist $n\leq \frac{k^{h+1}-1}{k-1}$
  • Für $k\geq 2$ gilt: $H\uml {o}he(T)\geq \log_{k}(n\cdot(k-1)+1)-1$

Für Binär-Bäume

  • $n\leq 2^{h+1}-1$
  • $H\uml {o}he(T)\geq\log_{2}(n+1)-1$

Erzeugung von Wäldern aus Graphen

Wälder werden erzeugt, indem der Graph mittels DFS oder BFS durchgegangen wird. Dies geschieht, indem wir die Knoten, die in den Adjazenslisten stehen entweder in die Queue oder den Stack einreihen. Sollen wir einen schon besuchten Konten einreihen, so reihen wir diesen nicht ein.
Dijkstra-Beweis Algorithmen der Informatik Ungerichtete Graphen