Graphen – das Wichtigste in einer Stunde
Graphen – das Wichtigste in einer Stunde
Navis, Paketdienste und Spiele lösen ständig Probleme wie „Wie komme ich am schnellsten von A nach B?“. Dazu stellen sie die Wirklichkeit vereinfacht dar: als Graph. In dieser Reihe lernst du Strategien kennen, mit denen Computer solche Probleme lösen – und warum manche Probleme selbst für sehr schnelle Rechner zu schwer sind.
Für die Fortbildung: Wer die Kapitel 1–5 der Graphentheorie (LK) kennt, kann dieses Kapitel überfliegen und mit Kapitel 2 beginnen.
Die Abbildung zeigt fünf Ortsteile im Köllertal. Eine Linie bedeutet: Zwischen den beiden Orten gibt es eine direkte Straße, ohne durch einen dritten Ort zu fahren.
Karte: KI-generiert
P = Püttlingen, K = Köllerbach, E = Engelfangen, R = Rittenhofen, W = Walpershofen
Merke
Ein Graph besteht aus Knoten (hier die Orte, dargestellt als Kreise mit Namen) und Kanten (Linien, die zwei Knoten verbinden). Zwei Knoten, die durch eine Kante verbunden sind, heißen benachbart.
Den Schritt von der Wirklichkeit zum Graphen nennt man Abstraktion: Man lässt alles weg, was für die Frage keine Rolle spielt – Häuser, Felder, die genaue Form der Straßen.
Zeige auf die Begriffe – im Graphen wird das Passende markiert. Auf dem Tablet: antippen.
Aufgabe 1: Welcher Ort hat im Graphen die meisten Nachbarn?
Graph anzeigen
Selbst einen Graphen zeichnen
Die Gemeinde Nalbach besteht aus mehreren Ortsteilen. Die Tabelle zeigt, zwischen welchen Ortsteilen es eine direkte Straße gibt (vereinfacht).
| Ortsteil | direkte Straße nach |
|---|---|
| Nalbach (N) | Piesbach, Körprich |
| Piesbach (P) | Nalbach, Bilsdorf |
| Bilsdorf (B) | Piesbach, Körprich |
| Körprich (K) | Nalbach, Bilsdorf |
🗺️ Hilfe: Karte von Nalbach einblenden
Karte: KI-generiert
Aufgabe 3: Zeichne den Graphen zur Tabelle. Die Ortsteile sind schon als Knoten platziert – verbinde sie mit Kanten. Als Hilfe kannst du oben mit „Hintergrund“ die Karte von Nalbach einblenden.
Aufgabe 3: Zeichne den Graphen zur Tabelle. Die Ortsteile sind schon als Knoten platziert – verbinde sie mit Kanten. Als Hilfe kannst du oben mit „Hintergrund“ die Karte von Nalbach einblenden.
Wege
Die nächste Karte zeigt größere Orte zwischen Saarlouis und Saarbrücken. Ein Weg ist eine Folge von Knoten, bei der je zwei aufeinanderfolgende Knoten benachbart sind. Wir schreiben ihn als Wort, z. B. SVB: von Saarlouis über Völklingen nach Saarbrücken. Ein Weg, der keinen Knoten doppelt besucht, heißt einfacher Weg.
Karte: KI-generiert
S = Saarlouis, D = Dillingen, L = Lebach, W = Schwalbach, V = Völklingen, P = Püttlingen, R = Riegelsberg, H = Heusweiler, B = Saarbrücken
Gewichtete Graphen
Für ein Navi reicht es nicht zu wissen, ob zwei Orte verbunden sind. Es braucht auch, wie lange man von einem zum anderen fährt. Dazu schreibt man an jede Kante eine Zahl, ihr Gewicht – hier die Fahrzeit in Minuten (gerundet, ohne Verkehr).
S = Saarlouis, D = Dillingen, L = Lebach, W = Schwalbach, V = Völklingen, P = Püttlingen, R = Riegelsberg, H = Heusweiler, B = Saarbrücken
Merke
In einem gewichteten Graphen hat jede Kante ein Gewicht (z. B. Länge, Zeit, Kosten). Die Länge eines Weges ist die Summe der Gewichte seiner Kanten.