Google
 
Web www.grundstudium.info
  Home     
    
    Bücher   Links   Impressum

next up previous contents
Nächste Seite: Ungerichtete Graphen Aufwärts: Hauptseite Algorithmen Vorherige Seite: Dijkstra-Beweis   Inhalt

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.
next up previous contents
Nächste Seite: Ungerichtete Graphen Aufwärts: Hauptseite Algorithmen Vorherige Seite: Dijkstra-Beweis   Inhalt