Graphentheorie - minimaler Spannbaum

Ein Teilgebiet der Graphentheorie beschäftig sich mit der Frage, welche Weg muss man in gewichteten Graphen nehmen, um die kürzeste Strecke zwischen allen im Graphen vorhandene Knoten abzuschreiten. Der sich daraus ergebene Graph nennt man minimalen Spannbaum, auch als Gerüst Spannwald oder aufspannder Wald bezeichnet. Ist nur in zusammenhängenden Graphen vorhanden, muss selber aber nicht zwingend zusammenhängend sein.

Inhaltsverzeichnis

1. Begrifferläuterung

   1.1 Graph
   1.2 Baum
   1.3 Knoten
   1.4 Kanten
   1.5 gerichtet/ungerichtet Graphen
   1.6 gewichtet/ungewichtete Graphen

2.Teilgebiete der Graphentheorie

   1.1 Graph

3.Algorithmen

   3.1 Tiefen- und Breitensuche 
   3.2 Algorithmus von Prim
   3.3 Algorithmus von Kruskal

4.Beispiele

   4.1 Tool algorithmus-4
   4.2 Wüstenstadt Dehram
   4.3 Lieferdienst Kassel 

1.Begrifferläuterung

Die in der Einleitung verwendeten Begriffe werden in diese Kapitel ausführlich erläutert

1.1 Graph

visuelle Darstellung einer Menge und ihre zusammenhänge

1.2 Baum

1.3 Knoten

1.4 Kanten

1.5 gerichtet/ungerichtet Graphen

gerichtet Graph = Kanten sind Pfeile mit Richtung und nur in dieser kann der Graph durchlaufen werden ungerichtet = Kanten können in beide Richtungen durchlaufen werden

1.6 gewichtet/ungewichteter Graphen

gewichteter Graph = knoten- und kantengewichteten Graphen werden den Knoten und/oder Kanten Werte zugeordnet ungewichteter Graph = den Kanten und/oder Knoten werden keine Werte zugeordnet