Решайте раскраску краев, раскраску карты и другие забавные задачи

Раскраска графа - это проблема, при которой определенные цвета назначаются определенному ограничению в графе. Например, может оказаться, что вы должны раскрасить граф либо вершины, либо ребра, чтобы никакие два одинаковых цвета не были смежными друг с другом - никакие две соседние вершины или ребра не были бы одного цвета.

Я наткнулся на этот алгоритм и думал о его назначении. По мере того, как я более глубоко изучал проблемы раскраски графов и их варианты использования, я понял, что они широко используются в приложениях, которые мы используем. В этой статье мы кратко расскажем об этом алгоритме и вариантах использования раскраски графов.

Алгоритм

Есть много способов решения задач раскраски графов. Вы можете выполнять окраску вершин, окраску ребер и географическую окраску карты. В этом алгоритме можно задавать разные вопросы. Например, мы можем ответить на вопросы о том, что одни и те же ресурсы не зависят друг от друга одновременно. Мы также можем ответить на вопросы о том, какое минимальное количество цветов необходимо для раскрашивания этого графика. Более того, мы можем превратить это в вопрос с возвратом, где мы хотим найти все возможные методы раскраски, которые могут раскрасить этот график.

Это будет простой вариант использования. Как только мы узнаем основной алгоритм, мы всегда сможем ответить на эти вопросы.

Предположим, это раскраска вершин, где я хочу раскрасить граф так, чтобы никакие две соседние вершины не имели одинаковый цвет.

Предположим, у нас есть пять вершин в графе. Максимальное количество цветов, которое мы можем назначить каждой из вершин, - пять. Следовательно, мы можем инициализировать наш список цветов пятью цветами.

Затем мы можем начать раскрашивать первую вершину на пустом графе. Вы можете выбрать любой случайный - неважно.

В следующем алгоритме мы раскрашиваем каждую вершину в графе на основе следующей операции:

  • Перебрать все соседние вершины. Если соседняя вершина имеет цвет, поместите этот цвет в ведро (набор).
  • Выберите первый цвет, которого нет в этом ведре (коллекции), и назначьте его текущей вершине.
  • Опустошите ведро и перейдите к следующей неокрашенной вершине.

Этого жадного алгоритма достаточно для решения раскраски графа. Хотя он не гарантирует минимальный цвет, он обеспечивает верхнюю границу количества цветов, назначенных графику.

Мы перебираем вершину и всегда выбираем первый цвет, которого нет в соседней вершине. Порядок, в котором мы запускаем наш алгоритм, имеет значение.

Если вершины, которые мы повторяем, имеют меньше входящих ребер, нам может потребоваться больше цвета для окраски графа. Следовательно, существует другой алгоритм, называемый алгоритмом Уэлша-Пауэлла.

Я хочу объяснить, как работает алгоритм Уэлша-Пауэлла. Чтобы доказать, что на графике будет гарантировано минимальное количество раскрасок, ознакомьтесь с приведенными ниже ресурсами. Есть много вещей, в которые стоит погрузиться в этой теме.

Алгоритм следующий:

  1. Подсчитайте входящие ребра в каждой вершине и расположите их в порядке убывания.
  2. Выберите первую вершину с наибольшим входящим порядком и назначьте вершинам цвет - назовем ее вершиной A.
  3. Пройдитесь по другим вершинам, назначьте им цвет, если только 1. Он не смежен с вершиной A. 2. Вершины еще не раскрашены. 3. Сосед этой вершины не того же цвета, что и вершина A.
  4. Продолжайте делать шаг 3, пока все вершины не будут окрашены.

Теперь, когда вы получили представление о том, как выглядит алгоритм раскраски графов, вам может быть интересно, какой в ​​этом смысл?

Случаи применения

Обычно алгоритм раскраски графа используется для решения задач, где у вас ограниченное количество ресурсов и другие ограничения. Цвет - это просто абстракция тех ресурсов, которые вы пытаетесь оптимизировать. График - это абстракция вашей проблемы.

Графы часто моделируются как реальные проблемы, и мы можем использовать алгоритмы для поиска любых атрибутов в графе, чтобы ответить на некоторые из наших вопросов.

Давайте посмотрим на некоторые варианты использования раскраски графов.

Алгоритм планирования

Представьте, что у вас есть несколько дел и несколько рабочих. Было бы полезно, если бы вы назначили рабочих на работу в течение определенного временного интервала. Вы можете назначать задания в любом порядке, но пара заданий может конфликтовать во временном интервале, потому что они используют одни и те же ресурсы. Как эффективно распределять задания, чтобы не возникало конфликта между заданиями? В этом случае вершины могут быть заданиями, а ребра могут быть соединением двух заданий, если они используют одни и те же ресурсы. Если у вас неограниченное количество рабочих, вы можете использовать алгоритм раскраски графа, чтобы получить оптимальное время для планирования всех заданий без конфликтов. В этом случае цветом будет номер рабочего. Если двум вершинам (заданиям) назначен один и тот же цвет, этот рабочий будет обрабатывать эти два задания.

Другой пример - составление расписания или расписания. Вы хотите составить планировщик экзаменов. У каждого предмета будет список студентов, и каждый студент будет брать несколько уроков. Вы хотите убедиться, что запланированные вами экзамены не противоречат друг другу. В этом случае вершины могут быть классами, и между двумя классами есть ребра, если один и тот же ученик находится в обоих классах. Цвет на графике в этом случае будет числом временных интервалов, необходимых для планирования экзаменов. Итак, один и тот же цвет на вершине A и вершине B означает, что A и B будут проводиться в одном временном интервале.

Обычно в этом типе проблемы есть общие ресурсы, и мы хотим иметь планировщик, чтобы гарантировать, что никакие два объекта в вашей системе не конфликтуют. Цвет обычно представляет временной интервал или рабочих.

Раскраска карты

Раскраска географической карты - это проблема, когда никаким двум соседним городам или штатам нельзя присвоить на карте один и тот же цвет. Согласно теореме о четырех цветах, четырех цветов достаточно, чтобы раскрасить любую карту. В этом случае вершина представляет каждую область, и каждый из ее смежных элементов можно классифицировать как ребро.

Судоку Головоломка

Судоку - это разновидность задачи раскраски графа, где каждая ячейка представляет собой вершину. Ребро образуется в пределах двух вершин, если они находятся в одной строке, столбце и блоке. Каждый блок будет иметь свой цвет.

Распределение регистров для компилятора

Компилятор - это программа, которая преобразует исходный код с высокого уровня (Java, Scala) в код машинного уровня. Обычно это делается отдельными шагами. Один из самых последних шагов - выделить регистры для наиболее частых значений программ, а другие поместить в память. Мы можем моделировать символьные регистры (переменные) как вершины, и ребро образуется, если две переменные необходимы одновременно. Если граф можно раскрасить в K цветов, то переменные можно сохранить в k зарегистрированных.

Есть много других вариантов использования алгоритмов раскраски графов. Надеюсь, вы кое-что узнали!

Ресурсы

Есть несколько отличных ресурсов по алгоритму Graph Coloring, а также по его вариантам использования. Если вам интересно узнать больше, ознакомьтесь с ресурсами ниже: