LCF-Notation

Der Foster-Graph: Bezeichnet man den obersten Knoten mit <math>v_0</math>, 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<ref>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)</ref> zurück und wurde von H. S. M. Coxeter und Robert Frucht erweitert.<ref>H. S. M. Coxeter, R. Frucht, D. L. Powers: Zero-Symmetric Graphs: Trivalent Graphical Regular Representations of Groups. Academic Press, New York 1981.</ref> Viele Programme zur Manipulation von Graphen unterstützen LCF-Eingaben.<ref>Beispielsweise Maple, NetworkX mit generators.small.LCF_graph, <templatestyles src="Webarchiv/styles.css" />R (Memento vom 21. August 2009 im Internet Archive), <templatestyles src="Webarchiv/styles.css" />sage (Memento vom 21. August 2009 im Internet Archive) und wahrscheinlich weitere.</ref>

Syntax

Jeder LCF-Code hat folgende Form:

<math> n, \left[s_0,s_1,\dots s_k \right], p </math>

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

Interpretation: Zunächst wird ein Kreis der Länge <math>n</math> mit Knoten <math>\{v_0, v_1\dots v_n\}</math> erstellt. Beginnend bei <math>i=0</math> bis <math>i=k\cdot p</math> werden die Sehnenkanten <math>\left(v_i,v_{(s_{i~\%~k})~\%~n}\right)</math> zum Kreis hinzugefügt, falls sie noch nicht existieren. Dabei bezeichnet <math>\%</math> den Modulooperator.<ref>Siehe Dokumentation der entsprechenden Klasse von Sage.</ref>

Ein Verfahren, um umgekehrt zu einem Graphen einen LCF-Code zu berechnen, lässt sich dann leicht konstruieren.<ref>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.</ref> LCF-Notationen zu einem Graphen sind im Allgemeinen nicht eindeutig bestimmt. Sie hängen von der Wahl des Startknotens <math>v_0</math> 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 <math>v_0</math> „ganz oben“ steht.

Einige Plots mit LCF-Codes
Der Wagner-Graph: 8, [-4], 8
Der Wagner-Graph:
```
8, [-4], 8
```
Der McGee-Graph: 24, [12,7,-7], 8
Der McGee-Graph:
```
24, [12,7,-7], 8
```
Der Franklin-Graph: 12, [5,-5], 6
Der Franklin-Graph:
```
12, [5,-5], 6
```
Der Möbius-Cantor-Graph: 16, [5,-5], 8
Der Möbius-Cantor-Graph:
```
16, [5,-5], 8
```
Der Franklin-Graph: (alternative Darstellung) 12, [-5,-3,3,5], 3
Der Franklin-Graph: (alternative Darstellung)
```
12, [-5,-3,3,5], 3
```

Weblinks

Eric W. Weisstein: LCF Notation. bei MathWorld.

Einzelnachweise