Graphentheorie - minimaler Spannbaum

Ein Teilgebiet der Graphentheorie beschäftig sich mit der Frage, welche Weg muss man in gewichteten Graphen nehmen, um die best mögliche Strecke zwischen allen im Graphen vorhandene Knoten abzuschreiten. Best möglich richtet sich dann nach den entsprechenden Algorithmen bzw. gewichteten Kanten. 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.

Begrifferläuterung

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

Graphentheorie Die älteste bekannte Schrift zum Thema Graphentheorie schrieb Leonhard Euler (geb.1707)namens

lat. solutio problematis ad geometriam situs pertinens

dt: Lösung eines Problems zur Geometrie der Lage

engl. The solution of a problem relating to the geometry of position

solutio = Lösung

probematis = Probleme

ad = Präfix bei

geometriam = Geometrie

situs = Lage

pertinens = sich beziehen auf Wird eingesetzt, wo graphentheoretische Probleme auftreten und Aussagen über Graphen bzw. deren Inhalt gemacht werden müssen. Wichtiges Teilgebiet der Mathematik, genauer der Kombinatorik.

1 Graph Ein Graph ist eine mathematische Struktur, die sich auch zeichnerische umsetzen läßt. Die visuelle Darstellung einer Menge an Punkten und ihre Zusammenhängen, den Geraden

Graph is ein geordnetes Paar (V,E) G=(V,E)

V = endliche Menge an Knoten(engl. vertices)

E = Menge der Kanten(engl. edges) einer zweidimensionalen Teilmenge von V ein Graph kann ein zusammenhängender Graph sein Beispiel:

1.1 gewichtet/ungewichteter 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

1.2 gerichtet/ungerichtet 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.3 zusammenhängend/nicht zusammenhängend zusammenhängend Graph = in einem ungerichteten Graphen läßt sich jeder Knoten zwischen einem Start zu einem Endzustand erreichen

nicht zusammenhängend Graph = besitzt mehr als eine Komponente und nicht jeder Knoten läßt sich zwischen einem Startzustand bzw. Endzustand erreichen

2 Baum Ein Baum ist ein Spezialform von Graph, der keine Kreise besitz. Unter anderen kann er dahingehend benutzt werden, eine Hierachien abzubilden, indem Elemente über- bzw untergeordnet werden Als Form des Graphen besitz er gleiche Eigenschaften. geordnetes Paar (V,E) G=(V,E) Bei Bäumen unterscheidet man wie bei Graphen zwischen gerichtet und ungerichte. Im Informatikbereich wird meist mit Bäumen gearbeitet, die eine Wurzel haben und gerichtet sind. Anders in der Graphentheorie, wo es Bäume wie den ungerichteten minimalen Spannbaum gib.

2.1 minimal Spannender Baum Alle Knoten eines ungerichteten Graphen verbindender minimal zusammenhängender Teilgraph. Dieser Spannwald hat auch Bezeichnungen wie auspannder Wald oder Spannwald. Ein in der Praxis recht häufige angewandte Problemlösungsstrategie. Überall wo der kürzeste Weg zwischen allen Punkten gesucht wird. => Beispiele in Kapitel 4

Graphenthoeretiker

Algorithmen

In diesem Kapitel werden die Algorithmen vorgestellte, die bei der Suche nach dem minimalen Spannbaum Unterstützung bieten. Diese Algorithmen sind allesamt der Kategorie Greedy-Algorithmus

1 Greedy-Algorithmen Wie dem Namen zu entnehmen, sind das gierige/gefrässig Algorithmen, d.h. Strategie die sich hinter diesem Algorithmus verbirgt, ist eine gefräßige. Versuch in einem Schritt so viel zu erreichen wie möglich und nimm der das beste Stücke, das du kriegen kannst. Welches Stück angemessen erscheint, wird mittels Algorithmus herrausgefunden. Ein Greedy-Algorithmus kommt ohne Rückgriff auf Werte, zum Beispiel Werte aus dem Cache und Entscheidungen werden nur einmal gefällt bzw. nicht zurückgezogen

1.1 Aufbau von Greedy-Algorithmen Bestandteile eines Greedy-Algorithmus

- (verbrauchende)Liste aller Kandidaten

- (aufbauende)Liste der Ergebnisse

- Funktion ergebnis? - ob sich eine Ergebnis für das Problem ergeben hat

- okay? - #t wenn Knoten zulässig isz

- next -wählt nächsten Knoten

- modi+ - Verändert Knotenliste, wenn es zu einer Erweiterung der Liste aller Knoten kommt

- modi- - Verändert Knotenliste, wenn es zu keiner Erweiterung der Liste aller Knoten kommt

- ziel - Ausgabefunktion des Algorithmus

1.2 Greedy Prozedure in Dr Racket

2 Tiefen- und Breitensuche

3 Algorithmus von Prim

4 Algorithmus von Kruskal

Beispiele =

Scheme Programm Algorithmus-4