Rückblick

Sortierte Folgen Bäume

Graphentheorie

Als ein Teilgebiet der Mathematik untersucht die Graphentheorie Beziehungen und Eigenschaften von Graphen. Die Graphentheorie spielt sowohl in der Mathematik als auch in der Informatik eine wichtige Rolle. Oft können algorithmische Probleme durch Graphenrepräsentation gelöst und umgekehrt Graphenproblematiken mit Hilfe von Algorithmen überwunden werden. Deshalb bilden Graphen einen essentiellen Teil der Komplexitätstheorie in der Informatik.

Königsberger Brückenproblem

Königsberger Brückenproblem in Form eines Graphen

Beim Königsberger Brückenproblem handelt es sich um eine mathematische Fragestellung aus dem 18. Jahrhundert. Königsberg wurde am Fluss Pregel erbaut, welcher sich im Stadtgebiet teilt. Über die beiden Flussarme wurden mehrere Brücken gebaut, um schnell von einem Stadtteil zum anderen zu gelangen. Im Jahr 1736 gab es sieben Brücken. Die Einwohner Königsbergs stellten sich die Frage, ob es möglich ist, alle sieben Brücken nur genau einmal zu überqueren. Wenn dies möglich ist, kann man auch einen Rundweg gestalten, bei dem man am Ende wieder am Ausgangspunkt ankommt?

Diesen Fragen nahm sich Leonhard Euler, ein bis heute bedeutender Mathematiker an. 1736 veröffentlichte er seine Arbeit "Solutio problematis ad geometriam situs pertinentis", in der er sich mit dem Königsberger Brückenproblem befasste. Er versuchte sich bei der Untersuchung des Problems nur auf die relevanten Informationen zu beschränken. So stellte er fest, dass es vier Stadtteile gab, die durch sieben Brücken verbunden sind. Er lässt jeden Stadtteil von einen Punkt repräsentiert und jede Brücke stellt eine Linie, also eine Verbindung zwischen zwei Stadtteilen dar. Nach dem Zusammenfügen aller dieser Informationen erhält man die Grafik auf der rechten Seite.

Durch dieses grafische Hilfsmittel ist leicht zu erkennen, dass das Königsberger Brückenproblem nicht lösbar ist. Beim Passieren eines Punktes (Stadtteil) müssen zwei Linien (Brücken) durchlaufen werden (hinein und hinaus). Egal wie in welcher Reihenfolge man versucht die Brücken zu überqueren, ist es unmöglich jede Brücke nur einmal zu benutzen. Somit ist auch ein Rundgang, bei dem Anfangs- und Endpunkt übereinstimmen unmöglich. Um beide Fragen positiv beantworten zu können, müsste von jedem Punkt eine gerade Anzahl von Linien ausgehen, d.h. ein Stadtteil muss mit einer geraden Anzahl von Brücken erreichbar sein. Die Zahlen geben die Anzahl an Linien (Brücken) an, die zum / vom Punkt (Stadtteil) führen.

Leonhard Eulers Arbeit zum Königsberger Brückenproblem gilt als eine der ersten Arbeiten auf dem Gebiet der Graphentheorie.

Grundlegende Begriffe

Teile eines Graphen

Um einen leichten Einstieg in die Theorie der Graphen zu ermöglichen, ist es von Nöten, grundlegende Begriffe dieses Themas zu erläutern.

Graphrepräsentation

Im Themenkomplex Graphrepräsentationen sollen Methoden zur Darstellung von Graphen behandelt werden. Dabei wird besonders auf die Struktur von Graphen Wert gelegt, da diese für das sich anschließende Thema, dem Durchsuchen von Graphen, bedeutsam ist.

Graph

Ein Graph G stellt ein Paar G = (V,E) bestehend aus einer endlichen Menge V und einer Menge E von zweielementigen Teilmengen V dar.

Ecke

Die endliche Menge V repräsentiert die Eckenmenge E, bestehend aus Ecken / Knoten (engl. vertex). Ecken sind einfache Objekte mit einem Namen oder einer Eigenschaft.

