Аналіз графів з позначеними вершинами

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

НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ

ІНСТИТУТ КІБЕРНЕТИКИ ІМЕНІ В.М.ГЛУШКОВА

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

УДК 519.7

АВТОРЕФЕРАТ

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

кандидата фізико-математичних наук

АНАЛІЗ ГРАФІВ З ПОЗНАЧЕНИМИ ВЕРШИНАМИ

Сапунов Сергій Валерійович

Київ 2007

Дисертацією є рукопис

Робота виконана в Інституті прикладної математики і механіки НАН України

Науковий керівник: кандидат фізико-математичних наук, с.н.с Грунський Ігор Сергійович, Слов'янський державний педагогічний університет, доцент кафедри алгебри

Офіційні опоненти: доктор фізико-математичних наук, професор Капітонова Юлія Володимирівна, Інститут кібернетики імені В.М.Глушкова НАН України, завідуюча відділом теорії цифрових автоматів

кандидат фізико-математичних наук Рисцов Ігор Костянтинович, Національний технічний університет України (КПІ), доцент кафедри математичного моделювання економічних систем

Провідна установа: Київський національний університет імені Тараса Шевченка, факультет кібернетики, кафедра теорії і технології програмування

Захист відбудеться “ 12 ” жовтня 2007 р. о 122 годині на засіданні спеціалізованої вченої ради Д.26.194.02 в Інституті кібернетики ім. В.М.Глушкова НАН України за адресою: 03680 МСП Київ-187, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомитися в науково-технічному архіві Інституту кібернетики ім. В.М.Глушкова НАН України за адресою:

03680 МСП Київ-187, проспект Академіка Глушкова, 40.

Автореферат розісланий “ 11 ” вересня 2007 р.

Вчений секретар спеціалізованої вченої ради В.Ф. Синявський

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

граф вершина розпізнавання

Актуальність теми. Основною проблемою теоретичної кібернетики є проблема взаємодії керуючої та керованої систем (керуючого автомата та його операційного середовища). Біля витоків цієї проблематики стояли В.М. Глушков та К. Шеннон. Взаємодія автомату та середовища найчастіше зображується як процес пересування автомата позначеним графом або лабіринтом середовища. Таке зображення інтенсивно розвивається у працях В.Б. Кудрявцева та керованої ним школи. Автомат, знаходячись у вершині графа, сприймає деяку інформацію про позначки локального околу цієї вершини, а також має можливість змінювати ці позначки і/або ставити додаткові. На підставі сприйнятої інформації автомат пересувається у деяку суміжну вершину.

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

При вирішенні проблеми аналізу графа операційного середовища виділилося кілька підходів. Один з них ґрунтується на тому, що досліджувані графи розглядаються як скінченні ініціальні автомати без виходу, тобто як скінченні орієнтовані графи з позначеними дугами. Такий підхід дозволяє використовувати методи та результати теорії автоматів, що є найстаршою та найбільш розвиненою галуззю теоретичної кібернетики. У рамках цього підходу у працях В.Б. Кудрявцева, Г.Ю. Кудрявцева, І.С. Грунського і Р.М. Олейника знайдено точні верхні оцінки найменшого часу, за який розрізняються два графи, запропоновано методи та алгоритми відрізнення графа-еталону від класу усіх таких графів, у яких кількість вершин не перевищує кількості вершин еталону. Другий підхід виник у межах вивчення проблеми навігації мобільних роботів та ґрунтується на тому, що операційне середовище розглядається як скінченний неорієнтований граф з позначеними кінцями ребер. У працях Г. Дудека, М. Дженкіна, Е. Міліоса та Д. Вілкеса запропоновано методи і алгоритми вирішення таких задач: задачі самолокалізації, тобто відрізнення деякої вершини відомого графа від усіх інших його вершин, і задачі контролю карти, тобто відрізнення графа-еталону від заданого класу графів. Третій підхід ґрунтується на тому, що операційне середовище розглядається як неорієнтований граф з позначеними вершинами. Такі графи виникли спочатку як блок-схеми та схеми програм, а у теперішній час знайшли застосування у задачах навігації роботів. У монографії Ю.В. Капітоновой і О.А. Летичевського з вершинами таких графів природно пов'язані мови у алфавіті позначок та показано, що такі мови регулярні та не містять пустого слова. У роботі І.С. Грунського і О.М. Курганського знайдено критерії зображуваності мов у всілякого виду графах з позначеними вершинами та побудовано ієрархію таких мов.

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

