imported>MacOrcas: Link

2024-11-08T18:13:55Z

Link

Neue Seite

Die '''Moser-Spindel''' ist ein [[Graph (Graphentheorie)|Graph]], der nach den Gebrüdern [[William Oscar Jules Moser|William Oscar Jules]] und [[Leo Moser (Mathematiker)|Leo Moser]] benannt wurde.<ref>{{Literatur|Autor = W. und L. Moser|Titel=Solution to problem 10|Sammelwerk=Can. Math. Bull.|Band=4|Jahr=1961|Seiten=187–189}}</ref> Es handelt sich dabei um einen [[Ungerichteter Graph|ungerichteten Graphen]] mit sieben Knoten und elf Kanten. Die Moser-Spindel lässt sich als [[Einheitsdistanz-Graph]] und als [[ebener Graph]] in die [[Ebene (Mathematik)|Ebene]] einbetten, ist jedoch kein [[Streichholzgraph]]. Eine ihrer Anwendungen ist der Beweis, dass die [[chromatische Zahl]] der Ebene größer oder gleich vier ist.<ref name = "soifer">{{Literatur|Autor = A. Soifer|Titel = The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators|Jahr = 2008| Ort = New York| Verlag = Springer| Seiten = 14–15 | ISBN = 978-0387746401}}</ref> Damit erhält man eine untere Schranke für das [[Hadwiger-Nelson-Problem]].

Die Moser-Spindel ist auch unter dem Namen ''Hajós-Graph'' (nach [[György Hajós]]) bekannt.<ref>{{Literatur|Titel=Graph Theory|Autor=J. A. Bondy, U. S. R. Murty|Verlag=Springer|Sammelwerk=Graduate Texts in Mathematics|Jahr=2008|Band=244|DOI=10.1007/978-1-84628-970-5|Seiten=358}}</ref>

== Konstruktion ==
[[Datei:Hajos construction.svg|miniatur|Hajós-Konstruktion der Moser-Spindel]]
Die Moser-Spindel lässt sich mit geometrischen Mitteln, oder, alternativ dazu, auch mit rein graphentheoretischen Überlegungen konstruieren.

Ausgangspunkt für die geometrische Konstruktion ist ein gleichseitiges Dreieck der Kantenlänge eins, welches an einer seiner Seiten gespiegelt wird. Die entstandene Figur ist eine [[Raute]] mit den Innenwinkeln 60° und 120°. Zwei solcher Rauten werden nun so in der Ebene positioniert, dass sie sich einen spitzwinkligen Eckpunkt teilen und die beiden jeweils gegenüberliegenden Ecken voneinander den Einheitsabstand haben. Die elf Kanten des Graphen entsprechen den Seiten der gleichseitigen Dreiecken und der Strecke zwischen den beiden spitzwinkligen Ecken der Rauten.

Rein graphentheoretisch lässt sich die Moser-Spindel mittels der [[Hajós-Konstruktion]], ausgehend von zwei [[Vollständiger Graph|vollständigen Graphen]] ''K4'' konstruieren. Bei dieser Konstruktion wird von beiden Graphen jeweils eine Kante entfernt. Von den jeweiligen Endpunkten dieser entfernten Kante wird ein Paar zusammengelegt und das andere Paar mit einer neuen Kante verbunden.<ref name="hajos">{{Literatur|Autor = G. Hajós|Titel=Über eine Konstruktion nicht n-färbbarer Graphen|Sammelwerk=Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe|Band=10|Seiten=116–117|Jahr=1961}}</ref>

== Anwendung auf das Hadwiger–Nelson-Problem ==
[[Datei:Hadwiger-Nelson.svg|miniatur|Die Moser-Spindel als Einheits-Distanzgraph in der Ebene; zusammen mit der 7-Färbung der Ebene]]
Das [[Hadwiger-Nelson-Problem]] untersucht die minimal benötigte Anzahl an [[Farbe (Graphentheorie)|Farben]], um eine Ebene derart einzufärben, dass jeweils zwei Punkte mit Einheitsabstand unterschiedliche Farben besitzen. Gesucht ist also die chromatische Zahl jenes Einheitsdistanz-Graphen, dessen Knoten alle Punkte der Ebene sind.<ref name = "soifer" /> Die Moser-Spindel ist ein [[Teilgraph]] jenes Graphen. Daraus folgt, dass man für die Färbung der Ebene mindestens so viele Farben benötigt wie zur Färbung der Moser-Spindel.

