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 abzuschreiten. Der sich daraus ergebene Graph, der alle Knoten des Ausgangsgraphen enthält, 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.

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 abzuschreiten. Der sich daraus ergebene Graph, der alle Knoten des Ausgangsgraphen enthält, 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/ungewichteter 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 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 werden den Knoten und/order Kanten Werte zugeordnet ungewichteter Graph = den Kanten und/oder Knoten werden keine Werte zugeordnet