Razlika između inačica stranice »Snark«
(Bot: Automatski unos stranica) |
m (bnz) |
||
| Redak 1: | Redak 1: | ||
Snark''' je 3-valentni [[Graf (teorija grafova)|graf]] koji nije [[Bojenje grafa|3-obojiv]].<ref name="Ivanšić">[http://www.matematika.hr/o-hmd-u/prica-o-logotipu/ Hrvatsko matematičko društvo] I. Ivanšić: Logo HMD-a - Blanušin graf (pristupljeno 3. listopada 2020.)</ref> | |||
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 [[Petersenov graf|Petersenova]]. Do Blanuše su matematički pisci bavili se istraživanjem samo [[ravninski graf|ravninskih]] trivalentnih grafova bez [[most (teorija grafova)|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.<ref name="Ivanšić"/> | 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 [[Petersenov graf|Petersenova]]. Do Blanuše su matematički pisci bavili se istraživanjem samo [[ravninski graf|ravninskih]] trivalentnih grafova bez [[most (teorija grafova)|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.<ref name="Ivanšić"/> | ||
Trenutačna izmjena od 21:07, 24. ožujka 2022.
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".