Skip to main content


Zutaten: Zucker, Kakaomasse (50%), Milchzucker, Weizenmehl, Vollmilchpulver, Magermilchpulver, Butterreinfett, Sahnepulver, Butter (1,4%)
Kann Spuren von Analysis und Geometrie enthalten.

III_21_titel-graph

Graphische Liebe

Letzte Nacht hatte Rike einen Alptraum: Sie geht auf einem Grat in einem riesigen Gebirge, rechts und links ganz tiefe Schluchten. Dann fällt sie zu der einen Seite und wacht auf. Sie macht sich Sorgen, sie hat Liebeskummer. Sie hat gehört, dass sich Max in Lila verliebt hat. Jetzt überlegt sie, ob sie nach Kalkutta fliegen soll, um mit Max ein paar schöne Tage zu verbringen. Doch wenn sie zu Max fliegt, wird Ben ihr das übelnehmen. Sie hat das Gefühl, sich endgültig einer Seite zuwenden zu müssen, sich somit entscheiden zu müssen.

Jetzt nimmt sie ein Blatt Papier und schreibt die Beziehungssituation graphisch auf. Wenn zwei Menschen zusammenkommen, sich lieben und sich trennen, sieht das graphisch so aus:

Beziehungsgraphen

III_21_graph_00_03
Elementarer Beziehungsgraph für Liebe und Trennung zweier Menschen

Doch bei ihr ist es komplizierter, es sind nicht nur 2 Menschen, sondern 4. Sie hat Max vor langer Zeit getroffen und ist seine Freundin. Dann sind Ben und Lila dazugekommen. Jetzt ist sie mit Ben zusammen, und Max mit Lila. Wenn sie nach Kalkutta fliegt, vielleicht kommt sie dann wieder mit Max zusammen?

III_21_graph_01_04
Graph

 

Neben der Traurigkeit über Max‘ neue Liebe hat sie auch Hoffnung. Hm, ein schöner planarer Graph, denkt sie. Doch was passiert, wenn sie mit Ben nach Kalkutta fliegt, mit Max wieder zusammenkommt und wenn Ben sich in Lila verliebt? Dann braucht sie eine weitere Dimension, um das zu zeichnen:

III_21_graph_02_04
Graph

 

Jetzt ist der Graph nicht mehr planar, sie weiß nicht weiter. Hier in Bielefeld weiß niemand weiter. Da muss sie wohl ihre Freundin Anna in Berlin anrufen.

Rike Hi, Anna. Ich habe so einen verdammten Graphen, der ist nicht planar. Warte, ich schicke ihn Dir. Hier! Weißt Du, welche Eigenschaften er hat? Wie kann ich ihn zeichnen?

Satz von Kuratowski

Anna Hi, Rike, geht es Dir nicht so gut? Ich versuche es mal. Wenn der Graph wirklich nicht planar ist, dann muss er entweder den Graphen oder den enthalten. Der eine ist ein vollständiger Graph mit 5 Vertices, der andere ist ein zweigeteilter, vollständiger, sogenannter bipartiter. Das ist der Satz von Kuratowski.

III_21_graph_K5_03
Graph
III_21_graph_K33_03
Graph

Rike Oh, ich glaube, die beiden sind nicht drin.

Anna Kannst Du nicht einen von den beiden nach unten gehenden Teilen nach oben klappen?

Rike Stimmt, ich wollte den Graphen zeichnen wie im Phasenraum, der Pfeil dachte ich, repräsentiert die Zeit und geht immer nach unten.

Anna Nein, das brauchst Du nicht. Ein Graph ist kein Phasenraum. Die Vertices sind nicht die Zustände.

Rike Stimmt, bei mir sind die Edges die Zustände und die Vertices stehen für Zustandsänderungen. Dann klappe ich einen Zweig nach oben, und fertig ist der planare Graph über die 4er Beziehung.

III_21_graph_03_04
Graph

Euler-Charakteristik

Anna Hast Du schon die Euler-Charakteristik bestimmt?

Rike Wie geht das? Ich dachte, die gibt’s nur für Polyeder?

Anna Nein, die gibt’s auch für Graphen. Man schneidet so einen Polyeder an einer Kante auf, klappt ihn auf und interpretiert die Vertices und Edges als die eines Graphen. Bei der Zählung der Flächen nimmt man noch die äußere dazu. Die Euler-Charakteristik ist eine Invariante für jeden Graphen

V … Anzahl der Vertices/Knoten
E … Anzahl der Edges/Kanten
F … Anzahl der Faces/Flächen inklusive die äußere

Jeder planare, zusammenhängende Graph hat die Charakteristik 2.

Rike Okay, bei diesem Graphen ist

und folglich

Die Euler-Charakteristik stimmt. Das ist einfach schön.

Anna Kann ich noch was für Dich tun?

Rike Danke, das war‘s erstmal. Grüß David von mir!

***

Übungsaufgaben

  1. Beweise die Euler-Charakteristik.
  2. Wie ändert sich der Graph , wenn man die beiden Kanten R+M identifiziert und versucht, den neuen Graphen planar zu zeichnen?

Lösung

  1. Mit vollständiger Induktion über die Anzahl der Vertices V.
  2. III_21_graph_04_04