Informatik 11 3.1 Einfache Graphen

 Inhalt des Kurses    
0. Startseite   3.1 Einfache Graphen
1. Die rekursive Datenstruktur Liste     3.2 Repräsentation von Graphen
2. Die rekursive Datenstruktur Baum   3.3 Durchlaufen von Graphen
3. Die Datenstruktur Graph  
4. Softwareentwicklung  
5. Softwareprojekt  
   
   
     
Zurück zur Seite des Werner-von-Siemens-Gymnasiums Regensburg    
     
         

3. Die Datenstruktur Graph

3.1 Einfache Graphen

Ein Graph besteht aus Knoten (englische Bezeichnung: vertex) und Kanten (englische Bezeichnung edge ) und eignet sich zur Darstellung netzwerkartiger Stukturen:

graph_1

Abb.3.1.1

Viele Anwendungen lassen sich durch Graphen übersichtlich darstellen.

Beispiele:

 

Je nach Anwendung ergeben sich verschiedene Arten von Graphen:

Die obige Abbildung 3.1.1 zeigt einen ungerichteten Graph , da alle Kanten ungerichtet sind.

In einem gerichteten Graph sind alle Kanten gerichtet, d.h. nur in einer Richtung befahrbar.

graph_2

Abb. 3.1.2

Ungerichtete Kanten kann man als Menge der beiden benachbarten Knoten kennzeichnen:

In Abb.3.1.1 ist e1 = {v1,v2}, e2 = {v1, v4} usw.

Gerichtete Kanten kann man als geordnetes Paar schreiben:

In Abb 3.1.2 ist dann e1 = (v1,v2); e5 = (v5, v3); e8 = (v3, v5) usw.

 

 

Für die Nutzung eines Graphen ist es oft entscheidend, ob es einen Weg von einem bestimmten Knoten zu einem anderen gibt.

Einen solchen Weg bezeichnet man als Pfad.

Einen geschlossenen Pfad, d.h. Anfangs- und Endknoten sind indentisch, bezeichnet man als Zyklus (oder auch als Rundweg).

graph_3

Abb. 3.1.3

Pfad: {v6,v8}, {v8,v1}, {v1,v5}

Zyklus: {v1,v2}, {v2,v4}, {v4,v1}

 

Gibt es in einem ungerichteten Graphen von jedem Knoten einen Pfad zu allen anderen Knoten, so nennt man den Graph zusammenhängend. Abb.3.1.1 und 3.1.3 zeigen zusammenhängende Graphen

Gibt es einen Knoten, der nicht von allen anderen erreicht werden kann, heißt der Graph unzusammenhängend .

Beispiel:

graph_4

Abb. 3.1.4

Unzusammenhängende Graphen erkennt man schnell an isolierten Knoten oder "Inseln".

 

In gerichteten Graphen unterscheidet man zwischen stark- und schwach zusammenhängend:

Ein gerichteter Graph heißt stark zusammenhängend, wenn es von jedem Knoten einen Pfad zu allen anderen Knoten gibt.

Beispiel.:

graph_5

Abb. 3.1.5

Beispiel für einen nicht stark zusammenhängenden Graphen:

graph_6

Abb. 3.1.6 (von v2 erreicht man z.B. v4 nicht mehr)

Ignoriert man die Richtungen und fasst den gerichteten Graphen als ungerichteten auf und ist dieser zusammenhängend, so nennt man ihn schwach zusammenhängend .
Der Graph in Abb.3.1.6 ist schwach zusammenhängend.

 

Fügt man den Kanten ein weiteres Attribut hinzu (z.B. die Entfernung zweier Nachbarknoten), erhält man einen gewichteten Graphen:

graph_7

Auf diese Weise lässt sich z.B. der kürzeste Weg zwischen zwei Knoten berechnen.



Viele Aufgaben aus der Graphentheorie thematisieren die Durchlaufbarkeit:

http://de.wikipedia.org/wiki/Durchlaufbarkeit_von_Graphen

 


Übung

Eine berühmtes Problem im Zusammenhang mit Graphen ist das von Leonard Euler formulierte sog. Königsberger Brückenproblem.

Gibt es einen Weg durch Königsberg (heute: Kaliningrad), auf dem man jede der 7 Brücken genau einmal überquert?

(Das Lied "Über sieben Brücken musst du gehen" von der DDR-Kultband "Karat" bzw. die Coverversion von Peter Maffay hat mit dieser Aufgabe übrigens nichts zu tun)

Die Stadtteile A,B,C und D kann man als Knoten betrachten und die Brücken als Kanten. Es entsteht ein ungerichteter Graph mit Doppelkanten.

Aufgabe 7 auf Seite 101 im Buch behandelt dieses Problem.

Wesentlich genauer durchleuchtet wird es auf der Seite MathePrisma der Universität Wuppertal

Arbeite auf dieser Seite auch im Modul "Wege auf Graphen" die Seiten 1 bis 4 durch.


Hefteintrag