Алгоритм раскраски графа (точный) — страница 4

  • Просмотров 3904
  • Скачиваний 89
  • Размер файла 133
    Кб

FjF, в которые оно входит и запишем произведение этих сумм ПС=(F4+F5)(F2+F3)F1*(F1+F3+F5)F4*(F2+F4)F4=(F2+F3F4)F1F4=F1F2F4+F1F3F4. Каждое из двух полученных слагаемых содержит в неявном виде все вершины графа G =(Х,U), Таким образом, для раскраски требуется минимум 3 цвета. Раскроем слагаемые и удалим дублирующие вершины. В результате получаем два варианта решения: F1F2F4={ХЗ,Х4;Х2;Х1,Х5,Х6,Х7} или F1F2F4={ ХЗ,Х4;Х2X6;Х1,Х5,Х7}; F1F3F4={X3;X2,Х4;Х1,Х5,Х6,Х7} или F1F3F4={XЗ,X4;X2;X1,X5,Xб,X7}. Первый и

последний варианты совпали. Получены три различных варианта минимальной раскраски вершин графа. 2.2 Разработанный алгоритм Разработанный алгоритм работает на основе операций с матрицей смежности. Данный алгоритм реализуется следующим образом: За основу берется матрица смежности M для данного графа G. Затем создается массив A, в каждой строке которого содержится множество вершин A[i]. первым элементом этого множества является

вершина Xi0, номер которой совпадает с номером строки. Остальные члены этого множества – все вершины данного графа G, смежные первой вершине из этого множества. Далее с этим массивом A проводятся следующие манипуляции: Множество вершин A[i] в каждой строке просматривается, начиная со второго элемента Xi1 этого множества A[i], и по матрице смежности M устанавливается, смежна ли данная вершина Xij всем предыдущим вершинам из множества A[i],

начиная с первой – Xi0. Если обнаруживается, что одна из вершин Xij при рассмотрении не смежна с другими вершинами Xik (k=0,j-1) этого множества A[i], то она удаляется из этого множества. Продолжается рассмотрение остальных вершин Xij до тех пор, пока множество не рассмотренных вершин не станет пустым. Таким образом, из данного множества вершин A[i], смежных с первой вершиной этого множества – Xi0 будут удалены все те вершины, которые не смежны

всем остальным вершинам этого множества A[i]. Таким образом, оставшееся множество вершин A[i] будет являться максимальным полным подграфом от первой вершины этого множества Xi0. После рассмотрения одного множества A[i] в массиве A рассматриваются следующие, по той же схеме. Из них также удаляются вершины. В конечном счече будет получен массив A, в каждой i-й строке которого будет содержаться максимально полный подграф A[i], возможный от

i-й вершины Xi0. На следующем шаге алгоритма будет создан еще один массив B, содержащий множество целых чисел. Каждый i-й элемент B[i] этого множества B представляет собой количество вершин в соответствующем максимально полном подграфе A[i]. Например если 3-й элемент данного множества равен 5, это означает, что максимально полный подграф, построенный от 3-ей вершины состоит из 5 вершин, включая 3-ю. множество вершин {X30..X34}, которые