Rückblick

Sortierte Folgen

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

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önne, 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

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

Im Themenkomplex Graphrepräsentationen sollen Methoden zu 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.
Ein Graph G stellt ein Paar G = (V,E) bestehend aus einer endlichen Menge V und einer Menge E von zweielementigen Teilmengen V dar.
Die endliche Menge V repräsentiert Eckenmenge E, bestehend aus Ecken / Knoten (engl. vertex). Ecken sind einfache Objekte mit einem Namen oder einer Eigenschaft.
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.

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

Graphentypen

ungerichtete gerichtete gewichtete Netzwerk

Darstellung

Aufgaben

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

2.

Unsortierte Kanten Abfolge

Adjazenzfelder - Statische Graphen

Adjazenzliste - Dynamische Graphen

Adjazenz Matrix

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

Implizite Repräsentation

Historisches