Spannbaum-Algorithmus

Spannbaum-Algorithmus
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 dieses Graphen enthält. Spannbäume existieren nur in zusammenhängenden Graphen.

Ein Teilgraph, der in einem Graphen für jede Komponente einen Spannbaum ergibt, wird Gerüst, Spannwald oder aufspannender Wald genannt. Dabei muss der Graph nicht notwendigerweise zusammenhängend sein. In zusammenhängenden Graphen sind Gerüst und Spannbaum identische Begriffe, während Spannbäume für unzusammenhängende Graphen nicht definiert sind.

In kantengewichteten Graphen lässt sich als Gewicht eines Graphen die Summe seiner Kantengewichte definieren. Ein Spannbaum bzw. ein Gerüst heißt minimal, wenn kein anderer Spannbaum bzw. kein anderes Gerüst in demselben Graphen mit geringerem Gewicht existiert. Häufig wird minimaler Spannbaum auch mit MST (Abkürzung des englischen Begriffs Minimum Spanning Tree) oder MCST (Minimum Cost Spanning Tree - ein Spannbaum mit minimalen Kosten) abgekürzt. Statt minimales Gerüst sagt man auch Minimalgerüst.

Inhaltsverzeichnis

Wichtige Algorithmen

Zum Finden eines minimalen Spannbaumes gibt es u.a. den Algorithmus von Kruskal und den Algorithmus von Prim. Letzterer ist der effizientere und besitzt die Worst-Case-Laufzeit \mathrm{O} \left( \left| V \right| \log \left( \left| V \right| \right) + \left| E \right| \right). Allerdings benötigt er dafür eine recht komplexe Datenstruktur, die sogenannten Fibonacci-Heaps. Es kann gezeigt werden, dass der Algorithmus von Prim optimal ist, da mit seiner Hilfe auch Zahlen sortiert werden können.

Anwendungen

Die Berechnung minimaler Spannbäume findet direkte Anwendung in der Praxis, beispielsweise für die Erstellung von kostengünstigen zusammenhängenden Netzwerken, wie beispielsweise Telefonnetze oder elektrische Netze. Auch bei Computernetzwerken mit redundanten Pfaden werden zur Vermeidung von Paketverdopplungen Spannbäume genutzt (siehe Spanning Tree Protocol).

In der Graphentheorie selbst sind MST-Algorithmen häufig Grundlage komplexerer Algorithmen für schwierigere Probleme. Die Berechnung minimaler Spannbäume ist zum Beispiel Bestandteil von Approximationsalgorithmen für das Problem des Handlungsreisenden, oft auch Traveling-Salesman-Problem genannt (siehe MST-Heuristik), oder für das Steinerbaum-Problem. Letzteres ist auch eine Verallgemeinerung des Problems, einen minimalen Spannbaum zu finden.

Des Weiteren spielen Spannbäume bei der algorithmischen Erzeugung von Labyrinthen eine Rolle. Ein Knoten im Spannbaum entspricht dabei einem Feld, während eine Kante einen möglichen Übergang zu einem Nachbarfeld darstellt. Eine fehlende Kante beschreibt folglich eine Wand. Da Spannbäume wie alle Bäume zyklenfrei sind, besitzt ein mittels Spannbäumen erzeugtes Labyrinth stets nur einen einzigen Lösungsweg.

Literatur

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

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

  • Algorithmus von Kruskal — Der Algorithmus von Kruskal ist ein Algorithmus der Graphentheorie zur Berechnung minimaler Spannbäume von ungerichteten Graphen. Der Graph muss dazu zusätzlich zusammenhängend, kantengewichtet und endlich sein. Der Algorithmus stammt von Joseph… …   Deutsch Wikipedia

  • Algorithmus von Jarnik, Prim und Dijkstra — Der Algorithmus von Prim dient der Berechnung eines minimalen Spannbaumes in einem zusammenhängenden, ungerichteten, kantengewichteten Graphen. Der Algorithmus wurde 1930 von dem tschechischen Mathematiker Vojtěch Jarník entwickelt. 1957 wurde er …   Deutsch Wikipedia

  • Algorithmus von Prim — Der Algorithmus von Prim dient der Berechnung eines minimalen Spannbaumes in einem zusammenhängenden, ungerichteten, kantengewichteten Graphen. Der Algorithmus wurde 1930 vom tschechischen Mathematiker Vojtěch Jarník entwickelt. 1957 wurde er… …   Deutsch Wikipedia

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

  • Algorithmus von Bellman und Ford — Der Algorithmus von Bellman und Ford (nach seinen Erfindern Richard Bellman und Lester Ford) ist ein Algorithmus der Graphentheorie und dient der Berechnung der kürzesten Wege ausgehend von einem Startknoten in einem kantengewichteten Graphen.… …   Deutsch Wikipedia

  • Gieriger Algorithmus — Greedy Algorithmen bzw. Gierige Algorithmen bilden eine spezielle Klasse von Algorithmen, wie sie in der Informatik auftreten. Sie zeichnen sich dadurch aus, dass sie schrittweise denjenigen Folgezustand auswählen, der zum Zeitpunkt der Wahl den… …   Deutsch Wikipedia

  • Greedy Algorithmus — Greedy Algorithmen bzw. Gierige Algorithmen bilden eine spezielle Klasse von Algorithmen, wie sie in der Informatik auftreten. Sie zeichnen sich dadurch aus, dass sie schrittweise denjenigen Folgezustand auswählen, der zum Zeitpunkt der Wahl den… …   Deutsch Wikipedia

  • Greedy-Algorithmus — Greedy Algorithmen oder gierige Algorithmen bilden eine spezielle Klasse von Algorithmen, die in der Informatik auftreten. Sie zeichnen sich dadurch aus, dass sie schrittweise den Folgezustand auswählen, der zum Zeitpunkt der Wahl den größten… …   Deutsch Wikipedia

  • Kruskal-Algorithmus — Der Algorithmus von Kruskal ist ein Algorithmus der Graphentheorie zur Berechnung minimaler Spannbäume von ungerichteten Graphen. Der Graph muss dazu zusätzlich zusammenhängend, kantengewichtet und endlich sein. Der Algorithmus stammt von Joseph… …   Deutsch Wikipedia

  • Minimaler Spannbaum — 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”