Размещено на http://www.allbest.ru/

Міністерство освіти і науки України

Дніпропетровський національний університет

УДК 519.17

Автореферат

дисертації на здобуття наукового ступеня кандидата фізико-математичних наук

Методи і алгоритми розпізнавання графів на передфрактальність і їх застосування

01.05.01 - теоретичні основи інформатики та кібернетики

Бобильова Олена Володимирівна

Дніпропетровськ 2005

Загальна характеристика роботи

алгоритм розпізнавання граф передфрактальність

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

Вперше поняття “фрактал” було започатковано Бенуа Мандельбротом в 1975 році для визначення нерегулярних та самоподібних структур і подальші дослідження науковців велися тільки для неперервних фрактальних функцій. Лише в другій половині 90-х років минулого століття в роботах Перепелиці В.О. і Сергієнка І.В. були розглянуті дискретні випадки. Вони дали строге визначення фрактальних та передфрактальних графів, а також запропонували алгоритми розпізнавання деяких графів на передфрактальність. Подальший розвиток ця теорія отримала в роботах Сергєєвої Л.С., Кочкарова А.М., Пінчука В.П., Стасюка В.П., B. Krohn, E. Teufl, J. Brown та ін.

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалася в період з 2000 по 2004 роки в науково-дослідній лабораторії “Оптимізація складних систем” Дніпропетровського національного університету в рамках держбюджетних науково-дослідних тем № 07-174-00, № 5-035-03. Здобувач є одним з виконавців цих тем. Його внесок полягає у розробці методів та алгоритмів розпізнавання графів на передфрактальність та використання їх для дослідження окремих класів дискретних задач.

Мета і завдання дослідження. Метою роботи є розробка методів і алгоритмів розпізнавання довільних графів на передфрактальність та їх використання при розв'язанні деяких NP-повних задач на цих графах.

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

Об'єкт дослідження - канонічні і неканонічні передфрактальні графи спеціальних конфігурацій.

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

Методи дослідження. Для розв'язання поставлених в дисертації задач використовувалися методи теорії дискретної оптимізації, теорії складності дискретних задач, теорії алгоритмів з оцінками, теорії ймовірності.

Наукова новизна одержаних результатів.

– вперше встановлені властивості повних канонічних передфрактальних графів, старі ребра яких перетинаються, і неканонічних передфрактальних графів, старі ребра яких можуть як перетинатись, так і не перетинатись;

– вперше побудовані ефективні точні алгоритми розв'язання дискретних задач розпізнавання (про вершинне покриття, домінуючу множину, гамільтонів цикл, розбиття на гамільтонові підграфи, виділення остового підграфу заданої конфігурації, розбиття на ліси) на передфрактальних графах;

– набула подальшого розвитку методика встановлення властивостей канонічних передфрактальних графів, старі ребра яких не перетинаються, породжених повним n-вершинним графом, колесом, зіркою (раніше були досліджені канонічні передфрактальні графи, породжені однорідним n-вершинним графом ступеня n\2sn-2).

Практичне значення одержаних результатів. Отримані теоретичні результати, які стосуються властивостей передфрактальних графів, можна використовувати для подальшого дослідження таких графів. Повні неканонічні передфрактальні графи з довільною кількістю вершин, що заміщуються, які досліджувалися в роботі, можна використовувати при моделюванні тих біологічних процесів, динаміка розвитку яких базується на принципах самоподібності. Отримані розв'язки розглянутих NP-повних задач можуть використовуватися при моделюванні таких прикладних задач, як розміщення телевізійних або радіопередаючих станцій на деякій території, розміщення військових баз, що контролюють дану територію, планування виробництва на підприємствах харчової, хімічної, фармацевтичної промисловості. Алгоритми виділення оптимального діадичного дерева можуть бути використані при моделюванні та дослідженні систем ієрархічної структури, таких як вибір схем прокладки доріг, ліній зв'язку та інших. Отримані в дисертації результати впроваджені в учбовий процес в Дніпропетровському національному університеті при підготовці спеціалістів з спеціальності “Інтелектуальні системи прийняття рішень”.

