Hyperbolischer Graph

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

Definition

Es sei 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 gibt, so dass für alle Tripel von Knoten und alle kürzesten Verbindungswege von nach für gilt:

liegt in der -Umgebung von
liegt in der -Umgebung von
liegt in der -Umgebung von

Beispiele

  • Endliche Graphen sind hyperbolisch, man kann für den Durchmesser des Graphen wählen.
  • Bäume sind hyperbolisch, man kann wählen.
  • Der Farey-Graph ist hyperbolisch, man kann wählen.
  • Cayley-Graphen hyperbolischer Gruppen sind (per Definitionem) hyperbolisch.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.