Einführung in Graphen oder „Über 7 Brücken musst du gehen!“

Landscape, Graphen in Python

Für Ihren Weg zur Arbeit müssen Sie den Fluss überqueren und wenn Sie nicht schwimmen wollen, fährt der Weg über eine Brücke. Genaugenommen müssen Sie auf Ihrem Weg zur Arbeit mindestens eine Brücke überqueren. Wieviele Wege können Sie für Ihren Arbeitsweg wählen? Welches ist der kürzeste Weg? Können Sie alle vier Brücken überqueren, ohne eine doppelt zu laufen?

Willkommen in der Graphentheorie! Genau mit solchen Fragen und ähnlichen beschäftigt sich nämlich die Graphentheorie und hinter obigen Bild versteckt sich ein Graph, oder anders formuliert: Wir können obiges Bild in einen Graphen wandeln, indem wir von den unwichtigen Informationen wie beispielsweise Bäumen abstrahieren.

Landscape graph, Graphen in Python

Bild 2 Landscape graph

Graphentheorie mit Python

Ein Graph besteht aus Knoten und Kanten. In dem obigen Diagramm haben wir zehn Knoten. Der Knoten mit der Nummer 1 entspricht dabei dem Haus in unserem ursprünglichen Bild und der Knoten mit der Nummer 10 entspricht dem Bürogebäude. Die Verbindungslinien zwischen den Knoten sind die Kanten. So entspricht beispielsweise die Kante vom Knoten 2 zum Knoten 6 dem Weg mit der ersten Brücke. In unserem Beispielgraphen ist jeder Knoten mit mindestens einem anderen Knoten verbunden. Allgemein kann es in Graphen aber auch Knoten geben, die nicht mit anderen Knoten verbunden. Man spricht dann von isolierten Knoten.

In unserem Beispiel sind die Kanten zwischen den Knoten ungerichtet. Sie können aber auch mit einer Richtung versehen sein. Man könnte sich dies beispielsweise wie eine Einbahnstraße in einem Straßennetzwerk vorstellen.

Auch wenn Graphen von Ihrer Definition her recht abstrakt scheinen mögen, so können sie recht praktisch in der Biologie, Psychologie, Physik, Geographie und vielen anderen Gebieten eingesetzt werden.

Kehren wir nun zu unserem obigen Beispiel zurück. Wie könnten Sie obigen Graphen, der unserem 4-BrÜckenproblem entspricht ohne Verwendung einer Programmiersprache beschreiben?

Es könnte zum Beispiel so aussehen:
Kante 1 ist verbunden mit Kante 2
Kante 2 ist verbunden mit Kante 1, 3 und 6
Kante 3 ist verbunden mit Kante 2, 4 und 7
usw.

Die gleiche Information könnte man auch deutlich kompakter darstellen, z.B. wie folgt:


1 : [2],
2 : [1,3,6],
3 : [2,4,7],
4 : [3,5,8],
5 : [4,8,9],
6 : [2,3,7],
7 : [3,6,8],
8 : [4,7,9],
9 : [5,8,10],
10: [9]]

Zu der obigen Schreibweise könnte man in natürlicher Weise kommen, auch wenn man kein Python kennt und auch wenn man kein Informatiker oder Mathematiker ist. Interessanterweise entspricht die obige Notation bereits einer möglichen Implementierung unseres Graphens in Python. Das einzige, was wir noch tun müssen: Geschweifte Klammern um die obigen Zeilen setzen und alles einer Variablen zuweisen. Das sieht dann so aus:


graph = {
    1 : [2],
    2 : [1,3,6],
    3 : [2,4,7],
    4 : [3,5,8],
    5 : [4,8,9],
    6 : [2,3,7],
    7 : [3,6,8],
    8 : [4,7,9],
    9 : [5,8,10],
    10: [9]]
}

Obiges Konstrukt entspricht einem Python-Dictionary. Die Zahlen vor den Doppelpunkten entsprechen den sogenannten Schlüsseln des Dictionaries und die Zahlen innerhalb der eckigen Klammern entsprechen Python-Listen. In unserem Fall entpricht eine solche Liste jeweils dem Wert für einen gegebenen Schlüssel, also einen Knoten. Will man für einen Knoten wissen, welche Knoten mit ihm verbunden sind, dann kann man dies durch folgenden Zugriff erreichen. Z.B. die zugehörige Knotenliste für den Knoten 4:

graph[4]

Sicherlich wollen Sie dies gerne in Python probieren. Dies kann man sehr einfach mit dem interaktiven Python-Interpreter durchführen. Am einfachsten kann man eine Python-Shell starten, wenn man unter Linux eine Konsole (Terminal) Öffnet. (Unter Windows entspricht dies dem Programm Eingabeaufforderung)
Dort tippt man nun einfach python (oder python3) gefolgt von der Eingabetaste ein. Es folgt dann der folgende Dialog:


