Feiner Graph

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Farey-Graph

In der Graphentheorie, einem Teilgebiet der Mathematik, sind feine Graphen eine Klasse von Graphen mit gewissen lokalen Endlichkeitseigenschaften. Feine Graphen spielen eine Rolle in der geometrischen Gruppentheorie, insbesondere im Zusammenhang mit Hyperbolizität und relativer Hyperbolizität von Graphen und Gruppen.

Ein Graph heißt fein, wenn er eine (und damit jede) der folgenden äquivalenten Bedingungen erfüllt:

  • Für jede Kante und jedes gibt es nur endlich viele durch verlaufende Kreise der Länge .
  • Für alle Knoten und jedes gibt es nur endlich viele und verbindende Wege ohne sich wiederholende Knoten.
  • Für alle gibt es keine unendliche Menge und verbindender paarweise unabhängiger Wege ohne sich wiederholende Knoten der Länge . (Hierbei heißen zwei Wege unabhängig, wenn sie nur Anfangs- und Endpunkt gemeinsam haben.)
  • Wenn ein Paar unterschiedlicher Knoten und ist und eine kanten-endliche Menge zusammenhängender Teilgraphen von , die alle jeweils Knoten haben und und enthalten, dann muss endlich sein. (Hierbei heißt eine Menge kantenendlich, wenn jede Kante nur in endlich vielen Teilgraphen aus enthalten ist.)
  • Für jeden Knoten ist die Nachbarschaft lokal endlich in . (Das heißt, jeder Knoten in ist in nur zu endlich vielen Knoten aus adjazent.)
  • Lokal endliche Graphen sind fein.
  • Der Farey-Graph ist fein.