Зв'язок роботи з науковими програмами. Дослідження з проблеми дисертаційної роботи проводилися у відповідності з планами наукових досліджень відділу теорії керуючих систем ІПММ НАН України в рамках тем: №0104u000863 “Алгебраїчні, комбінаторні, логічні та еволюційні методи дослідження дискретних та безперервних систем та їх застосування до задач ідентифікації та керування”, №0204u000771 “Дослідження актуальних проблем моделювання, керування та ідентифікації дискретних систем”.

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

У роботі ставляться і вирішуються задачі знаходження умов, методів та складності:

- розрізнення вершин графів;

- відрізнення однієї вершини графа від усіх інших його вершин;

- розрізнення графів;

- відрізнення графа-еталону від заданого класу графів.

Об'єкт дослідження - процеси порівняння вершин і графів за пов'язаними з вершинами мовами у алфавіті позначок вершин.

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

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

Наукова новизна результатів. У дисертаційній роботі отримано такі нові результати:

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

- знайдено окремий вид графів, названі детермінованими, для яких визначено досяжну лінійну верхню оцінку довжини слова, яке розрізняє вершини;

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

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

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

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

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

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

Всі отримані в роботі результати є новими, достовірними, завершеними і строго доведеними.

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

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

Апробація результатів. Основні результати роботи доповідалися та обговорювалися на:

- XIII Міжнародній конференції “Проблемы теоретической кибернетики” (Казань, 2002);

- Всеукраїнській конференції “Алгебраїчні методи дискретної математики (теорія та методологія)” (Луганськ, 2002);

- V Міжнародному конгресі по математичному моделюванню (Дубна, Росія, 2002);

- V Міжнародній конференції “Дискретные модели в теории управляющих систем” (Ратміно, Росія, 2003);

- VIII Міжнародному семінарі “Дискретная математика и ее приложения” (Москва, 2004);

- VI Міжнародній конференції “Дискретные модели в теории управляющих систем” (Москва, 2004);

- XIV Міжнародній конференції “Проблемы теоретической кибернетики” (Пенза, 2005);

- VII Міжнародній конференції “Дискретные модели в теории управляющих систем” (Москва, 2006);

- IX Міжнародній конференції “Интеллектуальные системы и компьютерные науки” (Москва, 2006);

- семінарах відділу теорії керуючих систем і лабораторії дискретної математики і прикладної алгебри Інституту прикладної математики і механіки НАН України (Донецьк, 2000-2007);

- обласному семінарі “Сучасні інформаційні та комп'ютерні технології” при Донецькому національному університеті (Донецьк, 2004-2006);

- семінарі відділу теорії цифрових автоматів Інституту кібернетики імені В.М.Глушкова НАН України (Київ, 2007).

Публікації. Основні результати дисертації опубліковано в 14 роботах, з яких 5 є статтями у фахових періодичних виданнях, затверджених ВАК України, 9 є тезами доповідей конференцій.

Структура та обсяг дисертації. Дисертаційна робота складається із списку умовних позначень, вступу, трьох розділів, розбитих на підрозділи, висновків та списку використаних джерел. Загальний обсяг дисертації - 150 сторінок. Список використаних джерел включає 66 найменувань і розташований на 8 сторінках.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

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

