Dinge in der Welt existieren nicht unabhängig voneinander.
"Die Tasse steht auf dem Tisch",
"Ich bin im Haus",
"Flora kennt Sam".
All diese Aussagen verbinden zwei (oder mehr) Objekte miteinander.
Der einfachste Weg das graphisch auszudrücken ist zwei Blobs durch eine Linie zu verbinden:
◯––◯. Wenn man mehrere Objekte und Verbindungen hat kann man das
folgendermaßen darstellen:
Soetwas nennt man einen Graph (nicht zu verwechseln mit einem 'Funktionsgraph' oder
anderen Graphen, die man benutzt, um Daten darzustellen).
Die Blobs nennt man Knoten (oder Ecken) und die Verbindungen die Kanten des Graphen.
Wenn man ausdrücken will, dass die Verbindung nicht symmetrisch ist, wie in den drei Beispielen
oben, kann man die Kanten durch Pfeile ersetzen: ◯→◯.
Ich hoffe es ist klar, warum ein Graph komplexere Strukturen abbilden kann als eine Menge.
(Aber wie gesagt, man kann Graphen auch als Mengen darstellen, wenn man unbedingt will.)
Anstatt einfach nur Elemente aufzuzählen, können wir nun sehen, wie diese miteinander
verbunden sind.
Beispiele
Es gibt tausende Dinge, die man sich (vereinfacht) als Graphen vorstellen kann.
Angefangen vom
Internet
(Computer verbunden durch Datenleitungen, oder auch auf dem Softwarelevel als Webseiten mit 'Links' als
Verbindungen) bis him zum menschlichen Gehirn (Nervenzellen als Knoten, die durch Dendriten und Axone
verbunden sind).
Wenn wir Atome als Blobs modellieren und diese mit Kanten verbinden, dann sind chemische Moleküle
auch als Graphen (eventuell mit Mehrfachkanten) darstellbar.
Andere interessante Alltagsbeispiele sind
Ablaufdiagramme,
Verkehrsnetze
und soziale Netzwerke (Menschen als Knoten und Kanten zwischen den Menschen, die sich
kennen oder Kontakt haben). Letztere werden beispielsweise dazu benutzt,
um Ausbreitung von Krankheiten besser zu verstehen.
Wozu ist das gut?
Für viele interessante Systeme reicht es, wenn wir diese mit endlich vielen 'Zuständen'
beschreiben. Beispiele sind Sonne/Regenwetter, Gefühlszustände (oder auch gesund/krank),
chemische und physikalische Zustände von Materielien oder Zustände
eines technischen/elektronischen Gerätes (an/aus). Diese Zustände sind die Knoten.
Die Verbindungen sind dann die möglichen Übergänge zwischen den verschiedenen Zuständen.
Diese Idee führt auf
endliche Automaten
und deren stochastische Cousins, die
Markovketten.
Diese simplistischen Modelle bilden Vergleichspunkte, um komplexere Modelle zu bewerten und
geben überaschend oft schon selbst interessante Einsichten.
Graphen sind eine der wichtigsten Datenstrukturen in der Informatik. Wenn man Probleme
in die Sprache der Graphentheorie übersetzt, erkennt man, dass viele davon
mit ähnlichen Algorithmen gelöst werden können.
Graphen und ihre Verallgemeinerungen sind sehr natürliche Strukturen, wenn es darum
geht unser Wissen zu organisieren und Zusammenhänge graphisch darzustellen. Wir werden
in späteren Kapiteln deswegen Mindmaps und andere Bäume kennenlernen.
In der Mathematik tauchen Graphen immer mal wieder als
Funktionen und Relationen auf endlichen Mengen auf.
Zum Nachdenken
Stellen sie ihren Bekanntenkreis als Graph dar. Sich selbst als zentralen Blob, die Familie, Freunde
und Bekannte als Knoten außenherum. Dann verbindet man diejenigen Personen die sich
gegenseitig kennen (jeder sollte mit 'mir' verbunden sein).
Wo und wie haben sie Leute kennengelernt? Gibt es strukturelle Unterschiede im Graphen,
die auf verschiedene 'Quellen' (Arbeit, Schule, ...) hindeuten? Welche Klassifikationen
kann man anhand dieser Daten vornehmen und was sagt das über die Art und Weise aus,
wie ihre Freundschaften und Bekanntschaften entstehen?
