Функция Гранди

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

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

Если необходимо покрасить вершину x_j графа, смежную с вершинами x_r, x_n и x_k, которые уже выкрашены, например, в цвета с номерами 0, 1 и 3, то вершина x_j красится в цвет, номер которого минимален и не равен номерам цветов смежных вершин – значит в цвет 2.

Общий подход к раскраске графа с помощью функции Гранди сводится к следующему:

1. На графе выбирают произвольную вершину. Её окрашивают в цвет, номер которого минимален.

2. Выбирают вершину графа, смежную с окрашенной, и красят её в цвет, номер которого минимален и не равен номеру цвета окрашенной вершины.

3. Далее ищут, если это возможно, вершину, смежную с окрашенными, и красят её в цвет, номер которого минимален и не равен номерам цветов окрашенных вершин.

4. Логически продолжают п. 3, ищут вершину, смежную с 3-мя и т.д. пока это возможно.

5. Далее окрашивают оставшиеся вершины согласно п. 1, 2, 3, 4.

Числом внутренней устойчивости графа называется максимальная мощность максимального внутренне устойчивого множества вершин.

Из 3-х вариантов разбиения вершин графа 1, 2, 3 выпишем максимальное внутренне устойчивое подмножество:

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

Задача. Необходимо разместить по ящикам следующие грузы:

1 – рыба в пакетах

2 – книги

3 – консервы в металлических банках

4 – мягкие игрушки

5 – техническая документация

6 – мука в бумажных пакетах

7 – ткань в рулонах

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

Соединяем рёбрами те вершины, грузы которых нельзя помещать в один ящик.

N₁ = {1, 3}, N₂ = {2, 4, 5, 7}, N₃ = {6}

Необходимо 3 ящика.