Експериментом з графом відносно апріорної інформації та мети з використанням засобів назвемо процес, який складається з трьох етапів. Етап 1: побудова тесту на основі з урахуванням . Етап 2: отримання породжених тестом з використанням експериментальних даних . Етап 3: виведення висновків про властивості графа на основі і . Апріорна інформація - це клас графів, до якого належить . Головна відміна експериментів з графами від експериментів з автоматами полягає у методах та засобах отримання експериментальних даних - мобільних агентах (МА), які пересуваються графом, сприймають локальну інформацію про вершини і мають можливість встановлювати в них допоміжні позначки. У подальшому розглядаються діагностичні і контрольні експерименти з графами. Експеримент назвемо діагностичним, якщо апріорі є повністю відомим граф , і МА встановлено у довільну початкову вершину графа, а метою є визначення цієї вершини. Експеримент назвемо контрольним, якщо є повністю відомим граф-еталон , задано клас графів і МА встановлено у початкову вершину довільного графа , а метою є перевірка ізоморфізму графів і . Множину також будемо називати експериментом з графом і казати, що експеримент породжується тестом . Тести, які породжують експерименти, також будемо називати відповідно діагностичними і контрольними. Висотою тесту назвемо найбільшу з довжин його слів, його кратністю - значення , його об'ємом - суму довжин усіх його слів. Операційною кратністю експерименту назвемо величину, яка дорівнює, у залежності від способу проведення експерименту, або кількості екземплярів МА, які використано при отриманні , або кількості встановлень експериментатором МА у початкову вершину досліджуваного графа. Якщо використовується лише один екземпляр МА (одне встановлення), то експеримент назвемо простим. Операційною висотою експерименту назвемо найбільшу з довжин шляхів, що їх проходить МА досліджуваним графом впродовж експерименту.

Дану дисертаційну роботу присвячено створенню засобів і методів теорії експериментів з позначеними графами, за аналогією з теорією експериментів з автоматами. До позначених графів поняття експерименту запроваджено, здається, вперше. У теорії автоматів експерименти досліджуються на базі методів розрізнення вершин графів автоматів та самих таких графів. Такий підхід ініційовано роботами Е. Мура та С.В. Яблонського та розвинуто у роботах А.М. Богомолова, М.П. Василевського, В.Б. Кудрявцева, С.В. Альошина, А.С. Подколзіна, Д.В. Сперанського, І.С. Грунського, І.К. Рисцова, А.Ф. Петренко, Н.В. Євтушенко, Ф. Хєнні та багатьох інших. У результаті було створено струнку й багату теорію експериментів з автоматами, яка послугувала взірцем дослідженням, які проводяться у цій роботі. У дисертації дослідження проводиться за наступним планом: у другому розділі вивчається відрізнимість вершин графів та самих графів, а у третьому на ґрунті результатів попереднього розділу досліджуються діагностичні і контрольні експерименти з позначеними графами.

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

У підрозділі 2.1 визначається базове для усієї роботи відношення - відношення

невідрізнимості вершин: вершини невідрізнимі, тобто , якщо . Позначимо як відношення -невідрізнимості: , якщо , де позначає

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

Теорема 2.1. Нехай є позначеним орграфом, тоді для деякого .

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

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

Теорема 2.2. Нехай є D-орграфом, тоді для деякого , і ця оцінка досяжна.

Ця теорема вказує на те, що оцінка довжини найкоротшого слова, яке розрізнює дві вершини D-орграфа, співпадає з оцінкою довжини найкоротшого слова, яке розрізнює два стани скінченного всюди визначеного детермінованого автомата Мура. Для побудови відношення модифіковано відомий у теорії автоматів алгоритм Мура із збереженням його складності.

У підрозділі 2.3 досліджено важливий окремий випадок D-орграфів, який виникає у прикладних задачах, а саме, прості D-орграфи для яких виконуються наступні умови: 1) вони симетричні і розглядаються як неорієнтовані; 2) для будь-якої вершини такого графа та довільних вершин з випливає, що (тут ). Такі графи назвемо сильно детермінованими або SD-графами.

З метою аналізу структури SD-графа введемо відношення покриття вершин : вершина покриває вершину , тобто , якщо . Показно, що, на відміну від D-орграфів і часткових детермінованих скінченних автоматів Мілі, вершина SD-графа покривається об'єднанням інших вершин цього ж графа точно тоді, коли вона покривається однією з вершин цього об'єднання (теорема 2.3). Ця властивість відіграє важливу роль при побудові діагностичних експериментів. Аналогічно визначається відношення : , якщо . Показано, що послідовність відношень монотонно спадає.

