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

v_{0}

, dann ist

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

eine zugehörige LCF-Notation.

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.[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 $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.

Einzelnachweise

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)
H. S. M. Coxeter, R. Frucht, D. L. Powers: Zero-Symmetric Graphs: Trivalent Graphical Regular Representations of Groups. Academic Press, New York 1981.
Beispielsweise Maple, NetworkX mit generators.small.LCF_graph, R, sage (Memento vom 21. August 2009 im Internet Archive) und wahrscheinlich weitere.
Siehe Dokumentation der entsprechenden Klasse von Sage.
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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.

[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, 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.