AuK/Graphrepräsentationen SS12

Wiki-Quelltext dieser Seite.

<language>Java</language>
=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==
[[Bild:Nico_Brueckenproblem.png|thumb|300px|right|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ö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==
[[Bild:Graph_Erklaerung.png|thumb|200px|right|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.<br>

===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.



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

ungerichtete
gerichtete
gewichtete
Netzwerk

== Darstellung ==


----
== Aufgaben ==
1. Mit welche Darstellung kann man schnell bestimmen, ob ein Knoten isoliert ist?
<popup name="Lösung 1">

</popup>

2.

<code id="4f990ab49df57" hidden>
import java.util.*;
import java.text.*;
   
   void getTime(){
      SimpleDateFormat formatter = new SimpleDateFormat ("yyyy.MM.dd 'at' HH:mm:ss ");
      Date currentTime = new Date();
      System.out.println("Zeit und Datum : " + formatter.format(currentTime));
   }

</code><run id="4f990ab49dfcb">getTime();</run>

<popup name="test">
dszlkshflkashflkaf
</popup>

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

== Anwendungsgebiete ==
[[Bild:U-Bahn_Wien.png|thumb|400px|rechts|Netz der Wiener U-Bahn - ein praktisches Beispiel für Graphen]]