Теорема 2.4. Нехай є D-орграфом, тоді для деякого .

Показано, що для побудови відношення на множині вершин довільного SD-графа достатньо кроків.

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

Теорема 2.5. Якщо , то .

З цієї теореми випливає: якщо деяка вершина компоненти зв'язності SD-графа максимальна, то й усі вершини цієї компоненти максимальні. Таким чином, кожному SD-графа можна поставити у відповідність його максимальний підграф , де - звуження на множину . Граф, який є ізоморфним до свого максимального підграфа, також назвемо максимальним. Очевидно, що кожен зв'язний SD-граф є максимальним.

Показано, що для будь-яких різних вершин та будь-якого зв'язного зведеного SD-графа довжина найкоротшого слова з не перевищує (теорема 2.6). Цю властивість використано у розділі 3 при побудові діагностичних експериментів з SD-графами.

Теорема 2.7. для будь-якого SD-графа.

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

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

висотою. Ідентифікатор кратності 1 назвемо простим. Усякий ідентифікатор можна зобразити як об'єднання двох множин і . Ідентифікатор назвемо позитивним, якщо , і негативним, якщо .

Теорема 2.8. Наступні твердження є еквівалентні: 1) існує ідентифікатор вершини ; 2) існує ідентифікатор вершини висоти не більшої за і кратності не більшої за ; 3) .

Наслідок 2.1. Для будь-якої вершини зведеного позначеного орграфа існує кратний ідентифікатор висоти не більшої за і кратності не більшої за , де і .

Теорема 2.9. 1) Простий позитивний ідентифікатор вершини існує точно тоді, коли . 2) Простий негативний ідентифікатор вершини існує точно тоді, коли .

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

Теорема 2.10. Для будь-якої вершини зведеного максимального SD-графа існує простий позитивний ідентифікатор висоти (, якщо зведений).

З теореми 2.10 випливає, що кратний позитивний ідентифікатор вершини SD-графа існує точно тоді, коли існує простий позитивний ідентифікатор цієї вершини (наслідок 2.2).

Показано, якщо є позитивним ідентифікатором вершини SD-графа і , де , , то множина слів є позитивним ідентифікатором вершини (твердження 2.4). Для довільних позначених орграфів і D-орграфів аналогічне твердження у загальному випадку не виконується.

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

Ідентифікатор вершини SD-графа назвемо редукованим, якщо ніяке з його слів не містить підслів-паліндромів і не є власним початковим відрізком іншого його слова. Показано, що кожному ідентифікатору вершини SD-графа відповідає єдиний редукований ідентифікатор (теорема 2.14) та запропоновано процедуру редукції. Показано далі, що множина мінімальних редукованих ідентифікаторів у загальному випадку теж нескінченна (теорема 2.15).

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

Теорема 2.15. Якщо множина є мінімальним ідентифікатором вершини SD-графа, то будь-який обхід кореневого дерева також є ідентифікатором цієї вершин.

Таким чином, якщо для двох множин слів та виконується рівність і одна з цих множин є ідентифікатором деякої вершини SD-графа , то інша множина також є ідентифікатором цієї вершини. Показано, що для ідентифікаторів вершин довільних позначених орграфів та початкових ідентифікаторів станів скінченних автоматів теорема, аналогічна теоремі 2.15, не виконується.

У підрозділі 2.5 вводяться відношення невідрізнимості і слабкої невідрізнимості на множині усіх позначених графів над алфавітом позначок . Знайдено характеризації цих відношень. Нехай . Графи і назвемо невідрізнимими й писатимемо , якщо . Графи і назвемо слабко невідрізнимими й писатимемо , якщо . Ясно, що . Показано, що на множині , а на підмножині усіх зв'язних SD-графів (теорема 2.16).

Твердження 2.4. Графи і невідрізнимі точно тоді, коли у кожному класі невідрізнимості графа знаходяться вершини обох графів.

Показано, що складність перевірки невідрізнимості графів становить , де .

Запропоновано метод налаштовування графа пар і з його допомогою доведено наступне

Твердження 2.5. Графи і слабко невідрізнимі точно тоді, коли жодна вершина налаштованого графа пар для графа не містить порожніх компонент.

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

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

