Application of Heuristic Algorithms in Graph Partition

U ovome radu se opisuju algoritmi koji koriste heurističke funkcije za particioniranje grafova. Na primjeru izgradnje integriranih čipova je osviještena važnost tog područja računarske znanosti. Prvo je opisan Kernighan-Lin algoritam. Jedan od najstarijih heurističkih algoritama široko korišten. Opisani su njegovi nedostatci koje pokriva iduće navedeni algoritam, Fiduccia-Mattheyses. Ta dva algoritma su detaljno opisana i pojašnjena na konkretnom primjeru. Spektralno te višerazinsko particioniranje su također objašnjeni jer su danas najraširenije metode za particioniranje grafova. Radi njihove široke familije algoritama i matematičke složenosti ovdje nisu razmatrani na razini detalja. Stoga su ta dva algoritma opisana na konceptualnoj razini uz navođenje osnovnih pojmova potrebna za osnovno shvaćanje rada.In this paper the algorithms which use heuristic functions for partitioning of graphs are being described. The importance of that area of computer science is shown in the example of the construction of integrated chips. First is described Kernighan-Lin algorithm - it's one of the oldest heuristic algorith with widespread use. The next one described is Fiduccia-Mattheyses - this one covers the flaws of the Keenighan-Lin algorithm. These two are minutely described and explained on the concrete example. Spectral and multilevel potentiation are also explained because of theire widespread use in potentiation of graphs. Because of theire wide family of algorithms and mathematical complexity in this paper they are not observed in large details. For that reason these two algorithms are described on conceptual level with basic terms necessary for understanding