Volltextsuche über das Angebot:

19 ° / 17 ° Regenschauer

Navigation:
Hinter jedem Navi liegen Knoten und Kanten

Graphentheorie Hinter jedem Navi liegen Knoten und Kanten

Vom Haus des Nikolaus bis zum Göttinger Stadtbusnetz reichte das Spektrum an Graphen, das Prof. Anita Schöbel, Institut für Numerische und Angewandte Mathematik der Universität Göttingen, am Dienstagabend im Rahmen der Ringvorlesung vorstellte. Welche dieser Gebilde nutzlos sind, bleibe dem Auge des Betrachters überlassen. Auch ein Spinnennetz sei ein Graph, über den die Spinne sicher ihre eigene Ansicht habe.

Voriger Artikel
Versuchsaffen: Mehr Kontrolle durch eigene Zucht
Nächster Artikel
Augustus mit „merkwürdigem Quadratschädel“

Zugverkehr im Bahnhof: Auch bei diesen Regelungen spielen Graphen eine Rolle.

Quelle: BB

„Graphen bestehen aus Knoten und Kanten“, erklärt die Mathematikerin. Knoten sind die Eck- und Kreuzungspunkte, während Kanten die Linien sind, die die Knoten verbinden. Diese Linien müssen keineswegs gerade sein. Hinter jedem Navigationssystem liegt ein Graph des Straßennetzes, in dem die „krummen“ Straßen zwischen Kreuzungen, Städten und Autobahnabfahrten unterschiedlich priorisierte Kanten sind.

Was beim Haus des Nikolaus funktioniert, nämlich das Nachfahren der Kanten ohne ein Absetzen des Stiftes, gelang dem Mathematiker Leonard Euler in Königsberg nicht: von seinem Haus aus und dorthin zurück einen Spaziergang über alle sieben Brücken der Stadt zu unternehmen, dabei jedoch jede der Brücken nur einmal zu überqueren. „Hier spielen Knotengrade die entscheidende Rolle, also die Anzahl der Kanten, die bei einem Knoten ankommen.“ Ist auch nur einer der Knotengrade in einem Graphen eine negative Zahl, lässt sich der Graph nicht dopplungsfrei nachverfolgen.

Beide Graphen seien nun nicht übermäßig nützlich. Ein Bereich, in dem die Graphentheorie erhebliche Beiträge leistet, sei dagegen die Verkehrsplanung. Plant man beispielsweise den Zugverkehr durch Bahnhöfe, dürfen nicht auf einem Gleis zwei Züge in zu engem zeitlichen Abstand einfahren. Ein so genannter Konfliktgraph verbindet zwei solche Züge. Die Züge je Gleis erhalten eine gemeinsame Farbe. Also muss sichergestellt werden, dass an keiner Stelle durch einen Konfliktgraphen verbundene Züge die gleiche Farbe haben.
„In der Realität ist das natürlich ungleich komplexer“, betont Schöbel. Man führe sich nur vor Augen, dass die ICE-Züge in Göttingen nur die Gleise 9 bis 11 nutzen können, dass es unterschiedliche Priorisierungen gibt und so weiter. „Ebenso lassen sich Stundenpläne, Raumbelegungen und viele andere Optimierungsprobleme, die mit der bestmöglichen Nutzung von Ressourcen zu tun haben, über Graphen abbilden.

Gleiches gilt für so genannte Matching-Probleme, also die optimierte Paarbildung. „Sind in der Tanzschule mehr Männer als Frauen zu vergeben und hat jede Tänzerin und jeder Tänzer bestimmte Vorlieben und Abneigungen, entsteht eine anspruchsvolle Matching-Aufgabe.“ Diese wird noch interessanter, wenn man beispielsweise danach gewichtet, welche Paare die beste gemeinsame „Tanz-Kompetenz“ haben.

Auch in der Verkehrsplanung kommt der Matching-Ansatz zum Einsatz. Hier geht es darum, dass die Fahrgäste von A nach B möglichst selten umsteigen müssen. Dabei werden die Linienstücke zu Knoten, die durch eine Kante verbunden sind, sofern sie durchgehend befahrbar sind.

Auch in wissenschaftlichen Fachbereichen, bei denen man es auf den ersten Blick vielleicht nicht vermutet, werden Graphen umfangreich genutzt. So lässt sich beispielsweise ein Beziehungsnetzwerk in einer großen Gruppe durch Graphen sehr anschaulich darstellen. Hauptgruppen, Randgruppen und Einzelgänger werden erkennbar, wenn man davon ausgeht, dass die beliebtesten Personen (Knoten) Beziehungen (Kanten) zu den meisten anderen Gruppenmitgliedern haben. Im Unternehmensalltag zumindest in großen Produktionsunternehmen können Graphen etwa bei der Mitarbeiterplanung zum Einsatz kommen.

Zur Festtagsstimmung passen vermutlich besser einige mutmaßlich nutzlose Graphen. Neben dem Haus des Nikolaus zählen hierzu beispielsweise auch Halma und Mühle.

Am Dienstag, 11. Januar, wird die Ringvorlesung mit dem Vortrag „Chemie - Eine gelungene Symbiose von Wissenschaft und Industrie“ von Dr. Stefan Marcinowski, Vorstand BASF SE, Vizepräsident der MPG, fortgesetzt. Beginn ist um 18 Uhr in der Aula am Wilhelmsplatz 1.

Von Heike Jordan

Voriger Artikel
Nächster Artikel
Möbel aus Popcorn