Особистий внесок здобувача. Всі результати дисертаційної роботи, що виносяться на захист, отримані автором особисто. У працях, написаних у співавторстві, дисертанту належать: в [1] - розробка узагальненого алгоритму розпізнавання передфрактального графу та обгрунтування його складності, в [4] - постановки задач та опис алгоритмів розв'язання NP-повних задач, в [6] - встановлення властивостей повного неканонічного передфрактального графу при довільному заміщенні вершин.

Апробація результатів дисертації. Основні результати роботи були оприлюднені і обговорені на ряді наукових конференцій і семінарів, у тому числі на: І Всеукраїнській науково-практичній конференції “Математичне та програмне забезпечення інтелектуальних систем” (17-19 листопада, м. Дніпропетровськ, 2003 р.), VIII Міжнародному семінарі “Дискретная математика и ее приложения” (4-8 лютого м. Москва, МДУ, 2004 р.), ІІ Міжнародній науково-практичній конференції “Математичне та програмне забезпечення інтелектуальних систем” (17-19 листопада м. Дніпропетровcьк, 2004 р.), щорічних підсумкових наукових конференціях за підсумками НДР у Дніпропетровському національному університеті (2001-2004 р.).

Публікації. По темі дисертації опубліковано 8 робіт, з них 3 статті у виданнях, затверджених ВАК України, 3 - тези доповідей на наукових конференціях.

Структура і обсяг роботи. Дисертаційна робота складається із вступу, 5 розділів, висновків, списку використаних джерел із 105 наіменувань, додатку. У роботі 4 таблиці і 83 рисунки. Загальний обсяг дисертації складає 172 сторінки, з яких 9 сторінок займає список літератури, 11 - додаток.

Основний зміст роботи

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

В першому розділі проведено аналіз попередніх робіт, присвячених дослідженню фрактальних (передфрактальних) графів. Відзначено, що основи теорії передфрактальних графів були сформульовані в роботах В.О. Перепелиці, І.В. Сергієнка. Вони запропонували індуктивне визначення передфрактального графу, ввели такі поняття, як канонічний і неканонічний передфрактальні графи, ранг графу, траекторія, повний передфрактальний граф, Р-адичне дерево. Також ними досліджені властивості канонічних передфрактальних графів, що породжені однорідним зв'язним графом, а також передфрактального дерева. На основі цих властивостей побудовані поліноміальні алгоритми розпізнавання довільних графів на передфрактальність. Вони ввели також термін “затравка”, який є визначальним при вивченні передфрактальних графів.

Під передфрактальним графом розуміється граф, процес породження якого складається з r=2,3,…,L кроків, де L - ранг кінцевого передфрактального графу. На першому кроці задається n-вершинний граф H=(W,Q), який виступає в якості затравки. Після виконання кроку r буде отримано поточний граф G_r=(V_r,E_r) рангу r, який утворюється шляхом застосування до вершин попереднього графу G_r-1=(V_r-1,E_r-1) операції заміщення вершини затравкою (ЗВЗ). Суть її полягає в тому, що кожна вершина vV_r-1, що розщеплюється, заміщується затравкою H=(W,Q). В процесі виконання цієї операції всі ребра eE_r-1 називаються старими ребрами по відношенню до всіх поточних графів G_r,G_r+1,…,G_L (L>1). Старі ребра, інцидентні вершині vV_r-1, що заміщується, стають інцидентними деяким вершинам затравки. Ребра, що з'явилися на кроці r-1, називаються новими ребрами для графа G_r.

Передфрактальні графи за кількістю вершин, що заміщуються, діляться на канонічні і неканонічні передфрактальні графи. У випадку, коли на кожному кроці r=2,3,…,L заміщуються всі вершини множини V_r-1 в поточному графі G_r-1=(V_r-1,E_r-1), буде отримано канонічний передфрактальний граф ((n,L)-граф). При побудові неканонічного передфрактального графу заміщуються не всі вершини множини V_r-1 графа G_r-1=(V_r-1,E_r-1), а тільки деяка їх підмножина, яка вибирається в залежності від специфіки поставленої задачі. Незаміщені вершини оголошуються заблокованими і на подальших кроках не заміщуються.

