Лингвистическое представление графов с помеченными вершинами

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

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2019
Автори:	Сапунов, С.В., Сенченко, А.С.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Видавничий дім "Академперіодика" НАН України 2019
Назва видання:	Доповіді НАН України
Теми:	Інформатика та кібернетика
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/162647
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Лингвистическое представление графов с помеченными вершинами / С.В. Сапунов, А.С. Сенченко // Доповіді Національної академії наук України. — 2019. — № 11. — С. 17-24. — Бібліогр.: 11 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-162647
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-1626472025-02-09T14:46:17Z Лингвистическое представление графов с помеченными вершинами Лінгвістичне зображення графів з поміченими вершинами Linguistic representation of vertex-labeled graphs Сапунов, С.В. Сенченко, А.С. Інформатика та кібернетика В работе вводится лингвистическое представление Д-графов, у которых в окрестности каждой вершины все вершины имеют разные метки, определяющей парой множеств слов, первое из которых описывает циклы графа, а второе — все его висячие вершины. Предложена процедура, которая по заданной паре множеств либо строит соответствующий ей Д-граф, либо показывает, что по этой паре Д-граф построить невозможно. Найдены процедура построения минимальной (канонической) определяющей пары для графа и процедура преобразования произвольной определяющей пары графа к канонической. Полученные результаты являются распространением соответствующих задач теории автоматов на графы с помеченными вершинами и позволяют задействовать новые методы и алгоритмы для решения задач анализа графов с помеченными вершинами. У роботі введено лінгвістичне зображення Д-графів, у яких в околі кожної вершини всі вершини мають різні мітки, визначальною парою множин слів, перша з яких описує цикли графа, а друга — усі його висячі вершини. Запропоновано процедуру, яка за заданою парою множин або будує відповідний їй Д-граф, або показує, що за цією парою неможливо побудувати Д-граф. Знайдено процедуру побудови мінімальної (канонічної) визначальної пари для графа та процедуру перетворення довільної визначальної пари графа до канонічної. Одержані результати є розповсюдженням відповідних задач теорії автоматів на графи з поміченими вершинами та дозволяють використовувати нові методи та алгоритми для розв'язання задач аналізу графів з поміченими вершинами. The representation of deterministic graphs (D-graphs) by sets of words over the vertex labels alphabet is studied. A vertex-labeled graph is said to be a D-graph, if all vertices in the neighborhood of every its vertex have different labels. Vertex-labeled graphs are widely used in the modeling of various computational processes in programming, robotics, model checking, etc. In such models, graphs play the role of an information environment of single or several mobile agents. Walks of agents on a graph determine the sequence of vertices labels or words in the alphabet of labels. For D-graphs in case where the graph as a whole and the initial vertex (i.e. the vertex, from which the agent started walking) are known, there exists the one-to-one correspondence between the sequence of vertices visited by the agent and the trajectory of its walks on the graph. In the case where the D-graph is not known as a whole, the agent walks on it can be arranged in such way that an observer obtains information about the structure of the graph sufficient to solve the problems of graph recognizing, finding the op timal path between vertices, comparison between current graph and etalon graph, etc. In this paper, the linguistic representation of D-graphs by the defining pair of sets of words (the first describes cycles of the graph and the second — all its vertices of degree 1) is introduced. This representation is an analog of the system of defining re lations for everywhere defined automata. A procedure that either constructs a D-graph using a given pair of sets or shows that it is impossible to construct a D-graph from this pair is proposed. A procedure for constructing a minimal (canonical) defining pair for a graph and a procedure for converting an arbitrary defining pair of a graph to the canonical one are found. The obtained results are the extension of corresponding problems of the automata theory to vertex-labeled graphs. This representation allows us to use new methods and algorithms to solve the problems of analyzing vertex-labeled graphs. 2019 Article Лингвистическое представление графов с помеченными вершинами / С.В. Сапунов, А.С. Сенченко // Доповіді Національної академії наук України. — 2019. — № 11. — С. 17-24. — Бібліогр.: 11 назв. — рос. 1025-6415 DOI: doi.org/10.15407/dopovidi2019.11.017 https://nasplib.isofts.kiev.ua/handle/123456789/162647 519.7 ru Доповіді НАН України application/pdf Видавничий дім "Академперіодика" НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Інформатика та кібернетика Інформатика та кібернетика
spellingShingle	Інформатика та кібернетика Інформатика та кібернетика Сапунов, С.В. Сенченко, А.С. Лингвистическое представление графов с помеченными вершинами Доповіді НАН України
description	В работе вводится лингвистическое представление Д-графов, у которых в окрестности каждой вершины все вершины имеют разные метки, определяющей парой множеств слов, первое из которых описывает циклы графа, а второе — все его висячие вершины. Предложена процедура, которая по заданной паре множеств либо строит соответствующий ей Д-граф, либо показывает, что по этой паре Д-граф построить невозможно. Найдены процедура построения минимальной (канонической) определяющей пары для графа и процедура преобразования произвольной определяющей пары графа к канонической. Полученные результаты являются распространением соответствующих задач теории автоматов на графы с помеченными вершинами и позволяют задействовать новые методы и алгоритмы для решения задач анализа графов с помеченными вершинами.
format	Article
author	Сапунов, С.В. Сенченко, А.С.
author_facet	Сапунов, С.В. Сенченко, А.С.
author_sort	Сапунов, С.В.
title	Лингвистическое представление графов с помеченными вершинами
title_short	Лингвистическое представление графов с помеченными вершинами
title_full	Лингвистическое представление графов с помеченными вершинами
title_fullStr	Лингвистическое представление графов с помеченными вершинами
title_full_unstemmed	Лингвистическое представление графов с помеченными вершинами
title_sort	лингвистическое представление графов с помеченными вершинами
publisher	Видавничий дім "Академперіодика" НАН України
publishDate	2019
topic_facet	Інформатика та кібернетика
url	https://nasplib.isofts.kiev.ua/handle/123456789/162647
citation_txt	Лингвистическое представление графов с помеченными вершинами / С.В. Сапунов, А.С. Сенченко // Доповіді Національної академії наук України. — 2019. — № 11. — С. 17-24. — Бібліогр.: 11 назв. — рос.
series	Доповіді НАН України
work_keys_str_mv	AT sapunovsv lingvističeskoepredstavleniegrafovspomečennymiveršinami AT senčenkoas lingvističeskoepredstavleniegrafovspomečennymiveršinami AT sapunovsv língvístičnezobražennâgrafívzpomíčenimiveršinami AT senčenkoas língvístičnezobražennâgrafívzpomíčenimiveršinami AT sapunovsv linguisticrepresentationofvertexlabeledgraphs AT senčenkoas linguisticrepresentationofvertexlabeledgraphs
first_indexed	2025-11-26T23:51:14Z
last_indexed	2025-11-26T23:51:14Z
_version_	1849898909248258048
fulltext	17 ОПОВІДІ НАЦІОНАЛЬНОЇ АКАДЕМІЇ НАУК УКРАЇНИ ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2019. № 11: 17—24 Помеченные графы широко применяются в информатике для описания и моделирования разнообразных вычислительных процессов. В этом контексте наиболее изучены конечные орграфы с помеченными дугами (LTS [1], взвешенные автоматы [2], конечные автоматы). Также существует множество вычислительных процессов, естественным образом представ- ляемых графами с помеченными вершинами (в программировании, робототехнике [3], ве- рификации моделей [4]). В работах [5—9] исследуется модель информационной системы как системы взаимодействующих объектов: агентов и их информационной среды, которая представляется в виде топологической модели, т.е. графа с помеченными вершинами. Ранее в [10] было предложено представление конечных всюду определенных автоматов без выхода системами определяющих соотношений — множествами пар слов специально- го вида. С помощью такого представления решена задача характеризации — определения, является ли данное множество пар системой определяющих соотношений для заданного автомата без непосредственного построения автомата. В настоящей работе предлагается распространить понятие и аппарат систем определяющих соотношений на т.н. детермини- © С.В. Сапунов, А.С. Сенченко, 2019 https://doi.org/10.15407/dopovidi2019.11.017 УДК 519.7 С.В. Сапунов, А.С. Сенченко Институт прикладной математики и механики НАН Украины, Славянск E-mail: sapunov_sv@ukr.net, senchenko.a76@gmail.com Лингвистическое представление графов с помеченными вершинами Представлено членом-корреспондентом НАН Украины И.И. Скрыпником В работе вводится лингвистическое представление Д-графов, у которых в окрестности каждой вершины все вершины имеют разные метки, определяющей парой множеств слов, первое из которых описывает ци- клы графа, а второе — все его висячие вершины. Предложена процедура, которая по заданной паре мно- жеств либо строит соответствующий ей Д-граф, либо показывает, что по этой паре Д-граф построить невозможно. Найдены процедура построения минимальной (канонической) определяющей пары для графа и процедура преобразования произвольной определяющей пары графа к канонической. Полученные резуль- таты являются распространением соответствующих задач теории автоматов на графы с помеченными вершинами и позволяют задействовать новые методы и алгоритмы для решения задач анализа графов с помеченными вершинами. Ключевые слова: графы с помеченными вершинами, определяющая пара, представление графов. ІНФОРМАТИКА ТА КІБЕРНЕТИКА 18 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2019. № 11 С.В. Сапунов, А.С. Сенченко рованные графы — класс графов с помеченными вершинами, у которых в окрестности каждой вершины все вершины имеют разные метки [7]. Целесообразность представления детерминированных графов аналогом систем определяющих соотношений вытекает из ес тест венного связывания с такими графами языков в алфавите меток вершин и последу- ющего применения методов теории автоматов к анализу графов. Основные понятия и определения. Под графом с помеченными вершинами пони- маем неориентированный, конечный, непустой, связный граф без петель и кратных ребер ( , , , ( ))G V E X V= ξ , где V — множество вершин графа, E — множество его ребер, ( ) :V V Xξ → — всюдуопределенная функция разметки вершин графа символами конечного алфавита 1{ , , }nX x x=  , значение этой функции для вершины v будем называть ее меткой. Мно- жество всех слов конечной длины в алфавите X будем обозначать X∗ . Пусть 1, , kp x x=  , тогда длина слова p обозначается ( )d p , через ( )E v обозначим множество вершин, смеж- ных вершине : ( ) ( , )v v E v v v E′ ′∈ ↔ ∈ . В зависимости от дополнительных условий, наложенных на функцию разметки вер- шин, из множества всех графов с помеченными вершинами выделяются отдельные под- множества. В работе рассматриваются т.н. детерминированные графы (Д-графы), у кото рых для любых вершин , ,v v v V′ ′′∈ из принадлежностей ( , ), ( , )X v v v v E′ ′′ ∈ и равенства ( ) ( )v v′ ′′ξ = ξ вытекает равенство v v′ ′′= . Содержательно говоря, у Д-графов любые две вер- шины, смежные каждой его вершине v , имеют разные метки. Для исследования Д-графов задействуются одиночные агенты или коллективы аген тов. Агенты помещаются в исследуемый граф и могут сообщать наблюдателю и/или другим агентам доступную им информацию о локальных окрестностях вершин, в которых они на- ходятся. На основании полученной информации и/или инструкций наблюдателя агенты могут перемещаться по ребрам графа от вершины к вершине, а также изменять метки по- сещаемых вершин. Перемещения агента по графу определяют последовательности меток посещенных вершин или слова в алфавите меток. В настоящей работе рассматривается простейший случай: граф исследуется одним аген- том, который не изменяет метки вершин, обозревает разметку замкнутой окрестности теку- щей вершины и передает информацию о разметке наблюдателю. В такой модели наблюда- тель, которому известны карта графа (т.е. множества , ,V E X и функция ( )Vξ ) и вершина, в которую изначально был помещен агент, на основании получаемой от агента информации может однозначно восстановить траекторию перемещений агента по графу. В случае, когда наблюдателю не известна карта исследуемого графа, перемещения агента могут быть ор- ганизованы таким образом, чтобы на основе их анализа наблюдатель получил информацию о структуре графа, достаточную для решения, например, задач составления карты графа, поиска оптимальных маршрутов между вершинами, сравнения исследуемого графа с гра- фом-эталоном и т.д. [3, 8, 11] Для этого в работе вводится представление Д-графа опре- деляющей парой множеств, первое из которых описывает циклы графа, а второе — все его висячие вершины (степени 1). Далее перейдем к понятиям, связанным с определяющей парой Д-графа. Пусть ( , , , ( ))G V E X V= ξ — произвольный граф с помеченными вершинами. Детер ми- низацией G назовем процедуру, которая продолжается до тех пор, пока в графе существуют такие вершины , ,v v v′ ′′ , что , ( )v v E v′ ′′∈ и ( ) ( )v v′ ′′ξ = ξ , и состоит в отождествлении вершин 19ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2019. № 11 Лингвистическое представление графов с помеченными вершинами v′ и v′′ , заменой возникающих кратных ребер одним ребром и удалением ребра ( , )v v′ ′′ (если оно существовало в G). Несложно видеть, что процедура детерминизации выполня- ется за конечное число шагов, результат детерминизации графа определяется однозначно, и этот результат является Д-графом. Пусть G — некоторый Д-граф. Удалим из G все висячие вершины вместе с инцидент- ными им ребрами. Эту процедуру будем повторять до тех пор, пока это возможно. Полу чив- шийся в результате этой процедуры граф ( )B G назовем базой графа G , вершины графа G , входящие в его базу ( )B G , назовем базовыми, а вершины G , не входящие в ( )B G , — сво- бодными. Несложно видеть, что база графа строится однозначно, база ( )B G может быть пустым графом (в случае, когда G — дерево), а в случае, когда граф ( )B G непустой, он со- держит хоть один простой цикл. Под изоморфизмом Д-графов с одинаковым множеством меток вершин 1 1 1( , , ,G V E X= 1 1( ))Vξ и 2 2 2 2 2( , , , ( ))G V E X V= ξ понимаем взаимнооднозначное соответствие ϕ между множествами их вершин, сохраняющее функции их разметки и отношения смежности: 1 1 2( ) ( ( ))v V v v∀ ∈ ξ = ξ ϕ и 1 1 2, (( , ) ( ( ), ( )) )v v V v v E v v E′ ′′ ′ ′′ ′ ′′∀ ∈ ∈ ↔ ϕ ϕ ∈ ; изоморфизм графов 1G и 2G обозначаем 1 2G G≅ . В Д-графе ( , , , ( ))G V E X V= ξ путь 1 kp v v′ ′=  из вершины 1v′ в вершину kv′ будем рассматривать как последовательность меток всех вершин, входящих в него: 1 2( ) ( ) ( )kp v v v′ ′ ′= ξ ξ ξ и обозначать равенством 1 kv p v′ ′= . Путь 1 2 kp x x x′ ′ ′=  назовем допустимым для вершины 1v′ , если 1 1( )v x′ ′ξ = и существуют такие вершины 2, , kv v V′ ′ ∈ , что 2 2( ) , , ( )k kv x v x′ ′ ′ ′ξ = ξ = и 1 2 1( , ), , ( , )k kv v v v E−′ ′ ′ ′ ∈ , в этом случае будем также говорить, что путь 1v p′ ведет в вершину kv′ . Множество всех слов допустимых для вершины v назо- вем языком, определяемым этой вершиной, а множество языков, определяемых всеми вер- шинами графа G назовем языком, определяемым G . Таким образом задается лингвисти- ческое представление графа G . Слово 1kx x′ ′ будем называть реверсом слова 1 kp x x′ ′=  и обозначать его 1p− , слова p и 1p− назовем взаимнообратными. Слово p, для которого вы- полняется vp v= , назовем циклическим для вершины v. Слово 1 mq x x′′ ′′=  назовем началь- ным отрезком слова 1 kp x x′ ′=  , в случае, когда выполняются равенства 1 1, , m mx x x x′′ ′ ′′ ′= = ; этот факт будем обозначать q p⊆ . Зафиксируем некоторую вершину 0v Д-графа ( , , , ( ))G V E X V= ξ , которую далее будем называть порождающей. Пусть 0{ , }( )C L v — такая пара конечных множеств слов ,C L X∈ , что для любого слова w C∈ выполняется равенство 0 0v w v= , а для любого слова w L∈ вершина 0v w является висячей (т.е. ее степень равна 1). Далее в работе термином “пара” подразумевается именно такая пара множеств, а сами множества C и L будут называться компонентами пары. Очевидно, что в этом случае все слова множества C начинаются и за- канчиваются символом 0( )vξ и все слова множества L начинаются символом 0( )vξ . В дальнейшем для краткости в формулах мы не всегда будем явно указывать в паре имя по- рождающей вершины и вместо 0{ , }( )C L v писать { , }C L ; также будем говорить, что пара 0{ , }( )C L v порождена вершиной 0v . Определим процедуру, которая по C и L либо строит Д-граф 0({ , }( ))G C L v , либо по- ка зывает, что по этой паре Д-граф построить невозможно. Процедура состоит из четы- рех этапов. Положим, что изначально граф 0({ , }( ))G C L v состоит из единственной вершины 0v с меткой 0( )v x′ξ = . 20 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2019. № 11 С.В. Сапунов, А.С. Сенченко Этап 1. Для каждого слова 1 1 i i i np x x x x C−′ ′= ∈ добавляем 1n− вершину 1 1, ,i i nv v − с метками со- ответственно 1 1 i i nx x − , n ребер 0 1 1 2( , ), ( , ), ,i i iv v v v  2 1 1 0( , ), ( , )i i i n n nv v v v− − − и детерминизируем получив- шийся граф. Этап 2. В графе, полученном на этапе 1, могут существовать висячие вершины. Каждую такую вер шину v , отличную от порождающей вершины 0v , помещаем в изначально пустое множество Q . Этап 3. Для каждого слова 1 1 j j j np x x x L−= ∈′  добавляем 1n− вершину 1 1, ,j j nv v − с метками со- ответственно 1 1 j j nx x − , 1n− ребро 0 1( , ), ,jv v  2 1( , )j j n nv v− − и детерминизируем получив- шийся граф. Если в результате детерминизации вершина 0 jv p не является висячей, то счи- таем, что Д-граф 0({ , }( ))G C L v не существует и процедура завершается, в противном слу- чае переходим к следующему слову множества L . Этап 4. Для каждой вершины v Q∈ исследуем все слова множества L : если не сущест- вует такого p L∈ , что для некоторого p p′ ⊆ выполняется 0v p v′ = , то считаем, что Д-граф 0({ , }( ))G C L v не существует. Если функция 0({ , }( ))C L vδ определена, то пару 0{ , }( )C L v назовем правильной. Правильную пару { , }C L назовем определяющей для Д-графа G , если ({ , })G C L G≅ . Отметим, что такое задание Д-графа определяющей парой в некоторой степени аналогично представлению автоматов системой определяющих соотношений, рассмотренному в [10]. В случае, когда { , }C L является определяющей парой для G , слова множества C описы- вают циклы базы ( )B G , а слова множества L — все свободные вершины. На первом этапе построения графа 0({ , }( ))G C L v строятся все базовые и, возможно, некоторые свободные вершины графа G , на втором этапе из свободных вершин, (если такие существуют) выделя- ются висячие вершины, на третьем этапе строятся остальные свободные вершины G , чет- вертый этап является проверкой корректности пары ({ , })G C L . Приведем пример построения графа ({ , })G C L . Пример 1. Пусть {41241525314,413214}C = и {41243,4123521}L = . На рис. а изображен граф, полученный после выполнения этапа 1 построения графа ({ , })G C L , выделенная вер- шина v является висячей, и она отлична от вершины 0v , поэтому после выполнения этапа 2 вершину v помещаем в множество Q . На рис. б изображен граф, полученный после выполнения этапа 3 построения ({ , })G C L , и поскольку 4123521 L∈ , 412352 4123521⊆ и 0 412352v v= , то после выполнения этапа 4 считаем, что ({ , })G C L существует и изображен на рис. б. Построение канонической определяющей пары. Далее пусть ( , , , ( ))G V E X V= ξ — некоторый Д-граф. Положим 1 2 nx x x� � � — ли- нейный порядок на X . Введем на X∗ лексикографический линейный порядок � таким образом: 1) i ix x� ; 2) если ( ) ( )d p d q< , то p q� ; Иллюстрация построения G({C, L}): а — этапы 1, 2; б — этапы 3, 4 21ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2019. № 11 Лингвистическое представление графов с помеченными вершинами 3) 1 1s sx x p q x x′ ′ ′ ′= = � , если k kx x′ ′′� для некоторого k s� , в то время как 1x′ = 1 1 1, , k kx x x− −′′ ′ ′′= = . Очевидно, что лексикографический порядок на X∗ однозначно определяется линей- ным порядком на X . Покажем, что G имеет хотя бы одну определяющую пару. В качестве порождающей вы- берем в G произвольную вершину 0v . Каждую вершину v графа G именуем кратчайшим по введенному порядку � словом p , для которого 0v p v= , то есть строим кратчайший по порядку � базис достижимости вершин графа G , который обозначим 0( )GV v . Пусть изначально множества GΣ и GΛ пустые. Все такие слова 0( )Gp V v∈ , что пути 0v p ведут в висячую вершину, помещаем в множество GΛ . Далее, для каждого слова 0( )G Gp V v∈ −Λ рассматриваем вершины множества 0( )E v p : если 0( )Gp V v′∈ , 0 0( )v p E v p′ = , p p′ ≠ и 0( )p v p p′ξ ≠ , то циклическое для вершины 0v слово 1( )p p −′ помещаем в мно- жест во GΣ (заметим, что неравенство p p′ ≠ может выполняться только в том случае, ког- да ве ршина 0v p′ принадлежит базе графа G ). После этого, из всех пар взаимнообратных слов p и 1p− множества GΣ оставляем одно, кратчайшее по порядку � , а другое исклю- чаем. Также исключим повторы слов в GΣ , оставляя по одному экземпляру. Обратим вни- мание, что для каждого слова Gp∈Σ из q p⊆ следует, что вершина 0v q принадлежит базе ( )B G . Полученную пару 0{ , }( )G G vΣ Λ назовем канонической для графа G , порожденной вер шиной 0v . Теорема 1. Пара { , }G GΣ Λ является определяющей для графа G . Характеризация определяющей пары. Под характеризацией определяющей пары по- нимаем следующую задачу: задан Д-граф и задана некоторая пара. Необходимо опреде- лить, является ли эта пара определяющей для данного графа. Было найдено решение этой задачи для случая, когда в заданном графе известна вершина, являющаяся инициальной для заданной пары. Для решения вышеуказанной задачи на множестве слов из обоих компонент пары { , }C L введем такие операции редукции (в определении операций считаем, что , ,p p q X′ ∈ и ,x x X′∈ ): 1) Слово pxx xp′ ′ из любой компоненты пары заменим в этой компоненте словом pxp′ . 2) Если p C∈ и 1p p− � , то в C слово p заменим словом 1p− . 3) Пусть слово pxp C′∈ и 1( )p p−′ � . Тогда слово pxq из любой компоненты пары при q p′≠ заменим в этой компоненте словом 1( )p xq−′ . 4) Удалим из C и L повторяющиеся слова, оставляя по одному экземпляру. Операции редукции выполняются над словами обоих компонент пары в циклическом порядке до тех пор, пока это возможно. Несложно видеть, что все операции редукции умень- шают количество (операция 4) или длину (операция 1, возможно, операция 3) слов в каж- дой из компонент пары, или заменяют подслова слов в компоненте на подслово такой же длины, но меньшее по порядку � (операция 2, возможно, операция 3), поэтому для конеч- ных C и L за конечное число шагов процедура редукции завершается. Получившуюся в результате пару обозначим ,C L〈 〉 . Теорема 2. Для любой пары { , }C L пара ,C L〈 〉 определяется однозначно. Пусть пара { , }C L′ ′ получена из правильной пары { , }C L однократным применением некоторой операции редукции 1—4. Несложно видеть, что если существует ({ , })G C L , то существует и ({ , })G C L′ ′ и ({ , }) ({ , })G C L G C L′ ′ ≅ . 22 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2019. № 11 С.В. Сапунов, А.С. Сенченко Теорема 3. Для любой правильной пары { , }C L выполняется ( , ) ({ , })G C L G C L〈 〉 ≅ . Решением задачи характеризации пары для указанного выше случая является следую- щая теорема. Теорема 4. Правильная пара 0{ , }( )C L v является определяющей для Д-графа G тогда, и только тогда 0 0, ( ) { , }( )G GC L v v〈 〉 = Σ Λ . Следствие 4.1. Пара 0{ , }( )G G vΣ Λ является минимальной определяющей парой для гра- фа G по мощности множества G GΣ Λ и по сумме длин слов, входящих в множество G GΣ Λ . Таким образом, каноническая определяющая пара 0{ , }( )G G vΣ Λ играет центральную роль среди всех определяющих пар графа G , порожденных вершиной 0v . При этом ес- тественным образом возникает целый ряд задач, связанных с представлением Д-графов определяющей парой, среди которых авторы выделяют такие задачи: нахождение необходимых и достаточных условий для множеств C и L, при которых пара { , }C L является правильной; для графа G с заданными параметрами (количество вершин, ребер, количество различ- ных значений функции разметки и т.д.) определить верхние и нижние границы количества и суммарной длины слов множества G GΣ Λ ; оптимальный выбор инициальной вершины, при котором указанные в предыдущем пункте оценки будут минимальными; эффективное построение по { , }G GΣ Λ кратчайших по порядку � путей между двумя произвольными вершинами графа G ; решение задачи характеризации пары для случая, когда в заданном графе явно не указа- на инициальная вершина пары. Таким образом, в настоящей работе предложено лингвистическое представление Д-гра- фов определяющей парой, которая является аналогом системы определяющих соотноше- ний для всюдуопределенных автоматов. Найдены процедура построения минимальной (канонической) определяющей пары для графа и процедура преобразования произволь- ной определяющей пары графа к канонической. Полученные результаты являются рас- пространением соответствующих задач теории автоматов на графы с помеченными вер- шинами. Такое представление позволяет задействовать новые методы и алгоритмы для ре- шения задач анализа графов с помеченными вершинами. ЦИТИРОВАННАЯ ЛИТЕРАТУРА 1. Letichevsky A. Algebra of behavior transformation and its application. Structural Theory of Automata, Se- migroups, and Universal Algebra. Kudryavtsev V.B., Rosenberg I.G., Goldstein M. (Eds). NATO Science Series II: Mathematics, Physics and Chemistry. Dordrecht: Springer. 2005. 207, P. 241—272. https://doi. org/10.1007/1-4020-3817-8_10 2. Droste M., Kuich W., Vogler H. Handbook of Weighted Automata. Berlin, Heidelberg: Springer, 2009. 608 p. https://doi.org/10.1007/978-3-642-01492-5 3. Dudek G., Jenkin M. Computational Principles of Mobile Robotics, 2nd ed. Cambridge: Cambridge Univ. Press, 2010. 406 p. https://doi.org/10.1017/CBO9780511780929 4. Baier C., Katoen J.-P. Principle of Model Checking. Cambridge: MIT Press, 2008. 984 p. 5. Капитонова Ю.В., Летичевский А.А. Математическая теория проектирования вычислительных сис- тем. Москва : Наука, 1988. 298 с. 6. Kilibarda G., Kudryavtsev V.B., Ushchumlich Sh. Collectives of automata in labyrints. Discrete Math. and Appl. 2003. 15, Iss. 5. P. 429—466. https://doi.org/10.1515/156939203322694736 23ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2019. № 11 Лингвистическое представление графов с помеченными вершинами 7. Grunskii I., Mikhaylova I., Sapunov S. Domination on the vertices of labeled graphs. Algebra and Discrete Math. 2012. 15, № 2. P. 174—184. 8. Stepkin A.V. Using a Collective of Agents for Exploration of Undirected Graphs. Cybernetics and System Analysis. 2015. 51, Iss. 2. P. 223—233. https://doi.org/10.1007/s10559-015-9715-z 9. Сапунов С.В. Восстановление графа с помеченными вершинами перемещающимся по нему мобиль- ным агентом. Изв. Саратов. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2015. 15, Вып. 2. С. 228—238. https://doi.org/10.18500/1816-9791-2015-15-2-228-238 10. Grunskii I.S., Senchenko A.S. Properties of systems of defining relations for automata. Discrete Math. and Appl. 2004. Vol. 14, Iss. 6. P. 593—601. https://doi.org/10.1515/1569392043272458 11. Albers S., Henzinger M.R. Exploring Unknown Environments. SIAM J. Computing. 2000. 29, № 4. P. 1164— 1188. https://doi.org/10.1137/s009753979732428x Поступило в редакцию 28.08.2019 REFERENCES 1. Letichevsky, A. (2005). Algebra of behavior transformation and its application. In Kudryavtsev V.B., Rosenberg I.G., Goldstein M. (Ed.) Structural Theory of Automata, Semigroups, and Universal Algebra. NATO Science Series II: Mathematics, Physics and Chemistry, Vol. 207, pp. 241-272, Dordrecht: Springer. https://doi.org/10.1007/1-4020-3817-8_10 2. Droste, M., Kuich, W. & Vogler, H. (2009). Handbook of Weighted Automata. Berlin, Heidelberg: Springer. https://doi.org/10.1007/978-3-642-01492-5 3. Dudek, G. & Jenkin, M. (2010). Computational Principles of Mobile Robotics, 2nd ed. Cambridge: Cambridge Univ. Press. https://doi.org/10.1017/CBO9780511780929 4. Baier, C. & Katoen, J.-P. (2008). Principle of Model Checking. Cambridge: MIT Press. 5. Kapitonova, Yu. V. & Letichevsky, A. A. (1988). Mathematical theory of computer systems design. Moscow: Nauka (in Russian). 6. Kilibarda, G., Kudryavtsev, V. B. & Ushchumlich, Sh. (2003). Collectives of automata in labyrints. Discrete Math. and Appl., 13, Iss. 5, pp. 429-466. https://doi.org/10.1515/156939203322694736 7. Grunskii, I., Mikhaylova, I. & Sapunov, S. (2012). Domination on the vertices of labeled graphs. Algebra and Discrete Mathematics, 15, No. 2, pp. 174-184. 8. Stepkin, A. V. (2015). Using a Collective of Agents for Exploration of Undirected Graphs. Cybernetics and System Analysis, 51, Iss. 2, pp. 223-233. https://doi.org/10.1007/s10559-015-9715-z 9. Sapunov, S. V. (2015). Reconstruction of a Labeled Graph by a Graph-walking Mobile Agent. Izvestiya of Saratov University. New Series. Series: Mathematics. Mechanics. Informatics, 15, Iss. 2, pp. 228-238 (in Russian). https://doi.org/10.18500/1816-9791-2015-15-2-228-238 10. Grunskii, I.,S. & Senchenko, A.,S. (2004). Properties of systems of defining relations for automata. Discrete Math. and Appl., 14, Iss. 6, pp. 593-601. https://doi.org/10.1515/1569392043272458 11. Albers, S. & Henzinger, M. R. (2000). Exploring Unknown Environments. SIAM Journal on Computing, 29, No. 4, pp. 1164-1188. https://doi.org/ 10.1137/s009753979732428x Received 28.08.2019 С.В. Сапунов, О.С. Сенченко Інститут прикладної математики і механіки НАН України, Слов’янськ E-mail: sapunov_sv@ukr.net, senchenko.a76@gmail.com ЛІНГВІСТИЧНЕ ЗОБРАЖЕННЯ ГРАФІВ З ПОМІЧЕНИМИ ВЕРШИНАМИ В роботі введено лінгвістичне зображення Д-графів, у яких в околі кожної вершини всі вершини мають різні мітки, визначальною парою множин слів, перша з яких описує цикли графа, а друга — усі його висячі вершини. Запропоновано процедуру, яка за заданою парою множин або будує відповідний їй Д-граф, або показує, що за цією парою неможливо побудувати Д-граф. Знайдено процедуру побудови мінімальної (канонічної) визначальної пари для графа та процедуру перетворення довільної визначальної пари графа до канонічної. Одержані результати є розповсюдженням відповідних задач теорії автоматів на графи з 24 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2019. № 11 С.В. Сапунов, А.С. Сенченко поміченими вершинами та дозволяють використовувати нові методи та алгоритми для розв’язання задач аналізу графів з поміченими вершинами. Ключові слова: графи з поміченими вершинами, визначальна пара, зображення графів. S.V. Sapunov, A.S. Senchenko Institute of Applied Mathematics and Mechanics of the NAS of Ukraine, Slov’yansk E-mail: sapunov_sv@ukr.net, senchenko.a76@gmail.com LINGUISTIC REPRESENTATION OF VERTEX-LABELED GRAPHS The representation of deterministic graphs (D-graphs) by sets of words over the vertex labels alphabet is stu- died. A vertex-labeled graph is said to be a D-graph, if all vertices in the neighborhood of every its vertex have different labels. Vertex-labeled graphs are widely used in the modeling of various computational processes in programming, robotics, model checking, etc. In such models, graphs play the role of an information environ- ment of single or several mobile agents. Walks of agents on a graph determine the sequence of vertices labels or words in the alphabet of labels. For D-graphs in case where the graph as a whole and the initial vertex (i.e. the vertex, from which the agent started walking) are known, there exists the one-to-one correspondence between the sequence of vertices visited by the agent and the trajectory of its walks on the graph. In the case where the D-graph is not known as a whole, the agent walks on it can be arranged in such way that an observer obtains information about the structure of the graph sufficient to solve the problems of graph recognizing, finding the op timal path between vertices, comparison between current graph and etalon graph, etc. In this paper, the lin- guistic representation of D-graphs by the defining pair of sets of words (the first describes cycles of the graph and the second — all its vertices of degree 1) is introduced. This representation is an analog of the system of de- fining re lations for everywhere defined automata. A procedure that either constructs a D-graph using a given pair of sets or shows that it is impossible to construct a D-graph from this pair is proposed. A procedure for con- structing a minimal (canonical) defining pair for a graph and a procedure for converting an arbitrary defining pair of a graph to the canonical one are found. The obtained results are the extension of corresponding problems of the automata theory to vertex-labeled graphs. This representation allows us to use new methods and algo- rithms to solve the problems of analyzing vertex-labeled graphs. Keywords: vertex-labeled graphs, defining pair, graph representation.

Лингвистическое представление графов с помеченными вершинами

Репозитарії

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