Es kann gezeigt werden, dass die chromatische Zahl der Moser-Spindel vier beträgt: Da die Moser-Spindel Dreiecke beinhaltet, sind mindestens drei Farben notwendig. Nimmt man an, dass bereits drei Farben ausreichen, dann haben der Knoten, den sich beide Rauten teilen, sowie die beiden jeweils gegenüberliegenden Eckpunkte der Rauten dieselbe Farbe. Dies führt zu einem Widerspruch. Vier Farben reichen jedoch aus, um die Moser-Spindel einzufärben.<ref name="hajos" />

Vier ist damit eine untere Schranke für die chromatische Zahl der Ebene.

Der [[Auswahlprinzip_von_Rado#Einige_Folgerungen|Satz von de Bruijn–Erdős]] besagt, dass unter der Voraussetzung des [[Auswahlaxiom]]s die chromatische Zahl eines unendlichen Graphen gleich der größten chromatischen Zahl eines endlichen Teilgraphen ist. Bis 2018 war kein endlicher Teilgraph bekannt, der mehr Farben als die Moser-Spindel benötigt. Die beste bekannte obere Schranke für das Hadwiger–Nelson-Problem beträgt sieben.<ref name = "soifer" />

== Weitere Eigenschaften ==
Die Moser-Spindel ist ein [[Laman-Graph]], das heißt, sie ist ein minimaler [[starrer Graph]] in der Ebene.<ref name = "horvat" />

Der zu der Moser-Spindel [[komplementärer Graph|komplementäre Graph]] ist ein [[dreiecksfreier Graph]]. Daraus folgt, dass unter drei Knoten der Moser-Spindel (betrachtet als Einheitsdistanz-Graph) immer mindestens ein Knotenpaar ist, das voneinander Einheitsabstand hat.<ref name = "soifer" /><ref>{{Literatur|Autor = Peter Winkler| Titel = Puzzled: Distances Between Points on the Plane| Sammelwerk = Communications of the ACM|Band = 54| Nummer = 11| DOI = 10.1145/2018396.2018422}}</ref>

Beim Hinzufügen von weiteren Kanten geht stets die Einheitsdistanz-Eigenschaft verloren. Außerdem gibt es keinen [[Homomorphismus|Graphenhomomorphismus]], der die Moser-Spindel auf einen kleineren Einheitsdistanz-Graph abbildet. Diese beiden Eigenschaften wurden von Horvat, Kratochvíl und Pisanski verwendet, um zu beweisen, dass das Testen, ob ein gegebener Graph eine Einbettung als Einheitsdistanz-Graph hat, ein [[NP-schwer]]es Problem ist.<ref name = "horvat">{{Literatur| Autor = Boris Horvat, Jan Kratochvíl, Tomaž Pisanski| Titel = On the Computational Complexity of Degenerate Unit Distance Representations of Graphs| Sammelwerk = Lecture Notes in Computer Science| Jahr = 2011| Band = 6460| Seiten = 274–285}}</ref>

Eine n-dimensionale Verallgemeinerung der Moser-Spindel spielt eine wichtige Rolle bei dem Beweis des [[Satz von Beckman und Quarles|Satzes von Beckman und Quarles]].<ref> {{Literatur | Autor=W. Benz | Titel=Geometrische Transformationen unter besonderer Berücksichtigung der Lorentztransformation | Verlag=BI-Wiss.-Verl. | Ort=Mannheim (u. a.) | Jahr=1992 | ISBN=3411150718 | Seiten=15-31}}</ref>

== Einzelnachweise ==
<references />

[[Kategorie:Planarer Graph]]
[[Kategorie:Geometrischer Graph]]

Moser-Spindel - Versionsgeschichte

imported>MacOrcas: Link