Теорема 2.17. Нехай є довільним D-орграфом, а є класом усіх D-орграфів з , невідрізнимих від , тоді граф є гомоморфним образом будь-якого графа з класу та єдиним (з точністю до ізоморфізму) графом з найменшою кількістю вершин у цьому класі.

Показано, що в класі всіх графів, невідрізнимих від деякого D-графа , ця теорема не виконується.

Нехай є класом усіх зведених SD-графів з , які слабко невідрізнимі від зведеного SD-графа .

Теорема 2.18. Клас частково упорядкований за відношенням ізоморфного вкладення позначених графів і є його найменшим елементом.

Умови скінченності класу дає наступна

Теорема 2.19. Наступні твердження є еквівалентні: (1) є циклічним графом; (2) будь-який граф з є циклічним графом; (3) клас є нескінченним.

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

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

У підрозділі 3.1 докладно розглядаються усі три етапи діагностичного експерименту.

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

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

Теорема 3.1. Множина слів, де - ідентифікатор вершини , є діагностичним тестом для графа .

Показано, що для довільного позначеного графа складність побудови тесту дорівнює ( для D-графа), його кратність не перевищує , його висота не перевищує ( для D-графа), а його об'єм дорівнює ( для SD-графа).

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

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

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

Нехай . Базисом досяжності графа назвемо довільну множину слів , яке задовольняє умовам: 1) ; 2) якщо , , то ; 3) нехай , где , тоді , . Базисом відрізнимості графа назвемо об'єднання ідентифікаторів усіх його вершин.

Теорема 3.3. Нехай і - довільні базиси досяжності і відрізнимості графа . Тоді: 1) є контрольним тестом для будь-якого дерева і підкласу усіх дерев з ; 2) є контрольним тестом для будь-якого дерева і та не є таким для будь-якого циклічного графа ; 3) є контрольний тест для будь-якого графа і .

Метод побудови контрольного тесту у пункті 3 цієї теореми використовує ідею відомого в теорії автоматів методу Василевського. Показано, що складність побудови дорівнює , його кратність не перевищує , його висота не перевищує , а об'єм дорівнює .

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

Далі запропоновано стратегію проведення контрольного експерименту, яка відрізняється від наведеної вище та ґрунтується на наступному твердженні

Теорема 3.4. Будь-який обхід дерева є контрольним тестом для і .

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

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

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

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

Теорема 3.5. 1) Графи ізоморфні точно тоді, коли . 2) Дерева ізоморфні точно тоді, коли . 3) Якщо граф є циклічним, то для будь-якого існує дерево таке, що .

Наслідок 3.1. 1) є контрольним тестом для будь-якого графа і класу . 2) є контрольним тестом для дерева і класу . 3) Для циклічного графа і класу множина за будь-якого не є контрольним тестом.

Твердження 3 наслідку 3.1 очевидно рівносильне наступному: ніяка скінчена підмножина множини не є контрольним тестом для циклічного графа і класу .

Позначимо як множину усіх слів таких, що . Показано, що будь-які графи ізоморфні точно тоді, коли (теорема 3.6), але не є контрольним тестом для графа і класу (наслідок 3.2).

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

Пару скінченних множин слів назвемо визначальною парою графа , якщо водночас виконуються умови: 1) і ; 2) для будь-якого графа з і випливає .

Позначимо як довільну максимальну за включенням підмножину множини , яка задовольняє умовам: 1) якщо , то і , де ; 2) якщо слово , то слово . З кожним графом пов'яжемо пару множин слів . Зрозуміло, що таких пар може бути декілька, оскільки множини і залежать від

вибору базису досяжності графа .

Теорема 3.7. Для будь-якого базису досяжності графа пара є визначальною.

Далі у підрозділі 3.3 узагальнюється поняття контрольного експерименту. Нехай МА перед початком експерименту позначає унікальною позначкою (маркером) початкову вершину досліджуваного графа , тобто при відвідуванні цієї вершини МА має можливість відрізнити її від усіх інших вершин за наявністю у ній маркеру. Узагальнення контрольного експерименту полягає у тому, що за наявності маркеру МА, окрім перевірки належності слова до , може здійснити перевірку і перевірку у протилежному випадку. Показано, що будь-яка визначальна пара є контрольним тестом для графа і класу (твердження 3.1).

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

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

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