Граф G, породжений повною n-вершинною затравкою, називається повним передфрактальним графом.

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

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

Теорема 1. Нехай G=(V,E) - повний канонічний передфрактальний граф, породжений n-вершинною затравкою H=(W,Q). Тоді множину всіх його затравок можна розбити на затравки, для яких потужність W₁=1, і кількість таких затравок дорівнює n, та на затравки, для яких потужність W₁=0 (W₁ - підмножина вершин множини W, що мають ступінь n-1).

Теорема 2. Нехай H=(W,Q) - n-вершина затравка, що породжує повний канонічний передфрактальний граф G. Тоді, якщо множина W₁ не порожня, то вершина vW₁ є суміжною з кожною вершиною із множини W₂ (W₂ - підмножина вершин множини W, що мають ступінь n).

Теорема 3. Нехай G=(V,E) - повний (n,L)-граф, що породжений затравкою H=(W,Q). Тоді для кожної затравки H=(W,Q) графа G, підграф, індукований множиною вершин W₂, є повним графом.

Лема 1. Множину вершин V канонічного передфрактального графу G=(V,E), породженого n-вершинною зіркою, можна розбити на три підмножини вершин V₁, V₂, V₃, ступені вершин яких дорівнюють s₁=1, s₂=2, s₃=n-1 відповідно, і потужності цих підмножин визначаються наступними рівностями:

V₃=n ^L-1,

V₂=2(n ^L-1-1),

V₁=n ^L-3n ^L-1 +2. (1)

Теорема 4. Нехай передфрактальний граф G=(V,E) породжений n-вершинною зіркою. Тоді для будь якої затравки H=(W,Q) графа G мають місце наступні оцінки для потужностей підмножин розбиття:

0W₁<n-1,

0<W₂n-1,

W₃=1, (2)

де W₁, W₂ , W₃ підмножини вершин множини W ступенів 1, 2, n-1 відповідно.

Лема 2. Нехай G=(V,E) - канонічний передфрактальний граф рангу L, породжений n-вершинним колесом H=(W,Q) (n=5,6,…). Тоді множину вершин V графа G можна розбити на три підмножини вершин V₁, V₂ і V₃ ступенів 3, 4 і n-1 відповідно, і потужності цих підмножин дорівнюють:

V₃= n ^L-1,

V₂=4(n ^L-1-1),

V₁=n ^L-5n ^L-1+4. (3)

Теорема 5. Нехай передфрактальний граф G=(V,E) породжений n-вершинним колесом H=(W,Q) (n=5). Тоді множину затравок графа G можна розбити на затравки двох видів: затравки, для яких W₁=1, W₂=n-2, W₃=1, і кількість таких затравок дорівнює (n-1); затравки, для яких W₁=0, W₂=n-1, W₃=1.

Лема 3. Множину вершин V канонічного передфрактального графу G=(V,E), породженого однорідною s-вершинною затравкою, старі ребра якого перетинаються, можна розбити на дві підмножини вершин V₁ і V₂ ступенів s і 2s відповідно і потужності цих підмножин визначаються рівностями:

V₂=n n-1n ^L-1-1,

V₁=n^L-n n-1n ^L-1-1. (4)

На основі цих властивостей було запропоновано методи та алгоритми розпізнавання довільних графів на передфрактальність, і отримано верхні оцінки складності алгоритмів, які мають порядок O(EL).

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

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

Сформульовано і доведено наступні леми і теореми, які обгрунтовують методи розпізнавання даних графів на передфрактальність.

Лема 4. Множину вершин V графа G=(V,E) можна розбити на дві підмножини вершин К і М, де К - множина вершин затравок, що розпізнаються, а M - множина заблокованих вершин, причому

К=nk^L-1, (5)

де k - кількість вершин, що заміщуються в одній затравці.

