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}, которые составляют этот подграф A[3] является мнжеством вершин в 3 строке массива A.

После того, как были созданы массивы A и B, создается линейный список С, каждый элемент которого содержит множество вершин X, составляющих уникальный наибольший полный подграф графа G.

Очевидно, что массив A будет содержать в себе одиаковые множества вершин. Единственным отличием этих множеств друг от друга будет то, что первый элемент каждого такого множества будет отличен от первого элемента такого же множества, находящегося в массиве A.

Например, если в массиве A имеется следующее множество вершин, состовляющее полный подграф: {2,4,5,7}, что означает, что во 2 строке массива А содержится это множество вершин, состоящее из 4 элементов, массив В содержит 4 одинаковых элемента - 4 по адресам 2,4,5,7. Однако это означает, что в 4, 5 и 7 строках массива А будет содержаться то же самое множество вершин.

Во время формирования списка С этот факт учитывается.

Список формируется следующим образом: в массиве В ищется максимальный элемент bmax. Это целое число, показывающее размер наибольшего полного подграфа графа G. Затем просматривается массив В. И если соответствующий элемент B[i]по адресу i равен bmax, то создается новый элемент в списке, в него заносится наибольший полный подграф из массива А по адресу i. Проводится дальнейший просмотр массива В и ищутся другие подграфы, содержащие bmax вершин. Если таковые находятся (а они обязательно находятся) то на этом этапе выполняется проверка, не добавлено ли уже это множество вершин A[i] в список НПП. Проверка осуществляется следующим образом: список С просматривается сначала, и каждое множество вершин, содержащееся в элементе этого списка сравнивается с множеством A[i]. Если обнаруживается, что такое множество A[i] уже содержится в списке С, то оно пропускается, происходит дальнейшее рассмотрение массива В. В противном случае, если такое множество не было найдено в списке, то создается еще одна ячейка списка С и в нее записывается множество A[i].

Таким образом, после того, как закончится рассмотрение массива В, то есть будут рассмотрены все возможные НПП и уникальные будут добавлены в список С, полученный список С будет содержать в себе все возможные НПП для данного графа G.