Feiner Graph
Definition
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.)
Beispiele
- Lokal endliche Graphen sind fein.
- Der Farey-Graph ist fein.