Algoritmi za particioniranje grafova

diplomski rad

• Autor: Ana Iveković
• Mentor: Zvonimir Bujanović (mentor)
• Član povjerenstva: Zvonimir Bujanović (predsjednik povjerenstva)
• Član povjerenstva: Nela Bosner (član povjerenstva)
• Član povjerenstva: Vjeran Hari (član povjerenstva)
• Član povjerenstva: Tina Bosner (č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: 2018-11-27, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Particioniranje grafa optimizacijski je problem na koji je moguće svesti velik broj problema iz stvarnog svijeta, na primjer optimizaciju transportne mreže, segmentiranje slika i analizu društvenih mreža. U ovom je radu opisan sam problem, s naglaskom na težinske grafove u kojima su svi vrhovi jednake težine. Definirani su pojmovi usko povezani s problemom, poput sparivanja na grafu, reza, vanjske i unutarnje povezanosti vrhova te ravnoteže particije. Kako se radi o NP-teškom problemu, rješavanje se provodi heurističkim i aproksimacijskim algoritmima. U radu je opisan algoritam spektralnog particioniranja te višerazinska metoda, unutar koje su opisani algoritmi iterativno sažimanje grafa te profinjavanje particije s viših razina na niže. Među tim se algoritmima nalazi i jedan od poznatijih algoritama za biparticioniranje, algoritam Kernighana i Lina, te njegovo poboljšanje, algoritam Fiduccie i Mattheysesa. U opisima je dan osvrt na probleme u kojima postoji uvjet na ravnotežu završne particije te na probleme u kojima takav uvjet ne postoji. U završnom dijelu rada implementirani su neki od opisanih algoritama i uspoređene su njihove performanse na potpuno povezanim težinskim grafovima s jednakom težinom vrhova.

Sažetak (engleski)

Graph partitioning is an optimization problem which can be used to solve many real-world problems, such as transportation network optimization, image segmentation and social networks analysis. This thesis focuses on partitioning of weighted graphs with equally weighted vertices. The key notions of graph matching, cut function, external and internal cut and balance of a partition are defined and explained. Graph partitioning problems are typically NP-hard, therefore, in order to solve them one needs to use heuristic and approximation algorithms. In this thesis several such algorithms are described, namely spectral partitioning algorithm and multilevel method. For the multilevel method, we describe algorithms for iterative coarsening of the graph, as well as algorithms for refining the partition obtained at the lower level to the higher level. Some of the well-known bipartitioning algorithms can be found there, such as the Kernighan-Lin algorithm and its improvement, the Fiduccia-Mattheyses algorithm. Solving techniques are described both from constrained and unconstrained partitioning point of view. In the final chapter an implementation for some of the mentioned algorithm is described. Their performance is compared on fully connected weighted graphs with vertices of equal weight.

• Ključne riječi: particioniranje grafa; optimizacija; algoritam Kernighana i Lina; algoritam Fiduccie i Mattheysesa
• Ključne riječi (engleski): graph partitioning; optimization; Kernighan-Lin algorithm; Fiduccia-Mattheyses algorithm
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:574134
• 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: 2019-05-14 10:27:18