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^[1] zurück und wurde von H. S. M. Coxeter und Robert Frucht erweitert.^[2] Viele Programme zur Manipulation von Graphen unterstützen LCF-Eingaben.^[3]

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

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

eine zugehörige LCF-Notation.

Syntax

Jeder LCF-Code hat folgende Form:

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

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

Interpretation

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

Ein Verfahren, um umgekehrt zu einem Graphen einen LCF-Code zu berechnen, lässt sich dann leicht konstruieren.^[5] LCF-Notationen zu einem Graphen sind im Allgemeinen nicht eindeutig bestimmt. Sie hängen von der Wahl des Startknotens ${\displaystyle 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 ${\displaystyle 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.