Алгоритмы и структуры данных ИДЗ по теме Графы

1. Текст индивидуального задания. № варианта: 16 Алгоритм для исследования : Раскраска минимальным числом цветов вершин неориентированного графа с соблюдением условия: никакое ребро не соединяет вершины одного цвета 2. Математическая формулировка задачи в терминах теории множеств. Раскраской вершин графа G = (V,E) является функция c : V → ℕ, которая каждой вершине графа ставит в соответствие натуральное число(цвет) так, что любым двум инцидентным вершинам u, v ∈ V назначаются разные цвета: {u, v} ∈ E ⇒ c(u) ≠ c(v). Имеется граф G = (V,Е), где V - множество вершин, Е - множество ребер между ними. Необходимо назначить каждой вершине v ∈ V цвет так, чтобы общее количество цветов было минимальным. 3. Выбор и обоснование способа представления данных. Для представления данных мной использовалось два различных класса: Node (узел) и Graph (граф в целом). Необходимость в использовании последнего объясняется тем, что: Во время выполнения некоторых операций над графом требуется доступ ко всем его узлам, Граф может состоять из нескольких не связных между собою компонент. Класс Node содержит метку узла (символ char), его цвет (натуральное число), а также вектор, содержащий указатели на смежные вершины. Выбор в пользу вектора, состоящего из указателей, а не битов, объясняется возможностью запроса дополнительных сведений о соседней вершине, недоступных из самого узла. В случае, если бы указатели имелись только в Graph, их все равно пришлось бы передавать в функцию (к примеру, в качестве параметра), что довольно неудобно в силу произвольного числа смежных вершин. В силу постановки задачи, задание ориентированного графа не имеет практического смысла. Graph состоит из вектора, содержащего все вершины, счетчика цветов, а также матрицы смежности. Несмотря на то, что, на первый взгляд, использование последней дублирует данные о соседях, уже имеющиеся в каждом соседнем узле, такая структура позволяет упростить работу алгоритма, сводя проверку смежности любых двух узлов к одному шагу. В качестве наглядного представления графа используется список смежности с указанием цветов и матрица смежности. 4. Описание алгоритма и оценка его временной сложности. 1) Генерация случайного графа: вначале генерируется набор отдельных узлов, размещаемых в векторе класса Graph, каждому из которых присваивается уникальный тег. Затем, вершины случайным образом соединяются ребрами (т.е., каждая из них получает указатель на соседнюю, и соответствующие изменения заносятся в матрицу смежности). Полученный при этом граф чаще всего являет собой множество «самостоятельных» вершин и отдельных связных подграфов (с циклами или без). Стоит отметить, однако, что вероятность появления полного или нулевого графа крайне мала. Исходя из этого, невозможно дать однозначную оценку хроматического числа графа для общего случая. Мною был использован алгоритм из учебника Ф.А. Новикова, относящийся к приближенным алгоритмам. В ряду случаев такой выбор, действительно, может не находить точного решения поставленной задачи, однако, достаточно эффективен для небольших множеств. 2) Последовательный обход вершин графа: - если вершина не окрашена, присваиваем ей минимальный из доступных (т.е. такой, в какой не окрашена ни одна из соседних) вершин в диапазоне от 1 до cur, где cur – текущее число используемых красок. - если все краски уже использованы, то увеличиваем cur на единицу и красим вершину в этот цвет. 3) Вывод результата работы программы. Стоит отметить, что существует «улучшенная» версия того же алгоритма, отличающаяся от описанной тем, что перед раскраской вершины графа упорядочиваются в порядке невозрастания. Впрочем, проверка программы с использованием одних и тех же тестов действительно привела к одним и тем же результатам вне зависимости от упорядоченности графа, в то время как отказ от дополнительного перебора всех узлов в процессе сортировки позволяет сэкономить время работы алгоритма.