Алгебраїчна характеристика класу графових перетворень

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2011
Hauptverfasser:	Редько, І.В., Снігур, Н.М.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2011
Schriftenreihe:	Системні дослідження та інформаційні технології
Schlagworte:	Математичні методи, моделі, проблеми і технології дослідження складних систем
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/50103
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Алгебраїчна характеристика класу графових перетворень / І.В. Редько, Н.М. Снігур // Систем. дослідж. та інформ. технології. — 2011. — № 2. — С. 104-114. — Бібліогр.: 22 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-50103
record_format	dspace
spelling	irk-123456789-501032013-10-05T03:09:34Z Алгебраїчна характеристика класу графових перетворень Редько, І.В. Снігур, Н.М. Математичні методи, моделі, проблеми і технології дослідження складних систем Изучены примитивные программные алгебры многоместных функций над множеством конечных графов. Дана алгебраическая характеристика класса графовых преобразователей. Изложенные результаты являются дополнением результатов, полученных ранее для векторных, матричных, реляционных и табличных функций. Вивчено примітивні програмні алгебри багатомісних функцій над множиною скінчених графів. Дано алгебраїчну характеристику класу графових перетво-рювачів. Викладені результати є доповненням результатів, отриманих раніше для векторних, матричних, реляційних та табличних функцій. Primitive program algebras of multiplace functions at a set of finite graphs were studied. Аn algebraic characteristic of the graph modifier class is given. The presented results are additional for the results previously obtained for vector, matrix, relational and table functions. 2011 Article Алгебраїчна характеристика класу графових перетворень / І.В. Редько, Н.М. Снігур // Систем. дослідж. та інформ. технології. — 2011. — № 2. — С. 104-114. — Бібліогр.: 22 назв. — укр. 1681–6048 http://dspace.nbuv.gov.ua/handle/123456789/50103 681.3.06 uk Системні дослідження та інформаційні технології Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Математичні методи, моделі, проблеми і технології дослідження складних систем Математичні методи, моделі, проблеми і технології дослідження складних систем
spellingShingle	Математичні методи, моделі, проблеми і технології дослідження складних систем Математичні методи, моделі, проблеми і технології дослідження складних систем Редько, І.В. Снігур, Н.М. Алгебраїчна характеристика класу графових перетворень Системні дослідження та інформаційні технології
description	Изучены примитивные программные алгебры многоместных функций над множеством конечных графов. Дана алгебраическая характеристика класса графовых преобразователей. Изложенные результаты являются дополнением результатов, полученных ранее для векторных, матричных, реляционных и табличных функций.
format	Article
author	Редько, І.В. Снігур, Н.М.
author_facet	Редько, І.В. Снігур, Н.М.
author_sort	Редько, І.В.
title	Алгебраїчна характеристика класу графових перетворень
title_short	Алгебраїчна характеристика класу графових перетворень
title_full	Алгебраїчна характеристика класу графових перетворень
title_fullStr	Алгебраїчна характеристика класу графових перетворень
title_full_unstemmed	Алгебраїчна характеристика класу графових перетворень
title_sort	алгебраїчна характеристика класу графових перетворень
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
publishDate	2011
topic_facet	Математичні методи, моделі, проблеми і технології дослідження складних систем
url	http://dspace.nbuv.gov.ua/handle/123456789/50103
citation_txt	Алгебраїчна характеристика класу графових перетворень / І.В. Редько, Н.М. Снігур // Систем. дослідж. та інформ. технології. — 2011. — № 2. — С. 104-114. — Бібліогр.: 22 назв. — укр.
series	Системні дослідження та інформаційні технології
work_keys_str_mv	AT redʹkoív algebraíčnaharakteristikaklasugrafovihperetvorenʹ AT snígurnm algebraíčnaharakteristikaklasugrafovihperetvorenʹ
first_indexed	2025-07-04T11:34:41Z
last_indexed	2025-07-04T11:34:41Z
_version_	1836716006905479168
fulltext	© І.В. Редько, Н.М. Снігур, 2011 104 ISSN 1681–6048 System Research & Information Technologies, 2011, № 2 TIДC МАТЕМАТИЧНІ МЕТОДИ, МОДЕЛІ, ПРОБЛЕМИ І ТЕХНОЛОГІЇ ДОСЛІДЖЕННЯ СКЛАДНИХ СИСТЕМ УДК 681.3.06 АЛГЕБРАЇЧНА ХАРАКТЕРИСТИКА КЛАСУ ГРАФОВИХ ПЕРЕТВОРЕНЬ І.В. РЕДЬКО, Н.М. СНІГУР Вивчено примітивні програмні алгебри багатомісних функцій над множиною скінчених графів. Дано алгебраїчну характеристику класу графових перетво- рювачів. Викладені результати є доповненням результатів, отриманих раніше для векторних, матричних, реляційних та табличних функцій. ВСТУП Робота присвячена дослідженню класу обчислюваних функцій на множині графів. Обчислюваність вводиться згідно з нумераційним підходом [1]. Вибір графових структур обумовлений їх важливістю та популярністю в теоретичному та прикладному програмуванні [2–10]. Зокрема в роботах [2, 3] визначено та досліджено поняття обчислювальної функції над скінченими графами (комплексами), робота [4] присвячена вивченню граф- схем алгоритмів, [5–8] — ізоморфізму графів, [9] — питанням абстрактної обчислюваності в різних областях, [10] — графовим засобам специфікації програм. При цьому треба зазначити, що практично всі згадані дослідження акцентують увагу безпосередньо на графи, не розглядаючи задачі огляду класу обчислюваних функцій над графами (класу графових перетворювачів). Мета роботи — надати алгебраїчну характеристику класу обчислю- вальних функцій над графами. В якості інструменту дослідження обрано апарат примітивних програмних алгебр (ППА). Доцільність цього вибору обгрунтована результатами, отриманими, наприклад, в [11–18]. Основну увагу приділено пошуку породжуючої множини для такої ППА. Отримані в роботі результати доповнюють результати для векторних, матричних, реляційних та табличних функцій [11–14]. Усі використані та невизначені в роботі поняття та позначення розуміються в сенсі [14]. БАЗОВІ ВИЗНАЧЕННЯ, ПОНЯТТЯ, РЕЗУЛЬТАТИ Носій ППА можуть складати або функції, залежні від змінних [11], або n -арні функції і предикати [12, 14]. Далі ППА розуміються в другому сенсі, тому під функціями (предикатами) мається на увазі n -арні функції Алгебраїчна характеристика класу графових перетворень Системні дослідження та інформаційні технології, 2011, № 2 105 (предикати) для …2,1,=n , хоча при їх позначенні перевага віддається не операторній, а термальній формі запису, зважаючи на її компактність [1]. Сигнатуру ППА (позначатимемо Ω ) складають операції суперпозиції, розгалуження та 1)( +n -арного циклування, що являють собою адекватні уточнення стандартних структур управління більшості мов програмування. Для зручності викладення матеріалу та його сприйняття корисно нагадати формальні визначення цих операцій [13]. 1. Під суперпозицією розуміється 1+m -арна операція, позначувана ,1+mS ...,3,2,1=m , яка будь-якому кортежу ,,...,, 1 >< mffϕ де ϕ — m -арна функція; арність функцій mifi ,...,1, = однакова й рівна, наприклад k , ста- вить у відповідність нову k-арну функцію ,ψ що задається як: ),),...,(,...),,...,((),...,( 1111 >><><<≅>< kmkk xxfxxfxx ϕψ для всіх >< kxx ,...,1 . 2. Розгалуження (параметричне) являє собою 1)( +m -арну операцію 1+♦m β , …3,2,=m , β — довільна, але фіксована унарна m -значна функція з множиною значень },...,2,1{ m , яка кортежу функцій 〉〈 mffh ,,, 1 … однієї арності, наприклад ,s ставить в залежності від параметра β у відповідність нову s -арну функцію g таку, що ≅>< ),..,( 1 sxxg ),,..,( 1 ><≅ si xxf якщо ixxh s =>< )),..,(( 1β , }.,...,1{ mi∈ 3. Нарешті циклування являє собою 1)( +n -арну операцію gffp n n →〉〈+ ,,,:* 1 1)( … , …1,2,=n , де p — предикат, а gfi , — функції, причому арність p , if , g дорівнює n . Значення ),,( 1 nxxg … покладається рівним першій компоненті першого кортежу послідовності кортежів >< n ii yy ,...,{ 1 , },1,0= …i , де j j xy ≡0 , ),,( 1 1 n iij j i yyfy …≡+ , ,0,1,= …i nj 1,= , для якого (позначимо його, наприклад, >< n kk yy ,,1 … ) falseyyp n kk =),,( 1 >< … . Тобто, 1 1 =),,( kn yxxg >< … . Якщо такого кортежу в послідовності не існує, то ),,( 1 nxxg … вважається невизначеним. Відзначимо, що операція 1)(* +n , по суті, є досить близькою до операції циклування, що досліджувалась у роботах [11–15, 17]. Очевидно, що ),,,,(= 2 1)( n n nn IIfpfp …+ , де арності p та f дорівнюють n . Звідси випливає, що всі твердження, отримані в [11–14] у межах попереднього визначення ППА, зберігаються при переході до зазначеного. При термальному записі операцій з Ω будемо вказувати явно лише ті змінні, значення яких будуть суттєво використовуватись. Зокрема, для циклування будемо використовувати записи вигляду 〉〈 ),,(,),,,(),,( 1 1 1 1 11 1 1 m mk m mk myy n zzfzzfxxp ………… … вказуючи явно лише ті змінні, значення яких будуть змінюватись. При цьому функція ),,( 1 i ik i i zzf … «керує» зміною значення змінної iy , а змінна І.В. Редько, Н.М. Снігур ISSN 1681–6048 System Research & Information Technologies, 2011, № 2 106 1y вважається «вихідною». Відновлення операторного запису при цьому очевидно. Ω складає сигнатуру ППА графових перетворювачів. Для того, щоб розглянути її носій — клас графових перетворювачів, попередньо звернемось до поняття графу. Тут будемо дотримуватись термінології, прийнятої в [13]. Під (скінченим) орієнтованим графом g розуміємо пару >< EV , , де V — деяка злічена непуста множина об’єктів, а E — бінарне відношення на .V Стандартна інтерпретація цих об’єктів V та E у цьому визначенні така: V — множина вершин графу, E — множина його дуг. Надалі вершини графу позначатимемо латинськими літерами wvu ,, , а дуги — літерами rpe ,, , можливо з індексами, …… ,,, 11 ev . У випадку необхідності явно вказати вершини дуги та її напрям, використовуватимемо позначення >< uv, , розуміючи, що дуга направлена від v до u . Вершини v та u дуги ><≡ uve , будемо називати суміжними. При цьому дуга e вважається додатно інцидентною вершині u та від’ємно інцидентною вершині .v Кількість дуг, що додатно (від’ємно) інцидентні вершині w називаються додатним (від’ємним) ступенем w і позначаються )(wg +δ ( )(wg −δ ). Вершину v графу ><≡ EVg , називатимемо від’ємно (додатно) інцидентною (від’ємною (додатною)) до вершини w того ж графу, якщо ),( , EwvEvw ∈><∈>< . Прагматика дослідження, частиною якого є ця робота спонукає до виділення серед усьго розмаїття графів таких, в яких E є рефлексивним. Така вимога є досить природною під час розгляду різного роду складних об’єктів, щодо яких коректно говорити про підлеглість їх складових. Тому надалі будемо розглядати тільки такі графи. Їх множину позначимо .G Під функціями далі розуміємо часткові функції з аргументами і значеннями із ,G а під предикатами — часткові предикати на .G Обчислюваність на G вводиться як нумераційна обчислюваність, за допомогою арифметичної функції, що представляє цю функцію на G у зафіксованій нумерації множини G [19]. Існування такої нумерації випливає зі зліченості множини .V Будь-яку частково-рекурсивну багатомістну функцію, або будь-який частково-рекурсивний багатомісний предикат (чр-функція, чр-предикат) будемо називати також графовим перетворювачем. Через чр GA позначимо ППА, носій якої складають графові перетво- рювачі на .G Породжуючу множину алгебри чр GA назвемо її повною системою (ПС); ПС ППА — n mI базисом, якщо будь-яка її підсистема, що отримується видаленням будь-якого предиката, або будь-якої функції, відмінної від селекторної, вже не буде повною. У силу зліченності множини V не буде суттєвим обмеженням, якщо покласти .= NV При цьому на множині вершин графу вводиться цілком природна впорядкованість. Алгебраїчна характеристика класу графових перетворень Системні дослідження та інформаційні технології, 2011, № 2 107 Отримані нижче результати спираються на теореми про ізоморфізм та про базис ППА [3, 5]. У контексті цієї роботи їх можна сформулювати наступним чином. Теорема (про ізоморфізм ППА). Бієктивне відображення →чр: GAαθ чр NA→ , яке співставляє кожній функції на G арифметичну функцію, яка її представляє (у заданій нумерації Gα ) є ізоморфізмом ППА чр GA на ППА чр NA , де чр NA — ППА чр-функцій та предикатів на .N Теорема про базис ППА. Існує n mI -базис алгебри чр GA , що складається з точністю до селекторних функцій з двох функцій та одного предиката. Під час знаходження повної системи алгебри чр GA корисними будуть такі визначення та пов’язані з ними результати. Функція f -арності n зберігає множину ∅≠⊂ LGL , , якщо LLLf n ⊆×× )( … [4, 21]. Нехай VG 2: на →β , де V — множина вершин (у роботі NV ≡ ), а B2 — множина всіх скінчених підмножин .B Будемо казати, що функція f -арності n β — зберігає денотати, якщо існує скінчена множина VV f ⊂ така, що для будь-якого ∈>< nxx ,,1 … fdom∈ виконується .)()),,(( 1= 1 fi n i n Vxxxf ∪⊆>< ββ ∪… Легко переконатись, що визначені властивості графових перетво- рювачів зберігаються в сигнатурі Ω . Таким чином, є справедливими такі необхідні умови повноти для ПС .чр GA Твердження 1. Будь-яка повна система алгебри чр GA для будь-якої множини L ( ∅≠⊂ LL ,G ) містить хочa б одну функцію, яка не зберігає цю множину для довільної множини L ( ∅≠⊂ LL ,G ). Твердження 2. Будь-яка повна система алгебри чр GA містить хоча б од- ну функцію, що не є β -зберігаючою денотати. Під час побудови у ППА зручними є логічні зв’язки для предикатів; вони легко моделюються в ППА за допомогою всюди істинного та всюди хибного предикатів ( Tp , Fp ), наприклад: =∨ ),,(),,( 11 mn yyqxxp …… ,))),(),,,((),(),,,(( F111T1 pxpyyqxpxxp Tmn …… ◊◊= =),,(&),,( 11 mn yyqxxp …… ,))(),),(),,,((),,,(( 1FF111 xppxpyyqxxp Tmn …… ◊◊= І.В. Редько, Н.М. Снігур ISSN 1681–6048 System Research & Information Technologies, 2011, № 2 108 )).(,),,,((=),,( 1F11 xppxxpxxp Tnn …… ◊¬ Позначатимемо через Ω][σ замикання множини графових перетво- рювачів σ операціями сукупності Ω . ППА ЧР-ФУНКЦІЙ І ЧР-ПРЕДИКАТІВ НА МНОЖИНІ СКІНЧЕННИХ ОРІЄНТОВАНИХ ГРАФІВ Із зазначеного вище є цілком очевидним, що будь-який граф g можна ефективно представити деякою матрицею gA , причому ефективність такого представлення прямо витікає з її побудови. Покладемо )(max ig vn −≡ δ ; k — кількість вершин ;g gs — відсортований «по зростанню» вектор вершин g — >< kvv ,...,1 , а ><≡− piig vvvs ,...,)( 1 ( ><≡+ piig vvvs ,...,)( 1 ), де )(vp g −= δ ( ))(vp g += δ — відсортований «по зростанню» вектор усіх вершин графу g , які є від’ємно (додатно) інцидентними вершині .v Матриця gA розмірності ( kn ×+ )1( ) може бути представлена як результат виконання такої ітеративної процедури. i -й рядок матриці gA може бути побудований таким чином: ][:1 isa gi = ; ⎪⎩ ⎪ ⎨ ⎧ <−< ≤−−≡ − njp pjjissa gg ij 1,0 1],1])[[( , ;,1 ki = ;][ ig vis ≡ .])[( kig vkvs ≡− Зокрема, у такому представленні порожньому графу, очевидно, відповідає порожня матриця ∆ [14, 21], а графу, що являє собою сукупність непов’язаних між собою вершин із петлями, тобто графу ><≡ EVg , , де E — таке відношення, що ,, vEuv ⇔>∈< uvVu =∈ & , відповідає матриця- стовпчик з перерахованими «по зростанню» вершинами графу. si i g v v A 1 = . Використовуватимемо для графу g також більш змістовне позначення g E s g \|\| , де \|\| E — кількість дуг графу g . Розглянемо такі функції на множині графів (граф-функції): 1. G 0C — константна функція: 1 00 =)( ggC G . 2. GS — для будь-якого графу ∆≠g збільшення на одиницю його «першої» вершини ]1[gs . Таким чином, якщо Алгебраїчна характеристика класу графових перетворень Системні дослідження та інформаційні технології, 2011, № 2 109 >∈==<≡>< }},...,{, ;,1 ),,(=\|{, 1 ,...,1 piiiiii vv n vvvvnivveeEVg kjkj p , то ,,)( 1 ,...,1 >≡<>< EVgS pvv n де 21 }],1[],1[{\= EEvsvsEE jgjg ∪∈><>< . Тут ,1]1[{2 +<≡ gsE }],1[ Evsv jgj ∈>< . 3. ∪̂ — об’єднання графів: 〉〈 111 ,= EVg , 〉〈 222 ,= EVg , 21 ˆ gg ∪ 21= VV ∪〈 , 〉∪ 21 EE . Зокрема, у випадку коли графи розглядаються над єдиним простором вершин (у цьому випадку NV ≡ ), для графів 〉〈 11 ,= EVg , 〉〈 22 ,= EVg їх об’єднанням є граф 21 ˆ gg ∪ V〈= , 〉∪ 21 EE . Усі наступні операції будемо разглядати в контексті останнього зауваження. 4. \ — різниця графів: 〉〈 11 ,= EVg , 〉〈 22 ,= EVg , 〉〈 2121 \,=\ EEVgg . 5. eE — виділення «першої» дуги. Формально, це означає, що для будь- якого ><>< EVg pvv n ,=,...,1 , >><=< −>< }]1])[1[(],1[{,)( ,...,1 ggg vv ne sssVgE p . Тут вираз ]1[])1[( gg ss− очевидно означає «першу» вершину від’ємно інцидентну вершині ]1[gs . Надалі скрізь, де йтиметься про «першу» вершину графу, «першу» від’ємно (додатно) інцидентну вершину, «першу» дугу графу то- що, сказане розуміється нами в контексті зазначеного вище (для функцій GS та eE ). 6. R — утотожнення «першої» вершини графу з «першою» від’ємно інцидентною їй вершиною. Нехай ,),(= {=,,...,1 kj p iiii vv n vveeEVg ≡<>< >∈= }},...,{, ;,1 1 pii vvvvni kj та ]1])[1[( gg ssw −≡ . Тоді >=<>< 1 ,..., ,)( 1 EVgR pvv n , де 21 }],1[{\= EwsEE g ∪ . Тут })(,,1],)[(],1[{2 wrrwsvvsE ggrrg −− ==><≡ δ… . 7. A — стягування кореня графу з першою від’ємно інцидентною вершиною. Нехай >∈=<≡>< }},...,{, ;,1 ,),(= {=, 1 ,...,1 piiiiii vv n vvvvnivveeEVg kjkj p . Тоді >=<>< 1 ,..., ,)( 1 EVgA pvv n , де 21 }],1[],1[{\= EEvsvsEE jgjg ∪>∈<>< . Тут }],1[],1])[1[({2 EvsvssE jgjgg ∈><><≡ − . 8. ∪ — об’єднання графів 1g та 2g із додаванням дуги із кореня графу 1g в корінь вершини графу 2g . Тобто, ∪∪=∪ ˆˆ 212 * 1 gggg >><<∪ }]1[],1[{,ˆ 21 gg ssV . 9. vE — виділення кореня графу 〉〈 EVg ,= : ],1[{,=)( gv sVgE <〈 }]1[ >gs . І.В. Редько, Н.М. Снігур ISSN 1681–6048 System Research & Information Technologies, 2011, № 2 110 Також знадобляться ще й такі функції: 1. eD — видалення «першої» дуги графу 〉〈 EVg ,= . 2. vD — видалення кореня («першої» вершини), якщо вона ізольована. 3. out vE — виділення підграфу графу 〉〈 EVg ,= , що складається з кореня («першої» вершини) g та всіх від’ємно інцідентних їй дуг: >< 1 out ,=)( EVgEv , де ])}1[(,...,1];[])1[(],1[{\1 ggggjjg srrssvvsEE −− =≠><≡ δ . 4. G∆ C — функція генерації порожнього графу: GG ∆∆ =)(gC . Покладемо .},=,,,,,,\,ˆ,,{=: 1,2,= 1,= * 0 …n nm n mve IEARESC GG G G ∪∪σ Можна безпосередньо перевірити, що всі ці функції є частково- рекурсивними. З метою моделювання граф-функцій векторними побудуємо кодуюче відображення : NG→φ , де i i NN ∪∞ 0= = , }{=0 ΛN , таким чином. Нехай g — деякий граф, mnijg aA = — відповідна йому матриця. Покладемо Λ=∆ )( Gφ , ,00=)( 12 212 1 111 ml mkmkljjlii aaaaaag …………φ (1) де rsia — ненульові елементи матриці A . Очевидно, φ — ін’єкція, але не сюр’єкція. Позначимо, )(=: GV φ . Вочевидь, ця множина є рекурсивною в нумерації Gα . Нижче під L -функцією (L -предикатом) мається на увазі багатомісна часткова операція (предикат) на множині L . Означення 1. V -функцію ),,( 1 nxxF … назвемо векторним образом граф-функції ),,( 1 nξξ …F , якщо ),,(;))(,),(( 11 nn ggggF …… Fφφφ для всіх ngg ,,1 … . Аналогічно V -предикат ),,( 1 nxxP … назвемо векторним образом граф-предиката ),,( 1 nξξ …P , якщо ),,(;))(,),(( 11 nn ggggP …… Pφφφ для всіх ngg ,,1 … . Лема 1. Векторний образ чр-граф-функції (чр-граф-предиката) є чр- V - функція (чр- V -предикат). Доведення. Доведення випливає із теореми 2.1.5 [22]. Безпосередньо із рекурсивності множини V випливає наступна лема. Лема 2. Будь-яка чр- V -функція є чр- N -функцією (векторною чр- функцією). Для чр- V -предикатів аналогічно. Наслідок 1. Векторний образ чр-граф-функцї (чр-граф-предиката) є векторною чр-функцією (векторним чр-предикатом). З метою моделювання векторних функцій граф-функціями побудємо кодуюче відображення GN →Φ : таким чином: Алгебраїчна характеристика класу графових перетворень Системні дослідження та інформаційні технології, 2011, № 2 111 ,)( G∆=ΛΦ nvn v v 11 =)(Φ . Означення 2. Граф-функція ),,( 1 nξξ …F називається граф-моделлю векторної функції ),,( 1 nxxF … , якщо )),,((;))(,),(( 11 nn vvFvv …… ΦΦΦF для всіх nvv ,,1 … . Граф-модель предиката вводиться аналогічно. Лема 3. Для будь-яких векторних чр-функцій та чр-предикатів існують їх граф-моделі, які належать замиканню Ω][ Gσ . Доведення. Доведення проводиться індукцією по довжині відповідних константних термів алгебри чр N A . Базис. Граф-моделлю векторної функції 0C є функція 0GC , а функції S — GS . Побудуємо граф-моделі для ,Π . 1. 〉〈≠ )(),())((=),( ,1 ξπξπξπ ξπ vESSG . ),(1 ξGG ∆ дає граф з однієї вершини, номер якої на 1 менший за номер першої вершини ξ . ))),(((=)( * 12 ξξξ ∪∆GGG REe ; 〉∪〈∆≠ ))((),(,ˆ)(=),( 2,,3 ξξζπξξπ ζξπ ee ED GG . Тоді ))(,(=)( 3 gDg e∆Π GF — граф-модель функції Π . 2. Аналогічно тому, як ми будували функції 43 ,GG , можемо визначити функцію, яка збільшує номер першої вершини на таку величину, яка нам потрібна. Позначимо її }){,( nM π , де }{n — граф із однієї вершини, номер якої n . Тобто, функція }){,( nM π повертає граф ,π в якого перша вершина має номер n . Нехай )(2 πF — функція, яка перераховує дуги графа π (результатом її дії є граф з однієї вершини, що має номер рівний кількості дуг графу). Позначимо 〉∪〈∆≠ ζξζξπξζξπ ξπ ),(),),((ˆ)(=),,( out , 6 vv DEMG . Тоді ),,(ˆ=),( 126121 ggggg ∆∪GF — граф-модель функції . Індуктивний крок. Тут варто врахувати те, що суперпозиція граф- моделей векторних функцій є граф-моделлю суперпозиції відповідних векторних функцій. Для розгалуження та циклювання — аналогічно. Нехай Φφψ =: . Очевидно, що )(: VG Φ→ψ — бієкція. Через χ позначимо будь-яке розширення відображення 1−ψ . Граф-функції ψ та χ відіграють роль кодуючої та декодуючої функцій відповідно. Безпосередньо із наведених вище означень випливає лема. І.В. Редько, Н.М. Снігур ISSN 1681–6048 System Research & Information Technologies, 2011, № 2 112 Лема 4. Нехай ),,( 1 nξξ …F — чр-граф-функція, а ),,( 1 nππ …H — граф- модель векторного образу функції ),,( 1 nξξ …F . Тоді )))(,),(((=),,( 11 nn AAAA ψψχ …… HF для всіх iA , ni 1,= . Аналогічно, нехай ),,( 1 mξξ …P — чр-граф-предикат, а ),,( 1 mππ …K — граф-модель векторного образу цього предиката. Тоді ))(,),((=),,( 11 nn AAAA ψψ …… KP для всіх iA , ni 1,= . Таким чином, для доведення повноти залишається побудувати функції ψ та χ . Лема 5. Має місце ][, Gσχψ ∈ . Доведення. 1. Почнемо з функції ψ . Покладемо 〉∪〈≠ τζζξπτζζξπ τζξπ ),(),(,))))((((=),,( ,,, 1 eeee DEERDG . ))))(((,,(1 gERDg ee∆G виділяє підграф усіх ребер, що є від’ємно інцідентними його першій вершині. Розглянемо також =),,(2 ζξπG ))))(((( ξζ ee ERD∪ )((ˆ ∆≠∪ ξ ζξπ ,, * ∪〈 ˆπ ( ∪ζ )))(( ξeEA , )(ξeD , ))( 〉ζGS . Тоді функція ∆(2G , ∆(1G , g , ))))((( gERD ee , )1 0g перетворює перший підграф графу G необхідним чином. Введемо ще функції }({3 mG , )(=}){ nmn + — збільшення номера вершини нульового графу на n , та )(4 ξG — підрахування кількості ребер .π =)(4 ξG )((( ξeE♦ ∆∆),= , ({1}F , )))(ξeD , де =),( ξπF ))(( δξ ≠eE ξπ , 〉〈 )(),( ξπ eDSG . Отримаємо, що ),,,( 05 Fgg∆G , де π(5G , ξ , =)ζ ))(( ∆≠ξeE ζξπ ,, * π〈 ∆∪ ((ˆ 2G , ξ , )))(ζGS , \ξ ∆(2G , ξ , ))(ζGS , ζ(( 3GGS , ∆(( 24 GG , ξ , 〉)))))(ζGS , кодує всі існуючі ребра графу .G Нам залишилось додати до графу-коду g~ дуги, що відповідають ізольованим вершинам графу g . Для цього використаємо функцію )(=),,(6 ∆≠ξζξπG ζξπ ,, * ∪〈 ˆπ ζ( ))(* ξvE∪ , 〉)(),( 2 ζξ GSDv . Таким чином, ),,(=)( 05 ggg ∆Gψ g,(ˆ 6 ∆∪G )((\ ∆≠ξ ξπ , * )(ˆ ξπ eE∪〈 , ))( 〉ξeD , 1 04 2 (( gS GG , ∆(5G , )))), 0gg як раз задає функцію .ψ Алгебраїчна характеристика класу графових перетворень Системні дослідження та інформаційні технології, 2011, № 2 113 2. Тепер розглянемо функцію χ . Розглянемо функції 〉∪〈≠ )(),(,ˆ))))((()))((((=),( ,, 2 7 ζξξπζξζπ ζξπ eeeee DEERDRDSGG , )))(((=)(8 ξξ ee ERDG , 〉∪∪〈∆≠ )(),(,),()(=),,( 8 * ,,, 9 ττξζξπττξπ τζξπ eDGG , 〉∆∆∆∆∪〈∆≠ ),(\))),,(()),,((,(ˆ*)(=),( 77789 , 10 ξξξξπξξπ ξπ GGGGGG eD . Тут )~,(7 g∆G виділяє підграф, який складається із дуг, від’ємно інцідентних першій вершині, потім другій тощо, поки не зустрінеться вершина, яка не має від’ємно інцідентних дуг. Функція )~(8 gG визначає вершину, з якої мають виходити дуги до інших вершин. ),~(,( 89 sgGG ∆ ))~( se gD виконує перетворення виділеного підграфу )~,(=~ 7 ggs ∆G . А отже, )).~(,(=))~(( 10 gg ∆Gχ Теорема 1. Gσ є породжуючою множиною алгебри чр GA . Доведення. Доведення теореми безпосередньо випливає із наслідка 1 та лем 3, 4. ВИСНОВКИ Зауважимо, що рівність із сукупності Gσ не можна видалити як єдиний предикат системи. З усіх функцій Gσ лише GS не є зберігаючою денотати (денотата в цьому випадку — вершина). Лише функція eE не зберігає множину графів, з кількістю дуг більшою або рівною 2. Лише функція vE не зберігає множину графів, які мають хоча б одну (непусту) дугу. Таким чином, функції GS , eE , vE та предикат =G не можуть бути вилучені з породжуючої сукупності Gσ . Щодо інших функцій із Gσ питання залишається відкритим. Тому, хоча питання існування n mI -базису ППА чр GA принципово вирішується відповідною теоремою, що наведена в розділі 2 цієї роботи, пошук природнього для області графових перетво- рювачів n mI -базису є актуальною задачею. Вирішенню останньої будуть присвячені декілька подальших робіт. ЛІТЕРАТУРА 1. Мальцев А.И. Алгоритмы и рекурсивные функции. — М.: Наука, 1965. — 391 с. 2. Колмогоров А.Н., Успенский В.А. К определению алгоритма // Успехи матем. наук. — 1958. — 13, № 4. — С. 3–28. І.В. Редько, Н.М. Снігур ISSN 1681–6048 System Research & Information Technologies, 2011, № 2 114 3. Asser G. Berechenbare Graphenabbildungen/-In:Kompliziertheit von Lern-und Erkennungsprozessen. — Jena: Friedrich-Schiller-Universitat, 1975. — Р. 7–17. 4. 3аславский И.Д. Граф-схемы с памятью // Тр. мат. ин-та АН СССР. — 1964. — 72. — С. 99–192. 5. Babai L., Grigoryev D., Mount D. Isomorphism of graphs with bounded eigenvalue multiplicity // Proc. 14th ACM symp. On theory of comput., STOC. — 1982. — Р. 310–324. 6. Пролубников А.В. Прямой алгоритм проверки изоморфизма графов // Компью- терная оптика: сб. научн. тр.; под ред. акад. РАН Ю.И. Журавлева. — Изд- во Самарского гос. ун-та. — 2007. — Вып. 27. — С. 123–128. 7. Foggia P., Sansone C., Vento M. A database of graphs for isomorphism and sub- graph isomorphism benchmarking // Proc. of the 3rd IAPR TC-15 international workshop on graph-based representations. — Italy, 2001. — Р. 157–168. 8. Spence E. The Stromgly Regular (40, 12, 2,4) Graphs // The Electronical Journal Of Combinatorics. — 2000. — 7, № 1. — Р. R22. 9. Ершов А.П. Вычислимость в произвольных областях и базисах // В кн.: Семи- отика и информатика. Вып. 19. — М.: Изд. ВИНИТИ, 1979. — С. 3–58. 10. Агафонов В.Н. Спецификация программ: понятийные средства и их организа- ция. — Новосибирск: Наука, 1987. — 240 с. 11. Буй Д.Б., Редько В.Н. Примитивные программные алгебры целочисленных и словарных функций // Докл. АН УССР. Сер. А. — 1984. — № 1. — С. 69–71. 12. Буй Д.Б., Мавлянов А.В. К теории программных алгебр // Укр. мат. журн. — 1984. — № 6. — С. 761–764. 13. Буй Д.Б. Примитивные программные алгебры: автореф. дис. … канд. физ.-мат. наук. — Киев, 1985. — 22 с. 14. Буй Д.Б., Редько В.Н. Примитивные программные алгебры. II // Кибернетика. — 1984. — № 5. — С. 1–7. 15. Буй Д.Б. Неперервність в індуктивних множинах: основні поняття та допоміжні результати // Вісн. Київського Ун-ту. Сер.фіз.-мат. науки. — 1998. — Вип. 1. — С. 142–148. 16. Буй Д.Б. Неперервність в індуктивних множинах: неперервність суперпозиції та суміжні результати // Вісн. Київського Ун-ту. Сер.фіз.-мат. науки. — 1998. — Вип. 2. — С. 187–195. 17. Буй Д.Б. Неперервність в індуктивних множинах: неперервність рекурсії та суміжні результати // Вісн. Київського Ун-ту. Сер.фіз.-мат. науки. — 1998. — Вип. 3. — С. 128–138. 18. Буй Д.Б., Поляков С.А. Композиційна семантика SQL-подібних мов: табличні структури даних, композиції, приклади // Вісн. Київського Ун-ту. Сер.фіз.- мат. науки. — 1999. — Вип. 1. — С. 130–140. 19. Ершов Ю.Л. Теория нумераций. — М.: Наука, 1977. — 416 с. 20. Голунков Ю.В. О полноте операций в системах алгоритмических алгебр // Алгоритмы и автоматы. — Казань: Изд-во Казан. ун-та, 1978. — С. 11–53. 21. Новиков Ф.А. Дискретная математика для программистов. — СПб: Питер, 2000. — 304 с. 22. Мальцев А.И. Конструктивные алгебры. Том I // Успехи мат. наук. — 1961. — № 3. — С. 3–60. Надійшла 27.11.2009

Алгебраїчна характеристика класу графових перетворень

Institution

Ähnliche Einträge