Prebrojavanje savršenih sparivanja u nekim klasama benzenoidnih grafova

diplomski rad

• Autor: Dijana Samaržija
• Mentor: Tomislav Došlić (mentor)
• Član povjerenstva: Tomislav Došlić (predsjednik povjerenstva)
• Član povjerenstva: Andrej Dujella (član povjerenstva)
• Član povjerenstva: Marko Tadić (član povjerenstva)
• Član povjerenstva: Marko Vrdoljak (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2019-09-26, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U ovom diplomskom radu izveli smo formule za broj savršenih sparivanja u nekim klasama benzenoidnih grafova. Na početku smo naveli osnovne pojmove vezane za teoriju grafova te definirali savršeno sparivanje. Nakon toga smo uveli pojmove benzenoidni sustav i benzenoidni graf i objasnili povezanost između njih. U nastavku smo uzeli šest klasa benzenoidnih grafova te odredili broj savršenih sparivanja u njima. Grafovi koje smo promatrali su \(L_n\) koji se sastoji od \(n\) šesterokuta pozicioniranih jedan do drugoga, \(Z_n\) koji sadrži \(n\) šesterokuta posloženih u cik-cak poziciji, \(B_n\) koji sadrži \(n\times m\) šesterokuta posloženih u obliku paralelograma, \(T_n\) koji se sastoji od šesterokuta poredanih u \(n\) redova na način da prvi redak sadrži \(n\) šesterokuta, a svaki sljedeći redak po jedan šesterokut manje, \(K_n\) koji se sastoji od koronena kojem je dodan jedan linearni lanac duljine \(n\) te za \(_6K_n\) koji se sastoji od koronena kojemu je dodano šest linearnih lanaca duljine \(n\). Osim toga, pokazali smo neke nizove brojeva koji se mogu dobiti kao broj savršenih sparivanja u navedenim klasama grafova.

Sažetak (engleski)

In this graduate thesis we calculate the number of perfect matchings in some classes of benzenoid graphs. At the beginning we mention the basic concepts related to graph theory and define the perfect matching in a graph. After that we define the concepts of benzenoid system and benzenoid graph and explain the connection between them. After that, we pointed out six classes of benzenoid graphs on which we will calculate the number of perfect matching. Graphs that we observed are \(L_n\) which consists of \(n\) hexagons positioned next to each other, \(Z_n\) which consists of \(n\) hexagons positioned in zigzag position, \(B_n\) which consists \(n\times m\) hexagons positioned in a shape of parallelogram, \(T_n\) consisting of \(n\) rows of hexagons, with the number of hexagons in a row decreasing by one from \(n\) in the lowest row to one in the uppermost row, each row shifted for one and a half hexagon to the right, \(K_n\) which consists of coronene to which a linear chain of length \(n\) is added and \(_6K_n\) which consists of coronene to which six linear chains of length \(n\) are added. In addition, we have shown some sequences of numbers which can be obtained as the number of perfect matching in the given graph classes.

• Ključne riječi: klase benzenoidnih grafova; formule za broj savršenih sparivanja; teorija grafova
• Ključne riječi (engleski): classes of benzenoid graphs; calculating number of perfect matchings; graph theory
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:899790
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2020-02-26 14:33:03