Wunschseite
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
== 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