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]

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

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

1. ↑ J. Lederberg: DENDRAL-64: A System for Computer Construction, Enumeration and Notation of Organic Molecules as Tree Structures and Cyclic Graphs. Part II: Topology of Cyclic Graphs. Interim Report to the National Aeronautics and Space Administration. Grant NsG 81-60. 15. Dezember 1965. [1] (PDF)
2. ↑ H. S. M. Coxeter, R. Frucht, D. L. Powers: Zero-Symmetric Graphs: Trivalent Graphical Regular Representations of Groups. Academic Press, New York 1981.
3. ↑ Beispielsweise Maple, NetworkX mit generators.small.LCF_graph, R (Memento vom 21. August 2009 im Internet Archive), sage (Memento vom 21. August 2009 im Internet Archive) und wahrscheinlich weitere.
4. ↑ Siehe Dokumentation der entsprechenden Klasse von Sage.
5. ↑ Ansonsten kann man es hier nachlesen: R. Frucht: A Canonical Representation of Trivalent hamiltonian Graphs. In: Journal of Graph Theory. 1, 1976, S. 46–60.