Wunschseite

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
= 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

<code id="562fdeb2aa612">
(define greedy
  (lambda(ls)
    (letrec([ergebnis(lambda(x)...)]
            [okay?(lambda(x)...)]
            [next(lambda(x)...)]
            [modi+(lambda(x)...)]
            [modi-(lambda(x...))]
            [ziel(lambda(x)(display x)(newline))])
     (ziel(cond[(empty? ls)'()]
           [else
            (begin
              (cons(ergebnis(car ls))
                   (greedy(cdr ls)))
              (if(equal? okay? #t)(modi+ value)(modi- value)))])))))
</code>

2 Tiefen- und Breitensuche 

3  Algorithmus von Prim

4  Algorithmus von Kruskal

== Beispiele  ==