Naslov
Grafovi snarkovi
(Graphs Snarks)

Autori
Sakač, Andrej

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, diplomski rad, preddiplomski

Fakultet
Fakultet elektrotehnike i računarstva

Mjesto
Zagreb

Datum
30.06

Godina
2022

Stranica
34

Mentor
Nakić, Anamari

Ključne riječi
graf ; snark
(graph ; snark)

Sažetak
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.

Izvorni jezik
Hrvatski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA