Python 3 - Lernen und professionell anwenden

751

27.3

Graphen

Bildschirmausgabe:

Noch ein Hinweis: Kapitel 32 geht auf die Implementierung von Consumer-Producer-Pro-

zessen mit dem Modul

multiprocessing ein.

27.3 Graphen

Mit Graphen hatten wir uns schon in Kapitel 7 im Zusammenhang mit Mengen beschäftigt.

Ein gerichteter Graph ist ein Modell zur Beschreibung von Objekten, die zueinander in

einer Beziehung stehen. Die Objekte werden durch Knoten und die Beziehungen zwischen

ihnen durch Kanten repräsentiert. Zeichnerisch stellt man die Knoten meist als Kreise oder

Kästen und die Kanten als Pfeile dar.

Mathematisch definiert man einen Graphen

G als Tupel, das aus einer Menge von Knoten V

(vertice: engl. für Knoten) und einer Menge von Kanten E (edge: engl. für Kante) besteht:

Jede Kante in der Menge

E wird durch ein Paar (v

i

, v

j

) dargestellt. Dabei sind v

i

, v

j

Knoten-

namen aus der Menge

V.

Abbildung 27.2 zeigt ein Beispiel.

Abb. 27.2: Beispiel eines gerichteten Graphen

#queue_test.py

from queue_ import Queue

q = Queue()

for i in range(5):

q.enqueue(i)

while not q.empty():

item = q.dequeue()

print(item, end=" ")

0 1 2 3 4

G = (V,E)

G=(V, G)

a

c

b

d

e

V={a, b, c, d, e}

E={(a, a), (b, a), (b, d), (d, c), (c, b)}

Kapitel 27

Modellieren mit Kellern, Schlangen und Graphen

752

Knoten e ist mit keiner Kante verbunden, er ist isoliert. Graphen ohne isolierte Knoten hei-

ßen zusammenhängend. Eine Kante kann auch einen Knoten mit sich selbst verbinden, wie

bei Knoten

a. Ein Weg oder Pfad von Knoten v

1

zu Knoten v

2

in einem Graphen ist eine Folge

von Knoten, die über Kanten so miteinander verbunden sind, dass

v

2

von v

1

aus über die

Knoten erreichbar ist. So gibt es im Beispiel von Knoten

b zu Knoten c einen Weg, nämlich

[b, d, c] mit den Kanten (b, d), (d, c). Manche Graphen enthalten Zyklen, das heißt, es

gibt einen Knoten

v, von dem aus ein Weg durch den Graphen wieder zu v führt. Oder

anders ausgedrückt: Es gibt eine Folge von Kanten mit

(v, v

i1

), (v

i1

, v

i2

), ... ,(v

in

, v). Im

Beispielgraphen gibt es den Zyklus

(b, d), (d, c), (c, b).

Graphen sind ein außerordentlich vielseitiges Hilfsmittel zur Modellierung. Abbildung 27.3

zeigt einige Beispiele:

쐽 Die Bedeutung von Begriffen kann als Hierarchie von Ober- und Unterbegriffen darge-

stellt werden. Die Kante

(a, b) ist zu lesen als »a ist Oberbegriff von b«.

쐽 In einem Stammbaum werden Verwandtschaftsbeziehungen modelliert. Die Kante (a,

b)

stellt die Beziehung »a ist Kind von b« dar.

쐽 Viele Beispiele für Graphen kommen aus dem Bereich der Verkehrsnetze. So können

Flugverbindungen durch gerichtete Graphen dargestellt werden. Hier bedeutet die

Kante

(a, b) »Es gibt eine direkte Flugverbindung von Flughafen a zu Flughafen b«.

Abb. 27.3: Beispiele für gerichtete Graphen

Lebewesen

Tier

Pflanze

Löwe

Eichhörnchen

Sonnenblume

Tan ne

ist Oberbegriff von ...

Annika

WalterStefanie

ist Kind von ...

direkte Flugverbindung

London

Düsseldorf

Frankfurt

753

27.3

Graphen

Beim dritten Beispiel gibt es zwischen Knoten, die miteinander verbunden sind, Pfeile in

beide Richtungen. Solche Graphen nennt man ungerichtet. Die Kanten werden dann verein-

fachend durch Linien (ohne Pfeilspitzen) dargestellt. Ungerichtete Graphen spielen bei der

Modellierung von Wegenetzen eine besondere Rolle, weil Wege meistens in beide Richtun-

gen passierbar sind.

Abb. 27.4: Ungerichteter Graph

Darstellung eines Graphen mit Adjazenzlisten

Mit Graphen lassen sich Wegenetze beschreiben, wie z.B. die Wege, die man durch die

Räumlichkeiten eines Hauses zurücklegen kann. Als Beispiel nehmen wir ein fiktives Insti-

tut für Verkehrstechnik, das sich z.B. in einem Gebäude einer Universität befinden kann.

Am Eingang steht ein Computer, der in der Lage sein soll, einem Fremden bei der Suche

nach einer Person oder einem Objekt im Institut zu helfen. Unser Ziel ist, einen »digitalen

Wegweiser« zu programmieren, der den (kürzesten) Weg zu einem gewünschten Punkt

(z.B. der Kaffeemaschine oder dem Institutsleiter) berechnet und ausgibt.

Abb. 27.5: Raumplan des Instituts für Verkehrstechnik

Der erste Schritt der Programmentwicklung ist die Modellierung durch einen Graphen.

Jeder Raum (dazu zählen auch die Flure) wird durch einen Knoten repräsentiert. Übergänge

zwischen Räumen – das sind fast immer Türen – sind die Kanten des Graphen. Abbildung

27.6 zeigt einen passenden ungerichteten Graphen. Das ist hier sinnvoll, weil man alle

Übergänge in beide Richtungen durchschreiten kann. Beachten Sie aber, dass es in realen

Gebäuden auch gerichtete Übergänge zwischen Räumen gibt. Man denke an Rolltreppen

oder Türen, die sich (ohne Schlüssel) nur an einer Seite öffnen lassen (wie z.B. Haustüren).

a

b

a

b

=

F21 Hauptflur

F22

F23

Institut für Verkehrstechnik

R21

Jessi Timms

R22

R23 D

R24

Dr. Froh

R25

Computer-

Labor

Medienraum

R26

Prof. Zeck

R27

Sekretariat

Elena Klar

R28

Seminar-

raum

R29

Bibliothek

R30

Sven Kurz

R31 H

Digitaler Wegweiser