Нехай є парою скінчених множин слів у алфавіті , де , і - фіксований символ. Позначимо як клас усіх зв'язних ініціальних SD-графів над алфавітом позначок . Під характеризацією пари розумітимемо вирішення наступних задач: 1) визначити чи існує граф такий, що пара є для нього визначальною; 2) визначити, чи є пара визначальною для фіксованого графа .

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

ВИСНОВКИ

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

У роботі отримано такі результати:

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

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

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

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

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

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

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

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

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ АВТОРА ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Сапунов С.В. Эквивалентность отмеченных графов // Труды института прикладной математики и механики. - 2002. - Т. 7. - С. 162-167.

2. Сапунов С.В. Контроль детерминированных графов // Труды института прикладной математики и механики. - 2003. - Т. 8. - С. 106-110.

3. Сапунов С.В. Построение контрольных экспериментов для неориентированных графов // Вісник ДонНУ, серія А: Природничі науки. - 2003. - В. 1. - С. 351-354.

4. Сапунов С.В. Структура класса неотличимости неориентированных помеченных графов // Труды института прикладной математики и механики. - 2005. - Т. 10. - С. 166-172.

5. Сапунов С.В. Проверка соответствия карты при навигации мобильных роботов // Искусственный интеллект. - 2006. - № 3 - С. 677-685.

6. Грунский И.С, Сапунов С.В. О контроле графов с отмеченными вершинами // Тезисы докладов XIII международной конференции “Проблемы теоретической кибернетики” (Казань, 27-31 мая 2002 г.). - М.: Изд-во центра приклад. исслед. при мех.-мат. ф-те МГУ им. М.В. Ломоносова, 2002. - С. 52.

7. Сапунов С.В. Отличимость вершин графа моделирующего информационную среду // Всеукраїнська конференція “Алгебраїчні методи дискретної математики (теорія та методологія)” в ЛДПУ iм. Т.Г. Шевченка (Луганськ, 23-27 вересня 2002 р.). - Луганськ: Alma Mater, 2002. - С. 81-82.

8. Grunsky I.S., Sapunov S.V. Map validation of robot environments // V international congress on mathematical modeling: Book of abstracts (September 30 - October 6, 2002). - M.: Изд-во мех.-мат. ф-та МГУ им. М.В. Ломоносова, 2002. - С. 93.

9. Грунский И.С, Сапунов С.В. О контроле детерминированных графов // Труды V международной конференции “Дискретные модели в теории управляющих систем” (Ратмино, 26-29 мая 2003 г.). - М.: Изд. отдел ф-та ВМиК МГУ им. М.В. Ломоносова, 2003. - С. 27-29.

10. Сапунов С.В. О неотличимости неориентированных графов с помеченными вершинами // Труды VI международной конференции “Дискретные модели в теории управляющих систем” (Москва, 7-11 декабря 2004 г.). - М.: Изд. отдел ф-та ВМиК МГУ им. М.В. Ломоносова, 2004. - С. 209-211.

11. Сапунов С.В. Структура класса неотличимости неориентированных помеченных графов // Материалы VIII международного семинара “Дискретная математика и ее приложения” (2-6 февраля 2004 г.). - М.: Изд-во мех.-мат. ф-та МГУ им. М.В. Ломоносова, 2004. - С. 304-307.

12. Сапунов С.В. О контроле помеченных графов при неизвестной верхней оценке числа вершин // Тезисы докладов XIV международной конференции “Проблемы теоретической кибернетики” (Пенза, 23-28 мая 2005 г.). - М.: Изд-во мех.-мат. ф-та МГУ им. М.В. Ломоносова, 2005. - С. 138.

13. Сапунов С.В. Контрольные эксперименты с помеченными графами при неизвестной верхней оценке числа вершин // Труды VII международной конференции “Дискретные модели в теории управляющих систем” (Покровское, 4-6 марта 2006 г.). - М.: МАКС Пресс, 2006. - С. 325-331.

