Дослідження та програмна реалізація паралельного алгоритму розфарбування ребер графу Edge Coloring

Abstract

The paper considers the development of a parallel algorithm for coloring the edges of a graph Edge Coloring. Known methods of coloring graphs are evaluated, the choice of a parallel approach to solving the problem is justified, which allows significantly improving the execution speed. The main stages of implementing a parallel algorithm for coloring the edges of a graph are determined. The analysis of the subject area has proven the importance of the edge coloring problem and the main applications of this problem in various fields are determined, such as: graph theory, task scheduling, computer graphics. A comparison of known algorithms for coloring edges, in particular, sequential and parallel approaches, is carried out. The most acceptable structure for representing graphs is determined - the adjacency matrix. The use of the adjacency matrix ensures efficient use of memory and facilitates simple distribution of tasks between processors for parallel calculations. The main parameters of the effectiveness of the parallel algorithm are formulated: execution time, scalability, use of computing resources. A stable parallel algorithm is created. On its basis, a software implementation of a parallel algorithm for edge coloring was carried out. The UML class diagram and the algorithm flowchart give a clear idea of the structure of the software implementation and describe the main stages of parallel execution. A software module using Python libraries (NetworkX, ThreadPoolExecutor) for an effective parallel algorithm was developed. Defining parallel stages of algorithm execution allowed to effectively distribute resources and maximize the use of multithreading capabilities. The results of testing the program on different sets of graphs showed high efficiency of the parallel algorithm compared to traditional methods. Comparison of execution time and used resources confirmed that the parallel approach significantly reduces the processing time of large graphs, which is critically important for the application of this algorithm in real problems.

В роботі наведено результати досліджень та програмна реалізація паралельного алгоритму розфарбування ребер графу Edge Coloring. Оцінено відомі методи розфарбування графів, обґрунтовано вибір паралельного підходу до розв`язання задачі, що дозволяє значно покращити швидкість виконання. Визначено основні етапи реалізації паралельного алгоритму, розроблено програмний модуль, що використовує бібліотеки Python (NetworkX, ThreadPoolExecutor) для ефективного паралельного виконання алгоритму. Результати показали покращення продуктивності та надійності процесу розфарбування графів у паралельному режимі.