20.500.12556/RUL-162249 Snarki Snarks V 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. In this paper we take a closer look at snarks, a certain group of graphs that appears in graph theory. We define them as cyclically $4$-edge-connected cubic graphs of girth at least five and chromatic index four. Petersen graph is the most well-known snark, as well as the smallest and only snark on 10 vertices. The number of known snarks rises very fast with the number of vertices in a graph. Snarks can help us prove the four colour theorem as the four colour theorem is equivalent to the statement that every snark must be non-planar. Up until 1975 only five snarks were known. In the year 1975, Rufus Isaacs classified two infinite families of snarks, depending on their construction. The first infinite family includes snarks, constructed by the dot or the star product. And the second infinite family are flower snarks, which get their name after their flower-like shape. Rufus Isaacs also produced a completely separate new snark, the double-star snark. teorija grafov snark barvanje povezav kromatični indeks izrek štirih barv točkovni produkt zvezdasti produkt cvetlični snarki graph theory snark edge colouring chromatic index four colour theorem dot product star product flower snarks true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2024-09-20 08:15:21 2024-09-20 08:15:24 2024-09-23 11:51:32 0000-00-00 00:00:00 2024 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 143799 208510979 12902.pdf 12902.pdf 1 5CD57BEBCC4AF73D01DB5140ED50D321 3bc52a5280e0d82819ebaba69e65f955072ed470e469d0076bcf5a575d4b65a0 9c8a0597-7717-11ef-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=191448 Fakulteta za matematiko in fiziko 0 0 0