Wurzel (Graphentheorie)

Wurzel (Graphentheorie)

Unter einer Wurzel versteht man bei gerichteten Bäumen denjenigen Knoten von dem aus alle anderen Knoten im Baum erreichbar sind, und der selbst von keinem anderen Knoten aus erreichbar ist. Eine Wurzel ist somit der einzige Knoten in einem Baum welcher keinen Vorgänger hat. Zeichnet man einen Baum, so ist die Wurzel immer der oberste Knoten des Baumes. Bäume haben in der Informatik immer genau eine Wurzel. Zerlegt man den ursprünglichen Baum in mehrere Teilbäume, so haben auch die entsprechenden Teilbäume wieder genau eine bestimmte Wurzel. Verallgemeinert man den Begriff der Wurzel auf allgemeine Graphen, so spricht man auch von Quellen.

Definition

Ein Knoten ist eine Wurzel genau dann wenn gilt:

  • Alle weiteren Knoten des Baumes sind von diesem Knoten aus erreichbar
  • Der Knoten hat keinen Vorgänger

Beispiel

Beispielbaum
  • Die Wurzel des Beispielbaumes hat die Marke 1.
  • Die Wurzel des Teilbaumes welcher aus den Knoten 5,9 und 10 besteht hat die Marke 5
  • Die Wurzel des Teilbaumes welcher nur aus dem Knoten 12 besteht hat die Marke 12

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Wurzel — (althochdeutsch wurzala „Krautstock“) steht für: Wurzel (Pflanze), den meist im Boden befindlichen Teil von Pflanzen in der Chemie ist eine Wurzel ein Wasserabscheider Im Norden Deutschlands eine andere Bezeichnung für Karotte Wurzel (Mathematik) …   Deutsch Wikipedia

  • Blatt (Graphentheorie) — Beispiele Ungerichteter Baum Gerichteter Baum (hier: Out Tree) …   Deutsch Wikipedia

  • Vater (Graphentheorie) — Als Elternknoten, Elter oder Vater eines Knotens v bezeichnet man in der Graphentheorie in einem Baum den zu v übergeordneten Nachbarn, also den Nachbarn der näher an der Wurzel des Baumes liegt. Entsprechend bezeichnet man den Knoten v als Kind… …   Deutsch Wikipedia

  • Abstand (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Adjazenz (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Benachbart (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Inzidenz (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Schlinge (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Tiefe (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Valenz (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”