Розфарбування графів: теоретичні та практичні аспекти

Abstract

The paper considers the theoretical foundations and methods for solving the graph coloring problem. The concept of the chromatic number is defined as the main quantitative indicator of the problem. Two types of algorithms are analyzed: an exact backtracking method, which guarantees the optimality of the solution, and an approximate greedy algorithm, aimed at obtaining a fast result. Using the example of the timetabling problem, the practical significance of the studied methods for process optimization is demonstrated.