Algorytmy rozwiązywania problemu kolorowania grafu

• Autorzy: Myśliwiec K. , Wieczorek B.

Warianty tytułu

EN

Graph colouring algorithms

• Języki publikacji: PL

Abstrakty

PL

Głównym celem pracy było zbadanie algorytmów rozwiązujących problem kolorowania grafu, kolejno: algorytmów zachłannych LF (ang. Largest First) i SFL (ang. Saturated Largest First), algorytmu genetycznego sekwencyjnego oraz równoległego. Ponadto, zaimplementowana została aplikacja działającej w środowisku przeglądarki internetowej pozwalająca na wizualizacje 3D procesu kolorowania grafu wraz z regulacją parametrów grafu (takich jak liczba wierzchołków i gęstość grafu) oraz obserwację uzyskanych wyników (czasu wykonywania algorytmu i liczby dobranych kolorów).

EN

The main aim of the study was to examine four algorithms concerning the graph colouring problem, respectively: LF (Largest First), SFL (Saturated Largest First), genetic algorithm, both sequential and multithreaded. Additionally, an application in a web browser environment was created to 3D visualisation of the graph colouring process allowing adjustment of graph parameters (such as number of vertices and graph density) and observation of the obtained results (execution time and number of colours).

Słowa kluczowe

PL

problem kolorowania grafu; algorytmy zachłanne; algorytmy genetyczne; wizualizacja 3D

EN

graph colouring problem; greedy algorithms; genetic algorithms; 3D visualisation

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Prace Naukowe Politechniki Śląskiej. Elektryka
• Rocznik: 2018
• Tom: z. 1
• Strony: 85--97
• Opis fizyczny: Bibliogr. 8 poz.

Twórcy

autor

Myśliwiec K.

• Politechnika Śląska, Wydział Elektryczny, Instytut Elektrotechniki i Informatyki, Akademicka 10, 44-100, Gliwice

autor

Wieczorek B.

• Politechnika Śląska, Wydział Elektryczny, Instytut Elektrotechniki i Informatyki, Akademicka 10, 44-100, Gliwice

Bibliografia

• 1. Figielska E. „Algorytmy ewolucyjne i ich zastosowania”, Biblioteka Narodowa, 2006
• 2. https://pl.wikipedia.org/wiki/Proble_NP-zupełny
• 3. https://pl.wikipedia.org/wiki/Twierdzenie_o_czterech_barwach
• 4. https://graphtheoryinlatex.wordpress.com/2010/02/18/a-coloring-of-the-petersen-graph-2/
• 5. https://en.wikipedia.org/wiki/Master/slave_(technology)
• 6. https://pl.wikipedia.org/wiki/Mediator_(wzorzec_projektowy)
• 7. https://msdn.microsoft.com/pl-pl/library/ee850490(v=vs.110).aspx
• 8. http://blog.helion.pl/wzorzec-projektowy-strategii/