Модифікація алгоритму визначення клік графа з параметричної адаптацією

В.А. Литвиненко И.Ю. Черненко

1. Основні положення

Кликов графа називається максимальний повний подграф, який не входить ні в один повний подграф більше високого порядку/1 /.

Під точністю рішення задачі визначення клік графа будемо розуміти кількість виділених клік. При цьому, якщо виділені всі кліки графа, то точність рішення дорівнює 100%.

Розглядається клас неріентірованних графів без петель і кратних ребер.

комбінаторна складність точних алгоритмів визначення клік графа призводить до необхідності використовувати наближені методи при вирішенні задач великої розмірності. До таких завдань, у зокрема, відносяться різні задачі конструкторського проектування інтегральних схем, у яких алгоритми визначення клік графа застосовуються в якості алгоритмів проектних операцій. Відомі алгоритми/1,2/дозволяють визначати тільки такі сімейства клік графа, властивості і потужність яких залежать від структури розв'язуваних графів і послідовності виконання самого алгоритму. Від якісного вирішення алгоритмів проектних операцій істотно залежить якість рішення алгоритмів проектних процедур.

Основними факторами, що впливають на якість виконання алгоритмів проектних операцій, є:

необхідна точність рішення;

ресурс часу, відведений на виконання проектної операції;

розмірність конкретної завдання.

Із вказаних факторів відомі наближені методи дозволяють враховувати тільки обмеження на час виконання алгоритму - ресурс часу шляхом переривання рішення в момент його закінчення/2 /.

Однак, можлива ситуація, коли ресурсу часу достатньо для отримання навіть точного рішення, а необхідна точність і розмірність задачі дозволяють виконати алгоритм за час менше, ніж ресурс часу. Можлива й інша ситуація, коли розмірність завдання і ресурс часу не дозволяють отримати необхідну точність рішення.

Можливість алгоритмічними методами враховувати такі випадки дозволяє оптимізувати час виконання алгоритму проектної операції проектної процедури і тим самим підвищувати ефективність використання математичного та програмного забезпечення САПР.

2. Базовий алгоритм

В/3/розроблений алгоритм визначення клік графа, що відрізняється від відомих можливістю адаптації до зміни ресурсу часу, необхідної точності і розмірності самої завдання, призначений для дослідження неорієнтовані графів без петель і кратних ребер. В основу алгоритму покладено метод параметричної адаптації, який дозволяє за допомогою вхідних параметрів "настроювати" алгоритм визначення клік графа на отримання рішень з різним ступенем точності. При цьому точність рішення може змінюватися від отримання точного рішення задачі визначення клік графа, тобто визначення всіх клік графа, до визначення такої кількості клік графа, якого достатньо для отримання рішення проектної процедури, для якої завдання визначення клік графа використовується в якості алгоритму проектної операції.

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

В основу базового алгоритму покладена наступна теорема, доведена в роботі/4 /.

Нехай у графі G = (X, U) є вершина і визначена кліка з безліччю вершин , де . Тоді, якщо виділені всі кліки, то й будуть виділені всі кліки.

Практичне значення цієї теореми полягає в наступному.

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

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

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

Позначимо таке число клік l. Тоді, задаючи значення l, можна "управляти" точністю рішення, одержуваного базовим алгоритмом, настраіваівая його на отримання рішення з різним ступенем точності.В такому разі l є параметром базового алгоритму визначення клік графа. Використання параметра для адаптації до алгоритму зовнішніх умов - необхідної точності рішення і послужило введенням назви класу алгоритмів - алгоритми з параметричної адаптацією.

Відзначимо, що при збільшенні l в граничному випадку точність рішення, яку можна отримати за допомогою базового алгоритму, відповідає кількості клік графа, яке може бути отримана за допомогою алгоритму визначення клік, покривають всі ребра графа/1,2 /. Це означає, що з допомогою базового алгоритму не можна отримати рішення з нульовою точністю.

Розглянутий базовий алгоритм покладений в основу модифікованого алгоритму, що пропонується в дипломної роботи.

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

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

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

У роботі пропонується для реалізації цього шляху розглядати вершини графа в порядку, відповідному зменшенню локальних ступенів вершін.Ето пов'язане з припущенням, що вершини, що мають велику локальну ступінь, найімовірніше будуть утворювати та кліки, що містять більше число вершин. Такий підхід і покладений в основу модифікації базового алгоритму.

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

Оцінимо складність модифікованого алгорітма.Оценка складності проводиться з метою показати аналітично правильність зробленого вище припущення.

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

Нехай n -- кількість стовпців першого рядка матриці, а b - Середня потужність клік у графі. Тоді, якщо оцінювати кількість операцій логічного множення елементів двох стовпців двох рядків матриці суміжності, то кількість операцій визначення однієї кліки буде складати суму членів арифметичній прогресії з кроком 1, перший член якої дорівнює (n-1), а кількість членів прогресії дорівнює (b-1), тобто

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

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

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

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

У відповідність з правилами перетворення O-функцій останнім вираз можна перетворити до наступного виду

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

Тепер, при b, яка прагне до n, O (0,5 (b-1) (2n-b-4) (nb)) ® O (n),

а при b, яка прагне до 0,5 n , 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