Раскраска графа, реализация в программе

Под раскраской графа будем понимать раскрашивание, как ребер графа, так и вершины.

Набор вершин графа называется максимальной независимой системой (МНС), если любые две вершины из этого набора не являются смежными и нельзя включить в этот набор другую вершину, чтобы это условие сохранилось.
Нахождение МНС в графе: берем произвольную вершину, затем находим любую вершину, не смежную с ней, затем находим вершину, не смежную с отобранными вершинами и т. д. МНС в графе может быть много и они могут содержать разное число вершин.
Функцией Гранди - называется функция на вершинах графа, отображающая вершины в множество {1,2,…, a}, причем если вершина xi окрашена в цвет с номером k, то функция Гранди h(xi) = k Хроматическое число(наименьшее число цветов) - является единственным, но функций Гранди может быть много. Нахождение хотя бы одной функции Гранди – значит, найти одну из возможных раскрасок (таких раскрасок может быть много).

Первый алгоритм нахождения раскраски вершин графа.

Пусть имеем граф G, найдем в нем какую-либо МНС, которую обозначим S1, и все вершины, входящие в эту МНС, окрасим в цвет № 1. Далее, удалим из данного графа все вершины, входящие в эту МНС (вместе с ребрами), и для нового графа снова найдем МНС, которую обозначим S2. Новые вершины окрасим в цвет № 2, затем удалим эти вершины из графа вместе с соответствующими ребрами, снова находим МНС, которую окрасим в цвет № 3, и т. д. При любом способе осуществления этой процедуры придем к наилучшей раскраске и найдем некоторую функцию Гранди и хроматическое число данного графа.

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