Використання спектральної теорії графів для знаходження хроматичного числа
Ескіз недоступний
Дата
2019-06
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
Анотація
Дипломна робота: 90 с., 29 рис., 9 табл., 2 дод, 32 джерела.
Об’єкт дослідження – хроматичне число для різних класів графів.
Предмет дослідження – методи спектральної теорії графів.
Мета роботи – проаналізувати методи спектральної теорії графів для знаходження хроматичного числа або оцінки його верхніх та нижніх границь для різних класів графів та скласти алгоритм для розрахунку оцінок хроматичного числа і реалізувати на його основі програмний код.
Метод дослідження – розгляд та аналіз методів спектральної теорії графів.
Актуальність – використання хроматичного числа та алгоритмів розмалювання вершин графів для практичних застосувань: моделювання і вирішення різних проблем планування, при розподілі регістрів, для технології цифрових водяних знаків та ін.
Проведено аналіз методів спектральної теорії графів, побудовано алгоритм для розрахунку верхніх та нижніх оцінок хроматичного числа для різних класів графів та реалізовано програмний код.
Опис
Ключові слова
граф, повний граф, дводольний граф, регулярний граф, зв’язний граф, спектральна теорія графів, матриця суміжності, спектр, розфарбування графа, хроматичне число, верхні та нижні оцінки хроматичного числа графа, graph, complete graph, bipartite graph, regular graph, connected graph, spectral graph theory, adjacency matrix, spectrum of a matrix, graph coloring, chromatic number, upper and lower bounds for the chromatic number of a graph
Бібліографічний опис
Ревуцька, Л. О. Використання спектральної теорії графів для знаходження хроматичного числа : дипломна робота ... бакалавра : 6.040303 Системний аналіз / Ревуцька Людмила Олександрівна. – Київ, 2019. – 113 с.