LCF-Notation

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Der Foster-Graph: Bezeichnet man den obersten Knoten mit , 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[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]

Syntax[Bearbeiten | Quelltext bearbeiten]

Jeder LCF-Code hat folgende Form:


Dabei ist die Zahl der Knoten, die sind Elemente aus einem vollständigen System kleinster Reste modulo ohne die Null (mit anderen Worten ganze Zahlen aus ) und ist ein Iterationsparameter, so dass . In gedruckten Publikationen schreibt man auch .

Interpretation
Zunächst wird ein Kreis der Länge mit Knoten erstellt. Beginnend bei bis werden die Sehnenkanten 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 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 „ganz oben“ steht.

Weblinks[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Lederberg, J. "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. December 15, 1965. (PDF).
  2. Coxeter, H. S. M.; Frucht, R.; and Powers, D. L. Zero-Symmetric Graphs: Trivalent Graphical Regular Representations of Groups. New York: Academic Press, 1981.
  3. Beispielsweise Maple, NetworkX (Memento vom 16. Juli 2011 im Internet Archive), R, sage 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 Journal of Graph Theory 1, 46 - 60 (1976)