Ungerichteter Baum

Ungerichteter Baum

Ein ungerichteter Baum ist in der Graphentheorie ein spezieller Baum, dessen Kanten keine ausgezeichnete Richtung besitzen. Im Gegensatz zu gewurzelten Bäumen mit Kantenrichtungen besitzen ungerichtete Bäume keine ausgezeichnete Wurzel. Es lassen sich lediglich Blätter identifizieren, die dadurch charakterisiert sind, dass sie nur genau einen Nachbarn besitzen, deren Grad also genau 1 ist. Als Ordnung bezeichnet man hier den Maximalgrad des Baumes. Als innere Knoten bezeichnet man alle Knoten, die keine Blätter sind.

Paarweise äquivalente Charakterisierungen

Ungerichtete Bäume sind einfache zusammenhängende Graphen

  1. ohne Kreis,
  2. in denen je zwei beliebige verschiedene Knoten durch genau einen Pfad verbunden sind oder
  3. die Anzahl der Knoten um 1 größer ist als die Anzahl der Kanten.

Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

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

  • ungerichteter Baum — neorientuotasis medis statusas T sritis automatika atitikmenys: angl. undirected tree vok. ungerichteter Baum, m rus. неориентированное дерево, n pranc. arbre non direct, m …   Automatikos terminų žodynas

  • Baum (Graphentheorie) — Ein Baum ist in der Graphentheorie ein spezieller Graph, mit dem sich eine Monohierarchie modellieren lässt. Je nachdem, ob die Kanten des Baums eine ausgezeichnete Richtung besitzen, lassen sich graphentheoretische Bäume unterteilen in… …   Deutsch Wikipedia

  • Baum (Datenstruktur) — Ein Baum ist in der Graphentheorie ein spezieller Graph, mit dem sich eine Monohierarchie modellieren lässt. Je nachdem, ob die Kanten des Baums eine ausgezeichnete Richtung besitzen, lassen sich graphentheoretische Bäume unterteilen in… …   Deutsch Wikipedia

  • Baum (Informatik) — Ein Baum ist in der Graphentheorie ein spezieller Graph, mit dem sich eine Monohierarchie modellieren lässt. Je nachdem, ob die Kanten des Baums eine ausgezeichnete Richtung besitzen, lassen sich graphentheoretische Bäume unterteilen in… …   Deutsch Wikipedia

  • Ungerichteter Graph — 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

  • Baum — I. Wirtschaftsinformatik:1. Begriff: Bei der ⇡ Programmentwicklung verwendete ⇡ abstrakte Datenstruktur. Rekursive Definition: Ein B. ist entweder leer oder er besteht aus einer Wurzel, die mit endlich vielen (Teil )B. verknüpft ist. 2.… …   Lexikon der Economics

  • Gerichteter Baum — Gewurzelter Baum als In Tree mit Knoten 2 als Wurzel. Ein gewurzelter Baum (auch Wurzelbaum oder Aboreszenz) ist in der Graphentheorie ein Baum, dessen Kanten eine ausgezeichnete Richtung besitzen, so dass im Gegensatz zum ungerichteten Baum ein… …   Deutsch Wikipedia

  • Aufspannender Baum — Ein Graph mit einem minimalen Spannbaum. Ein Spannbaum (auch aufspannender Baum oder manchmal spannender Baum genannt; englisch spanning tree) ist in der Graphentheorie ein Teilgraph eines ungerichteten Graphen, der ein Baum ist und alle Knoten… …   Deutsch Wikipedia

  • Minimal spannender Baum — Ein Graph mit einem minimalen Spannbaum. Ein Spannbaum (auch aufspannender Baum oder manchmal spannender Baum genannt; englisch spanning tree) ist in der Graphentheorie ein Teilgraph eines ungerichteten Graphen, der ein Baum ist und alle Knoten… …   Deutsch Wikipedia

  • Spannender Baum — Ein Graph mit einem minimalen Spannbaum. Ein Spannbaum (auch aufspannender Baum oder manchmal spannender Baum genannt; englisch spanning tree) ist in der Graphentheorie ein Teilgraph eines ungerichteten Graphen, der ein Baum ist und alle Knoten… …   Deutsch Wikipedia

Share the article and excerpts

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