В.А. Литвиненко І.Ю. Черненко
1. Основні положення
Клікою графа називається максимальний повний підграф, який не входить ні в один повний підграф вищого порядку / 1 /.
Під точністю рішення задачі визначення клік графа будемо розуміти кількість виділених клік. При цьому, якщо виділені всі кліки графа, то точність рішення дорівнює 100%.
Розглядається клас неріентірованних графів без петель і кратних ребер.
Комбінаторна складність точних алгоритмів визначення клік графа призводить до необхідності використовувати наближені методи при вирішенні задач великої розмірності. До таких завдань, зокрема, відносяться різні завдання конструкторського проектування інтегральних схем, в яких алгоритми визначення клік графа застосовуються в якості алгоритмів проектних операцій. Відомі алгоритми / 1,2 / дозволяють визначати тільки такі сімейства клік графа, властивості і потужність яких залежать від структури розв'язуваних графів і послідовності виконання самого алгоритму. Від якісного вирішення алгоритмів проектних операцій істотно залежить якість рішення алгоритмів проектних процедур.
Основними факторами, що впливають на якість виконання алгоритмів проектних операцій, є:
необхідна точність рішення;
ресурс часу, відведений на виконання проектної операції;
розмірність конкретного завдання.
Із зазначених факторів відомі наближені методи дозволяють враховувати тільки обмеження на час виконання алгоритму - ресурс часу шляхом переривання рішення в момент його закінчення / 2 /.
Однак, не виключено, коли ресурсу часу достатньо для отримання навіть точного рішення, а необхідна точність і розмірність завдання дозволяють виконати алгоритм за час менше, ніж ресурс часу. Можлива й інша ситуація, коли розмірність завдання і ресурс часу не дозволяють отримати необхідну точність рішення.
Можливість алгоритмічними методами враховувати такі випадки дозволяє оптимізувати час виконання алгоритму проектної операції проектної процедури і тим самим підвищувати ефективність використання математичного та програмного забезпечення САПР.
2. Базовий алгоритм
В / 3 / розроблений алгоритм визначення клік графа, що відрізняється від відомих можливістю адаптації до зміни ресурсу часу, необхідної точності і розмірності самої завдання, призначений для дослідження неорієнтованих графів без петель і кратних ребер. В основу алгоритму покладено метод параметричної адаптації, який дозволяє за допомогою вхідних параметрів "налаштовувати" алгоритм визначення клік графа на отримання рішень з різним ступенем точності. При цьому точність рішення може змінюватися від отримання точного рішення задачі визначення клік графа, тобто визначення всіх клік графа, до визначення такої кількості клік графа, якого достатньо для отримання рішення проектної процедури, для якої завдання визначення клік графа використовується в якості алгоритму проектної операції.
Таким чином, розглянутий алгоритм дозволяє отримувати рішення з різним ступенем точності і при цьому допускає принципову можливість визначення всіх клік графа. тобто отримувати точне рішення. Цей алгоритм використовується в якості базового алгоритму для модифікованого алгоритму, розглянутого в даній роботі.
В основу базового алгоритму покладена наступна теорема, доведена в роботі / 4 /.
Нехай в графі G = (X, U) є вершина
і визначена кліка
з безліччю вершин