Wunschseite

Aus ProgrammingWiki

Archivierte Version vom 2015-10-28T23:09:12+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Graphentheorie - minimaler Spannbaum
2 Begrifferläuterung
3 Graphenthoeretiker
4 Algorithmen
5 Beispiele =

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

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

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

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

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.

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

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, sind das gierige/gefrässig Algorithmen, d.h. Strategie die sich hinterdiesem 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

(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)))])))))

Tiefen- und Breitensuche

Algorithmus von Prim

Algorithmus von Kruskal

Beispiele =

Tool algorithmus-4 Kurze Einweisung in das Scheme Programm Algorithmus-4. Ermöglich das Erstellen von Graphen und Bäumen und errechnet anhand des gewählten Algorithmus den minimalen Spannbaum.

lang racket
(define-syntax-rule(s: var value)(define-syntax-rule var value))
(s:(s:p p)(require p))(s:p racket/gui)(s:p db)
;variable 
(define-syntax-rule(s:d n v)(define n v))(s:d frame-height 500)(s:d frame-width 500)(s:d m-index 0)(s:d index1 1)(s:d index2 1)(s:d kantenMod 0)(s:d tempV 0)(s:d bool1 #f)
;database
(define db1(sqlite3-connect #:database 'temporary #:mode 'create))
(s:(s:q n v)(query-exec db1 (string-append"create table "n" "v)))(s:q "knoten" "(id integer primary key,name varchar(50),xPos integer,yPos integer)")(s:q "kanten" "(id integer primary key,name varchar(50),knoten1 integer,knoten2 integer)")
(s:(s:in1 id n v1 v2)(query-exec db1 "insert into knoten values($1,$2,$3,$4)"id n v1 v2))
(s:(s:in2 id n id1 id2)(query-exec db1 "insert into kanten values($1,$2,$3,$4)"id n id1 id2))
(s:(s:get id v1 v2)(letrec([str (string-append "select " v1 " from "v2" where id ="(format"~a"id))][str-append(lambda(x y)(string-append "select id from "v2" where xPos = "(number->string x)" and yPos = "(number->string y)))])(query-value db1 str)))
;get id with X and Y
(define get-ID(lambda(x y id)(cond[(and(> x(-(s:get id "xPos" "knoten")30))(< x(+(s:get id "xPos" "knoten")30)))(if(and(> y(-(s:get id "yPos" "knoten")30))(< y(+(s:get id "yPos" "knoten")30)))id(get-ID x y(+ id 1)))][(< id index1)(get-ID x y(+ id 1))][else #f])))
;frontend
(define frame1(new frame% [label "minimaler Spannbaum"][width frame-width][height frame-height]))(send frame1 show #t)
(define tab-panel(new tab-panel%[choices(list "übersicht" "drag/drop" "simulation")][callback(lambda(t e)(set! m-index(send tab-panel get-selection) ))][parent frame1]))
(define text-F(new text-field%[label "name: "][init-value "z1"][parent frame1]))
(define radio-B(new radio-box%[label "wähle"][choices (list "knoten" "kanten")][parent frame1]))
(define canvas(class canvas%(define/override (on-event e)(if(=(send radio-B get-selection)0)
  (when(and(equal?(send e get-event-type)'left-down)(> (send e get-y) 25))(begin(s:in1 index1 (send text-F get-value)(send e get-x) (send e get-y))(set! index1(+ index1 1))(set! bool1 #t)(send text-F set-value (format"z~a"index1))))
  (begin(when(and(equal?(send e get-event-type)'left-down)(> (send e get-y) 25)(= kantenMod 0))(begin(set! kantenMod 1)(set! tempV (get-ID(send e get-x)(send e get-y)1))))
    (when(and(equal?(send e get-event-type)'motion)(= kantenMod 1))(set! kantenMod 2))          
    (when(and(equal?(send e get-event-type)'left-up)(= kantenMod 2))(begin(set! kantenMod 0)(s:in2 index2 (send text-F get-value) tempV (get-ID(send e get-x)(send e get-y)1))(set! index2 (+ index2 1))))))) 
    (super-new)))(define c(new canvas[label "graph"][min-height 500][parent frame1]))(define dc(send c get-dc))                
;drawfunktion
(define Draw1(lambda(ls1 ls2)
    (for([i ls2])(when(and(equal? bool1 #t)(< i(length ls2)))(if(< i 2)
            (letrec([v1 (query-row db1 "select knoten1,knoten2 from kanten where id = $1"i)][h1(lambda(x)(s:get x "xPos" "knoten"))][h2(lambda(x)(s:get x "yPos" "knoten"))])   
              (send dc set-brush (make-color 240 240 240)'solid) 
              (send dc draw-line (h1(vector-ref v1 0))(h2(vector-ref v1 0))(h1(vector-ref v1 1))(h2(vector-ref v1 1)))
              (send dc draw-rectangle (/(+(h1(vector-ref v1 0))(h1(vector-ref v1 1)))2) (-(/(+(h2(vector-ref v1 0))(h2(vector-ref v1 1)))2)5) 25 20) 
              (send dc draw-text(s:get i "name" "kanten")(+(/(+(h1(vector-ref v1 0))(h1(vector-ref v1 1)))2)5) (-(/(+(h2(vector-ref v1 0))(h2(vector-ref v1 1)))2)5)))
            (letrec([v1 (query-rows db1 "select knoten1,knoten2 from kanten where id = $1"i)])(draw-Rows v1 i)))))    
   (for([i ls1])(when(and(equal? bool1  #t)(< i(length ls1)))
        (send dc set-brush(if(< i 23)(make-color (- 240(* i 10)) 240 240) (if(< i 46)(make-color 230(- 480(* i 10)) 240) (make-color 230 230(- 700(* i 10))))) 'solid) 
        (send dc draw-ellipse (-(s:get i "xPos" "knoten")19)(-(s:get i "yPos" "knoten")16)40 40 )
        (send dc draw-text(s:get i "name" "knoten")(-(s:get i "xPos" "knoten")(* 2.2(string-length(s:get i "name" "knoten"))))(-(s:get i "yPos" "knoten")5))))))
(define draw-Rows(lambda(ls i)(cond[(empty? ls)void]
         [else(letrec([v1 (car ls)][h1(lambda(x)(s:get x "xPos" "knoten"))][h2(lambda(x)(s:get x "yPos" "knoten"))])
              (send dc draw-line(h1(vector-ref v1 0))(h2(vector-ref v1 0))(h1(vector-ref v1 1))(h2(vector-ref v1 1)))
              (send dc draw-rectangle(/(+(h1(vector-ref v1 0))(h1(vector-ref v1 1)))2)(-(/(+(h2(vector-ref v1 0))(h2(vector-ref v1 1)))2)5) 25 20) 
              (send dc draw-text(s:get i "name" "kanten")(+(/(+(h1(vector-ref v1 0))(h1(vector-ref v1 1)))2)5) (-(/(+(h2(vector-ref v1 0))(h2(vector-ref v1 1)))2)5))(draw-Rows(cdr ls)i))])))
;algorithmen
(define algorithmus(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))(algorithmus(cdr ls)))
;thread
(thread (lambda()(letrec([integer->list(lambda(x)(cond[(= x 1)'(1)][else(append(integer->list(- x 1))(list x))]))])(letrec([loop(lambda()(Draw1(integer->list index1)(integer->list index2))(Algorithmus(query-rows db1 "select Name from kanten order by id")(sleep 1.0)(loop))])(loop)))))

Wüstenstadt Dehram Die Wasserversorgung einer ganzen Region soll optimiert werden, so das jedes Dorf in der näheren Umgebung Zugang zu fließend Wasser erhält und trotzdem sollen die Gesamtkosten für 400€ pro Meter möglich gering ausfallen.

Lieferdienst Kassel Für einen kleinen Lieferservices soll ein Routenplan für die Stadt Kassel entworfen werden. Der Kostenfaktor Benzin soll dabei möglichst gering gehalten werden, indem jeweils die kürzeste Strecke zum Kunden errechnet werden soll.