Mjere nebipartitnosti u grafovima

diplomski rad

• Autor: Sandra Nežić
• 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: Hrvoje Šikić (č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 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.

Sažetak (engleski)

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.

• Ključne riječi: nebipartitnost grafa; nenegativna Laplaceove matrica; Mathematica
• Ključne riječi (engleski): non-bipartite property of a graph; signless Laplacian matrix; Mathematica
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:043910
• Studijski program: Naziv: Matematika i informatika; smjerovi: nastavnički; Smjer: nastavnički; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra edukacije matematike i informatike (mag. educ. math. et inf.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2020-02-13 13:46:22