Die kuerzesten Wege in Graphen

1. Was ist ein Graph?

Ein Graph ist eine Menge von Punkten (sog. Knoten oder Ecken), die durch Linien (sog. Kanten bzw. Boegen) miteinander verbunden sind. Die Form der Punkte und Linien spielt in der Graphentheorie keine Rolle.

Man unterscheidet dabei zwischen:

Komplexere Graphentypen sind:

Bei einem gerichteten Graphen G=(V,E) hat jede Kante (u,v) eine Richtung.

V= Menge von Knoten; E= Menge von Kanten

EIn ungerichteter Graph G= (V,E) heisst zusammenhaengend, falls es zu je 2 beliebigen Knoten v und w aus V einen ungerichteten Weg in G gibt, mit v als Startknoten und w als Endknoten. Falls G nicht zusammenhaengend ist, nennt man G unzusammenhaengend.

Zur Realisierung des Algorithmus muessen die folgenden Daten gespeichert werden:

  1. Distanz jedes Knoten zum Ausgangsknoten
  2. ein Vorgaengerknoten, um einen kuerzesten Weg nachvollziehen zu koennen
  3. die Farbe jedes Knoten, also rot oder gruen. Weiss ergibt sich durch "fehlende Farbe"

2. Anwendungen

Solche Aufgaben sind mithilfe des naiven Algorithmus (in Fall 1 und 3) und des Approximationsalgorithmus (Fall 2) zu loesen.

Der Eulersche Satz

Es gibt genau dann einen Rundweg, wenn G zsh und alle Eckengrade gerade sind.

Euler hat folgende Gesetzmaessigkeit entdeckt: Wenn in einem Graphen G ein Eulerweg existiert, dann haben maximal 2 Knoten ungeraden Grad (also haben nicht mehr als 2 Knoten eine ungerade Anzahl angeschlossener Kanten).

Der Algorithmus von Dijkstra

- dient zur Berechnung des kuerzesten Pfades zwischen einem Startknoten und einem beliebigen Knoten kantengewichtigen Graphen (keine negativen Gewichte!).

Das Hamiltonkreisproblem

Frage: Gibt es im folgenden Graph einen so genannten Hamiltonkreis?

Ein Hamiltonkreis ist dabei ein Kreis, der alle Knoten des Graphen enthaelt.

Der folgende "Traveller's Dodecahedron" ist ein regulaeren Dodekaeder, wobei die 20 Knoten mit Namen bekannter Staedte assoziiert sind. Ziel ist es, eine Reiseroute entlang der Kanten des Dodekaeders zu finden, die jede Stadt genau einmal besucht und dort aufhoert, wo sie beginnt.

Der Graph ist dann hamiltonsch, wenn er einen Hamiltonkreis zulaesst, also wenn es einen Kreis G gibt, der alle Knoten aus V enthaelt.