Лема 5. Множину усіх заблокованих вершин М неканонічного передфрактального графу G, породженого довільною зв'язною n-вершинною затравкою H, можна розбити на (L-1) підмножин М₁, М₂…М_L-1, причому для цих підномножин виконуються наступні рівності

М_i=(n-k)ⁱ, (при 1<k<n-1);

М_i=k^i-1, (при k=n-1);

М_i=n-1 (при k=1). (6)

Лема 6. Множину вершин V неканонічного передфрактального графу G=(V,E), породженого повною n-вершинною затравкою, можна розбити на дві підмножини вершин V₁ і V₂ ступенів n-1 і n відповідно, і

V₁=n. (7)

Теорема 6. Нехай G=(V,E) - повний неканонічний передфрактальний граф, що породжений n-вершинною затравкою H=(W,Q) і кількість вершин, що заміщуються в кожній затравці, дорівнює k. Тоді тільки для k затравок потужність множини W₁ одинична: W₁=1, для інших затравок W₁=0.

Теорема 7. Нехай G^(L)=(V^(L),E^(L)) - неканонічний передфрактальний граф рангу L, породжений повною n-вершинною затравкою, k - кількість вершин, що заміщуються в затравці. Тоді в графі G^(L) можна виділити підграфи

G^(L-1)=(V^(L-1),E^(L-1)),

G^(L-2)=(V^(L-2),E^(L-2)),

G^(L-3)=(V^(L-3),E^(L-3)),…,G⁽¹⁾=(V⁽¹⁾,E⁽¹⁾)

що не перетинаються, причому такі, що

G^(j)=i=1kG_i^(j)

де кожен граф G_i^(j)=(V_i^(j),E_i^(j)) є неканонічний передфрактальний граф рангу j (j=1,...,L-1), і для множини вершин і ребер графу G^(L) виконуються рівності:

V^(L)=V^(L-1)M₁, E^(L)=E^(L-1)R₁;

V^(L-1)=V^(L-2)M₂, E^(L-1)=E^(L-2)R₂;

….

V⁽²⁾=V⁽³⁾M_L-1, E⁽²⁾=E⁽³⁾R_L-1, (8)

де R_i - множина старих ребер, що утворені на кроці i (i=2,…,L); для кожного фіксованого j множина заблокованих вершин, множина старих ребер і множина вершин, суміжних з заблокованими відповідно, задовольняють рівностям

M_j+1=i=1k^jM_1i^(L-j);

R_j+1=i=1k^jR_1i^(L-j);

Z_j+1=i=1k^jZ_1i^(L-j). (9)

Тут M_j+1 - множина заблокованих вершин графу G^(L), утворених на кроці j+2; M_1i^(L-j) - множина заблокованих вершин графу G_i^(L-j), утворених в ньому на кроці 2; R_j+1 - множина старих ребер графу G^(L), утворених на кроці j+2; R_1i^(L-j) - множина старих ребер в графі G_i^(L-j), утворених в ньому на кроці 2; Z_j+1 - множина вершин графу G^(L), суміжних з вершинами множини М_j+1; Z_1i^(L-j) - множина вершин графу G_i^(L-j), суміжних з вершинами множини M_1i^(L-j) (j=1,…,L-2, i=1,…,k^j).

Теорема 8. Нехай G=(V,E) - неканонічний передфрактальний граф, породжений повною n-вершинною затравкою рангу L, і кількість вершин, що заміщуються в кожній затравці, дорівнює k=(n-1). V₁ - множина вершин ступеню (n-1). Тоді мають місце наступні оцінки:

2L-1(v_i)2^L-1,

L(w)2^L-1,

(v_i)=maxv_jV₁(v_i,v_j), v_iV₁\M₁; (w)=maxv_iV₁\M₁(w,v_i), wM₁, i=1,...,n-1, j=1,...,n-1.

Лема 7. Множина вершин V^(L) неканонічного передфрактального графу G^(L)=(V^(L),E^(L)), породженого однорідною зв'язною n-вершинною затравкою H=(W,Q), старі ребра якого перетинаються, розбивається на дві підмножини вершин V₁ і V₂ ступенів s і 2s відповідно (s - ступінь вершин затравки H).

