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

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

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2010
Автори:	Редько, І.В., Снігур, Н.М.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Інститут проблем реєстрації інформації НАН України 2010
Назва видання:	Реєстрація, зберігання і обробка даних
Теми:	Математичні методи обробки даних
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/50486
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Алгебраїчна характеристика класу графових перетворювачів, які зберігають денотати / І.В. Редько, Н.М. Снігур // Реєстрація, зберігання і обробка даних. — 2010. — Т. 12, № 4. — С. 54-61. — Бібліогр.: 23 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-50486
record_format	dspace
spelling	irk-123456789-504862013-10-22T03:05:59Z Алгебраїчна характеристика класу графових перетворювачів, які зберігають денотати Редько, І.В. Снігур, Н.М. Математичні методи обробки даних Розглянуто клас функцій, які зберігають денотати на множині графів. Визначено породжуючу множину алгебри функцій, які зберігають денотати на новому носії — графі, а також доведено її повноту. Рассмотрен класс функций, сохраняющих денотаты на множестве графов. Определено порождающее множество алгебры функций, сохраняющих денотаты на новом носителе — графе, а также доказана его полнота. The class of all saving denotations functions depending on finite graphs is considered. A generating set for the algebra of saving denotations graph functions is found, and it is also proved that this set is complete. 2010 Article Алгебраїчна характеристика класу графових перетворювачів, які зберігають денотати / І.В. Редько, Н.М. Снігур // Реєстрація, зберігання і обробка даних. — 2010. — Т. 12, № 4. — С. 54-61. — Бібліогр.: 23 назв. — укр. 1560-9189 http://dspace.nbuv.gov.ua/handle/123456789/50486 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	2010
topic_facet	Математичні методи обробки даних
url	http://dspace.nbuv.gov.ua/handle/123456789/50486
citation_txt	Алгебраїчна характеристика класу графових перетворювачів, які зберігають денотати / І.В. Редько, Н.М. Снігур // Реєстрація, зберігання і обробка даних. — 2010. — Т. 12, № 4. — С. 54-61. — Бібліогр.: 23 назв. — укр.
series	Реєстрація, зберігання і обробка даних
work_keys_str_mv	AT redʹkoív algebraíčnaharakteristikaklasugrafovihperetvorûvačívâkízberígaûtʹdenotati AT snígurnm algebraíčnaharakteristikaklasugrafovihperetvorûvačívâkízberígaûtʹdenotati
first_indexed	2025-07-04T12:12:53Z
last_indexed	2025-07-04T12:12:53Z
_version_	1836718410082287616
fulltext	54 УДК 681.3.06 І. В. Редько, Н. М. Снігур Національний технічний університет України «КПІ» проспект Перемоги, 37, 01037 Київ, Україна тел. (044) 477-10-60 Алгебраїчна характеристика класу графових перетворювачів, які зберігають денотати Розглянуто клас функцій, які зберігають денотати на множині гра- фів. Визначено породжуючу множину алгебри функцій, які зберігають денотати на новому носії — графі, а також доведено її повноту. Ключові слова: алгебра функцій і предикатів, які зберігають денота- ти, скінчений (орієнтований) граф, функція та предикат довільної ар- ності, зберігаючі денотати, пошук породжуючих множин і базисів. Вступ Проблема формального опису семантики програм виникла з появою програ- мування. Одним із науково обґрунтованих підходів у програмуванні є застосуван- ня алгебраїчних методів дослідження програм. В основі таких методів лежать програмні алгебри, тобто алгебри, носіями яких є спеціальні класи функцій, а операціями — композиції, що представляють собою абстарції від засобів синтезу програм. Зокрема, в термінах цих алгебр точно ставляться та вирішуються про- блеми повноти в різних класах обчислюваних функцій. Ці проблеми займають одне з найважливіших місць у сучасному програмуванні. Дана робота присвячена вивченню обчислюваних графових перетворювачів, що зберігають денотати. Вперше поняття функції, що зберігає денотати, було вве- дено в [1] для опису семантики мов маніпуляції даними. В даній роботі вихідне визначення зберігання денотатів узагальнюється за допомогою введення парамет- ра — так званої оцінки. Обчислюваність вводиться згідно нумераційному підходу [1]. Вибір графових структур обумовлений їхньою важливістю та популярністю в теоретичному та прикладному програмуванні (див., наприклад, [3–11]). Зокрема, в роботах [3, 4] визначено та досліджено поняття обчислюваної функції над скінченими графами (комплексами), [5] присвячена вивченню граф-схем алгоритмів, [6–9] — ізомор- фізму графів, [10] — питанням абстрактної обчислюваності в різних областях, [11] — графовим засобам специфікації програм. При цьому треба зазначити, що практично всі згадані дослідження акцентують увагу безпосередньо на графи, не © І. В. Редько, Н. М. Снігур Алгебраїчна характеристика класу графових перетворювачів, які зберігають денотати ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2010, Т. 12, № 4 55 розглядаючи задачі огляду класу обчислюваних функцій над графами (графових перетворювачів). Інструментом розв’язання поставлених проблем виступають так звані примі- тивні програмні алгебри (ППА) [2]. Доцільність даного вибору обґрунтована ре- зультатами, отриманими, наприклад, в [12–24]. Основну увагу приділено пошуку породжуючої множини для такої ППА. Усі використані та невизначені в роботі поняття та позначення розуміються в сенсі [15]. Базові визначення, поняття, результати Носій ППА складають n -арні функції і предикати для 1,2,=n Сигнатуру ППА (позначатимемо її  ) складають операції суперпозиції, розгалуження та 1)( n -арного циклування (визначення див. в [12]). Під (скінченим) орієнтованим графом g розуміємо пару  EV , , де V — деяка злічена непуста множина об’єктів, а E — бінарне відношення на V . Стандартна інтерпретація цих об’єктів V та E в даному визначенні така: V — множина вершин графа, E — множина його дуг. У силу зліченості множини V не буде суттєвим обмеженням, якщо покласти NV  . При цьому на множині вершин вводиться цілком природна впорядкованість. Домовимось надалі вершини графа позначати латинськими літерами wvu ,, , а дуги — літерами spe ,, , можливо з індексами, ,...,..., 11 ev У випадку необхідності явно вказати вершини дуги та її напрям, використовуватимемо запис  uv, , ро- зуміючи, що дуга направлена від v до u . Будемо називати першою вершиною графа вершину з найменшим номером. Граф будемо позначати через r E g , де r — номер першої вершини графа g , а E — кількість його дуг, або скорочено просто g . Вершини v та u дуги  uve , будемо називати суміжними. При цьому ду- га e вважається додатно інцидентною вершині u та від’ємно інцидентною вер- шині v . За аналогією домовимося вершину v графа  EVg , називати від’ємно (додатно) інцидентною (від’ємною (додатною)) до вершини w того ж графа, якщо ),(, EwvEvw  . Множину всіх графів позначимо G . Під функціями далі розуміємо часткові функції з аргументами і значеннями із G , а під предикатами — часткові предика- ти на G . Обчислюваність на G вводиться як нумераційна обчислюваність за допомо- гою арифметичної функції, що представляє дану функцію на G в деякій зафіксо- ваній нумерації G множини G 19. Існування такої нумерації випливає зі зліче- ності множини NV  . Будь-яку частково-рекурсивну багатомісну функцію або будь-який частково- рекурсивний багатомісний предикат (чр-функція, чр-предикат) будемо називати також графовим перетворювачем. Нехай : 2V на G  , де V — множина вершин і, відповідно, V2 — множина всіх скінчених підмножин V . І. В. Редько, Н. М. Снігур 56 Будемо казати, що функція f арності n  -зберігає денотати, якщо існує скінчена множина VV f  така, що для будь-якого fxx n dom,,1   викону- ється .)()),,(( 1= 1 fi n i n Vxxxf    Через чр GA , позначимо ППА, носій якої складають графові перетворювачі на G , які  -зберігають денотати. Породжуючу множину алгебри чр GA назвемо її по- вною системою (ПС), ПС ППА — n mI базисом, якщо будь-яка її підсистема, що отримується видаленням якого-небудь предиката або якої-небудь функції, відмін- ної від селекторної, вже не буде повною. Примітивна програмна алгебра чр-функцій і чр-предикатів на множині скінчених орієнтованих графів З вищезазначеного є цілком очевидним, що будь-який граф g можна ефекти- вно представити певним вектором gA , причому ефективність такого представлен- ня прямо витікає з її побудови. Нехай     ,,,,,,, 43211 iiiin vvvvEvvVg  , ni j 1 , ,2,1j . У подальшому буде зручно перенумерувати також і дуги графа. Для цього домовимось про певну впорядкованість пар натуральних чисел1. Зауважимо, що порядок на множині 2N можна вводити по-різному2, проте в даному випадку більш зручним нам видається наступний:   1,20,21,10,1,02,01,00,0 n (1) Тоді, дуги графа занумеруємо відповідно порядку (1), тобто першою дугою буде дуга, що відповідає найменшій парі в цьому порядку (найлівішій), а найбільший номер матиме дуга, що відповідає найбільшій парі (найправішій). Покладемо   214321 00 kkiiiig vvvvvvA  , де jkv , ,2,1j , — ізольовані вер- шини (якщо вони є). Зокрема, в такому представленні порожньому графу, очевид- но відповідає порожній вектор  , а повністю незв’язаному графу, тобто графу  EVg , , де E O, відповідає вектор  1 20 0 0 0 nv v v . Таким чином, побудова- не відображення : G N , де i i NN   0= = , }{=0 N . Очевидно,  — ін’єкція, але не сюр’єкція. Позначимо V : ( ) G . Вочевидь, ця множина є рекурсивною в нумерації G . 1 Такий крок є цілком природним, оскільки множина 2N , як відомо є ефективно зліченою. 2 Наприклад, як в канторівській нумерації (див. [1, стр. 60]). Алгебраїчна характеристика класу графових перетворювачів, які зберігають денотати ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2010, Т. 12, № 4 57 Нижче під L -функцією (L -предикатом) мається на увазі багатомісна частко- ва операція (предикат) на множині L . Означення 1. V -функцію ),,( 1 nxxF  назвемо векторним образом графого перетворювача 1 1( ( ), , ( )) ( , , )n nF g g F g g     для всіх ngg ,,1  . Аналогічно V -предикат ),,( 1 nxxP  назвемо векторним образом граф-предиката ),,( 1 n P , якщо 1 1( ( ), , ( )) ( , , )n nP g g P g g     для всіх ngg ,,1  . Лема 1. Векторний образ чр-графового перетворювача (чр-графового преди- ката) є чр- V -функція (чр- V -предикат). Безпосередньо із рекурсивності множини V випливає наступна лема. Лема 2. Будь-яка чр- V -функція є чр- N -функцією (тобто просто векторною чр-функцією). Для чр- V -предикатів аналогічно. Наслідок 1. Векторний образ чр-графового перетворювача (чр-граф- предиката) є векторною чр-функцією (векторним чр-предикатом). З метою моделювання векторних функцій графовими перетворювачами по- будуємо також кодуюче відображення GN  : . Для цього будь-якому вектору )( 21 nvvvA  поставимо у відповідність граф  1 2, , , ,ng V v v v    1 2 2 3 1, , , , , ,n nE v v v v v v  . Означення 2. Графовий перетворювач ),,( 1 n F називається граф-модел- лю векторного перетворювача ),,( 1 nxxF  , якщо 1( ( ), , ( ))nv v  F 1( ( , , ))nF v v   для всіх nvv ,,1  . Граф-модель предиката вводиться аналогічно. Лема 3. Для будь-яких векторних чр-функцій та чр-предикатів існують їхні граф-моделі, які належать замиканню   G . Нехай :   . Очевидно, що )(: VG  — бієкція. Через  позначимо яке-небудь розширення відображення 1 . Графові перетворювачі  та  гра- ють ролі кодуючої та декодуючої функцій відповідно. Безпосередньо із наведених вище означень випливає лема. Лема 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,= . І. В. Редько, Н. М. Снігур 58 Розглянемо наступні функції на множині графів (графові перетворювачі). 1. G 0C — константна функція: 1 00 =)( ggCG . 2. ̂ — об’єднання графів:  111 ,= EVg ,  222 ,= EVg , 21 ˆ gg  21= VV  ,  21 EE . 3. \ — різниця графів:  11 ,= EVg ,  22 ,= EVg ,  2121 \,=\ EEVgg . 4. eE — виділення «першої» дуги, тобто дуги, номер якої стосовно введеної вище впорядкованості є найменшим. Формально, це означає, що якщо     ,,,,= 111 ivvvg , то 1 ,)( 1 ie vvgE  . 5. vE — виділення «першої» вершини графа    EvVg ,,= 1  : 1( ) { },OvE g v . 6. vD — видалення «першої» вершини, якщо вона ізольована. 7. L — створення дуги. Часткова функція, що діє на множині з двох нульо- вих графів  m та  n таким чином, що },{},,{}){},({ nmnmnmL  . 8. eD — видалення «першої» дуги графа  EVg ,= (див. визначення функції eE ) 9. eD  — видалення всіх дуг графа         eee DED   . 10. G C — функція генерації порожнього графа: GG  =)(gC . Покладемо 1,2, 0 1, ˆ: { , , \, , , , , , } .G n n G e v v G m m n C E E D L I       Можна безпосередньо перевірити, що всі ці функції є частково-рекурсивними. Лема 5. Має місце  G , Доведення. 1.  . Покладемо          )(,,)(*))((=),( , 1   eeeveevee DDEEEDDLEE G . Тоді ),(1 gG представляє собою граф-код за винятком ізольованих вершин. А отже, повний граф-код  1 ˆ ( ) , ( )eg g G g D g     . Алгебраїчна характеристика класу графових перетворювачів, які зберігають денотати ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2010, Т. 12, № 4 59 2.  . Розглянемо функцію          eeee DDEE ,),( , 2 G . Тоді  2 ˆ ˆ ˆ( ) , ( )eg g G g D g     , що і треба було довести. Теорема 1. G є породжуючою множиною алгебри чр G,A . Доведення. Твердження теореми випливає безпосередньо із доведених вище результатів. Зауважимо, що видалити жодну із функцій G неможливо. Справді: 1) G є єдиним предикатом множини; 2) лише функція GC0 не зберігає множину графів \ , \|G g V E V    1 1, , 1v v  (множина графів, у яких номер першої вершини більше 1); 3) лише функція ̂ не зберігає множину  2\|,  VEVg (графи з кількіс- тю вершин меншою або рівною 2); 4) лише функція \ не зберігає множину  \ ,O \| 2G g V V  (усі графи, окрім тих, що є повністю незв’язними і мають більше однієї вершини); 5) лише eE не зберігає         1 1\ 1,2 , 1, 2 , , \| 2G g g v E v       1, 2 ,Og  (усі графи, окрім таких: графа, що складається із дуги 1,2 ; незв’язного графа, що складається із двох вершин з номерами 1 та 2; множини графів, для яких номер першої вершини дорівнює 2); 6) лише vE не зберігає      \ 2 , O 1, 2 , OG g g      1 1, , \| 1, 2g V e e   (усі графи, окрім таких: графа з однієї вершини з номером 2; графа із двох вершин з номерами 1 та 2; множини графів, у яких пер- шим ребром є 1,2 ); 7) лише vD не зберігає    GvEvg  1\|,, 11  (множина графів, для яких номер першої вершини дорівнює 1, та порожній граф); 8) нарешті, лише L не зберігає множину  ,O Gg V  (множина усіх по- вністю незв’язних графів і порожній граф). Це дає змогу припустити, що вказана система функцій G є базисом ППА графо- вих перетворювачів, що зберігають денотати. Висновок У статті було досліджено породжуючу множину для ППА класу функцій, які зберігають денотати над графами. Діаграми мов моделювання (зокрема, UML ), сукупності взаємозв’язаних і впорядкованих структур Bpwin, Erwin можуть бути представлені графовими засобами специфікації програм. Завданням цієї роботи є І. В. Редько, Н. М. Снігур 60 здобуття опису класу обчислюваних граф-функцій, які зберігають денотати, та пошуку природного для області графових перетворювачів n mI -базису, що, безпе- речно, є актуальною задачею. Декілька наступних робіт будуть присвячені прак- тичному застосуванню отриманих результатів. 1. Басараб І.А. Базы данных с логико-функциональной точки зрения / І.А. Басараб, В.Н. Ре- дько // Программирование. — 1984. — № 2. — С. 53–67. 2. Мальцев А.И. Алгоритмы и рекурсивные функции / А.И. Мальцев. — М.: Наука, 1965. — 391 с. 3. Колмогоров А.Н. К определению алгоритма / А.Н. Колмогоров, В.А. Успенский // Успехи матем. наук. — 1958. — Т. 13, № 4. — С. 3–28. 4. Asser G. Berechenbare Graphenabbildungen / G. Asser // In: Kompliziertheit von Lern-Und Erkennungsprozessen. — Jena: Friedrich-Schiller-Universitat, 1975. — Р. 7–17. 5. 3аславский И.Д. Граф-схемы с памятью / И.Д. Заславський // Тр. мат. ин-та АН СССР. — 1964. — 72. — С. 99−192. 6. Babai L. Isomorphism of Graphs with Bounded Eigenvalue Multiplicity / L. Babai, D. Grigoryev, D. Mount // Proc. 14th ACM Symp. on Theory of Comput. — STOC, 1982. — Р. 310–324. 7. Пролубников А.В. Прямой алгоритм проверки изоморфизма графов / А.В. Пролубников // Сб. научн. тр. «Компьютерная оптика». под ред. акад. РАН Ю.И. Журавлева. Из-во Самарского государственного университета, 2007. — Вып. 27. — С. 123–128. 8. Foggia P. A Database of Graphs for Isomorphism and Sub-Graph Isomorphism Benchmarking / P. Foggia, C. Sansone, M. Vento // Proc. of the 3-rd IAPR TC-15 International Workshop on Graph- Based Representations. — Italy, 2001. — Р. 157–168. 9. Spence E. The Stromgly Regular (40, 12, 2,4) Graphs // The Electronical Journal Of Combinatorics. — 2000. — Vol. 7(1). 10. Ершов А.П. Вычислимость в произвольных областях и базисах// В кн.: Семиотика и ин- форматика. — Вып. 19. — М.: ВИНИТИ, 1979. — С. 3–58. 11. Агафонов В.Н. Спецификация программ: понятийные средства и их организация / В.Н. Агафонов. — Новосибирск: Наука, 1987. — 240 с. 12. Буй Д.Б. Примитивные программные алгебры целочисленных и словарных функций / Д.Б. Буй, В.Н. Редько // Докл. АН УССР. Сер. А. — 1984. — № 10. — С. 69−71. 13. Буй Д.Б. К теории программных алгебр / Д.Б. Буй, А.В. Мавлянов // Укр. мат. журн. — 1984. — 36, № 6 — С. 761−764. 14. Буй Д.Б. Примитивные программные алгебры: автореф. дис. канд. физ.-мат. наук. — К., 1985. — 22 с. 15. Буй Д.Б. Примитивные программные алгебры / Д.Б. Буй, В.Н. Редько // Кибернетика. — 1984. — № 5. — С. 1−7. 16. Буй Д.Б. Примитивные программные алгебры / Д.Б. Буй, В.Н. Редько // Кибернетика. — 1985. — № 1. — С. 28−33. 17. Буй Д.Б. Неперервність в індуктивних множинах: основні поняття та допоміжні результа- ти / Д.Б. Буй // Вісник Київського Університету. — К., 1998. — С. 142–148. — (Серія: Фіз.-мат. науки; вип. 1). Алгебраїчна характеристика класу графових перетворювачів, які зберігають денотати ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2010, Т. 12, № 4 61 18. Буй Д.Б. Неперервність в індуктивних множинах: неперервність суперпозиції та суміжні результати / Д.Б. Буй // Вісник Київського Університету. — К., 1998. — С. 187–195. — (Серія: Фіз.-мат. науки; вип. 2). 19. Буй Д.Б. Неперервність в індуктивних множинах: неперервність рекурсії та суміжні ре- зультати / Д.Б. Буй // Вісник Київського Університету. — К., 1998. — С. 128–138. — (Серія: Фіз.- мат. науки; вип. 3). 20. Буй Д.Б. Композиційна семантика SQL-подібних мов: табличні структури даних, компо- зиції, приклади / Буй Д.Б., Поляков С.А. // Вісник Київського Університету. — К., 1999. — С. 130– 140. — (Серія: Фіз.-мат. науки; вип. 1). 21. Ершов Ю.Л. Теория нумераций / Ю.Л. Ершов. — М.: Наука, 1977. — 416 с. 22. Голунков Ю.В. О полноте операций в системах алгоритмических алгебр / Ю.В. Голунков // Алгоритмы и автоматы. — Казань: Из-во Казан. ун-та, 1978. — С. 11−53. 23. Новиков Ф.А. Дискретная математика для программистов / Ф.А. Новиков. — СПб: Питер, 2000. — 304 с. 24. Мальцев А.И. Конструктивные алгебры / А.И. Мальцев // Успехи мат. наук. — 1961. — 16, № 3. — С. 3−60. Надійшла до редакції 19.11.2010

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

Репозитарії

Схожі ресурси