Topologie
mathematisches Gebiet, wo Lagebeziehungen untersucht werden unter Weglassung metrischer Größen (Längen, Winkel).
Typische topologische Begriffe:
Zwei geometrische Strukturen sind topologisch gleichwertig (isomorph), wenn sie durch plastische Verformung (ohne Durchschneiden oder Zusammenkleben von Teilen) ineinander überführt werden können.
Als eigenständiges Gebiet aus der Topologie und aus der Kombinatorik hervorgegangen:
Graphentheorie
Ein
Graph besteht aus einer Menge von Ecken (Knotenpunkten, vertices ) und einer Menge von (gerichteten oder ungerichteten) Kanten (edges, links ), die je zwei Ecken verbinden.Beispiel für zwei isomorphe Graphen:
Gerichtete Graphen
(Digraphen, directed graphs ):Ein
Baum ist ein Graph ohne Kreise (geschlossene Ketten aufeinanderfolgender Kanten).Ein
Wurzelbaum ist ein Baum mit einer besonders ausgezeichneten Ecke, der Basisecke.Jeder Wurzelbaum kann mit einer "natürlichen Orientierung" der Kanten versehen werden, indem alle Kanten "von der Basisecke weg" orientiert werden.
Der
Grad (degree ) einer Ecke ist die Anzahl der Kanten, die diese Ecke berühren. Eingangsgrad (indegree ): Anzahl der dort endenden, Ausgangsgrad (outdegree ): Anzahl der dort ausgehenden Kanten.In einem binären Wurzelbaum ( = alle Ausgangsgrade 2 oder 0) gilt, wenn vi die Anzahl der Ecken mit Ausgangsgrad i und v die Gesamtzahl der Ecken ist:
v
= 2v0 – 1.Im allgemeinen Fall (d.h. nicht notwendig binärer Wurzelbaum) gilt:
v
= 2v0 – 1 + D,wobei 
("
Ein
Pfad (path) in einem gerichteten Graphen ist eine Kette aufeinanderfolgender, in gleicher Richtung durchlaufener Kanten (im obigen Beispiel etwa acf ).Die
topologische Tiefe (topological depth) einer Ecke in einem Wurzelbaum ist die Länge des Pfades von der Basisecke zu der jeweiligen Ecke. ("Länge": hier gemessen als Anzahl der Kanten, nicht metrisch!)Die
maximale topologische Tiefe (auch: "Höhe", engl. "altitude ") a eines Wurzelbaumes ist die maximale Länge eines von der Basisecke ausgehenden Pfades.Die
mittlere topologische Tiefe b ist das arithmetische Mittel der topologischen Tiefen aller Ecken mit Ausgangsgrad 0 (Außenecken, terminal oder exterior vertices).2 Extremfälle binärer
Wurzelbäume:
Zur Normierung gewinnt man aus a und b die folgenden
topologischen Indices qa und qb, deren Werte für binäre Wurzelbäume stets zwischen 0 und 1 liegen (0 = rein dichotom, 1 = Fischgräten-Muster):
,
darin ist lb v0 (= ln v0 / ln 2) der binäre Logarithmus (Logarithmus zur Basis 2).
Die 6 nichtisomorphen (topologisch unterschiedlichen)
binären Wurzelbäume mit v0 = 6 terminalen
Ecken
Die beiden Graphen oben links lassen sich weder durch a noch durch b unterscheiden. b unterscheidet die anderen Graphen genauer als a.
Zurück zum Plan des Veranstaltungs-Blocks
Back to Plant Modelling Group homepage
Last modification: May 11, 2001