Quelltext der Seite Einheitsdistanz-Graph

[[Datei:Petersen graph, unit distance.svg|150px|mini|Der [[Petersen-Graph]] ist ein Einheitsdistanz-Graph: er kann so gezeichnet werden, dass jede Kante gleich lang ist.]]

Ein '''Einheitsdistanz-Graph''' ist ein [[geometrischer Graph]], bei dem jede [[Kante (Graphentheorie)|Kante]] gleich lang ist.
Kanten eines Einheitsdistanz-Graphen dürfen sich überschneiden, d.&nbsp;h. der Graph muss nicht immer [[Planarer Graph|planar]] sein. Ein Einheitsdistanz-Graph ohne Überschneidungen wird [[Streichholzgraph]] genannt.

Das [[Problem von Hadwiger und Nelson]] beschäftigt sich mit der [[Chromatische Zahl|chromatischen Zahl]] des Graphen. Jeder Einheitsdistanz-Graph kann mit höchstens sieben [[Farbe (Graphentheorie)|Farben]] [[Färbung (Graphentheorie)|eingefärbt]] werden, bekanntlich existieren aber auch einige Graphen, die mindestens vier Farben benötigen. Ein anderes bekanntes [[Ungelöste Probleme der Mathematik|offenes Problem]] befasst sich mit der Frage, wie hoch das Verhältnis von Kanten- zu Knotenanzahl sein kann.

== Beispiele ==
[[Datei:Hypercubestar.svg|mini|150px|[[Hyperwürfel-Graph]] ''Q''<sub>4</sub> als Einheitsdistanz-Graph.]]
Folgende Graphen sind Einheitsdistanz-Graphen:
* Jeder [[Zyklischer Graph|zyklische Graph]]
* Jeder [[Gittergraph]]
* Jeder [[Hyperwürfel-Graph]]
* Der [[Petersen-Graph]]
* Der [[Heawood-Graph]]
* Das [[Wagenrad (Graph)|Wagenrad]] ''W''<sub>7</sub>

== Strikter Einheitsdistanz-Graph ==
[[Datei:Möbius–Kantor unit distance.svg|150px|mini|Einheitsdistanz-Variante des [[Möbius–Kantor-Graph]]en, bei dem einige nicht benachbarte Knoten ebenfalls eine Einheitsdistanz haben.]]
Einige Definitionen in der Literatur lassen die Möglichkeit zu, dass nicht benachbarte Knotenpaare ebenfalls Einheitsdistanz haben dürfen. Zum Beispiel gibt es eine Variante des [[Möbius–Kantor-Graph]]en von dieser Art.

Nach dieser abgeschwächten Definition sind alle [[Verallgemeinerter Petersen-Graph|verallgemeinerten Petersen-Graphen]] Einheitsdistanz-Graphen.<ref>Žitnik, Horvat und Pisanski, 2010.</ref> Um beide Definitionen zu unterscheiden, wird ein Graph, bei dem nur benachbarte Knoten eine Einheitsdistanz haben dürfen, '''strikter Einheitsdistanz-Graph''' genannt.<ref>Gervacio, Lim und Maehara, 2008.</ref>

Entfernt man beim [[Wagenrad (Graph)|Wagenrad]] ''W''<sub>7</sub> eine Speiche, erhält man einen nicht-strikten [[Teilgraph]]en. Es ist nicht möglich, die Knoten und insbesondere die beiden Endpunkte der fehlenden Speiche so anzuordnen, dass man wieder einen strikten Graphen erhält.<ref>Soifer, 2008, S. 94.</ref>

== Zählung von Einheitsdistanzen ==
[[Paul Erdős]] stellte 1946 das Problem, wie man in einer Menge von ''n'' Punkten die Anzahl an Punktpaaren mit Einheitsdistanz bestimmt. [[Graphentheorie|Graphentheoretisch]] formuliert: wie [[Dichte (Graphentheorie)|dicht]] kann ein Einheitsdistanz-Graph sein?

