Задание
Реализовать раскраску графа используя несколько алгоритмов.
Функционал программы
Раскраской графа называется присвоение меток его вершинам, дугам или, в случае плоского графа, граням. Метки удобно называть цветами. Основной задачей является правильная раскраска вершин, при которой необходимо так подобрать цвета, чтобы любым двум смежным вершинам соответствовали разные цвета.
Жадный алгоритм раскраски графа (жадная раскраска) — это алгоритм, который проходит вершины неориентированного графа в некоторой предопределённой последовательности и назначает каждой вершине первый доступный цвет. Цель — найти раскраску, при которой никакие две смежные вершины не имеют одного и того же цвета.
Рассмотрим жадный алгоритм раскраски графа с m вершинами.
- Упорядочить вершины: V = {v1, v2, . . . , vm}.
- Вершине v1 присвоить первый цвет.
- При i от 2 до m вершине vi присвоить цвет с наименьшим номером, не использовавшийся для смежных с vi вершин из набора {v1, v2, . . . , vi1}.
Жадный алгоритм с повторениями - это жадный алгоритм выполняющийся несколько раз.
Алгоритм рекурсивного поиска наибольшего - алгоритм присваивает цвета вершинам графа, создавая каждый цветовой класс по одному за раз. Это достигается путём определения максимального независимого набора вершин в графе, присвоения им одного цвета, а затем удаления этих вершин из графика. Эти действия повторяются для оставшегося подграфа, пока не останется ни одной вершины.
Алгоритм рекурсивного поиска наибольшего может быть описан следующими шагами:
- Определить максимальное независимое множество S. Первая вершина, добавленная в S, — вершина с наибольшим количеством соседей. Последующие вершины выбирают как те, которые (а) в данный момент не примыкают ни к одной вершине в S, и (б) имеют максимальное количество соседей, которые примыкают к вершинам в S.
- Установить S = S ∪ {S} и удалить вершины S из графа.
- Если граф всё ещё содержит вершины, то вернуться к шагу 2; в противном случае завершить.
Алгоритм работы с программой:
- Добавить точки
- Добавить ребра
- выбрать алгоритм
- Раскрасить граф
Скриншот архива с проектом
Пояснения по запуску программы
Разархивировать. Открыть файл .sln через visual studio.
Телеграм
-