$ python3
Python 3.2.3 (default, Oct 19 2012, 19:53:16) 
[GCC 4.7.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> 

 

Nun können Sie obiges Dictionary Zeile für Zeile eintippen und sich anschließend die Knotenliste für den Knoten 4 ausgeben lassen:


>>> graph = {
... 1: [2],
... 2: [1,3,6],
... 3: [2,4,7],
... 4: [3,5,8],
... 5: [4,8,9],
... 6: [2,3,7],
... 7: [3,6,8],
... 8: [4,7,9],
... 9: [5,8,10],
... 10: [9]
... }
>>> graph[4]
[3, 5, 8]
>>> 

 

Bisher haben wir uns bemüht alles auch für totale Anfängerinnen und Anfänger verständlich zu machen. Im folgenden müssen wir uns jedoch von diesen Verabschieden, da wir im folgenden Kenntnisse in Python voraussetzen müssen. Für diejenigen, die Python lernen wollen empfehlen wir unser Buch „Einführung in Python3“ und unser Tutorial auf unserer Webseite Python-Kurs.

Kanten

Für die folgenden Betrachtungen wollen wir unsere Landschaft mit einem kleinen Entenweiher erweitern.

landscape with pond and graph

Bild 3 Landscape with pond and graph

 

Um diesen führt ein Weg, der im Knoten 7 beginnt und endet. Dabei handelt es sich um eine Schleife, da wir wieder an den Ausgangspunkt zurückkehren, wenn wir diesen Weg wählen.
Wir können uns auch die kleine Insel im Teich als Knoten vorstellen. Allerdings als unerreichbaren Knoten, denn es gibt keinen
Weg, also keine Kante zu diesem Knoten. Einen Knoten, der mit keinen anderen Knoten verbunden ist, also keine Nachbarn hat, bezeichnet man in der Graphentheorie als isolierten Knoten. Wir erkennen in der Graphendarstellung, dass wir den Inselknoten
mit der Nummer 11 nicht innerhalb der Schleife um den Knoten dargestellt haben, denn ein Graph stellt keine geometischen
Positionen dar.

Eine Kante kann in Python als 2-elementige Menge mit den Knoten als Elementen angesehen werden, also z.B. {2,6}. Schleifen als Kanten um einen Knoten stellen wir mit einer ein-elementigen Menge dar. So gibt es in unserem Beispiel die Kante {7}.

Die Liste aller Kanten (edges) kann wie folgt berechnet werden:

 

graph = {
        1 : [2],
        2 : [1,3,6],
        3 : [2,4,7],
        4 : [3,5,8],
        5 : [4,9],
        6 : [2,7],
        7 : [3,6,7,8],
        8 : [4,7,9],
        9 : [5,8,10],
        10: [9],
        11: []
}

def generate_edges(graph):
    edges = []
    # vertex ist englisch für Knoten
    for vertex in graph:
        for neighbour in graph[vertex]:
            edges.append({vertex, neighbour})

    return edges

print(generate_edges(graph))

print(graph)

 

Obige Funktion inklusive path-Dictionary haben wir unter graph1.py abgespeichert. Wenn wir das Programm starten, erhalten wir folgende Ausgabe:

 

$ python3 graph1.py

Liste der Kanten:

[{1, 2}, {1, 2}, {2, 3}, {2, 6}, {2, 3}, {3, 4}, {3, 7}, {3, 4}, {4, 5}, {8, 4}, {4, 5}, {9, 5}, {2, 6}, {6, 7}, {3, 7}, {6, 7}, {7}, {8, 7}, {8, 4}, {8, 7}, {8, 9}, {9, 5}, {8, 9}, {9, 10}, {9, 10}]

Aus der Ausgabe können wir ersehen, dass die Schleife um den Knoten mit der Nummer 7 als ein-elementige Menge dargestellt ist.
Der Knoten 11 taucht in der Liste der Kanten nicht auf, da er isoliert ist.

Wenn wir uns das Dictionary von unserem Graphen anschauen, sehen wir, dass die Liste der benachbarten Knoten des Knotens 11 leer ist.
Entsprechend können wir leicht die Liste der isolierten Knoten berechnen:

 

def find_isolated_nodes(graph):
    """ returns a list of isolated nodes. """
    isolated = []
    for node in graph:
        if not graph[node]:
            isolated += [node]
    return isolated

 

Graphen als Python-Klasse

Im folgenden Programmlisting (siehe graph2.py) haben wir obige Ideen als Python-Klasse realisiert. In der __init__-Methode benutzen wir ein Dictionary self.__graph_dict, um die Knoten und ihre benachbarten Knoten abzuspeichern. Die Kanten eines werden nicht explizit abgespeicher, sondern werden aus dem Knoten-Dictionary (self.__graph_dict) erzeugt. Zur Erzeugung der Knoten gibt es die Methode edges(), die ihrerseits auf die private Methode __generate_edges() zurückgreift.

Pfade in Graphen

Kehren wir zu unserem anfänglichen Beispiel zurück. Eine der Fragen, die wir uns gestellt hatten, lautete: Was ist der kürzeste Weg? Wir suchen den Weg mit der geringsten Kantenzahl. Dies bedeutet natürlich nicht, dass es sich um den physikalisch kürzesten Weg handelt.
Zuvor benötigen wir jedoch noch ein paar Begriffe:

Benachbarte Knoten:

Zwei Knoten sind benachbart, wenn Sie durch eine gemeinsame Kante verbunden sind.

Pfad in einem ungerichteten Graphen:

Ein Pfad in einem ungerichteten Graphen ist eine Folge von Knoten P = ( v1, v2, …, vn ) ∈ V x V x … x V so dass vi benachbart zu v{i+1} ist für alle 1 ≤ i < n. Einen solchen Pfad P bezeichnet man als einen Pfad der Länge n von v1 nach vn.

Einfacher Pfad:

Ein Pfad, in dem sich keine Knoten wiederholen, wird als einfacher Pfad bezeichnet.

Beispiel:
P = (1,2,3,7) ist ein einfacher Pfad in unserem Beispielgraphen, ebenso wie P = (1,2,6,7,8). P = (1,2,3,7,6,2,3) ist ein Pfad aber kein einfacher Pfad, weil die Knoten 2 und 3 doppelt vorkommen.

Mit der Methode find_path() unserer Klasse können wir uns einen Pfad von einem Knoten zu einem anderen Knoten berechnen lassen. Die Methode arbeitet
rekursiv. Sie beginnt mit dem Startknoten. Entspricht der Startknoten dem Endknoten („if start_vertex == end_vertex“), gibt sie den bisher konstruierten Pfad zurück. Falls sich der Startknoten nicht im Graphen befindet, liefert die methode None zurück. Dann ermittelt die Funktion
über eine Schleife die Pfade von allen zum Startknoten (start_vertex) benachbarten Knoten (graph[start_vertex]) bis zum Endknoten (end_vertex).
Sobald ein Pfad gefunden ist, wird dieser zurückgeliefert.

Die Methode find_all_paths() funktioniert ähnlich. Die Pfade werden aber in einer Liste gesammelt und dann zurückgegeben.

Die Graphenklasse (siehe graph2.py) liefert folgende Resultate zurück:

$ python3 graph2.py 
Knoten: 1 2 3 4 5 6 7 8 9 10 
Kanten: {1, 2} {2, 3} {2, 6} {3, 4} {3, 7} {4, 5} {8, 4} {9, 5} {6, 7} {8, 7} {8, 9} {9, 10} 
Kanten des Graphen: 
[{1, 2}, {2, 3}, {2, 6}, {3, 4}, {3, 7}, {4, 5}, {8, 4}, {9, 5}, {6, 7}, {8, 7}, {8, 9}, {9, 10}]
Ein Pfad von "1" nach "8":
[1, 2, 3, 4, 5, 9, 8]
Alle Pfade von "1" nach "10":
[[1, 2, 3, 4, 5, 9, 10], [1, 2, 3, 4, 8, 9, 10], [1, 2, 3, 7, 8, 4, 5, 9, 10], [1, 2, 3, 7, 8, 9, 10], [1, 2, 6, 7, 3, 4, 5, 9, 10], [1, 2, 6, 7, 3, 4, 8, 9, 10], [1, 2, 6, 7, 8, 4, 5, 9, 10], [1, 2, 6, 7, 8, 9, 10]]
Isolierten Knoten hnizufügen '11':
Knoten: 1 2 3 4 5 6 7 8 9 10 11 
Kanten: {1, 2} {2, 3} {2, 6} {3, 4} {3, 7} {4, 5} {8, 4} {9, 5} {6, 7} {8, 7} {8, 9} {9, 10} 
Eine Schleife um den Knoten 7 hinzufügen: 
Knoten: 1 2 3 4 5 6 7 8 9 10 11 
Kanten: {1, 2} {2, 3} {2, 6} {3, 4} {3, 7} {4, 5} {8, 4} {9, 5} {6, 7} {8, 7} {7} {8, 9} {9, 10} 
Knoten: 1 2 3 4 5 6 7 8 9 10 11 
Kanten: {1, 2} {2, 3} {2, 6} {3, 4} {3, 7} {4, 5} {8, 4} {9, 5} {6, 7} {8, 7} {7} {8, 9} {9, 10}

 

Ich freue mich über Ihre Kommentare & Fragen!
Ihr
Bernd Klein

Klein, Einführung in Python 3, 2.A.Mehr zum Thema Python 3 lesen Sie im neuen Buch von Bernd Klein Einführung in Python 3.