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

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
>>> image
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
>>> image
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
>>> image
2 Baum
:Ein Baum ist ein Spezialform von Graph, der keine Kreise besitz. Unter anderen kann er dahingehendbenutzt 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 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

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  ==
Scheme Programm Algorithmus-4
<code id="56311758c6bff" hidden>
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)))))
</code>