Snark (Graphentheorie)
In der Graphentheorie ist ein Snark ein ungerichteter Graph mit genau drei Kanten pro Knoten, der nicht 3-Kanten-färbbar ist. Um triviale Fälle zu vermeiden, werden Snarks oft weiter in ihrem Zusammenhang und der Länge ihrer Kreise beschränkt.[1]
Der Name Snark wurde 1976 von Martin Gardner geprägt und ist inspiriert von Lewis Carrolls Unsinnsgedicht The Hunting of the Snark.[2] Allerdings wurde diese Klasse von Graphen schon lange vorher untersucht. Sie geht auf Peter Guthrie Tait zurück, der 1880 bewies, dass der Vier-Farben-Satz äquivalent ist zu der Aussage, dass kein Snark ein planarer Graph ist.[3] Der erste Graph, für den bewiesen wurde, dass es sich um einen Snark handelt, ist der Petersen-Graph (Beweis 1898 durch Julius Peter Christian Petersen[4]).
Neben ihrer Bedeutung für das Färbungsproblem sind Snarks auch mit anderen schwierigen Problemen der Graphentheorie verbunden. In einem Artikel aus dem Jahr 2010 heißt es:
„Bei der Untersuchung verschiedener wichtiger und schwieriger Probleme in der Graphentheorie (wie der cycle-double-cover-Vermutung und der 5-flow-Vermutung) stößt man auf eine interessante, aber etwas mysteriöse Sorte von Graphen, die Snarks genannt werden. Trotz ihrer einfachen Definition [...] und einer mehr als hundert Jahre andauernden Untersuchung sind ihre Eigenschaften und Struktur weitgehend unbekannt.“[5]
Seit den 1970er Jahren ist bekannt, dass es unendlich viele Snarks gibt.[6]
Weblinks Bearbeiten
Einzelnachweise Bearbeiten
- ↑ Ed Pegg, Jr. et al., Wolfram MathWorld: Snark
- ↑ Martin Gardner: Snarks, boojums, and other conjectures related to the four-color-map theorem. In: Scientific American. Band 234, Nr. 4, 1976, S. 126–130, doi:10.1038/scientificamerican0476-126, JSTOR:24950334.
- ↑ Peter G. Tait: Remarks on the colourings of maps. In: Proceedings of the Royal Society of Edinburgh. Band 10, 1880, S. 729, doi:10.1017/S0370164600044643.
- ↑ Julius Petersen: Sur le théorème de Tait. In: L'Intermédiaire des Mathématiciens. Band 5, 1898, S. 225–227 (archive.org).
- ↑ In the study of various important and difficult problems in graph theory (such as the cycle double cover conjecture and the 5-flow conjecture), one encounters an interesting but somewhat mysterious variety of graphs called snarks. In spite of their simple definition...and over a century long investigation, their properties and structure are largely unknown. Siehe Miroslav Chladný, Martin Škoviera: Factorisation of snarks. In: Electronic Journal of Combinatorics. Band 17, 2010, S. R32, doi:10.37236/304.
- ↑ Sarah-Marie Belcastro: The continuing saga of snarks. In: The College Mathematics Journal. Band 43, Nr. 1, 2012, S. 82–87, doi:10.4169/college.math.j.43.1.082.