Теорема 9. Нехай G^(L)=(V^(L),E^(L)) - повний неканонічний передфрактальний граф рангу L. Тоді суміжні між собою вершини множини Z (Z - множина вершин ступеню (n-1), ексцентриситет яких дорівнює L) є вершинами затравки H, що породжує граф G^(L) (тобто вершинами графу G⁽¹⁾).

Теорема 10. Нехай G^(L)=(V^(L),E^(L)) - повний неканонічний передфрактальний граф з довільною кількістю вершин, що заміщуються, який породжений n-вершинною затравкою H. Тоді в графі G^(L)=(V^(L),E^(L)) можна виділити L підграфів G⁽¹⁾, G⁽²⁾,…., G^(L) таких, що: G⁽¹⁾=G⁽¹⁾=H - затравка-ініціатор; G⁽²⁾=i=1k⁽¹⁾H_i⁽²⁾ і G⁽²⁾=G⁽¹⁾G⁽²⁾;…; G^(L)=i=1k^(L-1)H^(L)_i і G^(L)=G^(L)G^(L-1), де H_i^(p) - затравки, що були приєднані на кроці p (p=2,…,L), L - ранг графу, k⁽ⁱ⁾ - кількість вершин, що заміщуються на кроці i.

Лема 8. Серед множини вершин V неканонічного передфрактального графу G=(V,E), старі ребра якого не перетинаються, породженого множиною однорідних зв'язних затравок Ќ={H₁,H₂,…,H_T}, Т2, можна виділити j (jT) підмножин V^j₁ вершин ступенів s₁,s₂,…,s_Т відповідно, де s₁,s₂,…,s_Т - це ступені вершин затравок H₁,H₂,…,H_T.

Теорема 11. Нехай G^(L)=(V^(L),E^(L)) - повний неканонічний передфрактальний граф рангу L, породжений множиною затравок Ќ={H₁,H₂,…,H_T}, Т2, кожна з яких є повним графом. Тоді суміжні між собою вершини множини Z є вершинами затравки-ініціатора H₁ (тобто вершинами графу G⁽¹⁾).

Теорема 12. Нехай G^(L)=(V^(L),E^(L)) - повний неканонічний передфрактальний граф з довільною кількістю вершин, що заміщуються, який породжений множиною зв'язних затравок Ќ={H₁,H₂,…,H_T}, Т2. Тоді в графі G^(L)=(V^(L),E^(L)) можна виділити L підграфів G ⁽¹⁾, G⁽²⁾,…., G^(L) таких, що: G⁽¹⁾=H₁ - затравка-ініціатор; G⁽²⁾=i=1k⁽¹⁾H^(j)_i - затравки, що були приєднані на кроці 2 і G⁽²⁾=G⁽¹⁾G⁽²⁾;…; G^(L)=i=1k^(L)H^(j)_i - затравки, приєднані на кроці L і G^(L)=G^(L)G^(L-1), де L - ранг графу, k⁽ⁱ⁾ - кількість затравок, що заміщуються на кроці i.

На основі запропонованих методів побудовані алгоритми розпізнавання довільних графів на передфрактальність відносно заданої затравки. Поліноміальність наведених алгоритмів строго обгрунтована.

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

В четвертому розділі розглянуто деякі NP-повні задачі на канонічних і неканонічних передфрактальних графах, а саме: задача про домінуючу множину, задача про вершинне покриття, задача розбиття на трикутники, задача розбиття на гамільтонові підграфи, задача “гамільтонів цикл”. Сформульовано і доведено такі теореми про поліноміальну розв'язуваність даних задач на класі передфрактальних графів.

Теорема 13. Нехай G=(V,E) - канонічний передфрактальний граф, породжений однорідною 4-вершинною затравкою ступеня s=2, старі ребра якого не перетинаються. Тоді K<V таке, що задача “вершинне покриття” є поліноміально розв'язуваною на даному графі, причому потужність вершинного покриття задовольняє нерівності:

