Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Національна академія наук України
Інститут кібернетики імені В.М. Глушкова
ШУЛІНОК Георгій Олександрович
УДК 519.1
РОЗВ’ЯЗАННЯ ЗАДАЧ Ізоморфізму та знаходження хроматичного числа на числових графах
01.05.01 - теоретичні основи інформатики та кібернетики
Автореферат
дисертації на здобуття наукового ступеня
кандидата фізико-математичних наук
Київ – 2006
Дисертацією є рукопис.
Робота виконана в Інституті кібернетики ім. В.М. Глушкова НАН України.
Науковий керівник : доктор фізико-математичних наук,
Донець Георгій Панасович,
Інститут кібернетики ім. В.М. Глушкова
НАН України, завідувач відділу.
Офіційні опоненти: доктор фізико-математичних наук, професор,
Асельдеров Зайнутдін Макашаріпович,
Національний технічний університет України
“КПІ”, кафедра автоматизованих систем обробки інформації та управління,
кандидат фізико-математичних наук,
Журбенко Микола Георгійович,
Інститут кібернетики ім. В.М. Глушкова
НАН України, старший науковий співробітник.
Провідна установа: Київський національний університет
імені Тараса Шевченка, факультет кібернетики, кафедра математичних методів
еколого-економічних досліджень.
Захист відбудеться "____"_____________ 2006 р. о(об) годині на засіданні спеціалізованої вченої ради Д 26.194.02 при Інституті кібернетики імені В.М. Глушкова НАН України за адресою:
, МСП Київ-187, проспект Академіка Глушкова, 40.
З дисертацією можна ознайомитися в науково-технічному архіві інституту.
Автореферат розісланий "____"____________2006 р.
Учений секретар
спеціалізованої вченої ради СИНЯВСЬКИЙ В.Ф.
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. Дисертаційна робота присвячена розв’язанню на числових графах задач, що не мають ефективних алгоритмів розв’язку у загальному випадку, таких як пошук хроматичного числа графа та ізоморфізм графів. Дослідження велися у таких напрямках: а) дослідження структури числових графів та розробка методів визначення інваріантів; б) знаходження необхідних та достатніх умов ізоморфізму для певних підкласів числових графів; в) розробка методів пошуку ізоморфізму для однорідних та довільних числових графів; г) знаходження хроматичного числа для певних підкласів числових графів; д) дослідження наявних методів пошуку хроматичного числа числових графів; е) розробка методів, що дозволяють ефективно вирішувати задачу розфарбування довільних числових графів довільним числом кольорів; ж) розробка програмного забезпечення для деяких з напрямків.
Проблема ефективності алгоритмів (у тому числі не тільки на графах) за останні півстоліття породила величезну масу робіт. Разом з тим пошук ефективних алгоритмів на числових графах почався зовсім недавно. Дослідження почалося з базових для теорії графів алгоритмів, таких як пошук в ширину та глибину, проте ці алгоритми і так мали ефективні (поліноміальні) алгоритми розв’язку. З іншого боку, найбільш цікавими для практичного застосування є задачі на графах, що не мають відомих поліноміальних алгоритмів розв’язку.
Останнім часом дуже багато досліджень в галузі розпізнавання образів, структурного та системного аналізу, в розробці програмних комплексів, у конструюванні обчислювальної техніки та багатьох інших галузях як об’єкт початкових даних використовують графи, які мають специфічну структуру. Деякі користуються при цьому традиційним представленням графів, що вимагає величезної пам’яті та приводить до громіздких обчислень з великими витратами часу. В більшості випадків ці графи мають ієрархічну або симетричну структури, які складаються з однотипних частин або таких, що повторюються. А саме числові графи дозволяють з максимальним ефектом використовувати ці особливості. Необхідно тільки знайти підходящу функцію, яка адекватно описує суміжність вершин графа. Внаслідок вдалого підбору такої функції представлення заданого графу може зменшитися за обсягом пам’яті в декілька разів, а операції пошуку у величезних масивах пам’яті для отримання необхідної інформації замінюються невеликою кількістю елементарних обчислень.
Найпростіший клас числових графів –арифметичні графи –вивчаються вже понад 30 років. Уперше поняття арифметичного графа з’явилося в роботах Ю.Г. Григоряна та його співавторів, в яких йшлося про окремі властивості арифметичних графів і які не носили фундаментального характеру. Вони використовували арифметичні графи перш за все для ілюстрації деяких закономірностей схем в галузі кристалографії, хімії та електронного конструювання, але мало приділяли уваги їм як математичному об’єкту. Поняття числового графа виникло з появою робіт Г.П. Донця та його послідовників, після чого починається планомірне та інтенсивне дослідження числових графів (куди, крім арифметичних, включені модульні та їм подібні), їх властивостей. У наукових роботах Г.П. Донця незалежно від Ю.Г. Григоряна досліджувалися графи, що задаються аналітичним способом. Як окремий випадок цих графів можна трактувати числові графи. Отримані важливі вичерпні характеристики цих графів: зв’язність, цикломатичне число, оптимальне представлення. Уперше доведено, що на числових графах багато алгоритмів мають кращі показники, ніж на звичайних, тобто представлених за допомогою списку суміжностей. Виникло питання, чи можливо створити для числових графів специфічні алгоритми, які мають додаткові переваги над відповідними алгоритмами, розробленими для графів, представлених традиційним способом. Отримана позитивна відповідь, що зробило можливим дослідження, відображені у даній дисертаційній роботі: досліджені задачі, що не мають ефективних алгоритмів розв’язку у загальному випадку, проте досліджені необхідні та достатні умови ізоморфізму натуральних арифметичних і натуральних модульних графів; виконано перелік неізоморфних компонент для натуральних арифметичних графів спеціального виду; проведено дослідження однорідних натуральних модульних графів для побудови алгоритму перевірки ізоморфізму двох довільних натуральних модульних графів. Поставлена та розв’язана задача пошуку хроматичного числа для довільних натуральних модульних графів. Відомо, що натуральні арифметичні та натуральні модульні графи належать до найпростіших числових графів, тому є простір для розширення даного дослідження на інші підкласи числових графів: арифметичні, модульні, квадратичні та ін.
Незважаючи на очевидну значимість, яку набувають числові графи в різних галузях наукових досліджень, ця тема зовсім не набула поширення у зарубіжній математичній літературі. Є поодинокі публікації, в яких вживається поняття числового графа, але в іншому розумінні, де кожному ребру приписана його вага у вигляді певного числа.
На основі цих наведених фактів можна зробити висновок, що тема дисертаційної роботи за своїми отриманими науковими результатами та можливими перспективними напрямками є актуальною.
Зв’язок роботи з науковими програмами, планами, темами. Наведені в дисертаційній роботі дослідження виконувалися ó â³ää³ë³ економічної кібернетики ²íñòèòóòó ê³áåðíåòèêè ³ìåí³ Â.Ì. Ãëóøêîâà ÍÀÍ Óêðà¿íè. Ðåçóëüòàòè ðîáîòè âèêîðèñòîâóâàëèñÿ â 2000 – 2005 ðð. ïðè âèêîíàíí³ íàñòóïíèõ òåì ôóíäàìåíтàëüíèõ äîñë³äæåíü, çàòâåðäæåíèõ Ïðåçè䳺þ ÍÀÍ Óêðà¿íè:
В.Ф. 110.06 “Розробка ефективних методів та алгоритмів для розв’язування задач оптимального проектування в галузі машинобудування”;
В.Ф. 110.08 “Розробка методів та алгоритмів розв’язання зваженої задачі Штейнера для впровадження її до оптимального проектування промислових мереж”.
Описані в роботі алгоритми реалізовані у вигляді прикладних програм, які функціонують в середовищі WINDOWS.
Мета і завдання дослідження. Метою дисертаційної роботи є дослідження властивостей числових графів, які дозволяють ефективно розв’язувати складні задачі типу ізоморфізм графів та пошук хроматичного числа графів. Для цього були поставлені такі основні завдання:
Об’єкт дослідження –задачі пошуку ізоморфізму та хроматичного числа графів.
Предмет дослідження –числові графи, задані у вигляді двох множин натуральних чисел та функції суміжності, методи розв’язування дискретних задач оптимізації.
Методи дослідження: для вивчення властивостей числових графів застосовуються методи теорії чисел, теорії скінченних полів, теорії діофантових рівнянь, лінійної алгебри та комбінаторики. Для побудови відповідних алгоритмів застосовуються методи теорії графів, теорії дискретної оптимізації та теорії складності алгоритмів.
Наукова новизна отриманих результатів. Основні результати роботи, які визначають її наукову новизну та виносяться до захисту:
Практичне значення отриманих результатів дисертаційної роботи перш за все полягає в тому, що вони безпосередньо дають певний внесок в розв’язання проблеми ефективності алгоритмів на графах. Відомо, що багато задач на графах є NP-повними, тобто не мають поліноміальних алгоритмів розв’язку. Водночас переважна більшість практичних задач, що розв’язуються методами теорії графів, має свою специфіку, яка полягає в тому, що вони використовують такі графи, структура яких має однотипні та симетричні частини. Це дає можливість представляти ці графи у вигляді числових, для яких багато алгоритмів (навіть неполіноміальних) мають поліноміальну інтерпретацію.
Задачі знаходження хроматичного числа та пошуку ізоморфізму мають широке практичне застосування, і методи їх розв’язання присутні при розпізнаванні образів та сигналів, задачах ідентифікації тощо.
Особистий внесок здобувача. Всі результати, які складають суттєву частину дисертаційної роботи, отримані автором самостійно. Роботи [4–] написані здобувачем особисто, і всі наукові результати, що містяться в них, є оригінальними.
Роботи [1–] написані у співавторстві з науковим керівником Г.П. Донцем. В них керівнику належать теоретичні ідеї та постановка задач, а дисертанту –доведення основних тверджень, доопрацювання статей до логічного вигляду, розробка алгоритмів та перевірка на тестах теоретичних висновків.
Апробація результатів дисертації. Ðåçóëüòàòè äèñåðòàö³éíî¿ ðîáîòè áóëè çàñëóõàí³ íà íàóêîâîìó ñåì³íàð³ â³ää³ëó №130 ìàòåìàòè÷íèõ ìåòîä³â äîñë³äæåííÿ îïåðàö³é, семінарі „Теорія оптимальних рішень” відділу №110 економічної кібернетики ²íñòèòóòó ê³áåðíåòèêè ³ì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðà¿íè (Êè¿â, 2002 – 2006 рр.), семінарі кафедри обчислювальної математики Запорізького державного університету (2005 р.), кафедри обчислювальної математики та математичної кібернетики Дніпропетровського національного університету (2004 р.), семінарі кафедри обчислювальної математики Київського національного університету ім. Тараса Шевченка (2004 р.) і îïóáë³êîâàí³ â ìàòåð³àëàõ наступних êîíôåðåíö³é:
Публікації. Основні результати дисертації опубліковано в 8 роботах, із яких 6 робіт –у наукових фахових виданнях, 2 роботи –у збірниках доповідей міжнародних конференцій.
Структура та обсяг роботи. Дисертація складається із вступу, чотирьох розділів, висновків, додатків, списку використаних джерел, що містить 80 найменувань. Загальний обсяг роботи –140 сторінок друкованого тексту, обсяг основного тексту –сторінок. Робота містить 16 рисунків.
ЗМІСТ РОБОТИ
У вступі обґрунтовано актуальність обраної теми дисертаційної роботи. Показано, що ця тема належить до загальновідомих і складних задач дискретної математики. Із загальної проблеми шляхом уособлення деяких методів кодування виділені графи, які отримали назву числових. Дослідження властивостей цих математичних об’єктів, їх застосування в різних практичних галузях є основою теми дисертаційної роботи. Сформульовані мета та задачі дослідження, зроблено аналіз, подана характеристика наукової новизни і практичної значимості отриманих результатів. Зазначено зв’язок обраної теми з науковими програмами, планами, темами за місцем виконання дисертаційної роботи. Зазначено особистий внесок здобувача у кожній опублікованій науковій праці; відображено його виступи на фахових вітчизняних та міжнародних конференціях; подано перелік наукових праць за темою дисертаційної роботи.
Перший розділ присвячений огляду стану наукових досліджень за обраною темою та обґрунтуванню вибору напрямків досліджень дисертаційної роботи. Особливо підкреслюється, що обрана тема є малодослідженою галуззю дискретної математики, яка ще недостатньо висвітлена у світовій математичній літературі. У хронологічному порядку літературу можна поділити на кілька основних етапів.
Перший етап пов’язаний з роботами групи вірменських учених Ю.Г. Григоряна, Г.К. Манояна та А.М. Адонца, що почали друкуватися на початку 70-х років минулого століття. В них досліджувалися властивості арифметичних графів, які послужили прототипом більш загального класу числових графів. Але після 1990 р. наукові праці за даною темою зазначені автори не публікували.
Другий етап можна датувати початком 80-х років минулого століття, коли появилися роботи Г.П. Донця та його послідовників Ю.І. Нєженцева, І.М. Асельдерової. У них вперше були поставлені задачі математичного характеру й отримані загальні результати про структуру числових графів та їх оптимальне представлення.
Третій етап – останні 5–7 років, коли появилися роботи, присвячені побудові базових алгоритмів на числових графах. У роботах Г.П. Донця зазначено, що числові графи мають значну перевагу над графами, які задаються традиційними засобами. Це зумовило нові можливості побудови якісних алгоритмів на графах та дозволило наблизитись до ефективного розв’язання проблем, які є NP-повними для звичайних графів.
У другому розділі досліджується задача визначення ізоморфізму двох числових графів на прикладі натуральних арифметичних і натуральних модульних графів. Визначаються відповідні інваріанти числових графів, будуються графіки функцій степенів вершин графів і пропонується новий специфічний метод дослідження ізоморфізму для натуральних модульних графів.
Визначення 1. Числовим графом називається трійка , де –множина вершин, –множина твірних, а –деяка породжуюча однозначна функція двох аргументів, що задовольняє умовам
.
Стосовно множин та передбачається, що їх елементами можуть бути довільні об’єкти типу числа, вектора, матриці тощо. Але найбільший інтерес представляє випадок, коли елементи множин та –числа (цілі, раціональні, дійсні, комплексні), а задається як функція на множині дійсних чисел. В залежності від вигляду функції отримуються різні графи.
З усіх числових графів найбільш простими є графи, які називаються арифметичними, у яких породжуюча функція.
Визначення 2. Арифметичним графом (А-графом) називається граф, який задається двома множинами: множиною вершин та множиною твірних. У зв’язку з цим вершини суміжні тоді й тільки тоді, коли.
Визначення 3. Натуральним арифметичним -вершинним графом (NA-графом) називається арифметичний граф, у якого.
Визначення 4. Матрицею твірних для довільного NA-графа називається матриця, у якій, якщо існує таке, що, та –для інших значень.
Матриця твірних для повного NA-графа має вигляд
.
Кожній твірній відповідають ребра, число яких дорівнює
. (1)
З формули (1) випливає, що при число ребер, яке відповідає цій твірній, дорівнює.
Для натуральних арифметичних графів виконуються ряд властивостей, що дозволяє не тільки визначити ізоморфізм графів, а й розв’язати більш загальну задачу переліку ізоморфних компонент.
Теорема 1. Клас NA-графів з однією твірною, , розбивається на три ізоморфних собі підкласи:
) три графи з твірними
, , для;
2) графів типу 1), де граф може не існувати при;
3) графів типу 1), 2), які можуть не існувати для.
Таким чином, ізоморфні графи групуються і кількість ізоморфних компонент піддається простому переліку.
Лема 1. NA-граф з однією твірною не може бути ізоморфним NA-графу з числом твірних більше 2.
Лема 2. Необхідною і достатньою умовою того, що NA-граф з двома твірними має степінь вершин не більше 1:
;
;
.
Теорема 2. У класі NA-графів з двома твірними кожному NA-графу з однією твірною відповідає множина ізоморфних йому, що складається з
a) графів з твірними
, ,
,
для;
б) графів того ж типу, де граф з може не існувати, для;
в) графів перших трьох типів, де останні два можуть не існувати для.
Всі ці властивості можна записати у вигляді загального результату.
Наслідок. Кожному NA-графу з однією твірною відповідає множина ізоморфних NA-графів, що становить:
графів для;
графів для;
графів для, де.
Ці властивості дозволяють повністю перелічити не ізоморфні компоненти для натуральних арифметичних графів з кількістю твірних, що не перевищує 2.
Визначення 5. Модульним графом (М-графом) називається граф, який задається двома множинами: множиною вершин та множиною твірних. У зв’язку з цим вершини суміжні тоді і тільки тоді, коли.
Визначення 6. Натуральним модульним графом (NM-графом) називається модульний граф, у якого.
На відміну від натуральних арифметичних графів, натуральні модульні графи містять набагато менше ізоморфних собі. Так має місце така властивість.
Лема 3. Два NM-графи з однією твірною і ізоморфні тоді і тільки тоді, коли.
Це дає серйозне звуження для пошуку ізоморфних графів, адже будь-які два NM-графи з різними твірними не будуть ізоморфними.
Лема 4. Два NM-графи з двома твірними будуть ізоморфними за умови, що сума їх твірних збігається.
Лема 5. Два NM-графи з однаковою кількістю твірних будуть ізоморфними, якщо сума їх твірних збігається.
Ці властивості пов’язані з інваріантом NM-графа –кількістю його ребер.
Наступним інваріантом NM-графа є вектор степенів його вершин. Для того, щоб його визначити, скористаємося функцією, яка має такий вигляд:
1) якщо, то твірна додає до степеня вершини величину
2) якщо, то твірна додає до степеня вершини величину
Застосувавши цю функцію для всіх твірних графа маємо графіки векторів степенів вершин (рис.1), які можна порівнювати між собою.
РИС. 1. Графік функції степенів вершин
Для порівняння зручніше використовувати впорядковану функцію (або графік) який отримав назву канонічного (рис.2).
РИС. 2. Канонічний графік функції степенів вершин
У цьому випадку порівняння можна виконати за час O().
У випадку, коли всі вершини графа мають однаковий степінь, то канонічний графік функції степенів його вершин має вигляд прямої і такі графи були розглянуті детальніше.
Лема 6. Всі однорідні NM-графи степені мають множину твірних у вигляді, де,. Однорідний NM-граф степені можливий лише при парному числі вершин і відрізняється від графа степені додатковою твірною.
Ця лема дозволила досліджувати ізоморфізм для парних, при цьому для графів з парним числом вершин розповсюджувати результат на випадок, виключаючи з розгляду твірну і відповідні ребра як заздалегідь ізоморфні.
Ще один цікавий результат був отриманий для NM-графів з двома твірними.
Теорема 3. Граф - плоский граф; якщо, то він складається з циклів, з яких циклів мають довжину та циклів мають довжину 4, де.
Найпростіші однорідні графи –NM-графи з двома твірними, що є гамільтонівськими циклами.
Лема 7. Число NM-графів з двома твірними, що є гамільтонівськими циклами, складає, де - функція Ейлера.
Ця властивість виявилась ґрунтовною, оскільки однорідні графи з парною кількістю твірних складаються у найпростішому випадку з гамільтонівських циклів (рис.3,а,б).
РИС. 3. Ізоморфні графи, які складаються з композиції гамільтонівських циклів
Спочатку розглянуто випадок з простим. Будь-який однорідний граф буде складатись з композиції гамільтонівських циклів. Доведено ряд тверджень.
Нехай –пара твірних, що утворює гамільтонівський цикл. Позначимо кожен такий цикл.Тоді мають місце такі властивості.
Лема 8. Для перетворення циклу в необхідно застосувати перестановку
(2)
Формула (2) прийнятна для будь-яких графів, що містять гамільтонівські цикли у вигляді або їх комутативну композицію.
Лема 9. Два NM-графи та –ізоморфні, якщо виконується умова.
Ця властивість дозволила розв’язати задачу пошуку ізоморфізму для довільних композицій.
Теорема 4 Два NM-графи та –ізоморфні, якщо виконується одна з умов:
Інакше кажучи, якщо перевести цикл в, то цикл перейде в цикл, або ж якщо цикл перевести в, то цикл перейде в. Для загального випадку, коли кількість циклів довільна, виконується впорядкування циклів з тим, щоб отримати канонічну побудову, тобто граф з найменшим у лексикографічному порядку наборі твірних.
Для графів зі складеним знайдено наступні властивості.
Нехай в канонічному розкладі
, (3)
де - різні прості дільники числа. Тоді можна стверджувати, що всі дільники числа вичерпуються усіма числами у вигляді
, (4)
де
. (5)
У випадку маємо, , , а таких циклів, де - функція Ейлера, і до таких випадків застосовується підхід як і до простих.
У випадку граф з твірними складається з циклів довжиною, тобто 2-фактором з компонент зв’язності.
Позначимо для фіксованого, заданого у вигляді (3), з твірними, де,. Впорядкуємо множину всіх дільників у вигляді (4) з умовою (5) у порядку зростання. Очевидно, що загальна кількість таких дільників становить. З їх числа необхідно вилучити множник, при, а також при та.
Визначення 7. -класом графів будемо називати таку підмножину графів, для яких.
Лема 10. Число NM-графів -класу за фіксованого становить.
-клас графів, для якого індекси пробігають першу половину наведеної системи лишків по модулю утворює множину, де.
Теорема 5. Число неізоморфних NM-графів 1-класу, де становить
де.
Таким чином, для однорідних NM-графів отримано всі необхідні результати, що дозволили побудувати ефективний алгоритм перевірки ізоморфізму двох графів.
Третій розділ присвячений питанням знаходження хроматичного числа натуральних модульних графів.
Визначення 8. Хроматичним числом NM-графа називається найменше число, якому відповідає розбиття множини вершин на підмножин, які взаємно не перетинаються, таких, що будь-які дві вершини не суміжні, тобто.
Досліджено хроматичне число для деяких підмножин NM-графів. Для них стали відомі такі властивості.
Твердження. Хроматичне число NM-графа з однією твірною складає 2.
Теорема 6. Хроматичне число NM-графа для складає
де.
Разом з тим отримана нижня оцінка для хроматичного числа NM-графів, яка складає 2.
Теорема 7. Хроматичне число NM-графів з твірними (рис.4) при складає.
РИС. 4. Граф з твірними
Лема 11. NM-граф з твірними (рис.5) має хроматичне число.
РИС. 5. Граф для
Лема 12. Якщо в NM-графі усі твірні, то.
Крім того, наслідок цієї леми теж має практичне значення.
Наслідок. Якщо в NM-графі усі твірні мають вигляд, де, а –задана позитивна константа, то.
Лема 12 та її наслідок формально вказують на нижню оцінку хроматичного числа NM-графа і вичерпують підмножину графів даного підкласу, що розпадається на дві незв’язні підмножини вершин. Спираючись на ці властивості був отриманий такий результат.
Лема 13. Хроматичне число NM-графів з множиною твірних, де не задовольняють умовам леми 12 та її наслідку, і становить.
Для розв’язання задачі розфарбування числових графів були розглянуті існуючі методи знаходження хроматичного числа, такі як емпіричний, аналітичний, алгебраїчний тощо. Було вказано на обмеження у використанні цих методів для числових графів і запропоновано метод різниць, який дозволяє повною мірою використати спеціальну структуру NM-графів. На рис.6 показано приклад розфарбованого трьома кольорами NM-графа. Аналізуючи властивості розфарбування введено поняття коду розфарбування.
РИС. 6. Граф з,
Визначення 9. Кодом розфарбування графа назвемо періодичну послідовність чисел, таку, що дозволяють для кольору побудувати послідовність несуміжних вершин.
Коди розфарбування відповідають таким властивостям.
Властивість 1. Будь-яка сума послідовних чисел коду розфарбування не належить .
Властивість 2. Для кодів розфарбувань NM-графа має місце
,
де –довжини кодів розфарбувань відповідного кольору.
Властивості 1 та 2 накладають обмеження на значення кодів розфарбувань, але не на їх довжину. Це означає, що коди різної довжини теж можуть бути прийнятними.
У роботі наведений приклад розфарбування графа трьома кольорами як кодами однакової довжини, так і різної довжини. Проілюстровано вибір підходящого коду розфарбування для заданого графа для кожного з кольорів. Для вибору кодів розфарбувань використовувались матриці сумісності кольорів, де сумісність означає прийнятність різних кодів в одному розфарбуванні. Нижче наведені приклади матриць сумісності кодів розфарбувань
; .
Для довільної кількості кольорів розроблено розширення методу різниць.
У четвертому розділі проводилась побудова відповідних алгоритмів та дослідження їх обчислювальної ємності. Спочатку проаналізовано алгоритм знаходження ізоморфізму двох графів. Введено поняття канонічної побудови.
Визначення 10. Побудова твірних однорідного NM-графа називається канонічним, якщо і воно лексикографічно менше будь-якого іншого.
У такому випадку перевірка ізоморфізму графів полягає у порівнянні відповідних канонічних побудов. Таким чином, для довільного однорідного графа запропоновано алгоритм, який має оцінку, що залежить тільки від . Реалізація алгоритму перевірки ізоморфізму двох однорідних NM-графів включає в себе дві компоненти: 1) перевірка необхідних умов –порівняння інваріантів; 2) порівняння канонічних побудов. Графи, для яких не збігаються канонічні графіки, не ізоморфні.
Алгоритм знаходження хроматичного числа NM-графа складається з кількох етапів. Перший етап –визначення нижньої та верхньої оцінок хроматичного числа для заданого NM-графа. Нижня оцінка очевидна і складає 3 для графів, що містять більше двох твірних, якщо вони не відповідають умовам леми 12 та її наслідку, 2 –у протилежному випадку. Верхня оцінка для хроматичного числа також була детально вивчена. Доведено таке твердження.
Лема 14. Хроматичне число NM-графа не перевищує найменшого натурального числа, яке не є дільником жодної твірної.
Ця властивість узгоджується з лемою 12 та її наслідком. Окрім даної властивості, запропоновані ще кілька оцінок, такі як та . Алгоритм за методом різниць дозволяє виконати розфарбування заданою кількістю кольорів або ж дати відповідь про неможливість такого розфарбування. Застосування методу різниць у межах нижньої та верхньої оцінок дає розв’язок задачі знаходження хроматичного числа графа методом дихотомії між нижньою та верхньою оцінками. Розфарбування кольорами виконується за час , де –лінійна функція від .
Додатки містять тексти програм мовою програмування Python, які реалізують запропоновані алгоритми.
ВИСНОВКИ
У дисертаційній роботі отримані важливі наукові результати, які закономірно й послідовно поєднують теоретичні та практичні дослідження властивостей числових графів. Показано, що числові графи дозволяють будувати ефективні алгоритми для деяких задач, які є NP-повними для звичайних графів.
Основні здобутки:
. Уперше досліджено ізоморфізм натуральних арифметичних графів, а також виконано перелік ізоморфних підкласів для натуральних арифметичних графів з кількістю твірних, яка не перевищує 2.
. Розв’язана задача знаходження ізоморфізму NM-графів з кількістю твірних, яка не перевищує 3. Введено поняття такого інваріанта NM-графів як канонічний вектор степенів вершин. Знайдені необхідні та достатні умови ізоморфізму окремих типів NM-графів.
. Досліджена структура та властивості однорідних NM-графів. Досліджені однорідні натуральні модульні графи, які складаються з композиції гамільтонівських циклів, а також з комбінації гамільтонівських циклів і фактор-графів. Визначені підмножини натуральних модульних графів, які не мають собі ізоморфних.
. Уперше повністю розв’язана задача знаходження ізоморфізму однорідних NM-графів з кількістю твірних, яка не перевищує 5. На основі теорії розв’язання квадратичних рівнянь в скінченних полях розроблено метод розв’язання задачі ізоморфізму для однорідних NM-графів.
. Уперше побудовано поліноміальний алгоритм визначення ізоморфізму довільних однорідних NM-графів.
6. Поставлена, досліджена та розв’язана задача знаходження хроматичного числа натурального модульного графа. Виділені підкласи 2- та 3-хроматичних натуральних модульних графів. Побудовано та проілюстровано спеціальний метод розфарбування натурального модульного графа трьома і чотирма кольорами.
7. Визначені нижні та верхні оцінки хроматичного числа натуральних модульних графів, які не залежать від кількості вершин графа. Розроблено метод розфарбування NM-графів, який дозволяє ефективно розфарбовувати граф довільною кількістю кольорів.
8. Розроблено та реалізовано поліноміальний алгоритм визначення хроматичного числа довільного натурального модульного графа. Проведено ряд обчислювальних експериментів та перевірок, які підтверджують поліноміальну швидкість роботи алгоритмів визначення хроматичного числа.
ОСНОВНІ ПОЛОЖЕННЯ ДИСЕРТАЦІЇ ОПУБЛІКОВАНІ
В ТАКИХ ПРАЦЯХ:
АНОТАЦІЇ
Шулінок Г.О. Розв’язання задач ізоморфізму та знаходження хроматичного числа на числових графах . –Рукопис.
Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.01 –теоретичні основи інформатики та кібернетики. –Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, 2006.
Дисертацію присвячено дослідженню проблем ізоморфізму та хроматичного числа числових графів і побудові на них ефективних алгоритмів для розв’язку відповідних задач. Розглядаються такі підкласи числових графів як натуральні арифметичні та натуральні модульні графи. Повністю розв’язана задача визначення ізоморфності для натуральних арифметичних графів з кількістю твірних, що не перевищує 2, та для натуральних модульних графів з кількістю твірних, що не перевищує 3. Повністю розв’язана задача визначення ізоморфності для однорідних натуральних модульних графів з кількістю твірних, яка не перевищує 5. Запропоновано алгоритм, що дозволяє перевірити ізоморфізм двох довільних однорідних натуральних модульних графів з однаковою кількістю твірних. Поставлена і досліджена задача знаходження хроматичного числа натуральних модульних графів. Проведена класифікація натуральних модульних графів для визначення хроматичного числа. Виділені підмножини 2- та 3-хроматичних натуральних модульних графів. Проведено аналіз методів розфарбування графів, а також прийнятність цих методів для числових графів. Запропоновано метод різниць для розфарбування графа заданим числом кольорів. Запропоновано алгоритм, що дозволяє визначити хроматичне число довільного натурального модульного графа.
Ключові слова: числовий граф, арифметичний граф, модульний граф, зв’язність, ізоморфізм, хроматичне число, розфарбування, породжуюча функція, твірна, суміжність, алгоритм.
Шулинок Г.А. Решение задач изоморфизма и нахождения хроматического числа на числовых графах. –Рукопись.
Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.01 –теоретические основы информатики и кибернетики. –Институт кибернетики им. В.М. Глушкова НАН Украины, Киев, 2006.
Диссертация посвящена исследованию проблем изоморфизма и хроматического числа числовых графов, применению их свойств для создания на них эффективных алгоритмов решения соответствующих задач. Рассматриваются наиболее изученные подклассы числовых графов, такие как натуральные арифметические и натуральные модульные графы. Полностью решена задача определения изоморфизма для натуральных арифметических графов с количеством образующих, не превышающих 2, перечислены все изоморфные компоненты для заданного натурального арифметического графа с одной образующей. Полностью решена задача нахождения и существования изоморфных графов для натуральных модульных графов с количеством образующих, не превышающих 3. Найден метод определения вектора степеней натурального модульного графа и канонического вектора степеней как основного инварианта. Проведено полномасштабное исследование регулярных натуральных модульных графов. Найдены и классифицированы различные типы регулярных натуральных модульных графов, определено ряд свойств, позволяющих эффективно решать задачу изоморфизма таких графов. Решена задача нахождения изоморфизма регулярных натуральных модульных графов с количеством образующих не превышающих 5. Построен и реализован в виде программы алгоритм определения изоморфизма для произвольных регулярных натуральных модульных графов с произвольным количеством образующих. Поставлена и исследована задача нахождения хроматического числа натуральных модульных графов. Выделены подмножества 2- и 3-хроматических графов. Проведен обзор методов раскраски графов и проанализирована возможность их применения для числовых графов. Разработан и рассмотрен на примерах метод разностей, который позволяет построить раскраску заданного натурального модульного графа заданным набором красок. Определены нижняя и верхняя оценки хроматического числа натуральных модульных графов, что позволило построить алгоритм нахождения хроматического числа произвольного натурального модульного графа как направленный поиск минимальной раскраски в пределах существующих оценок.
Ключевые слова: числовой граф, арифметический граф, модульный граф, связность, изоморфизм, раскраска, хроматическое число, метод разностей, порождающая функция, смежность, алгоритм.
Shulinok G.A. Isomorphic graphs comparing and chromatic number problems solving for numeric graphs. –Manuscript.
Dissertation for a candidate degree in physics-mathematical science by the specialty 01.05.01 –theoretical fundamentals of informatics and cybernetics. – V.M.Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, 2006.
The dissertation is devoted to investigation of NP-problems such isomorphism comparing and chromatic number problem applied to numerical graphs and finding methods and algorithms for effective solving ones problems. Natural arithmetical and natural modular graphs were considered. It was completely solved isomorphism problem for natural arithmetical with number of generatrixes not greater 2. It was providing enumeration of all isomorphic to any numerical arithmetical graph with one generatrix. Also it was completely solved isomorphism problem for any natural modular graphs with number of generatrixes not greater 3. Regular natural modular graphs were fundamentally investigated. It was provided graphs classifications and separate subsets of graphs to have not isomorphic to ones. It was completely solved an isomorphism problem for regular natural modular graphs with number of generatrixes not greater than 5. Also it was built an algorithm to solve isomorphism problem for regular modular graphs with arbitrary number of generatrixes. The chromatic number problem was investigated. It was provided separation of 2- and 3-chromatic subsets of natural modular graphs. Also lower and upper evaluations for chromatic number were found. Known coloring methods were reviewed in sense to apply ones to numeric graphs coloring. A method of differences was proposed to effective coloring of natural modular graphs. Based on this method chromatic number finding algorithm was proposed.
Key words: numerical graph, arithmetical graph, modular graph, connectivity, isomorphism, chromatic number, coloring problem, generative function, generatrix, contiguity, algorithm.
Підп. до друку 03.05.2006. Формат 60х84/16. Папір офс.
Офс. друк. Ум.-друк. арк. 1,16. Ум. фарбо-відб. 1,39.
Обл.-вид. арк. 1,0. Зам. 70. Тираж 110 прим.
Редакційно-видавничий відділ з поліграфічною дільницею
Інституту кібернетики ім. В.М. Глушкова НАН України
МСП, Київ 187, проспект Академіка Глушкова, 40