Kapitelanfang Vorige Seite Nächste Seite Nächstes Kapitel
VERN Home navigation
 
Chemoinformatik
Einführung in die Chemoinformatik
Repräsentation chemischer Strukturen
Einleitung
Nomenklatur
Linearnotation
Konstitutionscodierung
Einführung
  Graphentheorie Grundlagen
Graphentheorie-Chemie
Adjazenz-Matrix
Distanz-Matrix
Inzidenz-Matrix
Bindungs-Matrix
Bindungs-Elektronen-Matrix
Beurteilung Matrizen
Bindungsliste I
Bindungsliste II
Bindungsliste III
Kanonisierung
Morgan Algorithmus
Morgan - Tutorial
Fragment-Kodierung
Fingerprints
Hashcode
Beurteilung Spezialnotationen
3D-Codierung
Oberflächen
Literatur
Repräsentation chemischer Reaktionen
Daten/Datenformate
Datenbanken/Datenquellen
Struktur-Suchmethoden
Berechnung physikalischer und chemischer Daten
Deskriptoren für chemische Verbindungen
Methoden zur Datenanalyse
Anwendungen

Startseite

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
Adjazent
Falls die Knoten eines Graphen gekennzeichnet sind (z.B. mit Nummern) ist der Graph bewertet oder geordnet.
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.
Indizent
Ein Graph ist zusammenhängend, wenn zwischen 2 Knoten mindestens eine Kante liegt (die meisten Molekülstrukturen)
Zusammenhängend
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)
Disjunkt
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.)
Digraph
Strukturdiagramme sind ungerichtete Graphen und werden meist in der Chemie als topologische Deskriptoren verwendet, da die Knoten s-Bindungen repräsentieren.
Ungerichtet
Ein Graph ist vollständig, wenn alle Knoten untereinander verbunden (adjazent) sind.
Vollständig
Ein Graph ist eben, wenn sich alle Kanten kreuzungsfrei in einer Ebene anordnen lassen
Eben
Eulerscher Weg: Wenn alle Knoten einen geradzahligen Grad besitzen, läßt sich ein Graph in einer geschlossenen Linie durchlaufen (S. Königsberger Problem)
Eulerlinie

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)

Haus des Nikolaus
Isomorphismus: Bei geordneten Graphen mit n Knoten gibt es n! Darstellungsmöglichkeiten mit gleicher Gestalt (z.B. n=3 -> 6 Isomere)
Isomorphismus

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