Der Hyperwürfel-Graph besitzt für die Anzahl an Einheitsdistanzen eine untere Schranke proportional zu {{nowrap|n·log n}}. Werden die Punkte in einem [[Quadratgitter]] mit vorsichtig gewählten Zwischenräumen angeordnet, gibt es nach Erdős eine verbesserte untere Schranke von

:<math>n^{1+c/\log\log n},</math>

Erdős bot ein Preisgeld von {{nowrap|500 $}}, falls jemand eine ähnliche Funktion für die obere Schranke findet.<ref>Kuperberg, 1992.</ref> Die beste bekannte obere Schranke<ref>Joel Spencer, Endre Szemerédi und William Trotter, 1984.</ref> liegt bisher proportional zu

:<math>n^{4/3};</math>

Diese Grenze kann auch als Zählung der [[Inzidenz (Geometrie)|Inzidenzen]] zwischen Punkten und [[Einheitskreis]]en betrachtet werden und ist nah mit dem [[Satz von Szemerédi und Trotter]] für Inzidenzen zwischen Punkten und [[Gerade]]n verwandt. Das Problem (Einheitsdistanz-Problem von Erdös) ist nach wie vor offen. Erdös vermutete, dass die Anzahl der Punkte mit Einheitsdistanz in der Größenordnung der unteren Schranke war.<ref>Endre Szemeredi, Erdös unit distance problem, in: John Forbes Nash jr., Michael Th. Rassias (Hrsg.), Open problems in mathematics, Springer 2016, S. 459–478</ref>

== Verallgemeinerung für höhere Dimensionen ==
Die Definition des Einheitsdistanz-Graphen kann selbstverständlich auch auf höherdimensionale [[Euklidischer Raum|euklidische Räume]] verallgemeinert werden. Jeder Graph kann als Punktmenge in eine genügend hohe Dimension eingebettet werden. Maehara und [[Vojtěch Rödl]] zeigten 1990, dass die notwendige Dimension um einen Graph auf diese Weise einzubetten durch den doppelten Maximalgrad des Graphen beschränkt ist.

Die notwendige Dimension um einen Graphen so einzubetten, dass alle Kanten Einheitsdistanz haben, und die notwendige Dimension um einen Graphen so einzubetten, dass alle Kanten genau den Einheitsdistanz-Paaren entsprechen, können sich stark voneinander unterscheiden: der [[Johnson-Graph]] mit {{nowrap|2·n Knoten}} kann so in die vierte Dimension eingebettet werden, dass all seine Kanten Einheitsdistanz haben, benötigt jedoch {{nowrap|n - 2}} Dimensionen für eine Einbettung, bei der nur die Kanten Einheitsdistanz-Paare sind.<ref>Erdős und Simonovits, 1980.</ref>

== Siehe auch ==
*[[Satz von Beckman und Quarles]]

