Graphen & Netze

Schau dir einen U-Bahn-Plan an: Er zeigt nicht, wie die Stadt wirklich aussieht. Straßen fehlen, Entfernungen stimmen nicht, die Linien sind ordentlich begradigt. Trotzdem findest du damit perfekt deinen Weg. Der Plan zeigt nämlich genau das, was zählt: welche Stationen es gibt und welche direkt verbunden sind. Diese Sichtweise ist so nützlich, dass die Informatik ihr einen eigenen Namen gibt: der Graph.

Knoten und Kanten

Ein Graph besteht aus zwei Zutaten. Die Knoten sind die Dinge selbst: Stationen, Personen, Computer. Die Kanten sind die Verbindungen zwischen ihnen: ein Gleis, eine Freundschaft, ein Netzwerkkabel. Mehr braucht es nicht. Wo die Knoten gezeichnet werden, ist egal, nur die Verbindungen zählen. Zwei Zeichnungen, die völlig verschieden aussehen, können deshalb genau denselben Graphen zeigen.

Wege und kürzeste Wege

Ein Weg durch einen Graphen ist eine Folge von Kanten, die dich von Knoten zu Knoten führt, so wie eine U-Bahn-Fahrt von Station zu Station. Oft gibt es viele mögliche Wege zwischen zwei Knoten, und dann interessiert der kürzeste: der mit den wenigsten Kanten. Genau diese Frage steckt in vielen Alltagshelfern. Die Navi-App sucht den kürzesten Weg im Straßengraphen, dort zählt allerdings nicht die Zahl der Kanten, sondern ihre Länge: Jede Kante bekommt dafür eine Zahl, ihr Gewicht. Soziale Netzwerke fragen dagegen, über wie viele Ecken du jemanden kennst.

Graphen sind überall

Sobald du Graphen kennst, entdeckst du sie überall. Das Internet ist ein Graph aus Routern und Leitungen, und weil es zwischen zwei Punkten meist mehrere Wege gibt, funktioniert es auch dann noch, wenn eine Leitung ausfällt. Ein soziales Netzwerk ist ein Graph aus Personen und Freundschaften. Sogar das Web selbst ist einer: Seiten sind Knoten, Links sind Kanten. Wer ein Problem als Graph zeichnen kann, kann die immer gleichen Werkzeuge darauf anwenden, allen voran die Wegsuche.