Grafovi snarkovi

undergraduate thesis

• Title (english): Graphs Snark
• Author: Andrej Sakač
• Mentor: Anamari Nakić (mentor)
• Committee member: Anamari Nakić (predsjednik povjerenstva)
• Committee member: Marina Furkes (član povjerenstva)
• Committee member: Filip Martinović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2023-09-15, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Za potrebe ovog rada istražena su teorijska svojstva grafova snarkova te su istraženi neki poznati snarkovi i posebna svojstva koja oni posjeduju. Graf G sastoji se od nepraznog konačnog skupa vrhova V(G) i konačnog skupa E(G) dvočlanih podskupova skupa V(G) koje zovemo bridovi. Snark je graf koji je jednostavan, povezan, nema mostova, 3-regularan i kromatskog indeksa 4. Graf je jednostavan ako ne sadrži petlje i ne sadrži višestruke bridove. Graf je povezan ako je moguće ostvariti šetnju između bilo koja dva vrha grafa. Brid u grafu G je most ako graf njegovim uklanjanjem gubi svojstvo povezanosti. Graf je k-regularan ako su mu svi vrhovi stupnja k, odnosno graf je 3-regularan ako su mu svi vrhovi stupnja 3. Kromatski indeks je najmanji broj boja potreban da se graf oboji tako da svi susjedni bridovi u grafu budu različitih boja.
Neki od poznatih primjera takvih grafova su:Petersenov graf, Blanušini snarkovi, Snark dvostruke zvijezde, Szekeresov snark, Watkinsov snark, Descartesov snark, Beskonačna familija cvjetnih snarkova.
Razvijena je aplikacija s grafičkim sučeljem koja omogućava jednostavnu provjeru svojstava nacrtanog grafa. Za rad je iskorišteno znanje diskretne matematike te vještine rješavanja algoritamskih problema kroz programski kod.

Abstract (english)

For purpose of this paper research has been done on the topic of theoretical features of snark graphs, as well as research regarding some well known snarks and their special features. Graph G consists of a nonempty, finite set of vertices V(G) and a finite set E(G) consisting of binomal subsets of set V(G) which we call edges. A snark is a graph that is simple, connected, has no bridges, is 3-regular and has a chromatic index of 4. A graf is simple if there are no loops in it and there are no multiple edges between two vertices. A graph is connected if there is a path from any one vertex to any other vertex. An edge in a graph is a bridge if the graph becomes unconnected by removing that edge from the graph. A graph is k-regular if all vertices of the graph are of degree k. A graph is 3-regular if all vertices of the graph are of degree 3. Chromatic index of a graph is the minimum number of colors necessary to color the graph so no incident edges are of the same color.
Some well known examples of such graphs are: Petersen graph, Blanuša snarks, Double-star snark, Szekeres snark, Watkins snark, Descartes snark, An infinite family of flower snarks.
An application with a graphical interface has been developed to give users a simple way of checking the features of a graph which they draw. For all that knowledge of discrete mathematics has been used, as well as skills regarding solving of alghorithmic problems through code.

• Keywords: graf; snark
• Keywords (english): graph; snark
• Language: croatian
• URN:NBN: urn:nbn:hr:168:194298
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-10-11 10:24:01