Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Національна академiя наук України
Iнститут кiбернетики імені В.М. Глушкова
ШУЛІНОК Ірина Едуардівна
УДК 519.1
РОЗВ’ЯЗАННЯ ЗАДАЧ ОПТИМАЛЬНОГО ПРЕДСТАВЛЕННЯ ЧИСЛОВИХ графів ТА ДОСЛІДЖЕННЯ УМОВ ПОБУДОВИ
НА НИХ ЕФЕКТИВНИХ АЛГОРИТМІВ
01.05.01 - теоретичнi основи iнформатики та кiбернетики
Автореферат
дисертацiї на здобуття наукового ступеня
кандидата фiзико-математичних наук
Київ – 2004
Дисертацією є рукопис.
Робота виконана в Інституті кібернетики ім. В.М. Глушкова НАН України.
Науковий керівник : доктор фізико-математичних наук,
Донець Георгій Панасович,
Інститут кібернетики ім. В.М. Глушкова
НАН України, завідувач відділу.
Офіційні опоненти: доктор фізико-математичних наук, професор, Асельдеров Зайнутдін Макашаріпович, Національний технічний університет
України “КПІ”, кафедра автоматизованих систем обробки інформації та управління,
кандидат фізико-математичних наук,
Шаріфов Фірдовсі Ахун-огли,
Інститут кібернетики ім. В.М. Глушкова
НАН України, старший науковий співробітник.
Провідна установа: Київський національний університет
імені Тараса Шевченка, факультет кібернетики, кафедра математичних методів
еколого-економічних досліджень.
Захист відбудеться "23"_ квітня _ 2004 р. о(об)_ годині на засіданні спеціалізованої вченої ради Д 26.194.02 при Інституті кібернетики імені В.М. Глушкова НАН України за адресою:
, МСП Київ-187, проспект Академіка Глушкова, 40.
З дисертацією можна ознайомитися в науково-технічному архіві інституту.
Автореферат розісланий "__"__березня_____2004 р.
Учений секретар
спеціалізованої вченої ради СИНЯВСЬКИЙ В.Ф.
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. Дисертаційна робота присвячена дослідженню числових графів та їх основних властивостей. Дослідження велися у трьох напрямках: а) оптимізація процесу кодування або розв’язання задачі оптимального представлення довільних класів графів у вигляді числових графів; б) визначення загальних структурних властивостей числових графів таких як зв’язність, цикломатичне число, групи автоморфізмів, хроматичне число тощо; в) використання цих властивостей для створення методів побудови на числових графах ефективних алгоритмів.
Слід зазначити, що проблема ефективності алгоритмів (у тому числі не тільки на графах) за останні 50 років породила величезну масу публікацій, водночас проблема оптимального представлення графів у вигляді числових графів до сьогодні має відображення не більше, ніж у трох десятках робіт.
Останнім часом дуже багато досліджень в галузі розпізнавання образів, структурного та системного аналізу, в розробці програмних комплексів, у конструюванні обчислювальної техніки та багатьох інших галузях як об’єкт початкових даних використовують графи, які мають специфічну структуру. Деякі користуються при цьому традиційним представленням графів, що вимагає величезної пам’яті та приводить до громіздких обчислень з великими витратами часу. В більшості випадків ці графи мають ієрархічну або симетричну структури, що складаються з частин, які є однотипові або повторюються. А саме, числові графи дозволяють з максимальним ефектом використовувати ці особливості. Необхідно тільки знайти підходящу функцію, яка адекватно описує суміжність вершин графа. В результаті вдалого підбору такої функції представлення заданого графу може зменшитися за об’ємом пам’яті в декілька разів, а операції пошуку у величезних масивах пам’яті для отримання необхідної інформації замінюются невеликою кількістю елементарних обчислень.
Найпростіший клас числових графів –арифметичні графи –вивчаються вже понад 30 років. Уперше поняття арифметичного графа з’явилося у роботах Ю.Г. Григорьяна та його співавторів, в яких йшлося про окремі властивості арифметичних графів, і які не носили фундаментального характеру. Вони використовували арифметичні графи перш за все для ілюстрації деяких закономірностей схем в галузі кристалографії, хімії та електронного конструювання, але вони мало приділяли уваги їм як математичному об’єкту. Поняття числового графа виникло з появою робіт Г.П. Донця та його послідовників, після чого починається планомірне та інтенсивне дослідження числових графів (куди, крім арифметичних, ще включені модульні та їм подібні) та їх властивостей. В наукових роботах Г.П. Донця незалежно від Ю.Г. Григорьяна досліджувалися графи, що задаються аналітичним способом. Як окремий випадок цих графів можна трактувати числові графи. Отримані важливі вичерпні характеристики цих графів –зв’язність, цикломатичне число, оптимальне представлення. Уперше доведено, що на числових графах багато алгоритмів мають кращі показники, ніж на звичайних, тобто представлених за допомогою списка суміжностей. Виникло питання, чи можливо створити для числових графів специфічні алгоритми, які мають додаткові переваги над відповідними алгоритмами, що розроблені для графів, представлених традиційним способом. Отримати позитивну відповідь на це питання стало можливим завдяки дослідженням, відображених у даній дисертаційній роботі. В ній, крім того, поряд з новими і важливими результатами про арифметичні графи розпочато вивчення такого нового підкласу числових графів як модульні графи. Так як арифметичні та ці графи не вичерпують всі числові графи, то в дисертації зазначені засоби можливого представлення довільних числових графів. Це дає простір для вивчення нових класів числових графів. Крім того, в дисертаційній роботі намічені й інші важливі задачі, які необхідно розв’язати для числових графів, а саме: ізоморфізм графів, проблеми фарбування, гіпотеза Турана, гіпотеза Хадвігера тощо.
Незважаючи на очевидну значимість, яку набувають числові графи в різних галузях наукових досліджень, ця тема зовсім не отримала розповсюдження у зарубіжній математичній літературі. Є поодинокі публікації, де вживається поняття числового графа, але в іншому розумінні, де кожному ребру приписана його вага у вигляді певного числа.
На основі цих наведених фактів можна зробити висновок, що тема дисертаційної роботи за своїми отриманими науковими результатами та можливими перспективними напрямками є актуальною.
Зв’язок роботи з науковими програмами, планами, темами. Наведені в дисертаційній роботі дослідження виконувалися за держбюджетними темами ВФ.110.03 “Створення математичних методів, алгоритмів та програмного забезпечення для розв’язування задач оптимальної побудови комунікацій довільного профілю в тримірному просторі з обмеженнями”(1997–рр.) (номер держ. реєстрації –U000319), ВФ.110.06 “Розробка ефективних методів та алгоритмів для розв’язування задач оптимального проектування в галузі машинобудування” (2000–рр.) (номер держ. реєстрації –U002649) та ВФ.110.08 “Розробити методи та алгоритми розв’язування зваженої задачі Штейнера з метою запровадження її до оптимального проектування промислових мереж” (2003–рр.) (номер держ. реєстрації –U003916). Описані в роботі алгоритми реалізовані у вигляді прикладних програм, які функціонують в середовищі MS DOS и WINDOWS 98.
Мета і завдання дослідження. Метою дисертаційної роботи є дослідження властивостей числових графів та знаходження достатніх умов для побудови на них ефективних алгоритмів. Для цього були поставлені такі основні задачі :
Об’єкт дослідження –задачі теорії графів та методи їх розв’язування.
Предмет дослідження –числові графи, задані у вигляді двох множин натуральних чисел та функції суміжності, методи розв’язування дискретних задач оптимізації.
Методи дослідженя: для вивчення властивостей числових графів застосовуються методи теорії чисел, теорії скінченних полів, зокрема теорії розв’язування діофантових рівнянь, лінійної алгебри та комбінаторіки. Для побудови відповідних алгоритмів застосовуються методи теорії графів, теорії дискретної оптимізації та теорії складності алгоритмів.
Наукова новизна отриманих результатів. Основні результати роботи, які визначають її наукову новизну та виносяться на захист, такі:
вперше досконально і вичерпно досліджені однорідні натуральні арифметичні графи. За допомогою спеціально введеного графа розкладу твірних повністю описані структура однорідних графів та його загальні параметри. На цій основі запропонована методика побудови таких графів з наперед заданими параметрами;
запропоновано новий загальний підхід до представлення натуральних арифметичних графів шляхом введення матриці твірних, що дало змогу вперше розв’язати задачу оптимального представлення однорідних дерев першого рангу в класі арифметичних графів;
розглянуто новий клас числових графів, які носять назву модульних. Розв’язані задачі про цикломатичне число та зв’язність цих графів. Повністю описано структуру цих графів з двома твірними та запропоновано підхід до вивчення структури модульних графів з довільним числом твірних;
доведено, що базові алгоритми на графах –пошук в глибину і пошук в ширину –для числових графів мають кращі показники по швидкодії та об’єму пам’яті у порівнянні зі звичайними графами, що задаються списками суміжності;
запропонована загальна методика, що дозволяє багато довільних графів з деякими певними ознаками представити у вигляді числових графів. Ця методика продемонстрована на типових прикладах, взятих з відомих робіт в галузі розпізнавання образів, математичних моделей та методів у паралельних процесах;
розроблено алгоритм для зв’язних числових графів з довільним числом твірних, який видає готовий список ребер остовного дерева графа та порядок обходу всіх вершин цього графа.
Практичне значення отриманих результатів. Практичне значення результатів дисертаційної роботи перш за все полягає в тому, що вони безпосередньо дають певний внесок в розв’язання проблеми ефективності алгоритмів на графах. Відомо, що багато задач на графах є NP-повними, тобто не мають поліноміальних алгоритмів розв’язку. Водночас переважна більшість практичних задач, що розв’язуються методами теорії графів, має свою специфіку, яка полягає в тому, що вони використовують такі графи, структура яких має однотипові та симетричні частини. Це дає можливість представляти такі графи у вигляді числових, для яких багато алгоритмів (навіть неполіноміальних) мають поліноміальну інтерпретацію.
Окремо слід зазначити і такий немаловажний фактор, який ураховується у багатьох практичних задачах, як об’єм пам’яті для розміщення початкових даних про структуру графа, а також їх надійність. Якщо традиційно граф задається у вигляді списку суміжностей, то це вимагає великого об’єму комп’ютерної пам’яті, що може привести до їх часткової утрати, або спотворення. Цього не може статися, коли граф представляється у вигляді числового, де структура графа обчислюється за відомою функцією.
Особистий внесок здобувача. Всі результати, які складають суттєву частину дисертаційної роботи, отримані автором самостійно. Роботи [1,2,4,5,6,10] написані здобувачем особисто, і всі наукові результати, що містяться в них, є оригінальними.
Роботи [3,7,8,9] написані у співавторстві з науковим керівником Г.П. Донцем. В них керівнику належать теоретичні ідеї та постановка задач, а дисертанту –доведення основних тверджень, доопрацювання статей до логічного вигляду та перевірка на тестах теоретичних висновків.
Апробація результатів дисертації. Окремі результати роботи доповідалися на наукових семінарах та конференції: XXI науковому семінарі “Дискретна математика” (Одеса, вересень, 1999); науковому семінарі кафедри обчислювальної математики та математичної кібернетики Дніпропетровського національного университету (Дніпропетровськ, лютий, 2000); Міжнародному симпозіумі “Питання оптимізації обчислень” (Севастополь, вересень, 2001); Міжнародній конференції з прикладної математики, присвяченій 65-річчю з дня народження Б.М. Пшеничного (Київ, червень, 2002).
Дисертаційна работа цілком обговорювалася на сумісному науковому семінарі “Теорія оптимальних рішень” в відділенні МК та СА Інституту кібернетики ім.В.М. Глушкова НАН України відділів № 110 та № 120 під керівництвом академіка Н.З. Шора (травень, 2003).
Публікації. Основні результати дисертації опубліковано в 10 роботах, із яких 7 робіт –у наукових фахових виданнях, 1 робота –у збірнику доповідей міжнародної конференції, 1 робота –у препринті, 1 робота –у нефаховому збірнику.
Структура та обсяг роботи. Дисертація складається із вступу, чотирьох розділів, висновків, списку використаних джерел, що містить 76 найменувань. Загальний обсяг роботи –175 сторінок друкованого тексту, обсяг основного тексту – 168 сторінок. Робота включає 5 таблиць та 35 рисунків.
У вступі обгрунтовано актуальність обраної теми дисертаційної роботи. Показано, що ця тема належить до загальновідомих і складних задач дискретної математики, пов’язаних з проблемою кодування графів, таких як задача про ширину та профіль графів, про довжину гіперграфів. Із загальної проблеми шляхом уособлення деяких методів кодування виділені графи, які отримали назву числових. Дослідження властивостей цих математичних об’єктів, їх застосування в різних практичних галузях –це і лягло в основу започаткованої теми дисертаційної роботи. Далі конкретно були сформульовані мета та задачі дослідження, зроблено аналіз та подана характеристика наукової новизни та пратичної значимості отриманих результатів. Зазначено зв’язок обраної теми з науковими програмами, планами, темами за місцем виконання дисертаційної роботи. Відзначено особистий внесок здобувача у кожній опублікованій науковій праці, відображено географію його виступів на фахових вітчизняних та міжнародних конференціях, подано перелік наукових праць за темою дисертаційної роботи.
Перший розділ присвячено аналізу стану наукових досліджень за обраною темою та обгрунтуванню вибору напрямків досліджень дисертаційної роботи.
Особливо підкреслюється, що обрана тема є малодослідженою галуззю дискретної математики, яка ще недостатньо висвітлена у світовій математичній літературі. У хронологічному порядку літературу можна поділити на три етапи.
Перший етап пов’язаний з роботами групи вірменських учених Ю.Г. Григорьяна, Г.К. Манояна та А.М. Адонца, що почали друкуватися на початку 70-х років минулого століття. В них досліджувалися властивості арифметичних графів, які послужили прототипом більш загального класу числових графів. Але після 1990 року наукові праці за даною темою зазначені автори не публікували.
Другий етап можна датувати початком 80-х років минулого століття, коли появилися роботи Г.П. Донця та його послідовників Ю.І. Нєженцева та І.М. Асельдерової. У них вперше були поставлені задачі математичного характеру й отримані загальні результати про структуру числових графів та їх оптимальне представлення.
Третій етап займає останні 5-7 років, коли появилися роботи, присвячені побудові базових алгоритмів на числових графах. У роботах Г.П. Донця було виявлено, що при цьому числові графи мають значну перевагу над графами, які задаються традиційними засобами. Ця обставина відкрила нові можливості побудови якісних алгоритмів на графах.
У другому розділі розглядаються арифметичні графи та вивчаються їх властивості. Показано, що це поняття є частковим випадком для графів, які задаються аналітичним способом. Досліджені однорідні арифметичні графи та знайдено оптимальне представлення зірок.
Визначення 1. Графом називається трійка , де –множина вершин, –множина твірних, а – деяка породжуюча однозначна функція двох аргументів, що задовольняє умовам
. (1)
Відносно множин та передбачається, що їх елементами можуть бути довільні об’єкти типу: числа, вектора, матриці тощо. Але найбільший інтерес представляє випадок, коли елементи множин та –числа (цілі, раціональні, дійсні, комплексні), а як дається функція на множині дійсних чисел. В залежності від вигляду функції отримуються різні графи. В подальшому ці графи отримали назву числових.
Досліджені квадратична та лінійна функції . Показано, що звичайні інваріанти, що характеризують рівняння кривих другого порядку, також характеризують і відповідний граф.
Будемо говорити, що у графі із вершини у вершину заходить дуга, якщо . Граф, у котрого називається неорієнтованим.
Очевидно, що класичне визначення графів, наприклад, в О.О. Зикова, та визначення, що задається аналітичним способом, еквівалентні. Для цього можна як функцію взяти інцидентор .
У дисертаційній роботі розглянуто лінійну та квадратичну породжуючу функції. Показано, що такі числові графи відповідають графікам прямої, або кривої лінії другого порядку, а вершинам відповідають точки графіка з цілочисельними координатами.
Із всіх числових графів найбільш простими є графи, які називаються арифметичними, у яких породжуюча функція .
Визначення 2. Арифметичним графом (А-графом) називається граф , який задається двома множинами: множиною вершин та множиною твірних . У зв’язку з цим вершини суміжні тоді й тільки тоді, коли .
Лема 2.1. Будь-який скінченний граф можна представити у вигляді А-графа.
Визначення 3. Натуральним арифметичним вершинним графом (NA-графом) називається арифметичний граф, у якого .
Визначення 4. Матрицею твірних для довільного NA-графа називається матриця , у якій , якщо існує таке , що , та для інших значень .
Матриця твірних для повного NA-графа має вигляд
. (2)
Кожній твірній відповідають ребра, число яких дорівнює
. (3)
Із формули (3) випливає, що якщо , то число ребер, яке відповідає цій твірній, дорівнює . Легко показати, що існують NA-графы з довільним числом ребер від 1 до .
Для самих простих графів можна легко знайти оптимальне представлення у вигляді NA-графів. Для вершинного ланцюга одне з представлень задається множиною (рис. 1).
Рис. 1. Представлення ланцюга у вигляді NA-графа
Аналогічно для вершинного гамільтонового циклу існує два представлення:
для парного , для непарного .
Для легко знайти представлення будь-якого графа у вигляді NA-графа. Для із всіх 11 графів тільки 2 неможливо представити у вигляді NA-графа, це трипроменева зірка та її доповнення –трикутник з ізольованою вершиною. Для із 34 графів 8 неможливо представити у вигляді натуральних арифметичних графів. Як видно з рисунків, структура NA-графів є специфічною. Всім твірним відповідає послідовність паросполучень тощо, при цьому всі вершини з номерами не використовуються. А твірним також відповідає послідовність паросполучень тощо, при цьому всі вершини з номерами не використовуються. Якщо , то вершина для даного вважається ізольованою.
У зв’язку з особливостями матриці твірних можна зробити висновок, що для регулярності графа до кожної твірної необхідно додавати твірну , і навпаки, до кожної твірної необхідно додавати твірну .
Для детального вивчення залежності між твірними у регулярному графі, вводиться граф розкладу твірних , вершинами якого є всі твірні вершинного NA-графа, число яких дорівнює N. Всі парні твірні зв’язані ребрами з твірними та . Всі непарні твірні є висячими вершинами, так як на них процес розкладу твірних закінчується. Позначимо (відповідно ) граф з непарною (парною) кількістю вершин. Про структуру таких графів стверджує наступна
Лема 2.3. Число рівней графа розкладу дорівнює , яке визначається з умови .
На рис. 2 наведено приклад графа розкладу твірних для .
Рис. 2. Граф
Визначення 5. Характеристичною перестановкою для графа розкладу твірних називається перестановка , де , а означає найбільше непарне число, на яке ділиться b.
Визначення 6.Вагою елемента на перестановці називається величина .
За допомогою гомоморфних перетворень отримано важливі результати про структуру графів розкладу твірних.
Теорема 2.2. Граф розкладу твірних [або ] складається з компонент зв’язності, із яких одна є ланцюгом довжиною 3(відповідно вершиною ), а інші компоненти містять рівно один цикл з вершин остаточної множини. Число дорівнює числу циклів у характеристичній перестановці , а довжина кожного циклу в графі дорівнює сумі ваг елементів відповідного циклу в .
У дисертації наведені таблиці, які містять дані про довжину циклів і їх ваги для значень . З теореми випливає важливий
Наслідок 2.1. .
Окремо була розв’язана задача про оптимальне представлення n-вершинних дерев першого рангу, або зірок, в класі А-графів. Перш за все було знайдено величину N максимального коду вершин таких дерев.
Теорема 2.7. В оптимальному представленні вершинної зірки N.
Для доведення цієї теореми було введено спеціальний граф , в якому дві вершини суміжні, якщо їх коди в сумі дають число . В результаті задача зводилася до розв’язання серії рівнянь з параметром такого типу
. (4)
Це рівняння завжди має розв’язок , що безпосередньо перевіряється. Якщо НСД, то це єдиний розв’язок і вершини зірки кодуються всіма непарними числами від 1 до . Якщо НСД, то рівняння (10) при та перетвориться у наступне
. (5)
Розв’язком його є . В цьому випадку граф складаться із компонент. Шляхом вибору множини незалежних вершин отримується той же розв’язок. Послідовно кодуючи центральну вершину зірки, було отримано ще декілька варіантів.
Наслідок 2.2. Число оптимальних кодувань вершинної зірки дорівнює .
Один з варіантів оптимального кодування зірки показано на рис.3.
Рис. 3. Оптимальне представлення зірки для
В цьому ж розділі отримані нові результати про загальне представлення A-графів. Оскільки не всякий граф може бути представлений у класі NA-графів, виникає питання, як ці графи представить у класі A-графів. Якщо , то завжди можна досягти, змінюючи значення , щоб . Позначимо тоді N та . Тоді задача кодування A-графа зводиться до мінімізації N.
В кожному конкретному випадку можна скористуватися універсальним кодуванням, яке годиться для будь-якого графа. Таке кодування існує, і в ньому кожна твірна застосовується тільки один раз. Доведена
Теорема 2.8. Розв’язок задачі про різниці є оптимальним універсальним кодуванням для довільного арифметичного n-вершинного графа.
Доведено, що для представлення у класі A-графів довільної кількості циклів, необхідно скористуватися результатами представлення ланцюгів.
Теорема 2.9. Оптимальним представленням двох n-вершинних непарних циклів є
,
. (6)
Одна з реалізацій теореми показана на рис.4.
Рис. 4. Оптимальне представлення двох циклів для довільного непарного
Загальне представлення графів у вигляді арифметичних графів зводиться до розв’язання задачі ІЗОМОРФІЗМ ГРАФУ. Дійсно, у кожному окремому випадку треба знайти мінімальне N, для якого матриця твірних містить підматрицю, що відповідає даному графу, котрий ізоморфний підграфу N-вершинного повного графа.
У третьомурозділі досліджується новий досить потужний підклас числових графів –модульні графи (M-графи). Повністю описана структура графів з двома твірними, виведено формули для числа компонент зв’язності та цикломатичного числа .
Визначення 7. Модульним графом (М-графом) називається граф , який задається двома множинами: множиною вершин та множиною твірних . У зв’язку з цим вершини суміжні тоді й тільки тоді, коли .
Лема 3.1. Будь-який скінченний граф можна представити у вигляді певного М-графа.
За аналогією з NA-графами М-графи, у яких , називаються натуральними модульними графами (NM-графами).
Матриця твірних , де відповідає довільному повному натуральному модульному графу, який має nвершин.
. (7)
Будь-яка підматриця А визначає деякий NM-граф . Неважко побачити, що кожній твірній відповідає множина ребер кількістю
. (8)
Лема 3.2. NM-граф з одною твірною складається з компонент зв’язності, з яких є ланцюгами з вершин, інші –ланцюгами з вершин.
Розглядаються NM-графи з двома твірними , у яких , наведених на рис.5. У зв’язку з цим доводиться розв’язувати рівняння типу.
. (9)
Рис. 5. Граф с двома твірними
Якщо и – взаємно прості, то , і граф стає гамільтоновим циклом. Якщо ж вони мають спільний дільник, то існує розв’язок для . Тоді граф складається з декількох циклів. Тому справедлива
Лема 3.3. NM-граф з двома твірними та умовою є множиною із циклів довжиною , де НСД.
Випадок зводиться до розглянутого, якщо ввести фіктивну вершину . Тоді , і справедлива
Лема 3.4. NM-граф з двома твірними за умови представляє множину з циклів довжиною та одним ланцюгом довжиною , де НСД.
Якщо граф разом з фіктивною вершиною є гамільтоновим циклом, то видалення останньої приведе до утворення гамільтонового ланцюга.
Доведено декілька теорем про зв’язність натуральних модульних графів.
Теорема 3.1. Нехай задано NM-граф , у якого та . Тоді графів можна представити як NM-граф , у котрого , а .
Наслідок .3. NM-граф з твірними, для яких НСД, незв’язаний.
Теорема 3.4. Для зв’язності NM-графа з вершинами та твірними (), необхідно та достатньо, щоб знайшлась хоча б одна така підмножина твірних , у якій
1) НСД; 2) ; 3) НСД.
Теорема 3.5. Цикломатичне число NM-графа з вершинами та твірними () дорівнює
. (10)
Знайдені умови існування ейлерового циклу в NM-графах.
Теорема 3.6. Для того щоб в зв’язаному NM-графі існував ейлерів цикл, необхідно та достатньо, щоб множина його твірних мала вигляд
. (11)
У зв’язку з цим граф буде однорідним степеня .
Для NM-графів з двома твірними, або 2-графів, повністю досліджена їх структура.
Нехай далі означають тільки додатні лишки. Тоді число вершин такого графа . Нехай –простий ланцюг з вершин, а –простий цикл з вершин. Якщо граф складається з ланцюгів та циклів, то його можна представити у вигляді
, (12)
де –число ланцюгів з кількістю вершин , а –число циклів з кількістю вершин .
Теорема 3.7. Граф , кратний , буде залишатися 2-графом, якщо друга твірна належить відрізку , при цьому
1) для ;
2) для ,
де , .
Теорема 3.8. Граф з однією твірною та числом вершин буде належати класу 2-графів після додавання другої твірної тоді і тільки тоді, коли , при цьому
1) якщо , то ;
2) якщо , то .
Серед довільних графів у яких , можливі два випадки:
Тоді : ,
де , , .
Тоді : ,
де , а
.
У четвертому розділі розглядаються питання застосування числових графів. Ці питання розглядаються у двох аспектах: по-перше, з точки зору оптимального представлення звичайних графів у класі числових, а по-друге, з точки зору побудови на числових графах більш досконалих алгоритмів, ніж ті, які існують для звичайних. Для цього, крім розглянутих і вивчених арифметичних та модульних, вводяться інші числові графи, які мають більш загальне визначення.
Визначення 8. Числовим графом називається вершин-ний граф, представлений двома множинами –множиною вершин та –множиною твірних, функцією суміжності та функцією виключення . Вершина , якщо , а вершини суміжні, якщо .
Розглянемо деякі приклади графів з відомої книги: Т.К. Винцюк. Анализ, распознавание и интерпретация речевых сигналов. –Киев: Наук.думка, 1987. –с. На рис.6 представлено зменшений граф, який використовувався для рівняння розпізнавання сигнала слова.
Рис. 6. Розвернутий граф слова та його представлення у вигляді числового графа
В даному випадку, отримуєм граф з числом вершин , тобто , , а . Таким чином, інформація про граф містить 6 чисел. В цитованій книзі граф за розміром більший, він по вертикалі має 21 вершину, а по горизонталі –вершин, тобто всього –. Числовий граф (з урахуванням доданих фіктивних вершин) буде мати вершин і буде заданий таким чином: , .
Аналогічне представлення допускає і граф, зображений там же (рис. 9.6, стор.185). Числовий граф має такі параметри: , тобто , , .
Розглянемо ще один тип графів звідтіля (рис. 8.1, стор. 159, граф для оцінювання оператора настройки), де функція суміжності не є елементарною. Йому відповідає числовий граф з 80 вершин, який складається з 10 колонок по 8 вершин в кожній. Нумерація вершин починається з нуля до 79, іде знизу вверх. Вершини та будуть фіктивними. Вершина 0 відповідає вершині , а вершина 79 –вершині .
Числовий граф має параметри:
, , .
У багатьох монографіях, присвячених побудові та дослідженню математичних моделей паралельних обчислювальних систем (наприклад, В.В. Воеводин. Математические модели и методы в параллельных процессах . –М.: Наука, 1986. –с.), особливо успішним виявилося використання графів, у тому числі за описом графів систем, що реалізують заданий алгоритм. Відомо, що графи алгоритмів мають такі властивості як симетричність, періодичність або подібність окремих частин. В цьому відношенні числові графи та способи їх представлення можуть принести відчутну користь, чи йдеться про обсяг комп’ютерної пам’яті, чи про швидкодію алгоритмів.
В згаданій книзі (рис.15.1, стор.153) як приклад можна привести решітчасті графи, які легко реалізуються в класі М-графів при використанні лише двох твірних.
Існують алгоритми, графи яких можна задавати решітчастими тривимірними графами. Такий алгоритм використовується при множенні двох прямокутних матриць (у згаданій книзі на рис. 6.2, стор. 70). Реалізація цього графа у класі М-графів наведена на рис.7.
Рис. 7. Реалізація тривимірного решітчатого графа
Тут , , . Фективні вершини, які складають верхній шар, визначаються властивістю ділитися на 4. Подібні тривимірні решітчасті графи часто використовуються при синтезі нових структур систолічних масивів.
У теорії графів існують базові алгоритми, які використовуються в тій чи іншій мірі в більш складних алгоритмах. Це алгоритми пошуку в ширину та глибину. В дисертаційній роботі доведено, що на числових графах, конкретно на арифметичних та модульних, ці алгоритми мають перевагу над графами, які задаються за допомогою списків суміжності, тобто звичайними графами. Якщо для звичайних графів з n вершинами та m ребрами потрібен обсяг необхідної пам’яті порядку , то для числових графів ця оцінка дорівнює , де p – потужність множини твірніх. Враховуючи співвідношення , це стає очевидним.
Ці оцінки були одержані за умови, що для числових графів застосовуються алгоритми, записані для звичайних графів. У дисертації доведено, що на числових графах можна побудувати спеціальні алгоритми, які мають ще більшу перевагу над вищезгаданими алгоритмами. Наводяться два такі алгоритми: для NM-графів з двома твірними та для NM-графів з довільною кількістю твірних. Алгоритми базуються на двох теоремах.
Теорема 4.2. Наступний набір ребер NM-графа з двома твірними визначає остовне дерево: , де , , а також ребра для .
Приклад обходу остовного дерева показано на рис. 8.
Рис.8. NM-граф з та порядок його обходу
Позначимо НСД(.
Теорема 4.3. Наступний набір з типів ребер NM-графа, у якого твірних забезпечують зв’язність, визначає остовне дерево:
1) ;
) ;
) ;
) .
У загальному випадку кожен алгоритм включає три стадії: підготовка початкових даних, сам алгоритм та видача відповіді. Специфіка наведених алгоритмів для числових графів полягає в тому, що для них перші дві стадії відсутні, тобто весь алгоритм зводиться до запису множини ребер остовного дерева. В цьому і криється перевага цих алгоритмів над відповідними алгоритмами для звичайних графів, і це відкриває нові можливості в побудові інших алгоритмів на числових графах.
У дисертаційній роботі отримані важливі наукові результати, які закономірно й послідовно поєднують теоретичні дослідження властивостей числових графів з практичними розробками відносно застосування цих графів для побудови досконалих алгоритмів на графах загального типу.
Основні здобутки роботи полягають в наступному.
. Вперше грунтовно описано структуру однорідних натуральних арифметичних графів. За допомогою спеціально побудованого графа розкладу твірних доведено, що одна множина натуральних арифметичних графів шляхом багаторазового застосування операції радіального гомоморфізму зводиться до іншої. Складено декілька таблиць, що дозволяють відтворити за даними параметрами відповідні однорідні натуральні арифметичні графи.
. Розв’язана задача оптимального представлення дерев першого рангу в класі арифметичних графів. Для цього було побудовано спеціальний двоїстий граф несуміжності, який дозволив звести задачу до розв’язування серії рівнянь у класі лишків за різними модулями, залежними від кількості вершин. Розв’язок цих рівнянь дав можливість перелічити всі можливі оптимальні представлення зазначених дерев.
. Вперше зформульована загальна задача про оптимальне представлення довільних графів у класі арифметичних графів і пов’язана з нею проблема універсального кодування цих графів. Отримані позитивні результати вирішення першої задачі для нових типів графів і доведено, що кожний розв’язок відомої задачі про різниці є оптимальним розв’язком проблеми про універсальне кодування.
. Започатковано дослідження такого підкласу числових графів як модульні графи. Вперше отримані важливі результати про структурні властивості цих графів такі як зв’язність графа, цикломатичне число, про існування гамільтонового та ейлерового циклу. Повністю описана якісна структура множини натуральних модульних графів з двома твірними.
. З практичних міркувань запропоновано загальне, більш розширене визначення числових графів і показано, що багато графів, які застосовуються в галузі розпізнавання образів, математичного моделювання паралельних процесів, теоретичних основ створення інформаційних технологій, можна представити у класі числових графів за розширеним визначенням.
. Вперше доведено, що такі базові алгоритми теорії графів як пошук в глибину, або в ширину при застосуванні їх до модульних графів мають кращі показники відносно обсягу комп’ютерної пам’яті та швидкодії, ніж при застосуванні їх до традиційних графів.
. Доведено, що для числових графів можливо створити такі алгоритми, які на відміну від традиційних алгоритмів зводяться лише до видачі відповіді у вигляді списку. Це продемонстровано на двох алгоритмах пошуку в глибину для зв’язаних модульних графів з двома та з довільною кількістю твірних.
ОСНОВНІ ПОЛОЖЕННЯ ДИСЕРТАЦІЇ ОПУБЛІКОВАНІ В ТАКИХ
ПРАЦЯХ:
. Шулинок И.Э. Структура натуральных арифметических графов с нечетным числом вершин // Оптимизация и ее приложения. –Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины, 1997. –С. 54 – 60.
. Шулинок И.Э. Об одном классе числовых графов // Теория и приложение методов оптимизации. –Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины, 1998. –С. 24 – 29.
. Донец Г.А., Шулинок И.Э. Однородные натуральные арифметические графы. –Киев, 1998. –с. –(Препр. / НАН Украины, Ин-т кибернетики им. В.М. Глушкова, 98-7).
. Шулинок И.Э. О связности натуральных модульных графов // Кибернетика и систем. анализ. –. –№ 5. –С. 50 –53.
. Шулинок И.Э. О связности и цикломатическом числе натуральных модульных графов // Теория оптимальных решений. –Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины, 1999. –С. 51 – 57.
. Шулинок И.Э. Полное описание структуры одного подкласса NM –графов // Теория оптимальных решений. –Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины, 2000. –С. 75 – 81.
. Донец Г.А., Шулинок И.Э. Об оценке сложности алгоритмов для натуральных модульных графов // Теория оптимальных решений. –Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины, 2001. –С. 61 – 68.
. Донец Г.А., Шулинок И.Э. Оптимальное представление однородных деревьев первого ранга в классе А-графов // Комп’ютерна математика. Оптимізація обчислень. – Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины, 2001. –С. 127 – 134.
. Донец Г.А., Шулинок И.Э. О сложности алгоритмов поиска в глубину на модульных графах // Теория оптимальных решений. –Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины, 2002. –С. 105 – 110.
. Шулинок И.Э. О сложности алгоритмов на числовых графах // Прикладная математика: Тез. докл. Междунар. конференции, посв. 65-летию со дня рожд. Б.Н. Пшеничного, 25 –июня, 2002. – Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины, НТУ Украины “КПИ”, ИПСА, 2002. –С. 110 – 111.
Шулінок І.Е. Розв’язання задач оптимального представлення числових графів та дослідження умов побудови на них ефективних алгоритмів. –Рукопис.
Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.01 –теоретичні основи інформатики та кібернетики. –Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, 2004.
Дисертацію присвячено дослідженню числових графів та застосуванню їх властивостей для побудови на них ефективних алгоритмів. Розглядаються такі підкласи числових графів як арифметичні та модульні графи. Доведено, що будь-який граф може бути представлений у класі даних графів. Повністю описані однорідні натуральні арифметичні графи та вираховані таблиці, що дозволяють відтворювати такі графи з заданими параметрами. Однією з основних задач в дисертації є оптимальне представлення довільних графів у класі числових графів. Розв’язано таку задачу для дерев першого рангу, або зірок, для двох циклів довільної довжини, та інших типів графів. Для модульних графів знайдені необхідні та достатні умови зв’язності, виведена формула для обчислення цикломатичного числа, повністю описано структуру натуральних модульних графів з двома твірними. Розроблено нові методи представлення графів у класі числових графів. Показано, що багато графів, які використовуються у різних практичних галузях, можуть бути представлені як числові графи у розширеному трактуванні. Доведено, що базові алгоритми на графах такі як пошук в глибину, або в ширину діють набагато краще, якщо попередньо графи представити як числові. Доведено, що для числових графів можна створити такі алгоритми, дія яких зводиться до видачі готового розв’язку поставленої задачі. Наведено два приклади таких алгоритмів для модульних графів з двома та довільним числом твірних.
Ключові слова: числовий граф, арифметичний граф, модульний граф, зв’язність, цикломатичне число, представлення графів, породжуюча функція, твірна, суміжність, алгоритм, дерево обходу графа, пошук у глибину та ширину.
Шулинок И.Э. Решение задач оптимального представления числовых графов и исследование условий построения на них эффективных алгоритмов. –Рукопись.
Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.01 –теоретические основы информатики и кибернетики. –Институт кибернетики им. В.М. Глушкова НАН Украины, Киев, 2004.
Диссертация посвящена исследованию числовых графов и применению их свойств для создания на них эффективных алгоритмов. Рассматриваются наиболее мощные подклассы числовых графов такие как арифметические и модульные графы. Доказано, что произвольный граф может быть представлен в виде любого из данных графов. Полностью описана структура однородных натуральных арифметических графов, рассчитаны таблицы, позволяющие по заданным параметрам однозначно восстанавливать соответствующие графы. Для новых типов графов, среди которых деревья первого ранга, или звезды, наборы двух циклов произвольной длины и другие, решена задача об оптимальном представлении в классе арифметических графов. Для модульных графов определены характеристические параметры такие как цикломатическое число, гамильтоновость, эйлеровость. Найдены необходимые и достаточные условия связности модульных графов. Полностью описано структуру натуральных модульных графов с двумя образующими. Разработаны новые методы представления графов в виде числовых с учетом более расширенного определения последних. Показано, что многие типичные графы, которые используются как объекты в теории распознавания образов, математического моделирования параллельных процессов, создания информационных технологий, могут быть представлены как числовые. Доказано, что базовые алгоритмы на графах такие как поиск в глубину, или в ширину действуют намного эффективнее, если предварительно эти графы представить в виде числовых. Доказано, что для числовых графов можно создавать такие алгоритмы, действие которых сводится к выдаче готового решения поставленной задачи. Приведены два таких примера в виде алгоритмов поиска в глубину для модульных графов с двумя и больше образующими.
Ключевые слова: числовой граф, арифметический граф, модульный граф, связность, цикломатическое число, представление графов, порождающая функция, образующая смежность, алгоритм, дерево обхода графа, поиск в глубину и ширину.
Shulinok I.E. Numerical graphs optimal representation problems solving and effectiv algorithms construction conditions investigation. –Manuscript.
The dissertation for candidate degree in Physics and Mathematics by specialty 01.05.01 –theoretical fundamentals of informatics and cybernetics. –V.M.Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, 2004.
The dissertation is devoted to numerical graphs investigation and application of their properties for construction above ones efficient algorithms. Numerical graphs subclasses as arithmetical and modular are considered. It is proved, that any graph can be represented in given graph class. Homogeneous natural arithmetical graphs are completely described and tables, which permit to reproduce ones graphs with given parameters are calculated. One of the base problems in the dissertation is an optimal representation of arbitrary graphs in the class of numerical. The problem is solved for the trees with the rank equal 1 or stars, for two cycles arbitrary length and others graph types. For modular graphs the necessary and sufficient conditions of connectivity are found, the formula of cyclomatic number computing is deduced, structure of natural modular graphs with two generatrixes is completely described.
New methods of the graph representation in the class of numerical are developed. It is shown, that lot of graphs, used in different practical areas, can be represented as numerical in extended interpretation. It is proved, that base algorithms above graphs as search in depth or width works much better, if graphs previously represented as numerical. It is proved, that it is possible to create such algorithms for numerical graphs, whose operation is reduced to yielding of a ready to a stated problem. Two examples of such algorithms for modular graphs with 2 and arbitrary number of generatrixes are presented.
Key words: numerical graph, arithmetical graph, modular graph, connectivity, cyclomatic number, graph representation, generative function, generatrix, contiguity, algorithm, graph traversal tree, search in depth and width.
Підп. до друку 11.03.2004. Формат 60х84/16. Папір офс.
Офс. друк. Ум.-друк. арк. 1,16. Ум. фарбо-відб. 1,29.
Обл.-вид. арк. 1,0. Зам. 42. Тираж 100 прим.
Редакційно-видавничий відділ з поліграфічною дільницею
Інституту кібернетики ім. В.М. Глушкова НАН України
МСП, Київ 187, проспект Академіка Глушкова, 40