imported>DynaMoToR: /* Einzelnachweise */

2024-04-15T04:34:48Z

Einzelnachweise

Neue Seite

[[Datei:Foster graph hamiltonian.png|mini|Der [[Foster-Graph]]: Bezeichnet man den obersten Knoten mit <math>v_0</math>, dann ist
<pre>
90, [17,-9,37,-37,9,-17], 15
</pre>
eine zugehörige LCF-Notation.]]

In der [[Kombinatorik]] als Teilgebiet der [[Diskrete Mathematik|diskreten Mathematik]] ist die '''Lederberg-Coxeter-Fruchte-Notation''' (kurz '''LCF''') eine kompakte Darstellung endlicher [[Kubischer Graph|kubischer]] [[hamiltonsch]]er [[Graphentheorie|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. [http://profiles.nlm.nih.gov/BB/A/B/I/U/_/bbabiu.pdf] (PDF)</ref> zurück und wurde von [[Harold Scott MacDonald Coxeter|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 [http://www.maplesoft.com/support/help/AddOns/view.aspx?path=GraphTheory/SpecialGraphs/LCFGraph Maple], [[NetworkX]] mit [https://networkx.github.io/documentation/stable/reference/generated/networkx.generators.small.LCF_graph.html#networkx.generators.small.LCF_graph generators.small.LCF_graph], {{Webarchiv|url=http://igraph.sourceforge.net/doc/R/graph.lcf.html |wayback=20090821090801 |text=R }}, {{Webarchiv|url=http://sage.math.washington.edu/home/mhansen/sage-epydoc/sage.graphs.graph_generators.GraphGenerators-class.html|text=sage|wayback=20090821090801}} 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ändiges Restesystem|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 [http://www.sagemath.org/doc/reference/sage/graphs/graph_generators.html?highlight=lcf#sage.graphs.graph_generators.GraphGenerators.LCFGraph Dokumentation] der entsprechenden Klasse von [[Sage (Software)|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 von Graphen|Isomorphie]], eindeutigen Graphen geben.
Stellt man LCF-Code zusammen mit einem [[Plotter|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.

<gallery caption="Einige Plots mit LCF-Codes" perrow="5">
Wagner graph ham.png|Der [[Wagner-Graph]]:<pre>8, [-4], 8</pre>
MC Gee graph hamiltonian.png|Der [[McGee-Graph]]:<pre>24, [12,7,-7], 8</pre>
Franklin graph hamiltonian.png|Der [[Franklin-Graph]]:<pre>12, [5,-5], 6</pre>
Möbius-kantor Graph hamiltonian.png|Der [[Möbius-Cantor-Graph]]:<pre>16, [5,-5], 8</pre>
franklin graph hamiltonian2.png|Der Franklin-Graph: (alternative Darstellung)<pre>12, [-5,-3,3,5], 3</pre>
</gallery>

== Weblinks ==
* Eric W. Weisstein: ''[http://mathworld.wolfram.com/LCFNotation.html LCF Notation].'' bei ''[[MathWorld]].''

== Einzelnachweise ==
<references />

{{SORTIERUNG:Lcfnotation}}
[[Kategorie:Kombinatorik]]
[[Kategorie:Graphentheorie]]
[[Kategorie:Programmiersprachen]]

LCF-Notation - Versionsgeschichte

imported>DynaMoToR: /* Einzelnachweise */