V? (4^L-1-1), (10)

де V - вершинне покриття; L - ранг передфрактального графу G (L=2,3,…), q - кількість ребер затравки.

Теорема 14. Задача “вершинне покриття” є поліноміально розв'язуваною на канонічному передфрактальному графі G=(V,E), що породжений повною n-вершинною затравкою, при умові, що це покриття V співпадає з підмножиною V₂V вершин ступеню n, і його потужність визначається рівністю

V=2q n-1n^L-1-1 , (11)

де L - ранг передфрактального графу (L=2,3,…), q - кількість ребер затравки.

Ця задача буде поліноміально розв'язуваною і в тому випадку, якщо вимагати, щоб підграф, індукований підмножиною V, був зв'язним.

Теорема 15. Задача “вершинне покриття” поліноміально розв'язувана на повному неканонічному передфрактальному графі G=(V,E), породженому n-вершинною затравкою, при умові, що старі ребра перетинаються, причому, якщо кількість вершин, що заміщуються в кожній затравці, постійна і дорівнює k, то потужність вершинного покриття V дорівнює:

V=k k²-1k^2(L-2)-1 , (L непарне);

V= k²-1k^2(L-2)-1 (L парне), (12)

де L - ранг графу G.

Теорема 16. Задача “домінуюча множина” поліноміально розв'язувана на канонічному передфрактальному графі, що породжений n-вершиним колесом, при цьому виконуються рівності

V=V₃;

V=n^L-1, (13)

де V - домінуюча множина, V₃ - підмножина вершин, що мають ступінь (n-1).

Ця задача буде поліноміально розв'язуваною на цьому графі і у тому випадку, коли множина V буде незалежною.

Теорема 17. Задача “домінуюча множина” поліноміально розв'язувана для канонічного передфрактального графу, що породжений n-вершинною зіркою.

Теорема 18. Задача “розбиття на ліси” поліномиально розв'язувана для канонічного передфрактального графу, що породжений однорідною n-вершинною затравкою ступеня s=2.

Теорема 19. Задача “гамільтонів цикл” поліноміально розв'язувана на повному канонічному передфрактальному графі.

Теорема 20. Задача “гамільтонів цикл” поліноміально розв'язувана на повному неканонічному передфрактальному графі.

Теорема 21. Задача “гамільтонів цикл” поліноміально розв'язувана на канонічному передфрактальному графі, породженому n-вершинним колесом.

Доведення сформульованих теорем конструктивне і для кожної поставленої задачі запропоновано поліноміальні алгоритми її розв'язання.

В п'ятому розділі досліджується NP-складна задача про виділення у довільному графі мінімального остового підграфу. В якості остового підграфу береться діадичне дерево, що являється передфрактальним графом. Запропоновано поліноміальний алгоритм , який майже завжди виділяє діадичне дерево мінімального розміру в довільному графі. Він складається з двох етапів (₁ і ₂), і верхня оцінка його обчислювальної складності має порядок O(n³). Етап ₁ представляє собою алгоритм градієнтного типу. Він реалізується за s кроків, де s=(n-3)/4, і результатом кроку s є побудова (2s+1)-вершинного діадичного дерева. На етапі ₂ будуються два двудольних підграфи. За допомогою будь якого відомого поліноміального алгоритму (наприклад, за допомогою угорського алгоритму) знаходяться оптимальні паросполучення у виділених двудольних підграфах, а всі ребра, що складають отримані паросполучення, приєднуються до знайденого на етапі ₁ діадичного дерева.

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

Через G_n,q позначається n-вершинний граф, в якому для кожної пари вершин i, j (i, j=1,…,n) ребро u_ij з'являється з імовірністю 1-q (0q<1) незалежно від інших ребер. При цьому, якщо ребро u_ij з'явилося, то йому з умовною імовірністю p приписується вага p_ij= (=1,2,…,r; Уr=1p=1). Нехай P{D_n} - імовірність того, що в графі G_n,q алгоритм виділить діадичне дерево D_n. Ставиться задача визначити, яким умовам повинна задовольняти величина q, щоб виконувалася рівність