== Literatur ==
* {{Literatur
   |Autor=F. S. Beckman, D. A. Quarles
   |Titel=On isometries of Euclidean spaces
   |Sammelwerk=Proceedings of the American Mathematical Society
   |Band=4
   |Datum=1953
   |Seiten=810–815
   |Online=[http://www.ams.org/mathscinet-getitem?mr=0058193 MR0058193]}}
* {{Literatur
   |Autor=[[Paul Erdős]]
   |Titel=On sets of distances of ''n'' points
   |Sammelwerk=[[American Mathematical Monthly]]
   |Band=53 (5)
   |Verlag=The American Mathematical Monthly, Vol. 53, No. 5
   |Datum=1946
   |Seiten=248–250
   |DOI=10.2307/2305092
   |JSTOR=2305092}}
* {{Literatur
   |Autor=[[Paul Erdős]], Miklós Simonovits
   |Titel=On the chromatic number of geometric graphs
   |Sammelwerk=Ars Combinatoria
   |Band=9
   |Datum=1980
   |Seiten=229–246}}
* {{Literatur
   |Autor=Eberhard H.-A. Gerbracht
   |Titel=Eleven unit distance embeddings of the Heawood graph
   |Datum=2009
   |arXiv=0912.5395}}
* {{Literatur
   |Autor=Severino V. Gervacio, Yvette F. Lim, Hiroshi Maehara
   |Titel=Planar unit-distance graphs having planar unit-distance complement
   |Sammelwerk=Discrete Mathematics
   |Band=308 (10)
   |Datum=2008
   |Seiten=1973–1984
   |DOI=10.1016/j.disc.2007.04.050}}
* {{Literatur
   |Autor=[[Greg Kuperberg]]
   |Titel=The Erdos kitty: At least $9050 in prizes!
   |Datum=1992
   |Kommentar=Posting in der Usenet-Gruppe rec.puzzles and sci.math}}
* {{Literatur
   |Autor=Hiroshi Maehara
   |Titel=Distances in a rigid unit-distance graph in the plane
   |Sammelwerk=Discrete Applied Mathematics
   |Band=31 (2)
   |Datum=1991
   |Seiten=193–200
   |DOI=10.1016/0166-218X(91)90070-D}}
* {{Literatur
   |Autor=Hiroshi Maehara
   |Titel=Extending a flexible unit-bar framework to a rigid one
   |Sammelwerk=Discrete Mathematics
   |Band=108 (1–3)
   |Datum=1992
   |Seiten=167–174
   |Online=[http://www.ams.org/mathscinet-getitem?mr=1189840 MR1189840]
   |DOI=10.1016/0012-365X(92)90671-2}}
* {{Literatur
   |Autor=Hiroshi Maehara, Vojtech Rödl
   |Titel=On the dimension to represent a graph by a unit distance graph
   |Sammelwerk=Graphs and Combinatorics
   |Band=6 (4)
   |Datum=1990
   |Seiten=365–367
   |DOI=10.1007/BF01787703}}
* {{Literatur
   |Autor=[[Alexander Soifer]]
   |Titel=The Mathematical Coloring Book
   |Verlag=Springer-Verlag
   |Datum=2008
   |ISBN=978-0-387-74640-1}}
* {{Literatur
   |Autor=[[Joel Spencer]], [[Endre Szemerédi]], William T. Trotter
   |Titel=Unit distances in the Euclidean plane
   |Sammelwerk=Graph Theory and Combinatorics
   |Verlag=Academic Press
   |Datum=1984
   |Seiten=293–308}}
* {{Literatur
   |Autor=Apoloniusz Tyszka
   |Titel=Discrete versions of the Beckman-Quarles theorem
   |Sammelwerk=Aequationes Mathematicae
   |Band=59 (1–2)
   |Datum=2000
   |Seiten=124–133
   |Online=[http://www.ams.org/mathscinet-getitem?mr=1741475 MR1741475]
   |DOI=10.1007/PL00000119}}
* {{Literatur
   |Autor=Arjana Žitnik, Boris Horvat, [[Tomaž Pisanski]]
   |Titel=All generalized Petersen graphs are unit-distance graphs
   |Band=1109
   |Datum=2010
   |Kommentar=IMFM preprints
   |Online=[http://www.imfm.si/preprinti/PDF/01109.pdf online]
   |Format=PDF
   |KBytes=377}}

== Weblinks ==
* {{Internetquelle |autor=Suresh Venkatasubramanian |url=http://maven.smith.edu/~orourke/TOPP/P39.html |titel=Problem 39: Distances among Point Sets in '''R'''<sup>2</sup> and '''R'''<sup>3</sup> |werk=The Open Problems Project |abruf=2011-10-16}}
* {{MathWorld | title = Unit-Distance Graph | id = Unit-DistanceGraph}}

== Einzelnachweise ==
<references />

[[Kategorie:Geometrischer Graph]]