У меня есть неориентированный граф G = (V, E), давайте обозначим max = максимальная степень вершины v в G (так, max - максимальная степень всех доступных вершин в G) Мне нужно описать жадный алгоритм (нет фактический код) который окрашивает G максимум + 1 цветами. Предположим, у меня есть max = 3, поэтому у меня всего 4 цвета = {1,2,3,4} (Раскраска означает, что если вершина a получает цвет '1', нет, если его соседи получают тот же цвет)
Мой жадный алгоритм таков: 1) Выберите произвольную вершину и присвойте ей цвет «1». 2) для каждой вершины v в G: раскрасьте вершину самым низким доступным цветом. 3) вернуть Раскраску
Я думаю, что мой подход довольно хороший, не могу найти никакого противоречия, но я не уверен в этом, Хотел бы услышать некоторые мысли.