Wald (Graphentheorie)

Wald (Graphentheorie)

Als Wald oder azyklischen Graphen bezeichnet man in der Graphentheorie einen ungerichteten Graphen ohne Zyklus. Ist dieser zusammenhängend, so spricht man von einem (ungerichteten) Baum. Die Zusammenhangskomponenten eines Waldes stellen in diesem Sinne für sich einen Baum dar, so dass ein so erklärter Wald aus Bäumen besteht. Eine Verallgemeinerung auf gerichtete Graphen kann man erklären, indem man diese auf die zugrundeliegenden Ungerichteten zurückführt.

Um eine topologische Charakterisierung, eine Höhe, zu finden, kann es sinnvoll sein, einen Knoten als Wurzel auszuzeichnen. Diese Strukturen heißen Wurzelbaum. Solche Wurzeln kann man einerseits beliebig festlegen. Andererseits gibt es spezielle gerichtete Graphen, wo sich eine Wurzel über die Struktur der Kantenrichtungen von selbst erklärt, etwa als einziger Knoten ohne eingehende/ausgehende Kante. Solche Bäume heißen In-, beziehungsweise Out-Trees. Die In- und Out-Wälder sind dann Graphen mit mehreren solchen Komponenten.

Inhaltsverzeichnis

Algorithmen auf Wäldern

Aufgrund ihrer einfachen Struktur kann die Komplexität von auf Bäumen arbeitenden Algorithmen meist gut abgeschätzt werden. Oft arbeiten die Algorithmen mit einem Baum als Datenstruktur schneller als andere Algorithmen für dasselbe Problem. Beispielsweise ist für das Problem Sortieren das auf Bäumen arbeitende Heapsort schneller als ein eher naives Insertionsort.

Sonderrolle innerhalb der Graphentheorie

Um alle Knoten eines Graphen effizient betrachten zu können, werden aus den bereits erwähnten Gründen gerne Bäume oder Wälder aus dem Graphen konstruiert. Dazu eignen sich Verfahren wie Breitensuche oder Tiefensuche auf den Graphen anzuwenden. Das Ergebnis ist ein Spannbaum. Ein minimaler Spannbaum wird unter gesonderter Betrachtung der Kantengewichte konstruiert, wie es durch den Algorithmus von Kruskal oder den Algorithmus von Prim geschieht. Dies dient beispielsweise als Grundlage für Algorithmen zum Problem des Handlungsreisenden.

Gegenbeispiel: gerichtet azyklische Graphen müssen keine Wälder sein

Wichtige Aussagen und Sätze

  • Alle Wälder sind bipartit. Eine Bipartition bekommt man, indem man die Knoten bezüglich ihrer Distanz modulo 2 zu einem beliebig, fest gewählten Knoten zusammenfasst.
  • Alle Wälder sind planar.
  • Genau alle gerichtet azyklischen Graphen können topologisch sortiert werden, gerichtete Wälder also insbesondere.

Siehe auch


Wikimedia Foundation.

См. также в других словарях:

  • Wald (Begriffsklärung) — Wald steht für: Wald, ein Ökosystem Waldgesellschaft, die Pflanzengesellschaft, die ein Gelände als Wald kennzeichnet Forst, ein Stück Waldland, eine waldbestandene Flur Wald (Graphentheorie), ein Graph, der aus einer Menge von Bäumen besteht… …   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

  • Glossar Graphentheorie — Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik zur Löschung vorgeschlagen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen. Dabei werden Artikel… …   Deutsch Wikipedia

  • Artikulation (Graphentheorie) — Wenn ein Graph zusammenhängend ist, bedeutet das intuitiv, dass jeder Knoten des Graphen von jedem anderen Knoten aus über einen Weg erreichbar ist. Inhaltsverzeichnis 1 Mathematische Definition 1.1 Ungerichtete Graphen 1.2 Gerichtete Graphen 2… …   Deutsch Wikipedia


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»