Kante

Bei der Menge E handelt es sich um die Kantenmenge mit den Teilelementen Kanten (engl. edge), die Verbindungen zwischen je zwei Ecken darstellen. Sie treten stets paarweise auf, da sie die beiden Ecken, die sie verbinden enthalten. Kanten müssen nicht zwingend Verbindungen zweier Ecken sein, sie können genauso eine Ecke mit sich selbst verbinden.

Schlinge

Eine Schlinge ist eine Kante der Form [a,a], wobei die Ecke durch die Kante mit sich selbst verbunden ist. Solche Kantenformen treten häufig bei der Repräsentation von Automaten (DEA, NEA) durch Graphen auf.

Zyklus

Zyklus Besitzt ein Graph keine Zyklen so spricht man von einem Baum. Mehrere zusammenhängende Bäume werden als Wald bezeichnet. Graphen sind unabhängig von ihrer Darstellung definiert.

dicht licht

Spannbaum

Spannbaum

Graphentypen

Ungerichteter Graph

Ein ungerichteter Graph ist ein einfacher Graph ohne Mehrfachkanten, dessen Kanten durch Linien repräsentiert werden. Man kann eine Kante sowohl von der Ecke a nach Ecke b überqueren, als auch umgekehrt. Ein solcher Graph stellt den einfachsten Graphentyp dar.

Gerichteter Graph

Im Gegensatz zum ungerichteten Graph ist es bei gerichteten Graphen nicht möglich Kanten nach Belieben zu nutzen. Es wird stattdessen stets eine Richtung unter Verwendung einens Pfeils vorgegeben. Der Pfeil zeigt von Ecke a nach Ecke b und gibt somit eine Art Einbahnstraße vor.

Multigraph

Als Mutltigraph werden komplexere Graphen bezeichnet, die in jede Richtung nicht nur eine Kante zwischen Ecken zulassen, sondern mehrere. Solche Kanten bezeichnet man als Mehrfachkanten. Ein Beispiel für einen Multigraph ist die Visualisierung des Königsberger Brückenproblems.

Unvollständiger Graph

Unvollständige Graphen enthalten nicht alle maximal möglichen Kanten, d.h. nicht jede Ecke ist mit jeder anderen Ecke durch eine Kante verbunden.

Vollständiger Graph

Drei vollständige Graphen A, B, C

Man bezeichnet einen Graph als vollständig, wenn alle Ecken miteinander durch eine Kante verbunden sind. Man spricht auch von einem Simplex.

Ungewichteter Graph

Gewichteter Graph

Ein Graph kann als gewichtet bezeichnet werden, wenn seine Kanten Zusatzinformationen enthalten. So wird beispielsweise einer Kante eine Zahl zugeordnet, die Entfernungen oder Kosten repräsentiert. Sowohl gerichtete als auch ungerichtete Graphen können gewichtet sein.

Netzwerke

Erfüllt ein Graph die Eigenschafte eines gewichteten und gerichteten Graphens, so kann er als Netzwerk bezeichnet werden.

Darstellung

Aufgaben

1. Mit welcher Darstellung kann man schnell bestimmen, ob ein Knoten isoliert ist?

2.

Unsortierte Kanten Abfolge

Adjazenzfelder - Statische Graphen

Adjazenzliste - Dynamische Graphen

Adjazenzmatrix

Es sei ein Graph G =(V,E) mit von 1 bis |V| durchnummerierter Knoten gegeben. Die Dazugehörige Ajazenzmatrix besteht aus |V|x|V|-Matrix A =(a_ij) mit den Elementen a_ij falls0

== Inzidenzmatrix

Implizite Repräsentation

Anwendungsgebiete

Verkehrsnetze

Netz der Wiener U-Bahn - ein praktisches Beispiel für Graphen

Chemische Isomerie

Strukturen in der organischen Chemie

Elektrische Netzwerke

Umfüllaufgabe