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.

Der Name Snark wurde 1976 von Martin Gardner geprägt und ist inspiriert von Lewis Carrolls Unsinnsgedicht The Hunting of the Snark. 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. 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).

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.“

Seit den 1970er Jahren ist bekannt, dass es unendlich viele Snarks gibt.

Commons: Snark – Sammlung von Bildern, Videos und Audiodateien

Einzelnachweise

  1. ↑ Ed Pegg, Jr. et al., Wolfram MathWorld: Snark
  2. ↑ 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.
  3. ↑ 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.
  4. ↑ Julius Petersen: Sur le théorème de Tait. In: L'Intermédiaire des Mathématiciens. Band 5, 1898, S. 225–227 (archive.org).
  5. ↑ 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.
  6. ↑ 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.