Exkurs: Graphentheorie - Grundlagen

Graphen werden in der Mathematik zur Beschreibung verschiedener Probleme und Situationen verwendet. Die Methoden der Graphentheorie (algebraische, topologisch/geometrische und kombinatorische) beschreiben und analysieren dabei die Graphen und der durch sie modellierten Probleme. Die relativ einfache Übertragung von Modellen und Abstraktionen aus anderen Wissenschaften (Informatik, Chemie, Physik, Ökonomie, Soziologie usw.), erlaubt die mathematische Bearbeitung durch die leicht verständlichen Grundlagen der Graphentheorie.
Die aus der Graphentheorie erstellten Graphen werden meist durch Punkte und Linien repräsentiert, die die Knoten bzw. Kanten darstellen. Einfache Definitionen geben einen schnellen Überblick über die Notation von Graphen.

Graphentheoretische Ausdrücke	Graphen
Punkte (Knoten) sind adjazent wenn sie durch eine gemeinsame Linie (Kante) verbunden sind
Falls die Knoten eines Graphen gekennzeichnet sind (z.B. mit Nummern) ist der Graph bewertet oder geordnet.
Eine Kante indiziert in zwei gemeinsame Knoten. Der Grad eines Knoten ist durch die Anzahl der Kanten bestimmt, die im Knoten indizieren (enden). Im Beispiel ist der Grad 2.
Ein Graph ist zusammenhängend, wenn zwischen 2 Knoten mindestens eine Kante liegt (die meisten Molekülstrukturen)
Das Gegenteil ist ein disjunkter Graph, der isolierte Knoten ohne Kanten enthält (in der Chemie sind das z.B. Substanzgemische oder z.T. Substrukturen)
Ein Diagraph ist Graph, der gerichtete Kanten (d.h. eine gewichtete Orientierung) zwischen 2 Knoten enthält. (In der organischen Chemie sind dies z.B. unterschiedliche Atome bzw. I- und M-Effekte.)
Strukturdiagramme sind ungerichtete Graphen und werden meist in der Chemie als topologische Deskriptoren verwendet, da die Knoten s-Bindungen repräsentieren.
Ein Graph ist vollständig, wenn alle Knoten untereinander verbunden (adjazent) sind.
Ein Graph ist eben, wenn sich alle Kanten kreuzungsfrei in einer Ebene anordnen lassen
Eulerscher Weg: Wenn alle Knoten einen geradzahligen Grad besitzen, läßt sich ein Graph in einer geschlossenen Linie durchlaufen (S. Königsberger Problem)
Das Haus des Nikolaus: Ein Graph läßt sich in einen Zug zeichnen, wenn genau zwei Knoten einen ungeraden Grad haben und alle übrigen einen geraden Grad. Startpunkt der Zeichnung ist dann ein Knoten mit ungeradem Grad (offene Euler-Tour)
Isomorphismus: Bei geordneten Graphen mit n Knoten gibt es n! Darstellungsmöglichkeiten mit gleicher Gestalt (z.B. n=3 -> 6 Isomere)

© Prof. Dr. J. Gasteiger, Dr. Th. Engel, CCC Univ. Erlangen, Thu Dec 18 14:53:53 2003 GMT
 BMBF-Leitprojekt Vernetztes Studium - Chemie