imported>Mikematics: Grammatik: doppeltes Wort gelöscht.

2024-02-13T19:46:24Z

Grammatik: doppeltes Wort gelöscht.

Neue Seite

[[Datei:Harborth graph vector.svg|mini|Der Harborth-Graph, kleinstes bekanntes Beispiel eines 4-regulären Streichholzgraphen]]
[[Datei:Vogel-Dinkelacker-Winkler-Graph.svg|mini|4-regulärer Streichholzgraph mit 54 Knoten]]
[[Datei:Winkler-Graph.svg|mini|4-regulärer Streichholzgraph mit 57 Knoten]]
[[Datei:4-regular matchstick graph with 60 vertices.svg|mini|4-regulärer Streichholzgraph mit 60 Knoten]]
Ein '''Streichholzgraph''' ist in der [[Geometrische Graphentheorie|geometrischen Graphentheorie]] ein in der Ebene gezeichneter [[Graph (Graphentheorie)|Graph]], bei dem alle [[Kante (Graphentheorie)|Kanten]] dieselbe Länge haben und sich nicht überschneiden. Anders ausgedrückt handelt es sich dabei um einen Graphen, der gleichzeitig eine [[Einbettung (Mathematik)|Einbettung]] als [[Einheitsdistanz-Graph]] und als [[planarer Graph]] hat. Der Name lässt sich darauf zurückführen, dass man solche Graphen auf einer flachen Oberfläche mit [[Streichholz|Streichhölzern]] nachbilden kann.<ref name="mmg">{{MathWorld | title = Matchstick Graph | id = MatchstickGraph}}</ref>

Es gibt einige Streichholzgraphen, die bis zum vierten [[Grad (Graphentheorie)|Grad]] [[Regulärer Graph|regulär]] sind. Die [[Vollständiger Graph|vollständigen Graphen]] ''K''1 und ''K''3 sind 0-regulär bzw. 2-regulär, dagegen ist der [[Linearer Graph|lineare Graph]] ''P''2 1-regulär. Den kleinsten 3-regulären Streichholzgraphen erhält man, indem man zwei Kopien des [[Diamantgraph]]en leicht geneigt nebeneinander auf die Spitze stellt und die Knoten mit Grad 2 jeweils durch eine Kante verbindet. Dieser Graph besitzt als [[bipartite Doppelüberdeckung]] den 8-[[Gekreuzter Prismagraph|gekreuzten Prismagraphen]].<ref name="mmg" />

1986 stellte [[Heiko Harborth]] einen Graphen mit 104 Kanten und 52 Knoten vor, der als kleinstes bekanntes Beispiel eines 4-regulären Streichholzgraphen gilt und der nach ihm den Namen '''Harborth-Graph''' trägt.<ref name="mhg">{{Literatur |Autor= [[Heiko Harborth]] |Hrsg=R. K. Guy, R. E. Woodrow |Titel=Match sticks in the plane |Sammelwerk=The Lighter Side of Mathematics: Proceedings of the Eugéne Strens Memorial Conference of Recreational Mathematics and its History, Calgary, Canada, 1986 |Verlag= [[Mathematical Association of America]] |Ort=Washington D.C. |Datum=1994 |Seiten=281–288}}</ref>
Dabei handelt es sich um einen [[Starrer Graph|starren Graphen]].<ref>{{Literatur |Autor=E. H.-A. Gerbracht |Titel=Minimal polynomials for the coordinates of the Harborth graph |Datum=2006 |arXiv=math.CO/0609360}}</ref>

Es existieren keine 4-regulären Streichholzgraphen mit weniger als 20 Knoten.<ref name="Kurz,Pinchasi,2011">{{Literatur |Autor=Sascha Kurz, Rom Pinchasi |Titel=Regular matchstick graphs |Sammelwerk=American Mathematical Monthly |Band=Vol. 118 |Nummer=3 |Datum=2011 |Seiten=264–267 |Sprache=en |DOI=10.4169/amer.math.monthly.118.03.264}}</ref> Für 4-reguläre Streichholzgraphen sind Beispiele für alle Knotenzahlen ≥ 52 außer für 53, 55, 56, 58, 59, 61 und 62 bekannt, wobei die Fälle 54, 57, 65, 67, 73, 74, 77 und 85 erstmals 2016 vorgestellt wurden. Für die Knotenzahlen 52, 54, 57, 60 und 64 ist jeweils nur ein Beispiel bekannt. Von diesen fünf Graphen ist nur der mit 60 Knoten flexibel, die anderen vier sind starr.<ref>{{Literatur |Autor=Mike Winkler, Peter Dinkelacker, Stefan Vogel |Titel=New minimal (4; n)-regular matchstick graphs |Sammelwerk=Geombinatorics |Band=Band 27 |Datum=2017 |Seiten=26-44 |arXiv=math.MG/1604.07134}}</ref><ref>{{Literatur |Autor=Mike Winkler, Peter Dinkelacker, Stefan Vogel |Titel=On the existence of 4-regular matchstick graphs |Datum=2017 |arXiv=math.CO/1705.00293}}</ref> Für die noch unbekannten Knotenzahlen von 50 bis 62 existieren sehr gute Näherungslösungen.<ref>{{Literatur |Autor=Mike Winkler |Titel=Approximate Solutions of 4-regular Matchstick Graphs with 50-62 Vertices |Datum=2020 |arXiv=math.GM/1906.11908}}</ref> Diese finden sich auch in der Webanwendung unter „Weblinks“.

