LCF-Notation

Der Foster-Graph: Bezeichnet man den obersten Knoten mit $v_{0}$, dann ist

90, [17,-9,37,-37,9,-17], 15

eine zugehörige LCF-Notation.

In der Kombinatorik als Teilgebiet der diskreten Mathematik ist die Lederberg-Coxeter-Fruchte-Notation (kurz LCF) eine kompakte Darstellung endlicher kubischer hamiltonscher Graphen. Die Notation geht auf Joshua Lederberg zurück und wurde von H. S. M. Coxeter und Robert Frucht erweitert. Viele Programme zur Manipulation von Graphen unterstützen LCF-Eingaben.

Syntax

Jeder LCF-Code hat folgende Form:

$n,\left[s_{0},s_{1},\dots s_{k}\right],p$

Dabei ist $n=|V|$ die Zahl der Knoten, die $s_{i}$ sind Elemente aus einem vollständigen System kleinster Reste modulo $n$ ohne die Null (mit anderen Worten ganze Zahlen aus $\left[-\left\lfloor {\frac {|V|}{2}}\right\rfloor ,\left\lfloor {\frac {|V|}{2}}\right\rfloor \right]\setminus \{0\}\subset \mathbb {Z}$) und $p\in \mathbb {N}$ ist ein Iterationsparameter, so dass $k\cdot p=n$. In gedruckten Publikationen schreibt man auch $\left[s_{0},s_{1}\dots s_{k}\right]^{p}$.

Interpretation

Zunächst wird ein Kreis der Länge $n$ mit Knoten $\{v_{0},v_{1}\dots v_{n}\}$ erstellt. Beginnend bei $i=0$ bis $i=k\cdot p$ werden die Sehnenkanten $\left(v_{i},v_{(s_{i~\%~k})~\%~n}\right)$ zum Kreis hinzugefügt, falls sie noch nicht existieren. Dabei bezeichnet $\%$ den Modulooperator.

Ein Verfahren, um umgekehrt zu einem Graphen einen LCF-Code zu berechnen, lässt sich dann leicht konstruieren. LCF-Notationen zu einem Graphen sind im Allgemeinen nicht eindeutig bestimmt. Sie hängen von der Wahl des Startknotens $v_{0}$ und von der Wahl des Hamiltonkreises ab (dort hat man stets wenigstens die Wahl einer Orientierung). Umgekehrt kann es aber zu jeder LCF-Notation nur einen, bis auf Isomorphie, eindeutigen Graphen geben. Stellt man LCF-Code zusammen mit einem Plot dar, ist es Konvention, die Knoten, wenn sie nicht nummeriert sind, entlang des gewählten Hamiltonkreises „kreisförmig“ (genauer polygonal) zu setzen, wobei der Knoten $v_{0}$ „ganz oben“ steht.

• Einige Plots mit LCF-Codes
• 
  Der Wagner-Graph:

  8, [-4], 8

• 
  Der McGee-Graph:

  24, [12,7,-7], 8

• 
  Der Franklin-Graph:

  12, [5,-5], 6

• 
  Der Möbius-Cantor-Graph:

  16, [5,-5], 8

• 
  Der Franklin-Graph: (alternative Darstellung)

  12, [-5,-3,3,5], 3

Weblinks

• Eric W. Weisstein: LCF Notation. bei MathWorld.