Snark je 3-valentni graf koji nije 3-obojiv.[1]
Postojanje snarkova pokazao je hrvatski matematičar Danilo Blanuša. Pokazao je to u djelu gdje je ciljao riješiti problem četiriju boja, no nije bio svjestan koliko je velika stvar što je otkrio snarkove. U radu je dokazao postojanje trivalentnih grafova koji nisu 3-obojivi, a kompliciraniji su od Petersenova. Do Blanuše su matematički pisci bavili se istraživanjem samo ravninskih trivalentnih grafova bez mostova trudeći se dokazati da su 3-obojivi. Na osnovi Petersenova primjera istraživači su znali da nisu svi neravninski trivalentni grafovi 3-obojivi. Blanuša je iznio tezu da kad bi se sve te 3-neobojive trivalentne grafove potpuno obuhvatiti i klasificirati, možda bi se dalo ustanoviti je li među njima koji ravninski te bi se tim putem riješio problem četiriju boja.[1]
Rufus Isaacs je u djelu Infinite families of nontrivial trivalent graphs which are not Tait colorable, [2] utvrdio da su rijetki 3-valentni grafovi koji nisu 3-obojivi rijetki te da ih je teško naći. Martin Gardner ih je motiviran pjesmom Lewisa Carrolla The Hunting of the Snark nazvao "snarkovima" (tajanstvena nepostojeća bića) u svom radu iz 1976. Mathematical games: Snarks, boojums and other conjectures related to the four-color-map theorem. [3], a matematičari su to prihvatili.[1]
Najmanji snark je Petersenov graf.[4]
Izvori
- ↑ 1,0 1,1 1,2 Hrvatsko matematičko društvo I. Ivanšić: Logo HMD-a - Blanušin graf (pristupljeno 3. listopada 2020.)
- ↑ American Mathematical Monthly 82(1975), s.221-239., Taylor & Francis, doi: 10.2307/2319844
- ↑ Scientific American 234(No 4)(1976), s. 126-130
- ↑ math.e Snježana Majstorović i Luka Boras: Petersenov graf, br. 27. (pristupljeno 25. svibnja 2020.)
Vanjske poveznice
- Wolfram MathWorld Pegg, Ed Jr. i Weisstein, Eric W. "Snark".