Таким образом оценка числа операций логического умножения, которые необходимо произвести для элементов строки , составляет
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