mini|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 LederbergJ. 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) zurück und wurde von H. S. M. Coxeter und Robert Frucht erweitert.H. S. M. Coxeter, R. Frucht, D. L. Powers: Zero-Symmetric Graphs: Trivalent Graphical Regular Representations of Groups. Academic Press, New York 1981. Viele Programme zur Manipulation von Graphen unterstützen LCF-Eingaben.Beispielsweise Maple, NetworkX mit generators.small.LCF_graph, , und wahrscheinlich weitere.
Syntax 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.Siehe Dokumentation der entsprechenden Klasse von Sage.
Ein Verfahren, um umgekehrt zu einem Graphen einen LCF-Code zu berechnen, lässt sich dann leicht konstruieren.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. 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 Eric W. Weisstein: LCF Notation. bei MathWorld.
Einzelnachweise
Kategorie:Kombinatorik Kategorie:Graphentheorie Kategorie:Programmiersprachen