Ungerichteter Graph/Geometrische Realisierung/Achsen/Einführung/Textabschnitt

Es sei ${}(V,E)$ ein Graph. Wir realisieren die Knotenmenge als Menge der Standardvektoren ${}e_{v}$ ${}v\in V$, im reellen Vektorraum ${}\mathbb {R} ^{V}$, also der Menge aller ${}V$-Tupel mit Werten in ${}\mathbb {R}$. Der Vektor ${}e_{v}$ hat also an der Stelle ${}v$ den Wert ${}1$ und an den anderen Stellen den Wert ${}0$. Eine Kante zwischen zwei Knotenpunkten ${}u$ und ${}v$ realisieren wir als die Strecke

$se_{u}+(1-s)e_{v},\,s\in [0,1].$

Diese Strecke enthält ${}e_{u}$ und ${}e_{v}$ als Endpunkte, für ${}s=0$ bzw. ${}s=1$. Diese beiden Endpunkte sind zugleich die einzigen Punkte dieser Strecke, bei denen nur eine Koordinate von ${}0$ verschieden ist, bei den anderen Punkten der Strecke sind zwei Koordinaten von ${}0$ verschieden, nämlich die ${}u$- und die ${}v$-Koordinate. Die Strecken zu verschiedenen Kanten haben allenfalls einen Endpunkt gemeinsam, und dies ist genau dann der Fall, wenn die zugrunde liegenden Kanten im Graphen einen gemeinsamen Knotenpunkt besitzen. D.h. es liegt insbesondere eine (überschneidungsfreie) geometrische Realisierung des Graphen im Sinne der folgenden Definition vor.

Definition

Es sei ${}G=(V,E)$ ein Graph. Eine (überschneidungsfreie) geometrische Realisierung von ${}G$ im ${}\mathbb {R} ^{d}$ besteht aus folgenden Daten.

1. Eine injektive Abbildung

   $V\longrightarrow \mathbb {R} ^{d},\,v\longmapsto P_{v},$

   zu jedem Knotenpunkt ${}v\in V$ gibt es also einen Punkt ${}P_{v}\in \mathbb {R} ^{d}$ und verschiedene Knotenpunkte besitzen verschiedene Realisierungen ${}P_{v}$.

2. Zu jeder Kante ${}L=\{u,v\}\in E$ eine injektive stetige Abbildung

   $\varphi _{L}\colon [0,1]\longrightarrow \mathbb {R} ^{d}$

   mit ${}\varphi _{L}(0)=P_{u}$ und ${}\varphi _{L}(1)=P_{v}$.

3. Für verschiedene Kanten ${}L\neq L'$ ist

   ${}\varphi _{L}(]0,1[)\cap \varphi _{L'}(]0,1[)=\emptyset \,.$

Zu einer jeden Kante in ${}G$ gibt es also einen injektiven stetigen Verbindungsweg zwischen den zugehörigen geometrischen Punkten. Man bezeichnet diese stetigen Abbildungen als stetige Wege, manchmal auch die Bilder davon. Diese (Bilder der) Wege sind untereinander überschneidungsfrei in dem Sinne, dass allenfalls die geometrischen Endpunkte identisch sind. Letzteres liegt genau dann vor, wenn die beiden zugrunde liegenden Kanten einen gemeinsamen Endpunkt besitzen. Die oben beschriebene geometrische Realisierung des Graphen im ${}\mathbb {R} ^{V}$ heißt Standardrealisierung. Sie ist hochdimensional, eine sinnvolle Fragestellung ist, in welcher niedrigeren Dimension man einen Graphen ebenfalls realisieren kann.