Hamiltonpfad = Pfad in G, der alle Knoten aus V enthaelt.

  • Jeder Graph G mit mind. Minimalgrad n/2 hat einen Hamiltonkreis.
  • Jeder 4-zusammenhaengende planareGraph hat einen Hamiltonkreis (Planare Graphen sind Graphen, die sich so in die Ebene zeichnen lassen, dass sich keine ihrer Kanten schneiden).
  • Ist die Summe des Grades zweier nicht-adjazenter (nicht-verbundener/nicht-benachbarter) Knoten mindestens n, so ist G hamiltonsch.
  • Ist die Summe der Grade zweier nicht-adjazenter Knoten x,y mindestens n, so gilt: G+{x,y\} hamiltonsch --> G ist hamiltonsch.
  • Mein Tagebuch des IWR-BOGY-Praktikums

    Tag 1

    Ausarbeitung des Themas " Kuerzeste Wege in Graphen" per Internetrecherche

    Besprechen des Themas im Konferenzsaal mit Hrn Dr. Winkler und 2 anderen Praktikanten (in Englisch^^)

    How to represent/programm a graph on a computer

    e.g.: vertex class

  • derive vertex objects
  • single/double connected list
  • EITHER:

  • Edges: 2D-Array
  • Advantages:

    Disadvantages:

    OR:

  • List
  • (AB), (AD), (AE), (BD), (BE),...

    Advantages:

    Data structures:
  • simple (scalare) variables INT. A,B,C,...
  • array variables INT. v[10) - v[0]= / v[9]=...
  • list--> includes list items with special information inside (e.g. x-coordinate, y-coordinate, name, ID-Number) and directed pointers on them.-->The first and the last list item points on NULL.
  • Another good solution: Adjecency matrix

    A first program

    1. start with 100 cities
    2. take arrays for vertecies and edges
    3. generate random roads (Edges)

    - either for each city

    - or a total number of roads

    Question: Is the graph connected? Bonus: read and write to disk

    Tag 2

    Erstellen dieser Webseite

    Zusammenstellen der o.g. Informationen. Zusammenstellen von Bildern.

    Tag 3

    Voraussichtlich geplanter Besuch meiner Franzoesischlehrerin Fr. Budia-Alvarez am IWR

    -fiel aus.

    An diesem Tag habe ich mich genauer mit dem Algorithmus von Dijkstra beschaeftigt und habe dazu ein paar Uebungen aus dem Buch "Diskrete Mathematik fuer Informatiker" gemacht. Danach haben wir uns in der Bibliothek zusammengesetzt und uns ├╝ber die Graphentheorie unterhalten. Dabei haben wir auch den Verlauf des heutigen und des naechsten Tages besprochen.

    Tag 4

    Zusammenfassung zum Thema "Graphen"

    Ein gerichteter Graph oder Digraph ist ein Paar (V,E), wobei V eine endliche Menge von Knoten und E eine Relation auf V ist. Die Elemente von E heissen Pfeil.

    Wenn uv ein Pfeil ist, so heisst u ein Vorgaenger von v.

    Ein Weg der Laenge k in einem Digraphen ist eine Folge verschiedener Knoten v0, v1,..., vk, derart, dass vi-1vi fuer i=1,...,k ein Pfeil ist.

    Ein Zyklus in einem Digraphen G ist eine Folge von Knoten v0, v1,..., vk, derart, dass vi-1vi fuer i=1,...,k ein Pfeil ist, der erste Knoten gleich dem letzten ist und keine anderen Knoten wiederholt durchlaufen kann.

    Ein Digraph heisst azyklisch, wenn er keine Zyklen enthaelt. Bei Problemen der Aufgabenplanung heisst der entsprechende azyklische Digraph ein PERT-Chart.

    Eine konsistente Anordnung der Knoten eines Digraphen ist eine Bezeichnung der Knoten mit 1,2,3,...,n, derart, dass fuer jeden Pfeil uv, bei dem u mit i und v mit j bezeichnet ist, i= kleiner j gilt.

    Zu einem Digraphen existiert genau dann eine kosistente Anordnung, wenn er azyklisch ist. Der topologische Sortieralgorithmus erzeugt eine konsistente Anordnung zu einem azyklischen Digraphen.

    Sei G = (V,E) ein Digraph mit n Knoten und der Adjazenzmatrix M. Das logische Boolesche Produkt M hoch k enthaelt die Information zur Existenz von Wegen der Laenge k zwischen beliebigen 2 Knoten in G. Die Matrix M* = M oder M hoch 2 oder ... oder M hoch n heisst Erreichbarkeitsmatrix des Digraphen. Sie enthaelt die Information zur Existenz von Wegen zwischen Knoten.

    Der Algorithmus von Warschall laesst sich zur Bestimmung der Erreichbarkeitsmatrix eines Digraphen verwenden. Der Algorithmus erzeugt eine Folge von Matrizen W0, W1, W3,...,Wn mit W0 = M und Wn = M*. Fuer k groesser gleich 1 wird Wk folgendermassen aus Wk-1 hergeleitet:

    1. Spalte k von Wk-1 betrachten.
    2. Fuer jede Zeile mit dem Eintrag F in dieser Spalte diese Zeile in Wk kopieren.
    3. Fuer jede Zeile mit dem Eintrag F in dieser Spalte logisches oder auf diese Zeile und Zeile k anwenden und die sich ergebende Zeile in Wk eintragen.

    Ein kuerzester Weg zwischen 2 beliebigen Knoten in einem gewichteten Digraphen ist ein Weg geringsten Gesamtgewichts. Das Gesamtgewicht eines kuerzesten Wegs zwischen Knoten u und v heisst Entfernung von u nach v. Falls kein Weg von u nach v existiert, so ist die Enfernung 8 (unendlich).

    Der Algorithmus von Dijkstra bestimmt in einem gewichteten Digraphen einen kuerzesten Weg von einem vorgegebenen Knoten zu einem beliebigen anderen Knoten.

    Tagesverlauf

    9.30 - 12.00 Loesen von Aufgaben bezueglich des Algorithmus von Dijkstra .

    12.00 - 13.00 Rundfuehrung durch ein paar Raeume des IWR. Dabei hat Hr. Dr. Winkler einen Raum gezeigt, in dem man im Computer gespeicherten 3-D-Objekte mithilfe eines grossen Bildschirms naturgetreu darstellen kann.

    Ausserdem untersuchte Julia am Computer das Verhalten der Wassermolekuele bei unterschiedlicher Stroemung auf der Haifischhaut. Ein kleiner Ausschnitt der Haifischhaut wurde am Computer als 3-D-Objekt rekonstruiert und deren Rillen mit Wassermolekuelen befuellt. Danach wurde am Computer kuenstliche Stroemung erzeugt und das Verhalten der Wassermolekuele beobachtet. Als Film wurde dann der ganze Verlauf aufgezeichnet.

    Zur Darstellung der 3-D-Computerobjekte am grossen Bildschirm: In einer Box wird ein Magnet, der ein elektrisches Feld erzeugt, staendig umgepolt. Dabei sendet die Box elektrische Signale an eine spezielle mit ihr verbundene Brille. Die Brille wird aufgesetzt und verdunkelt mithilfe dieser Information abwechselnd ein Auge mit einer sehr hohen Frequenz (ca. 60 Hz), sodass wir kein Flimmern wahrnehmen. Die auf dem grossen Bildschirm dargestellten Objekte (Information wird vom Computer gesendet), sehen wir jetzt direkt vor uns und koennen mithilfe einer speziellen an der Box angeschlossenen Maus das Objekt in alle Richtungen bewegen.

    Sollte man sich buecken oder nach links bzw. nach rechts bewegen, wird an die Brille durch elektrische Signale von der Box die Information ihrer Lage gesendet. Somit bewegt sich auch das Objekt entsprechend mit, wie in der Realitaet.

    Man sollte dabei beachten, dass sich das Objekt, waehrend man es anschaut, immer im Rahmen des Bildschirmes bewegt; sobald dies nicht der Fall ist, verschwindet das Objekt.

    file:///export/home/bogy/Nastja/Webseite/WEBSITE.html