Модифицированный алгоритм

3. Модифицированный алгоритм

Процесс перебора полных подграфов для каждой вершины  в базовом алгоритме связан с перебором всех вершин, смежных с вершиной . Тогда чем больше вершин, смежных с вершиной , будет исключено из рассмотрения, тем больше будет сокращен перебор полных подграфов.

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

В работе предлагается для реализации этого пути рассматривать вершины графа в порядке, соответствующем уменьшению локальных степеней вершин.Это связано с предположением, что вершины, имеющие большую локальную степень, вероятнее всего будут образовывать и клики, содержащие большее число вершин. Такой подход и положен в основу модификации базового алгоритма.

4. Оценка сложности модифицированного алгоритма

Оценим сложность модифицированного алгоритма.Оценка сложности производится с целью показать аналитически правильность сделанного выше предположения.

Алгоритм соотоит из иттераций, каждая из которых связана с одной стокой треугольной матрицы смежности. Нетрудно заметить, что трудоемкость выполнения одной иттерации будет наибольшей для первой строки матрицы смежности. Поэтому для того, чтобы оценить преимущество модифицированного алгоритма, достаточно оценить сложность определения клик графа для первой строки матрицы смежности.

Пусть n – количество столбцов первой строки матрицы, а b - средняя мощность клик в графе. Тогда, если оценивать количество операций логического умножения элементов двух столбцов двух строк матрицы смежности, то количество операций определения одной клики будет составлять сумму членов арифметической прогрессии с шагом 1, первый член которой равен (n-1), а количество членов прогресси равно (b-1), т.е.

0,5(b-1)(2n-b-n).

Так как вершины каждой первой выделенной клики из рассмотрения исключаются, то количество операций логического умножения элементов строки со строками матрицы, номерам которых в строке соответствуеют значения, равные 1, в худшем случае будет равно (b-1).

Таким образом оценка числа операций логического умножения, которые необходимо произвести для элементов строки , составляет

O(0,5(b-1)(2n-b-4)(n-b)).

В соответствие с правилами преобразования O-функций последнее выражение можно преобразовать к следующему виду

O(b(2n-b)(n-b)).

Теперь, при b, стремящемся к n , O(0,5(b-1)(2n-b-4)(n-b)) ® O(n),

а при b, стремящемся к 0,5n , O(0,5(b-1)(2n-b-4)(n-b)) ® O(n).

Таким образом, эффективность модифицированного алгоритма возрастает с увеличением b -средней мощности клик в графе, т.е. аналитичеки подтверждается предположение, положенное в основу модификации базового алгоритма.

5. Реализация модифицированного алгоритма

Разработана программа на Borland C++ Builder для Windows`95 и проведено исследование эффективности предложенного модифицированного алгоритма на графах размерности до 500 вершин, а также на графах Муна-Мозера, которые являются критическими для задачи определения клик графа, так как содержат набольшее количество клик для графов с одинаковым числом вершин.

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

Исследования показали, что предложенная модификация алгоритма позволяет сократить время выполнения базового алгоритма, при этом наибольший эффект достигается при исследовании графов со средней мощностью клик близкой к числу вершин графа.

Список литературы

Мелихов А.Н., Берштеин Л.С., Курейчик В.М. Применение теории графов для проектирования дискретных устройств.М.:Сов.радио,1975.224с.

Литвиненко В.А. Методы определения семейств клик графа. В кн.: Методы и программы решения оптимизационных задач на графах и сетях. Часть 2. Теория, Алгоритмы. Новосибирск:1982,с.90-92.

Калашников В.А., Литвиненко В.А. К вопросу определения семейств клик графа.30. Intern. Wiss. Koll. TH llmenau Vortragsreihe.1985.c.41-44.

Литвиненко В.А. Курейчик В.М. Определение клик симметрического графа //Известия Северо-Кавказского научного центра высшей школы. Технические науки, 1979,№2,с.13-16