nur Design
Zum Startframe
Zum .pdf der Seite
Zum Start von matherockt.de
GRAPHENTHEORIE
bei matherockt.de

Paul Erdös

Emmy und Max wollten eine heiße Schokolade im Café der Mathe-rockt!-Galerie trinken, aber da war es so laut, dass es nicht gemütlich war. Max und Emmy verließen das Café, und tauschten sich über die aufgeschnappten Fetzen aus: "Schwachsinnsbeweis", "Bewiesen ist bewiesen", "Wer weiß, vielleicht braucht man doch fünf Farben"

"Ich glaube es ging um Graphentheorie. Komm, lass uns den Raum suchen, ich erzähl dir inzwischen, was es mit diesem Schwachsinnsbeweis auf sich hat."
Während sie einen von den riesigen Wegweisern suchten, die sonst an jeder Ecke standen, sich aber jetzt hartnäckig versteckten, erzählte Emmy:
"1852 färbte ein Engländer eine britische Landkarte. Gebiete, die eine gemeinsame Grenze hatten, bekamen verschiedene Farben. Erstaunlicherweise reichten ihm dafür vier Farben.
4-Farben-Gef&uauml;rbte Deutschlandkarte
Die Bundesländer in vier Farben

Er fragte seinen Bruder, der Mathe studierte, ob das bei jeder Landkarte so sei."
Max unterbrach Emmy.
"Das kann ich mir nicht vorstellen. In diesem verworrenen Haus hier braucht man bestimmt zehn Farben um die Räume so zu färben."
"Nein, 1977 wurde endlich bewiesen, dass vier Farben immer reichen. Dazu wurden alle denkbaren - und das sind unendlich viele - Karten in 1482 mögliche Fälle zusammengefasst. Dann wurden sie mit einem Computer durchgetestet. Und das spaltet die mathematische Welt. Viele denken, dass das kein Beweis ist, weil er nicht von einem Menschen nachvollzogen werden kann."

"Darüber haben die sich also vorhin so gefetzt. Emmy, wir finden den Graphentheorieraum einfach nicht."
"Willst du trotzdem was über Telefonnetze, Routenplaner oder Heiratsprobleme hören?"
"Das hat alles was mit Graphen zu tun? Was ist denn eigentlich ein Graph?"
"Du kennst doch sicher das Haus vom Nikolaus?"
Max nickte, zog ein Blatt Papier und einen Bleistift aus seinem Rucksack und zeichnete ein Nikolaushaus.
"Das ist ein Graph, ein paar Punkte, von denen manche miteinander verbunden sind?"
Das Haus vom Nikolaus

"Ja. Das Haus vom Nikolaus kann in einem Strich gezeichnet werden. Das funktioniert aber nicht bei jedem Graphen, schau hier", und Emmy zeichnete einen Graphen.
Nicht-Euler-Graph
"In diesem Graphen gibt es vier Ecken mit drei Kanten. Wenn du durch so eine Ecke zeichnest, lässt du immer eine Kante übrig, und wenn du zurück kommst, bleibst du stecken."
"Aber das Haus vom Nikolaus hat doch auch zwei Ecken mit drei Kanten."
"Das funktioniert trotzdem: du kannst in einer starten, und in der anderen aufhören."
"Oh, deshalb muss ich in einer der beiden unteren Ecken anfangen und auch wieder aufhören. Und was hat das mit Heiratsproblemen zu tun?"

"Fangen wir erstmal mit den Telefonnetzen an. Jedes Telefon wird durch eine Ecke gekennzeichnet, jedes Kabel durch eine Kante.
Telefon-Graph
Eine interessante Frage ist, wie das Telefonnetz am besten gebaut werden kann, damit alle Gespräche durchkommen und die Kosten möglichst gering sind. Ein ganz ähnliches Problem steht beim Routenplaner."
"Macht das nicht der Computer?"
"Naja, die Graphentheorie entwickelt die Methoden, die die Computer dann verwenden. Die meisten von den Fragen sind übrigens auch für Computer sehr schwer. Für sehr große Graphen dauert das ewig."

"Und das Heiraten?"
"Der Heiratssatz von Hall sagt, dass in einer rein heterosexuellen Gesellschaft mit genauso vielen Frauen wie Männern alle verheiratet werden können. Zumindest wenn es für jede beliebige Gruppe von Frauen mindestens genauso viele Männer gibt, die sich für wenigstens eine der Frauen interessieren. Andersrum stimmt das übrigens auch."
"Der Herr Hall hatte ja ziemlich altertümliche Vorstellungen. Guck mal da, direkt um die Ecke hätten wir einen Wegweiser gefunden."
"Na dann mal los, suchen wir uns einfach den nächsten Raum."

Anmerkung der Redaktion: Hier ein paar Graphentheorie-Links:
Die Graphentheorie hat ihren Ursprung im Königsberger Brückenproblem
Über kürzeste Wege in Graphen
Über das Vierfarbenproblem

nach oben

Zum Startframe Zum .pdf der Seite Zum Start von matherockt.de