Loading AI tools
Aus Wikipedia, der freien Enzyklopädie
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]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.