Project and implementation of a graph partitioning problem.

This bachelor's thesis presents the analysis and implementation of a graph partition problem.The aim of the algorithm is to make a partition of a weighted graph, with weights of nodes and weights of edges in the way which enable us to get two parts of the graph, which have equal (or as most similar as possible) sums of weights of the nodes. Moreover, we want this partition to cause deleting of edges which have as low as possible sum of weights.Algorithm has been written on a base of GGGP (Greedy Growing Graph Partition) algorithm.Thanks to the analysis of the tests' results for many different graphs, I was able to project and implement algorithm better than GGGP in the context of the graphs which represent finite element method mesh.

Poniższa praca licencjacka przedstawia analizę i implementację algorytmu rozwiązującego problem podziału grafu. Celem algorytmu jest dokonanie podziału grafu ważonego, z wagami wierzchołków i wagami krawędzi w ten sposób, by uzyskać podział grafu na dwie części, które będą miały równe (albo jak najbardziej zbliżone do siebie) sumy wag wierzchołków. Jednocześnie chcemy, by podział ten powodował przecięcie krawędzi o jak najmniejszej sumie wag.Algorytm został napisany w oparciu o algorytm GGGP (Greedy Growing Graph Partition).Dzięki analizie rezultatów podziałów dla różnych grafów, udało się zaprojektować i zaimplementować algorytm korzystniejszy w kontekście grafów reprezentujących siatkę elementów skończonych.