КОНФЕРЕНЦІЇ ВНТУ електронні наукові видання, 
Молодь в науці: дослідження, проблеми, перспективи (МН-2026)

Розмір шрифта: 
РОЗФАРБУВАННЯ ГРАФІВ: ТЕОРЕТИЧНІ ТА ПРАКТИЧНІ АСПЕКТИ
Олександр Миколайович Пилипенко, Наталія Василівна Сачанюк-Кавецька

Остання редакція: 2026-01-05

Анотація


У роботі розглянуто теоретичні засади та методи розв’язання задачі розфарбування графів. Визначено поняття хроматичного числа як основного кількісного показника задачі. Проаналізовано два типи алгоритмів: точний метод пошуку з поверненням, що гарантує оптимальність розв’язку, та наближений жадібний алгоритм, орієнтований на швидке отримання результату. На прикладі задачі складання розкладів продемонстровано практичну значущість досліджуваних методів для оптимізації процесів

Ключові слова


розфарбування графа; хроматичне число; алгоритм пошуку з поверненням; жадібний алгоритм; складання розкладів

Посилання


1. Voloshin V. I. Graph Coloring: History, results and open problems // Alabama Journal of Mathematics. 2009. С. 1–3.


2. West D. Introduction to Graph Theory / D. West. Prentice Hall, 2001. 588 с.


3. Дослідження та програмна реалізація паралельного алгоритмурозфарбування ребер графу Edge Coloring / В. Денисюк та ін. // Вісник Хмельницького національного університету. 2025. Т. 357, № 5. С. 95–107. URL: https://heraldts.khmnu.edu.ua/index.php/heraldts/issue/view/35. (дата звернення: 25.12.2025).

4.

 


Повний текст: PDF