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 KantenEIn 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:
Solche Aufgaben sind mithilfe des naiven Algorithmus (in Fall 1 und 3) und des Approximationsalgorithmus (Fall 2) zu loesen.
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).
- dient zur Berechnung des kuerzesten Pfades zwischen einem Startknoten und einem beliebigen Knoten kantengewichtigen Graphen (keine negativen Gewichte!).
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.
How to represent/programm a graph on a computer
e.g.: vertex class
EITHER:
Advantages:
Disadvantages:
OR:
(AB), (AD), (AE), (BD), (BE),...
Advantages:
Another good solution: Adjecency matrix
- either for each city
- or a total number of roads
Question: Is the graph connected? Bonus: read and write to diskZusammenstellen der o.g. Informationen. Zusammenstellen von Bildern.
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.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:
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.
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