Prebrojavanje savršenih sparivanja u nekim klasama benzenoidnih grafova

master's thesis

• Author: Dijana Samaržija
• Mentor: Tomislav Došlić (mentor)
• Committee member: Tomislav Došlić (predsjednik povjerenstva)
• Committee member: Andrej Dujella (član povjerenstva)
• Committee member: Marko Tadić (član povjerenstva)
• Committee member: Marko Vrdoljak (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2019-09-26, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: klase benzenoidnih grafova; formule za broj savršenih sparivanja; teorija grafova
• Keywords (english): classes of benzenoid graphs; calculating number of perfect matchings; graph theory
• Language: croatian
• URN:NBN: urn:nbn:hr:217:899790
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2020-02-26 14:33:03