SnarkiČižman, Teja (Avtor) Škrekovski, Riste (Mentor) teorija grafovsnarkbarvanje povezavkromatični indeksizrek štirih barvtočkovni produktzvezdasti produktcvetlični snarkiV delu si podrobneje ogledamo snarke, ki spadajo v teorijo grafov. Snark definiramo kot ciklično $4$-povezan kubični graf z ožino vsaj pet in kromatičnim indeksom štiri. Najbolj znan snark je gotovo Petersenov graf, ki je prav tako najmanjši snark in edini na desetih vozliščih. Število snarkov se glede na število vozlišč zelo hitro veča. S snarki si lahko pomagamo pri dokazovanju izreka štirih barv. Izrek je namreč ekvivalenten dokazu, da noben snark ni ravninski. Do leta 1975 je bilo znanih le pet snarkov, leta 1975 pa sta definirani dve neskončni družini snarkov, deljeni glede na njihov način konstrukcije. V prvo neskončno družino spadajo snarki, ki so konstruirani ali s točkovnim produktom ali z zvezdastim produktom. Pri obeh konstrukcijah je možno konstruirati snark tudi, če vhodna grafa nista snarka. Druga neskončna skupina snarkov so cvetlični snarki, ki dobijo ime po svoji obliki. Rufus Isaacs je v želji po definiranju tretje neskončne družine snarkov konstruiral tudi double-star snark.20242024-09-20 08:15:21Delo diplomskega seminarja/zaključno seminarsko delo/naloga162249UDK: 519.17VisID: 143799COBISS_ID: 208510979sl