Aufgaben

Konfiguration und Python-Pakete

import numpy as np
import matplotlib.pyplot as plt

# falls nicht vorhanden: conda install networkx pydot
import networkx as nx
from networkx.drawing.nx_pydot import graphviz_layout

Aufgabe 1: Anwendungsbeispiele

Nenen Sie mindestens fünf Anwendungsbeispiele von Graphen, die in der Vorlesung noch nicht genannt sind.

Aufgabe 2: Adjazenzmatrix

1. Konstruieren und zeichnen Sie mit NetworkX einen Graphen \(G\) mit 5 Knoten und 5 Kanten, die einen Kreis bilden.

2. Mit dem Befehl nx.adjacency_matrix(G).todense() erhalten Sie die Adjazenzmatrix von \(G\). Was beschreibt Sie?

3. Wie sieht ein Graph aus, dessen Adjazenzmatrix Nullen auf der Diagonalen hat und ansonsten Einträge 1 hat? Zeichnen Sie ein Beispiel auf.

Aufgabe 3: Breitensuche

Implementieren Sie die Breitensuche mit einer Funktion, die den resultierenden Spannbaum als gerichteten Graphen zurückgibt. Vergleichen Sie Ihre Implementierung mit jener von NetworkX anhand mehrerer zufälliger, ungerichteter Graphen, die Sie z. B. mit dem Befehl gnm_random_graph erzeugen können.

Aufgabe 4: Tiefensuche

Implementieren Sie die Tiefensuche mit einer Funktion, die den resultierenden Spannbaum als gerichteten Graphen zurückgibt. Vergleichen Sie Ihre Implementierung mit jener von NetworkX anhand mehrerer zufälliger, ungerichteter Graphen, die Sie z. B. mit dem Befehl gnm_random_graph erzeugen können.

Hinweis: Mit G.nodes[node][attribute] = value können Sie dem Knoten node des Graphen G ein Attribute attribute mit Wert value zuweisen.

Aufgabe 5: Dijkstra-Algorithmus

Durch den Code unten ist ein ungerichteter Graph \(G\) definiert.

1. Führen Sie von Hand den Dijkstra-Algorithmus aus, indem Sie die Tabelle unten analog zur Vorlesung füllen.

   S	B	C	D	E	F	G	H
   0	ue.	ue.	ue.	ue.	ue.	ue.	ue.

   Dabei steht ue. für unendlich.

2. Überprüfen Sie Ihr Ergebnis am Computer mit entsprechenden NetworkX-Funktionen.

G = nx.Graph()

G.add_edge('S', 'B', weight= 3)
G.add_edge('S', 'C', weight= 10)
G.add_edge('B', 'D', weight= 3)
G.add_edge('D', 'E', weight= 6)
G.add_edge('D', 'F', weight= 3)
G.add_edge('E', 'C', weight= 5)
G.add_edge('B', 'F', weight= 2)
G.add_edge('C', 'F', weight= 2)
G.add_edge('E', 'G', weight= 4)
G.add_edge('G', 'H', weight= 7)
G.add_edge('F', 'G', weight= 1)
G.add_edge('D', 'H', weight= 3)

pos = nx.spring_layout(G, seed=5)
nx.draw(G, pos=pos, with_labels=True, node_color='yellow')
edge_labels = nx.get_edge_attributes(G,'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels);