Wie hängt das Bahnnetz zusammen?
Ein Graph besteht aus Knoten und Kanten und beschreibt jedes Netz: Bahnstrecken, Router, Freundschaften. Mit Graphen finden Sie Wege und erkennen, ob ein Netz in getrennte Teile zerfällt.
Ein Beispiel: Sechs Städte sind durch fünf Direktverbindungen verbunden. Kommt man von Hamburg nach Frankfurt? Ein Graph beantwortet das ohne Karte.
Am Ende dieser Lektion
Notiz
Ich kann ein Netz als Graph beschreiben und prüfen, ob es zusammenhängt.
Schlüsselwörter
| Begriff | Was er bedeutet |
|---|---|
| Knoten | ein Punkt im Netz, hier eine Stadt |
| Kante | eine Verbindung zwischen zwei Knoten |
| Grad | die Zahl der Kanten an einem Knoten |
| Weg | eine Folge von Knoten, die durch Kanten verbunden sind |
| Zusammenhängend | zu je zwei Knoten gibt es einen Weg |
| Baum | ein zusammenhängender Graph ohne Kreis |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ein Graph hat Knoten und Kanten
Ein Graph besteht aus Knoten und Kanten. Im Bahnnetz sind die Städte die Knoten und die Direktverbindungen die Kanten.
Die Kanten sind hier ungerichtet: Eine Strecke von Hamburg nach Bremen führt auch von Bremen nach Hamburg. In Python schreibt man jede Kante als Paar von Namen.
Der Grad zählt die Kanten an einem Knoten
Der Grad eines Knotens ist die Zahl seiner Kanten. Berlin hängt nur an Hannover und hat Grad 1. Hannover hat Grad 3.
Jede Kante hat zwei Enden. Darum ist die Summe aller Grade immer doppelt so groß wie die Zahl der Kanten.
Grad von Hannover und doppelte Kantenzahl
python3 -c "k = [('Hamburg', 'Bremen'), ('Bremen', 'Hannover'), ('Hannover', 'Berlin'), ('Hannover', 'Kassel'), ('Kassel', 'Frankfurt')]; print(sum('Hannover' in e for e in k), 2 * len(k))"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Beispiel: die Grade im Bahnnetz
| Stadt | Kanten an der Stadt | Grad |
|---|---|---|
| Hamburg | Bremen | 1 |
| Bremen | Hamburg, Hannover | 2 |
| Hannover | Bremen, Berlin, Kassel | 3 |
| Berlin | Hannover | 1 |
| Kassel | Hannover, Frankfurt | 2 |
| Frankfurt | Kassel | 1 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ein Weg folgt Kanten von Knoten zu Knoten
Ein Weg ist eine Folge von Knoten, bei der je zwei aufeinanderfolgende durch eine Kante verbunden sind. Hamburg, Bremen, Hannover ist ein Weg der Länge 2, denn er hat zwei Kanten.
Ein Graph ist zusammenhängend, wenn es zu je zwei Knoten einen Weg gibt. Gibt es getrennte Teile, ist er es nicht.
Eine Suche findet alle erreichbaren Knoten
Um zu prüfen, ob ein Netz zusammenhängt, starten Sie an einem Knoten. Eine Liste besucht merkt sich, was schon erreicht ist, und eine Liste offen, was noch untersucht wird.
Sie nehmen einen Knoten aus offen und fügen jeden neuen Nachbarn hinzu. Am Ende steht in besucht, was man von dort erreicht.
Die Suche im Bahnnetz
kanten = [["Hamburg", "Bremen"], ["Bremen", "Hannover"],
["Hannover", "Berlin"], ["Hannover", "Kassel"],
["Kassel", "Frankfurt"]]
besucht = ["Hamburg"]
offen = ["Hamburg"]
while len(offen) > 0:
stadt = offen.pop()
for kante in kanten:
if kante[0] == stadt and kante[1] not in besucht:
besucht.append(kante[1])
offen.append(kante[1])
if kante[1] == stadt and kante[0] not in besucht:
besucht.append(kante[0])
offen.append(kante[0])
print(besucht)
print(len(besucht) == 6)
Ein Baum ist ein Netz ohne Kreis
Ein Baum ist ein zusammenhängender Graph ohne Kreis. Ein Kreis ist ein Weg, der am Start endet.
Ein Baum mit n Knoten hat genau n minus 1 Kanten. Das Bahnnetz hat 6 Knoten und 5 Kanten und ist ein Baum. Fügen Sie Hamburg–Hannover hinzu, entsteht der Kreis Hamburg, Bremen, Hannover.
Beispiel: Baum oder nicht?
| Netz | Knoten | Kanten | Zusammenhängend | Baum |
|---|---|---|---|---|
| Das Bahnnetz | 6 | 5 | ja | ja |
| Bahnnetz mit Hamburg–Hannover | 6 | 6 | ja | nein, mit Kreis |
| Hamburg–Bremen und Berlin–Potsdam | 4 | 2 | nein | nein |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Knoten und Kanten des Bahnnetzes zählen
python3 -c "k = [('Hamburg', 'Bremen'), ('Bremen', 'Hannover'), ('Hannover', 'Berlin'), ('Hannover', 'Kassel'), ('Kassel', 'Frankfurt')]; print(len({x for e in k for x in e}), len(k))"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Ein häufiger Fehler
Warnung
Viele glauben, ein Graph mit n minus 1 Kanten sei immer ein Baum. Das stimmt nicht. Vier Knoten A, B, C, D mit den Kanten A–B, B–C und C–A haben 3 Kanten. Trotzdem gibt es einen Kreis, und D ist getrennt. Erst Zusammenhang und n minus 1 Kanten zusammen ergeben einen Baum.
Weiterführend: der kürzeste Weg
Die Suche aus dieser Lektion findet alle erreichbaren Knoten, aber nicht den kürzesten Weg. Dafür arbeitet man Ebene für Ebene: erst alle Nachbarn des Starts, dann deren Nachbarn.
Zählen Sie am Bahnnetz von Hamburg aus: Wie viele Kanten braucht der Weg nach Frankfurt? Schreiben Sie die Städte der Reihe nach auf.