Hyperbolischer Graph

In d​er Mathematik s​ind hyperbolische Graphen i​n Graphentheorie, Geometrie u​nd Gruppentheorie v​on Bedeutung.

Definition

Es sei ${\displaystyle X=(V,E)}$ ein zusammenhängender Graph. Wir identifizieren jede Kante mit dem Einheitsintervall und machen den Graphen damit zu einem metrischen Raum. (Der Abstand zweier Knoten ist also die Anzahl der Kanten eines minimalen Verbindungsweges.)

Der Graph heißt hyperbolisch wenn es ein ${\displaystyle \delta \geq 0}$ gibt, so dass für alle Tripel von Knoten ${\displaystyle v_{1},v_{2},v_{3}}$ und alle kürzesten Verbindungswege ${\displaystyle w_{ij}}$ von ${\displaystyle v_{i}}$ nach ${\displaystyle v_{j}}$ für ${\displaystyle i,j\in \left\{1,2,3\right\}}$ gilt:

${\displaystyle w_{12}}$ liegt in der ${\displaystyle \delta }$ -Umgebung von ${\displaystyle w_{13}\cup w_{23}}$

${\displaystyle w_{13}}$ liegt in der ${\displaystyle \delta }$ -Umgebung von ${\displaystyle w_{12}\cup w_{23}}$

${\displaystyle w_{23}}$ liegt in der ${\displaystyle \delta }$ -Umgebung von ${\displaystyle w_{12}\cup w_{13}}$

Beispiele

• Endliche Graphen sind hyperbolisch, man kann für ${\displaystyle \delta }$ den Durchmesser des Graphen wählen.
• Bäume sind hyperbolisch, man kann ${\displaystyle \delta =0}$ wählen.
• Der Farey-Graph ist hyperbolisch, man kann ${\displaystyle \delta =1}$ wählen.
• Cayley-Graphen hyperbolischer Gruppen sind (per Definitionem) hyperbolisch.

Weblinks

• Hyperbolic graphs, fractal boundaries and graph limits (PDF; 5,4 MB)