limnP{D_n}=1.

Теорема 22. Якщо q1- ц--n , де ц=ц(n) - поволі зростаюча функція від n і ц(n) при n, то limnP{D_n}=1.

Задача про діадичне дерево також була розглянута на повному n-вершиному графі G=(V,E) у випадку, коли n - непарне, і ребра E цього графу зважені вагами w(e), що набувають значення на множині Y, яка є монотонно зростаючою послідовністю чисел y (=1,…,N) на відрізку [a,b]; y₁=a; a?0; y_N=b.

Нехай L - вага оптимального діадичного дерева в графі G, тобто діадичного дерева, яке має мінімальну вагу. Необхідно побудувати алгоритм, який для заданого графу G і _n, n=1,2,… (limn_n=0) знаходить таке діадичне дерево, вага якого не більша за величину (1+_n)L.

Для розв'язання цієї задачі було розроблено асимпотично точний алгоритм виділення діадичного дерева і обгрунтовані імовірнісні умови його асимптотичної точності.

У додатку наведені тестові приклади розпізнавання довільних графів на передфрактальність. У випадку успішного розпізнавання розв'язуються наступні NP-повні задачі: задача знаходження гамільтонового циклу для канонічних і неканонічних передфрактальних графів, що породжені повними затравками, а також для канонічного передфрактального графу, порожденого n-вершиним колесом; задача знаходження мінімальної домінуючої множини для передфрактальних графів, які породжені n-вершинними затравками “колесо”, “зірка”; задача про максимальну незалежну множину на передфрактальних графах, які породжені n-вершинною затравкою - “зірка”.

Висновки

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

Основні наукові результати і висновки, що були отримані в роботі, полягають у наступному:

1. Встановлено властивості канонічних передфрактальних графів, старі ребра яких не перетинаються, породжених повною n-вершинною затравкою, колесом, зіркою. Розроблено методи та алгоритми розпізнавання довільних графів на передфрактальність і отримані верхні оцінки складності алгоритмів.

2. Вперше отримані властивості повних канонічних передфрактальних графів, старі ребра яких перетинаються і запропоновано поліноміальні алгоритми їх розпізнавання.

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

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

5. Вперше досліджена складність розв'язання дискретних задач розпізнавання (про вершинне покриття, домінуючу множину, гамільтонів цикл, розбиття на гамільтонові підграфи, розбиття на ліси) на передфрактальних графах. Наведено теореми про поліноміальну розв`язність цих задач на даному класі графів, доведення яких мають конструктивний характер.

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

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

Список опублікованих праць за темою дисертації

1. Киселева Е.М., Бобылева Е.В. Обобщенный алгоритм распознавания предфрактального графа // Проблемы управления и информатики. - 2005. - № 2. - С. 82 - 92.

2. Бобылева Е.В. Алгоритмы распознавания графов на предфрактальность // Питання прикладної математики і математичного моделювання. - Д.:ДНУ, 2003. - С. 9-15.

3. Бобылева Е.В. О полиномиально разрешимых подклассах NP-полных задач на предфрактальных графах // Питання прикладної математики і математичного моделювання. - Д.:ДНУ, 2004. - С. 12-27.

4. Бобылева Е.В., Черепинский К.М. Програмная реализация алгоритмов решения задач распознавания на предфрактальных графах // Системні технології. Регіональний міжвузівський збірник наукових праць. - Дніпропетровськ, 2004. - № 4. - С. 17 - 24.

5. Бобылева Е.В. Алгоритмы с оценками для задачи о диадическом дереве // Вісник запорізького державного університету. - Запоріжжя: ЗДУ, 2004. - № 2. - С. 5-9.

6. Киселева Е.М., Бобылева Е.В. Задача распознавания неканонического предфрактального графа // Тези доповідей IІ Міжнародної науково-практичної конференції ”Математичне та програмне забеспечення інтелектуальних систем”. - Д.: ДНУ, 2004. - С. 54 - 55.

