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 wie 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.

== Graph ==
:Ein rein mathematische Struktur, die fälschlicherweise mit der grafischen Abbildung gleichgesetzt wird.
:Kann zeichnerisch einer Menge an Punkten und ihre Zusammenhängen, den Geraden, darstellen.
: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 [[Datei:Graph1.jpg]]

== Graphenkategorien ==
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[[Datei:Graph2.jpg]]
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[[Datei:Graph3.jpg]]
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[[Datei:Graph4.jpg]]

== 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.[[Datei:Graph5.jpg]]

== 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..[[Datei:Graph6.jpg]]

= Motıvatıon =

das Ziel besteht darin, eine Teilmenge E‘ ⊆ E auszuzeichnen, so
dass a) der Teilgraph G‘ = (V,E‘) zusammenhängend ist und b) E‘
möglichst wenige Kanten hat
 
[[Bild:Rene_Ziel_bsp.png]]

es sei G = (V,E) der folgende ungerichtete, zusammenhängende Graph,
wobei jeder Kante eine reelle Zahl (ihr Gewicht) zugeordnet wird (/* z.B.
ihre Länge ... */)
.. das Ziel besteht darin, eine Teilmenge E‘ ⊆ E auszuzeichnen, so
dass a) der Teilgraph G‘ = (V,E‘) zusammenhängend ist und b) die
Summe der Gewichte der Kanten in E‘ möglichst klein ist

 
Anmerkungen :

• es sei G = (V,E) ein ungerichteter, zusammenhängender Graph mit
Gewichten an den Kanten

 es sei G‘ = (V,E‘) ein zusammenhängender Teilgraph von G mit einer
möglichst kleinen Summe der Gewichte der Kanten in E‘

Dann gilt;;

1) G‘ ist zyklenfrei.
2) G‘ enthält genau |V| - 1 viele Kanten.

Warum ist diese Frage interessant?

die Knoten entsprechen Städte
die Kanten geben an, welche Städte mit Stromleitungen verbunden
werden können (/* aufgrund von geographischen Besonderheiten ist es
nicht möglich, zwischen allen Städten Stromleitungen zu legen */)
die Gewichte geben an, wie lang diese Stromleitungen sein müssten

>>>>  es geht darum, ein möglichst kurzes Stromleitungsnetz zu finden, dass
es erlaubt, alle Städte zu versorgen <<<<


= Graphenthoeretiker =
Leonhard Euler 
Edsger W. Dijkstra 
William Thomas Tutte

= 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

== Greedy-Algorithmen == 
:Wie dem Namen zu entnehmen, handelt es sich um gierige/gefrässig Algorithmen, d.h. die 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

== Aufbau von Greedy-Algorithmen - Blickwinkel Graphentheorie == 
Bestandteile eines Greedy-Algorithmus
:*(verbrauchende)Liste aller Knoten
:*(aufbauende)Liste der Ergebnisse
:*Funktion ergebnis? - ob sich eine Ergebnis für das Problem ergeben hat
:*zulässig? - #t wenn Knoten zulässig ist
:*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
:*Resultat - Ausgabefunktion des Algorithmus

== 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>

== Tiefen- und Breitensuche == 

== Algorithmus von Prim ==

== Algorithmus von Kruskal ==

= Anwendungsbeispiele =
Tool algorithmus-2
:Kurze Einweisung in das Scheme Programm Algorithmus-2.
:Ermöglich das Erstellen von Graphen und Bäumen bzw. errechnet anhand des gewählten Algorithmus den minimalen Spannbaum.
[[[Link-Text http://new-lv.de/algorithmus-2.rkt]]]

== Wüstenstadt Dehram ==
Die Wasserversorgung einer ganzen Region soll dahingehende optimiert werden, das jedes Dorf in der näheren Umgebung Zugang zu fließend Wasser erhält. Dabei sollen die Gesamtkosten für 400€ pro Meter möglichst gering ausfallen. Die angegebene Strecken zwischen den Dörfern wird in Kilometer gewichtet.

== Solar Holiday ==
Ein Flugunternehmen biete interstellar Reisen zu anderen Sonnen an. Mit weit über Lichtgeschwindigkeit werden 5 Lichtjahr an einem Tag zurückgelegt. Finden sie den kürzesten Weg zwischen allen Sonnen und berechnen sie die Reisedauer.