Wald (Graphentheorie) - LinkFang.de





Wald (Graphentheorie)


Als Wald bezeichnet man in der Graphentheorie einen ungerichteten Graphen ohne Zyklus. Ist dieser zusammenhängend, so spricht man von einem (ungerichteten) Baum. Jede Zusammenhangskomponente eines Waldes ist ein Baum. Eine Verallgemeinerung auf gerichtete Graphen kann man erklären, indem man diese auf die zugrundeliegenden Ungerichteten zurückführt.

Manchmal ist es sinnvoll, einen Knoten als Wurzel auszuzeichnen. Man spricht dann von einem 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.

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.

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.
  • Ein Graph ist genau dann ein Wald, wenn seine zyklomatische Zahl [math]0[/math] ist.

Siehe auch


Kategorien: Bäume und Wälder

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Wald (Graphentheorie) (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.