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:

${\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.

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 ${\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.

Einzelnachweise

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. (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.