РОЗДІЛ 2
ДОСЛІДЖЕННЯ ОБЧИСЛЮВАЛЬНОЇ СКЛАДНОСТІ ЗНАХОДЖЕННЯ ПОВНОЇ МНОЖИНИ АЛЬТЕРНАТИВ
ДЛЯ РІЗНИХ ПОСТАНОВОК ЗАДАЧІ ПОКРИТТЯ ГРАФА ТИПОВИМИ ПІДГРАФАМИ
Використовуване в цьому розділі поняття "обчислювальна складність" визначається в класичному змісті, що поданий у фундаментальних роботах з теорії обчислювальної складності задач дискретної математики [5,25,64,91]. Мова йде про оцінки складності "за найгіршим випадком"[5,25]. Варто особливо відзначити, що в переважній більшості публікацій, присвячених дослідженню обчислювальної складності дискретних задач, розглядається або задача розпізнавання, або оптимізаційна задача. Систематичний огляд обчислювальної складності дискретних багатокритеріальних задач здійснено у роботі [33]. Що стосується обчислювальної складності дискретних інтервальних задач, то до теперішнього часу публікації на цю тему відсутні.
Згідно з [33], будемо оцінювати обчислювальну складність знаходження ПМА в шкалі вигляду: "поліноміальні задачі" - "NP-важкі задачі" - "важкорозв'язувані задачі" . Зауважимо, що поняття NP-важкої задачі за [25] означає оптимізаційну постановку NP-повної задачі розпізнавання.
Як стверджують в [33], обчислювальна складність знаходження ПМА зростає (чи принаймні не спадає) в міру поповнення ВЦФ новими критеріями. Як правило, та чи інша екстремальна задача на графах стає важкорозв'язуваною в той момент, коли її ВЦФ поповнилася хоча б парою критеріїв вигляду MAXSUM (1.4) чи MINSUM .
Метою розділу є аналіз і оцінка обчислювальної складності різноманітних постановок задач, що є математичними моделями змістовних проблем, описаних вище.
2.1. Оцінки обчислювальної складності для оптимізаційної задачі покриття з одним типовим підграфом
Розглянемо послідовність множин типових графів , , де означає число вершин у типових підграфах, що складають множину . З алгоритмічної точки зору задача покриття графа типовими підграфами стає нетривіальною, починаючи з . При одержуємо відому задачу про довершені паросполучення, що є поліноміально розв'язуваною [64]. При отримуємо дві задачі: про 3-сполучення і про покриття даного графа 3-вершинними ланцюгами. В оптимізаційній постановці ці задачі є -важкими [25]. При множина складається із шести типових підграфів, поданих на рис.1.5. До цього часу залишається відкритим питання про оцінки обчислювальної складності задач покриття графа типовими підграфами з як в оптимізаційній, так і в багатокритеріальній постановці. З огляду на актуальність цих задач і їх застосувань, досліджуємо в запропонованому розділі оцінки обчислювальної складності оптимізаційних і векторних задач покриття графа типовими підграфами з .
Оцінимо спочатку обчислювальну складність знаходження хоча б одного припустимого розв'язку сформульованої вище задачі покриття графа типовими підграфами вигляду (рис. 1.6). Умовимося надалі називати підграф вигляду "ракеткою" . Доведемо, що справедливою є наступна лема.
Лема 2.1. При n, кратному 4, задача покриття n-вершинного графа типовими підграфами вигляду є NP-повною.
Доведення. Спочатку розглянемо так звану задачу 3-С чи задачу про три-сполучення, яка, як відомо [25], є NP-повною. Далі під назвою "задача 2" розглянемо задачу покриття графа типовими підграфами . Ідея доведення леми 2.1 полягає в тому, що задача 3-С є частковим випадком (звуженням) задачі 2, і NP-повнота задачі 2 випливає з природного зведення до неї задачі 3-С [25]. Припустимим розв'язком задачі 3-С для даного графа є такий його остовний підграф, кожна компонента зв'язності якого є 3-вершинним циклом. Множина 3-вершинних циклів, що не перетинаються, у графі G називається три-сполученням цього графа. Таким чином, екстремальна задача про три-сполучення з цільовою функцією (ЦФ) вигляду MAXSUM
(2.1 )
є NP-важкою, причому ця задача залишається NP-важкою і у випадку, коли вона розглядається на повних зважених графах.
Для обґрунтованого доведення леми 2.1 розглянемо однокритеріальну задачу покриття графа типовими графами вигляду на множині n-вершинних 1-зважених графів наступного вигляду. Множина вершин V складається з підмножин і , потужність яких відповідно дорівнює . Підграф , індукований у множиною , є повним m-вершинним графом, множину ребер якого позначимо через . Вершини підмножини попарно не суміжні, причому кожна вершина суміжна з усіма вершинами підмножини . Через позначимо сукупність усіх ребер, що з'єднують вершини підмножин і . Таким чином, одержуємо розбиття множини на підмножини і . Кожному ребру приписана вага , усякому ребру приписана вага , тобто ваги ребер будь-якого графа задовольняють умові:
, якщо ; , якщо . (2.2 )
Із визначення графа і умови (2.2) випливає взаємозвідність задачі про три-сполучення на підграфі і задачі покриття графа типовими графами . Так, нехай знайдено оптимальний (за ЦФ (2.1)) розв'язок задачі про три-сполучення на . Тоді, приєднавши до кожного трикутника знайденого оптимального три-сполучення по одному ребру з множини Е2 (дотримуючись принципу попарного неперетинання цих ребер), одержимо оптимальний розв'язок задачі покриття даного графа типовими підграфами . Тобто алгоритм знаходження оптимального покриття графа типовими підграфами складається з двох етапів. На першому етапі знаходиться оптимальне 3-сполучення на підграфі , а на другому - задача про паросполучення на дводольному графі . Отже, розв'язання задачі про 3-сполучення є тільки одним з етапів розв'язку задачі 2.
Правильним є і зворотне: нехай знайдений оптимальний розв'язок задачі покриття графа типовими підграфами вигляду . При цьому кожна компонента зв'язності цього розв'язку є таким графом вигляду , що має номер 1 на рис. 2.1, тобто тільки одна його висяча вершина належить множині , а всі інші - множині . У цьому випадку одержуємо оптимальний
Рис.2.1. Чотири випадки розподілення вершин типового підграфу між мно