Out-Tree

Out-Tree

Ein Out-Tree ist in der Graphentheorie ein spezieller Graph, genauer ein gewurzelter Baum.

Definition

Ein Out-Tree ist ein gerichteter Graph mit einem ausgezeichneten Knoten, der so genannten Wurzel, für den im Gegensatz zu In-Trees gilt, dass jeder Knoten durch genau einen gerichteten Pfad von der Wurzel aus erreichbar ist.

Weitere Begriffe

Der maximale Ausgangsgrad wird als Ordnung eines Out-Trees bezeichnet und alle Knoten mit Ausgangsgrad 0 bezeichnet man als Blätter. Als Tiefe eines Knotens bezeichnet man die Länge des Pfades von der Wurzel zu ihm und als Höhe des Out-Trees die Länge eines längsten Pfades.

Wie bei ungerichteten Bäumen bezeichnet man auch in gewurzelten Bäumen alle Knoten, die kein Blatt sind, als innere Knoten. Manchmal schließt man die Wurzel dabei aber aus.

Für einen von der Wurzel verschiedenen Knoten v bezeichnet man den Knoten, durch den er mit einer eingehenden Kante verbunden ist als Vater, Vaterknoten, Elternknoten oder Vorgänger von v. Als Vorfahren von v bezeichnet man alle Knoten, die entweder Vater von v oder Vorgänger des Vaters sind.

Umgekehrt bezeichnet man alle Knoten, die von einem beliebigen Knoten v aus durch eine ausgehende Kante verbunden sind als Kinder, Kindknoten, Sohn oder Nachfolger von v. Als Nachfahren von v bezeichnet man Kinder von v oder deren Nachfahren. Als Geschwister oder Geschwisterknoten werden in einem Out-Tree Knoten bezeichnet, die den gleichen Vater besitzen.

Alternative Definition

Out-Trees lassen sich auch rekursiv definieren. Sie bestehen aus einem Knoten w, der die Wurzel des Baumes darstellt, welcher ausschließlich mit den Wurzeln knotendisjunkter Out-Trees T1, T2, ..., Tn verbunden ist, und zwar in Richtung der Wurzeln von T1, T2, ..., Tn.


Wikimedia Foundation.

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

  • Tree — /tree/, n. Sir Herbert Beerbohm /bear bohm/, (Herbert Beerbohm), 1853 1917, English actor and theater manager; brother of Max Beerbohm. * * * I Woody perennial plant. Most trees have a single self supporting trunk containing woody tissues, and in …   Universalium

  • Tree house — Tree houses, treehouses, or tree forts, are buildings constructed among the branches, around or next to the trunk of one or more mature trees, and are raised above the ground. Tree houses are built and used for recreation, as temporary retreats,… …   Wikipedia

  • Tree sitting — is a form of environmentalist civil disobedience in which a protester sits in a tree, usually on a small platform built for the purpose, to protect it from being cut down (speculating that loggers will not endanger human lives by cutting an… …   Wikipedia

  • out of your tree — informal phrase not thinking in a clear or sensible way Thesaurus: crazy or sillysynonym Main entry: tree * * * out of your tree informal : ↑crazy …   Useful english dictionary

  • Out of My Tree (album) — Out of My Tree Studio album by John Sykes Released August 1995 …   Wikipedia

  • Tree worship — (dendrolatry) refers to the tendency of many societies throughout history to worship or otherwise mythologize trees. Trees have played an important role in many of the world s mythologies and religions, and have been given deep and sacred… …   Wikipedia

  • Tree stand — Tree stands give an edge to hunters who use them. Many people also know tree stands as deer stands. Tree stands are becoming more popular with advances in technology. TypesHunters use three different types of tree stands. A fourth type of stand… …   Wikipedia

  • out on a limb — {adv. phr.} With your beliefs and opinions openly stated; in a dangerous position that can t be changed. * /The president went out on a limb and supported a foreign aid bill that many people were against./ * /Grandfather went out on a limb before …   Dictionary of American idioms

  • out on a limb — {adv. phr.} With your beliefs and opinions openly stated; in a dangerous position that can t be changed. * /The president went out on a limb and supported a foreign aid bill that many people were against./ * /Grandfather went out on a limb before …   Dictionary of American idioms

  • Tree Solitaire — Tree SolitaireTree solitaire is a special form of solitaire in which cards are laid out as follows: Row one One card Row two Two cards Row three Three cards Row four Four cards Row five Five cards Row six Six Cards Row seven Seven cardsAll rows… …   Wikipedia

Share the article and excerpts

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