Алгоритм раскраски графа Уэльса Пауэлла
В теории графов раскраска вершин - это способ пометить каждую отдельную вершину таким образом, чтобы никакие две соседние вершины не имели одинаковый цвет. Но нам нужно узнать, сколько цветов нам нужно, чтобы удовлетворить заданному условию. Нежелательно иметь большое разнообразие цветов или этикеток. Итак, у нас есть алгоритм, называемый валлийским алгоритмом Пауэлла, который дает минимальный необходимый нам цвет. Этот алгоритм также используется для нахождения хроматического числа графа. Это итеративный жадный подход.
Хроматическое число : граф G, которому для правильной раскраски требуется K различных цветов, и не меньше, называется K-хроматическим графом, а число K называется хроматическим числом графа G.
Алгоритм Уэльса Пауэлла состоит из следующих шагов:
- Найдите степень каждой вершины
- Перечислите вершины в порядке убывания степеней.
- Раскрасьте первую вершину в цвет 1.
- Переместитесь вниз по списку и закрасьте все вершины, не связанные с цветной вершиной, в один цвет.
- Повторите шаг 4 для всех неокрашенных вершин с новым цветом в порядке убывания степеней, пока все вершины не будут окрашены.
Начиная с наивысшей степени, мы гарантируем, что вершина с наибольшим количеством конфликтов может быть устранена как можно раньше.
| Вершина | Степень |
|---|---|
| А | 2 |
| B | 2 |
| C | 1 |
| D | 4 |
| E | 2 |
| F | 2 |
| грамм | 3 |
| ЧАС | 5 |
| я | 3 |
| J | 3 |
| K | 5 |
Сначала расположите список в порядке убывания степеней. В случае ничьей мы можем случайным образом выбрать любые способы ее разрыва.
Итак, новый порядок будет: H, K, D, G, I, J, A, B, E, F, C.
Теперь, следуя алгоритму раскраски графа Уэлша Пауэлла,
H - цвет Красный
K - не окрашивать в красный цвет, так как он соединяется с H
D - цвет Красный
G - не красить красный, так как он соединяется с H
I - не окрашивать в красный цвет, так как он соединяется с H
J - не окрашивать в красный цвет, так как он соединяется с H
A - не окрашивать в красный цвет, так как он соединяется с H
B - не окрашивайте в красный цвет, так как он соединяется с D
E - цвет Красный
F - не окрашивать в красный цвет, так как он соединяется с E
C - не окрашивать в красный цвет, так как он соединяется с D
После этого график будет выглядеть так, как показано ниже.
Игнорируя уже окрашенные вершины, у нас остаются: K, G, I, J, A, B, F, C
Мы можем повторить процесс со вторым зеленым цветом.
К - цвет зеленый
G - не окрашивать в зеленый цвет, так как он соединяется с K
I - цвет зеленый
J - не окрашивать в зеленый цвет, так как он соединяется с I
А - цвет зеленый
B - не окрашивать в зеленый цвет, так как он соединяется с A
F - цвет зеленый
C - цвет зеленый
Опять же, игнорируя окрашенные вершины, у нас остаются G, J, B. Давайте раскрасим его в синий цвет.
G - цвет синий
J - цвет синий
B - цвет синий
Окончательный рисунок показан ниже. Теперь мы видим, что с помощью алгоритма Уэлша Пауэлла мы можем раскрасить вершины только тремя типами цветов ( хроматическое число этого графа равно 3 ), что является оптимальным решением, поскольку этот граф содержит хотя бы один треугольник.