نبذة مختصرة : Zadatak ovog završnog rada bio je istražiti postojeće algoritme za bojenje grafova te odabrati jedan i implementirati ga u proizvoljnom programskom jeziku. Prvo su opisani teorijski pojmovi vezani uz teoriju grafu kako bi se lakše razumio sam rad, zatim je objašnjeno bojenje grafova te njegova važnost u primjeni na stvarnim problemima. Nakon toga su navedeni postojeći algoritmi za bojenje grafova kao i način njihova rada te vremenska složenost, nadalje su opisane korištene tehnologije te razvojno kruženje u kojem je implementiran odabrani algoritam. Na samome kraju je odabran algoritam pohlepnog bojenja te je u programskom jeziku C# stvorena Windows Forms aplikacija. Windows Forms aplikacija radi na način da se unese matrica susjedstva željenog grafa, a ona će koristeći algoritam pohlepnog bojenja obojiti zadani graf te rješenje prikazati u grafičkom obliku. ; The aim of this final paper was to investigate the existing algorithms for coloring graphs, select one and implement it in an arbitrary programming language. Firstly, theoretical concepts related to graph theory are described in order to better understand the reseach paper itself, then the coloring of graphs and their importance in dealing to real problems are explained. After that, the existing algorithms for coloring graphs are listed, as well as the way they work and the run time, then are described the used technologies and the development environment in which the selected algorithm is implemented. At the very end, the greedy coloring algorithm was selected and the Windows Forms application was created in the C# programming language. The Windows Forms application works by entering the adjacency matrix of the desired graph, and it will use a greedy coloring algorithm to color the default graph and display the solution in graphical form.
Processing Request
No Comments.