https://demowiki.knowlus.com/index.php?action=history&feed=atom&title=Wald_%28Graphentheorie%29 2026-04-09T13:43:13Z Versionsgeschichte dieser Seite in Demo Wiki MediaWiki 1.44.2 https://demowiki.knowlus.com/index.php?title=Wald_(Graphentheorie)&diff=9717&oldid=prev 2020-01-30T21:37:36Z

<p>Definition auf gerichtete und ungerichtete Graphen erweitert.</p> <p><b>Neue Seite</b></p><div>Als &#039;&#039;&#039;Wald&#039;&#039;&#039; bezeichnet man in der [[Graphentheorie]] einen [[Zyklus (Graphentheorie)|azyklischen]] Graphen. Ist dieser [[zusammenhängender Graph|zusammenhängend]], so spricht man von einem [[Baum (Graphentheorie)|Baum]]. Jede [[Zusammenhang von Graphen|Zusammenhangskomponente]] eines Waldes ist ein Baum.<br /> <br /> Manchmal ist es sinnvoll, einen [[Knoten (Graphentheorie)|Knoten]] als Wurzel auszuzeichnen. Man spricht dann von einem &#039;&#039;[[Wurzelbaum]]&#039;&#039;. 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 &#039;&#039;[[In-Tree|In-]]&#039;&#039;, beziehungsweise &#039;&#039;[[Out-Tree]]s&#039;&#039;. Die In- und Out-Wälder sind dann Graphen mit mehreren solchen Komponenten.<br /> <br /> == Algorithmen auf Wäldern ==<br /> Aufgrund ihrer einfachen Struktur kann die [[Komplexität]] von auf Wäldern arbeitenden [[Algorithmus|Algorithmen]] meist gut abgeschätzt werden. Oft arbeiten die Algorithmen mit einem [[Baum (Datenstruktur)|Baum als Datenstruktur]] schneller als andere Algorithmen für dasselbe [[Problem]]. Beispielsweise ist für das Problem [[Sortierverfahren|Sortieren]] das auf Bäumen arbeitende [[Heapsort]] schneller als ein eher naives [[Insertionsort]].<br /> <br /> == Sonderrolle innerhalb der Graphentheorie ==<br /> Um alle [[Knoten (Graphentheorie)|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 [[Kantengewicht]]e 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]].<br /> <br /> [[Datei:Directed acyclic graph 3.svg|thumb|Gegenbeispiel: gerichtet azyklische Graphen müssen keine Wälder sein]]<br /> <br /> == Wichtige Aussagen und Sätze ==<br /> * Alle Wälder sind [[bipartiter Graph|bipartit]]. Eine Bipartition bekommt man, indem man die Knoten bezüglich ihrer Distanz [[modulo]] 2 zu einem beliebig, fest gewählten Knoten zusammenfasst.<br /> * Alle Wälder sind [[Planarer Graph|planar]].<br /> * Genau alle gerichtet azyklischen Graphen können [[Topologische Sortierung|topologisch sortiert]] werden, gerichtete Wälder also insbesondere.<br /> * Ein Graph ist genau dann ein Wald, wenn seine [[zyklomatische Zahl]] &lt;math&gt;0&lt;/math&gt; ist.<br /> <br /> == Siehe auch ==<br /> * [[Dendrogramm]]<br /> <br /> [[Kategorie:Bäume und Wälder| Wald (Graphentheorie)]]</div>

imported>DixMartin