Mjere nebipartitnosti u grafovima

master's thesis

• Author: Sandra Nežić
• 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: Hrvoje Šikić (č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 radu promatramo svojstvo nebipartitnosti grafa. Osnovna karakterizacija nebipartitnosti kaže nam da je graf bipartitan ako i samo ako ne sadrži cikluse neparne duljine. No, nisu svi grafovi jednako daleko od toga da budu bipartitni. Kako bi mogli mjeriti koliko je neki graf udaljen od toga da bude bipartitan, definiramo četiri različite mjere nebipartitnosti, koje postižu vrijednosti između 0 i 1. Pritom grafove zapisujemo koristeći matrice. Prva mjera temelji se na omjeru broja frustriranih bridova i ukupnog broja bridova grafa. Njezinu aproksimaciju računamo uz pomoć svojstava nenegativne Laplaceove matrice. Druga i treća mjera temelje se na udaljenosti između najmanje i najveće svojstvene vrijednosti matrice susjedstva, odnosno normalizirane matrice susjedstva. Zadnja mjera temelji se na omjeru broja neparnih ciklusa i ukupnog broja ciklusa u grafu, te ju računamo koristeći svojstva matrice susjedstva. Na kraju rada, uz pomoć programa Mathematica testiramo definirane mjere i proučavamo promjenu mjera za neke poznate klase grafove - potpune grafove, cikluse, zvijezde i generalizirane Petersenove grafove.

Abstract (english)

In this thesis, we consider the non-bipartite property of a graph. The basic characterization of non-bipartivity says that a graph is bipartite if and only if it does not contain cycles of odd length. But, not all graphs are equally far from being bipartite. To be able to measure how far a graph is from being bipartite, we define four different non-bipartivity measures, all of whom achieve values between 0 and 1. The first measure is based on the ratio of the number of frustrated edges to the total number of edges in a graph. We calculate this measure approximately, using the properties of the signless Laplacian matrix. The second measure is based on the distance between the smallest and the largest eigenvalues of the adjacency matrix, while the third measure is based on the distance between the smallest and the largest eigenvalues of the normalized adjacency matrix. The final measure is based on the ratio of the number of odd cycles to the total number of all cycles in a graph, and we calculate it using the properties of the adjacency matrix. Using Mathematica we are able to test the defined measures and observe how their values change for some known classes of graphs - complete graphs, cycles, stars, and generalized Petersen graphs.

• Keywords: nebipartitnost grafa; nenegativna Laplaceove matrica; Mathematica
• Keywords (english): non-bipartite property of a graph; signless Laplacian matrix; Mathematica
• Language: croatian
• URN:NBN: urn:nbn:hr:217:043910
• Study programme: Title: Mathematics and Computer Science Education; specializations in: Mathematics and Computer Science Education; Course: Mathematics and Computer Science Education; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra edukacije matematike i informatike (magistar/magistra edukacije matematike i informatike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2020-02-13 13:46:22