Snarki

delo diplomskega seminarja

Teja Čižman (Avtor), Riste Škrekovski (Mentor)

Povzetek

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.

Ključne besede

teorija grafov;snarki;barvanje povezav;kromatični indeks;izrek štirih barv;točkovni produkt;zvezdasti produkt;cvetlični snarki;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2024
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FMF - Fakulteta za matematiko in fiziko
Založnik:	[T. Čižman]
UDK:	519.17
COBISS:	208510979
Št. ogledov:	30
Št. prenosov:	12
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Snarks
Sekundarni povzetek:	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.
Sekundarne ključne besede:	graph theory;snarks;edge colouring;chromatic index;four colour theorem;dot product;star product;flower snarks;
Vrsta dela (COBISS):	Delo diplomskega seminarja/zaključno seminarsko delo/naloga
Študijski program:	0
Komentar na gradivo:	Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 1. stopnja
Strani:	29 str.
ID:	25105281