Es existieren keine regulären Streichholzgraphen mit Grad größer als 4.<ref name="Kurz,Pinchasi,2011" />
Der kleinste 3-reguläre Streichholzgraph ohne eingeschlossene Dreiecke ([[Taillenweite (Graphentheorie)|Taillenweite]] ≥ 4) besitzt 20 Knoten und wurde 2009 von Kurz und Mazzuoccolo vorgestellt.<ref>{{Literatur |Autor=Sascha Kurz, Giuseppe Mazzuoccolo |Titel=3-regular matchstick graphs with given girth |Sammelwerk=Geombinatorics |Band=19 |Datum=2009 |Seiten=156–175}}</ref>
Ein Beispiel eines 3-regulären Streichholzgraphen mit Taillenweite 5 und Knotenzahl von 54 wurde 2019 von Mike Winkler, Peter Dinkelacker und Stefan Vogel vorgestellt.<ref>{{Literatur |Autor=Mike Winkler, Peter Dinkelacker, Stefan Vogel |Titel=A 3-regular matchstick graph of girth 5 consisting of 54 vertices |Sammelwerk=Geombinatorics |Band=29 |Datum=2020 |Seiten=116–121 |arXiv=math.CO/1903.04304}}</ref>
[[Datei:Winkler 3-reg girth5 54.svg|mini|Kleinstes bekanntes Beispiel eines 3-regulären Streichholzgraphen mit Taillenweite 5]]

Das [[Entscheidungsproblem]], welches fragt, ob ein gegebener ungerichteter planarer Graph ein Streichholzgraph ist, gehört zu den [[NP-Schwere|NP-schweren]] Problemen.<ref>{{Literatur |Autor=Peter Eades, Nicholas C. Wormald |Titel=Fixed edge-length graph drawing is NP-hard |Sammelwerk=Discrete Applied Mathematics |Band=28 (2) |Datum=1990 |Seiten=111–134 |DOI=10.1016/0166-218X(90)90110-X}}</ref><ref>{{Literatur |Autor= Sergio Cabello, [[Erik Demaine]], Günter Rote |Titel=Planar embeddings of graphs with specified edge lengths |Sammelwerk= [[Journal of Graph Algorithms and Applications]] |Band=11(1) |Datum=2007 |Seiten=259–276 |Online=[https://jgaa.info/accepted/2007/CabelloDemaineRote2007.11.1.pdf Online] |Format=PDF |KBytes=2600 |Abruf=2021-09-09}}</ref>

== Weblinks ==
* [https://mikematics.de/matchstick-graphs-calculator.htm Matchstick Graphs Calculator] Eine [[Webanwendung]] von Stefan Vogel zur Übersicht, Konstruktion und Berechnung von Einheitsdistanz-Graphen und Streichholzgraphen.
* [https://www.di.univr.it/?ent=persona&id=33026&lang=en Homepage] von Giuseppe Mazzuoccolo an der [https://www.univr.it/it/home Universität von Verona]
* [http://www2.math.technion.ac.il/~room/ Homepage] von Rom Pinchasi am [https://web.math.technion.ac.il/site/ Israel Institute of Technology]
* [http://www.wm.uni-bayreuth.de/de/team/Kurz_Sascha/index.php Homepage] von Sascha Kurz an der [https://www.uni-bayreuth.de/de/index.html Universität Bayreuth]
* [https://www.mikematics.de/ Homepage] von Mike Winkler ([https://math.ruhr-uni-bochum.de/ Ruhr-Universität Bochum])

== Einzelnachweise ==
<references />

[[Kategorie:Geometrischer Graph]]

Streichholzgraph - Versionsgeschichte

imported>Mikematics: Grammatik: doppeltes Wort gelöscht.