14. Сапунов С.В. Анализ графов с помеченными вершинами // Материалы IX международной конференции “Интеллектуальные системы и компьютерные науки” (Москва, 23-27 октября 2006 г.). - М.: Изд-во мех.-мат. ф-та МГУ им. М.В. Ломоносова, 2006. - С. 233-234.

АНОТАЦІЯ

Сапунов С.В. Аналіз графів з позначеними вершинами. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.01 - теоретичні основи інформатики та кібернетики. - Інститут кібернетики імені В.М.Глушкова НАН України, Київ, 2007.

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

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

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

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

АННОТАЦИЯ

Сапунов С.В. Анализ графов с помеченными вершинами. - Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.01 - теоретические основы информатики и кибернетики. - Институт кибернетики имени В.М.Глушкова НАН Украины, Киев, 2007.

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

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

Впервые введено понятие эксперимента с графом. Экспериментом с графом относительно априорной информации и цели с использованием средств назовем процесс, состоящий из трех этапов. Этап 1: построение теста , являющегося множеством слов в алфавите меток, на основе с учетом . Этап 2: получение порождаемых тестом с использованием экспериментальных данных . Этап 3: вывод заключений о свойствах графа на основе и . Априорная информация - это класс графов, к которому принадлежит . Средства - это перемещающиеся по графу мобильные агенты, воспринимающие локальную информацию о вершинах и имеющие возможность ставить в них дополнительные стираемые/нестираемые метки. Рассмотрены два вида экспериментов: диагностические и контрольные. Эксперимент назовем диагностическим, если априори полностью известен граф , и мобильный агент установлен в произвольную начальную вершину этого графа, а целью является определение этой вершины. Эксперимент назовем контрольным, если полностью известен инициальный граф-эталон , задан класс графов и мобильный агент установлен в начальную вершину произвольного графа , а целью является проверка .

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

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

ANNOTATION

Sapunov S.V. The analysis of vertex-labeled graphs. - Manuscript.

Thesis for a candidate's degree of physics and mathematics by speciality 01.05.01 - theoretical basis of informatics and cybernetics. - V.M. Glushkov institute of cybernetics, National Academy of Science of Ukraine, Kyiv, 2007.

The thesis is dedicated to the problem of vertex-labeled graph analysis, particularly the problem of existence and construction methods for distinguishing and checking experiments with such graphs conducted by an automaton walking on graph and reading vertex labels.

Analysis methods for languages over the alphabet of labels associated with graphs and their vertices are developed. Relation of covering one vertex with another and vertex equivalence relation induced by vertex languages comparison are proposed. An effective method of checking these relations is developed. An exponential upper bound of vertex distinguishing word length is obtained. A particular kind of graphs, the so-called deterministic graphs, with attainable linear upper bound of vertex distinguishing word length is discovered. A finite subset of words over vertex labels alphabet distinguishing a given vertex from others called vertex identifier is proposed. Existence conditions and complexity estimations for vertex identifiers are discovered and construction methods are developed. Relations of equivalence and weak equivalence of graphs induced by their languages comparison are suggested. An effective characterization of these relations is obtained. Their structure and power is investigated and extremal elements of equivalence classes are discovered.

A new concept of experiments with graphs, where a mobile agent checks if given sets of words are a part of graph's language, is introduced. Two important particular cases are investigated: distinguishing experiments detecting the vertex where the mobile agent started walking and checking experiments that discriminate etalon graph from a given class of graphs. Construction and realization methods for distinguishing experiments based on all vertices identifiers construction are proposed. Upper bounds of complexity of such experiments are estimated to be exponential in general and polynomial for deterministic graphs. Construction and realization methods for checking experiment for an initial deterministic etalon graph with respect to a finite class of initial deterministic graphs with the number of vertices not surpassing the number of etalon's vertices and to the class of all deterministic graphs. The former method is grounded on a substantial modification of Vasilevsky's method for finite automata. For the latter case a representation of an etalon by a special pair of finite sets of words, which is analogous to defining relation systems for finite automata, is proposed. Polynomial upper bounds of these experiments complexity are discovered.

...