7. Бобылева Е.В. Исследование неканонических предфрактальных графов // Материалы VIII-го международного семинара ”Дискретная математика и ее приложения”. (2-6 февраля, 2004) - М: МГУ, 2004. - С. 326-329.

8. Бобылева Е.В. Распознавание пространственных графов на предфрактальность // Тези доповідей I Всеукраїнської науково-практичної конференції ”Математичне та програмне забеспечення інтелектуальних систем”. - Д.: ДНУ, 2003. - С. 12.

Анотація

Бобильова О.В.: Методи і алгоритми розпізнавання графів на передфрактальність і їх застосування. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.01 - теоретичні основи інформатики та кібернетики, Дніпропетровський національний університет Міністерства освіти і науки України, Дніпропетровськ, 2005.

В роботі досліджені властивості канонічних передфрактальних графів, породжених повною n-вершинною затравкою, колесом, зіркою, старі ребра яких не перетинаються, і повних канонічних передфрактальних графів, старі ребра яких перетинаються. Вперше були встановлені властивості повних неканонічних передфрактальних графів, старі ребра яких не перетинаються, у випадках, коли заміщення вершин відбувається довільним чином, або за певним правилом, а також властивості повних неканонічних передфрактальних графів з довільною кількістю вершин, що заміщуються, старі ребра яких перетинаються. Запропоновані поліноміальні алгоритми розпізнавання таких графів на передфрактальність.

Вперше досліджена складність розв'язання деяких NP-повних задач розпізнавання (про вершинне покриття, домінуючу множину, гамільтонів цикл, розбиття на гамільтонові підграфи, розбиття на ліси) на передфрактальних графах і розглянута NP-складна задача про остові дерева заданої конфігурації на довільних графах. Для цієї задачі побудовано поліноміальний алгоритм, що виділяє оптимальне діадичне дерево в заданному графі, розроблено асимптотично точний алгоритм виділення діадичного дерева в повному графі.

Ключові слова: передфрактальний граф, канонічний і неканонічний передфрактальні графи, затравка, операція заміщення вершини затравкою, діадичне дерево, остовний підграф.

Аннотация

Бобылева Е.В.: Методы и алгоритмы распознавания графов на предфрактальность и их применение. - Рукопись.

Дисертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.01 - теоретические основы информатики и кибернетики, Днепропетровский национальный университет Министерства образования и науки Украины, Днепропетровск, 2005.

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

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

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

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

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

Summary

Bobylova E.V.: The Methods and Algorithms of Recognition of the Graphs on the Prifractile and their Application. - The manuscript.

The dessirtation submitted for the Candidate Degree in Physics and Mathematics by specialty 01.05.01 - Theoretical Bases of Computer Science and Cybernetics.- Dnipropetrovsk National University of Ministry of Education of Ukraine, Dnipropetrovsk, 2005.

The properties of the canonical prifractal graphs, the old edges of which aren't crossed, and are generated by the full n-vertex zatravka, wheel, star, are studied. The full canonical prifractal graphs, the old edges of which are crossed, are investigated.

For the first time the full noncanonical prifractal graphs in the chance of the vertexes replaced in the graph according to the special rule or taken in a free position, were investigated. Also the properties of the full noncanonical prifractal graphs, the old edges which are crossed, and the amount of the vertexes, which are replaced, is arbitrary, were examined.

On the base of the characters of the enumerated graphs the methods and polynomial algorithms of their recognition were constructed.

For the first time complexity of the some NP-full problems (the task of vertex cover, the task of the dominating set, the problem of the partition on the forests, the task of the partition on the Hamilton subgraphs, the task of the Hamilton cycle) was explored.

The statistically exact and asymptotically effective algorithms of the isolation of the framing dyadic tree which has a limited degree were constructed.

Key words: prifractal graph, canonical and nonkanonical prifractal graphs, zatravka, the operation of replacement the vertex of zatravka, dyadic tree, framing subgaraph.

Размещено на Allbest.ru