Лингвистическое представление графов с помеченными вершинами
В работе вводится лингвистическое представление Д-графов, у которых в окрестности каждой вершины
 все вершины имеют разные метки, определяющей парой множеств слов, первое из которых описывает циклы графа, а второе — все его висячие вершины. Предложена процедура, которая по заданной паре множ...
Saved in:
| Published in: | Доповіді НАН України |
|---|---|
| Date: | 2019 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Видавничий дім "Академперіодика" НАН України
2019
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/162647 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Лингвистическое представление графов с помеченными вершинами / С.В. Сапунов, А.С. Сенченко // Доповіді Національної академії наук України. — 2019. — № 11. — С. 17-24. — Бібліогр.: 11 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862583794555420672 |
|---|---|
| author | Сапунов, С.В. Сенченко, А.С. |
| author_facet | Сапунов, С.В. Сенченко, А.С. |
| citation_txt | Лингвистическое представление графов с помеченными вершинами / С.В. Сапунов, А.С. Сенченко // Доповіді Національної академії наук України. — 2019. — № 11. — С. 17-24. — Бібліогр.: 11 назв. — рос. |
| collection | DSpace DC |
| container_title | Доповіді НАН України |
| description | В работе вводится лингвистическое представление Д-графов, у которых в окрестности каждой вершины
все вершины имеют разные метки, определяющей парой множеств слов, первое из которых описывает циклы графа, а второе — все его висячие вершины. Предложена процедура, которая по заданной паре множеств либо строит соответствующий ей Д-граф, либо показывает, что по этой паре Д-граф построить
невозможно. Найдены процедура построения минимальной (канонической) определяющей пары для графа
и процедура преобразования произвольной определяющей пары графа к канонической. Полученные результаты являются распространением соответствующих задач теории автоматов на графы с помеченными
вершинами и позволяют задействовать новые методы и алгоритмы для решения задач анализа графов с помеченными вершинами.
У роботі введено лінгвістичне зображення Д-графів, у яких в околі кожної вершини всі вершини мають
різні мітки, визначальною парою множин слів, перша з яких описує цикли графа, а друга — усі його висячі
вершини. Запропоновано процедуру, яка за заданою парою множин або будує відповідний їй Д-граф, або
показує, що за цією парою неможливо побудувати Д-граф. Знайдено процедуру побудови мінімальної
(канонічної) визначальної пари для графа та процедуру перетворення довільної визначальної пари графа
до канонічної. Одержані результати є розповсюдженням відповідних задач теорії автоматів на графи з
поміченими вершинами та дозволяють використовувати нові методи та алгоритми для розв'язання задач
аналізу графів з поміченими вершинами.
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.
|
| first_indexed | 2025-11-26T23:51:14Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-162647 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1025-6415 |
| language | Russian |
| last_indexed | 2025-11-26T23:51:14Z |
| publishDate | 2019 |
| publisher | Видавничий дім "Академперіодика" НАН України |
| record_format | dspace |
| spelling | Сапунов, С.В. Сенченко, А.С. 2020-01-13T10:04:40Z 2020-01-13T10:04:40Z 2019 Лингвистическое представление графов с помеченными вершинами / С.В. Сапунов, А.С. Сенченко // Доповіді Національної академії наук України. — 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 В работе вводится лингвистическое представление Д-графов, у которых в окрестности каждой вершины
 все вершины имеют разные метки, определяющей парой множеств слов, первое из которых описывает циклы графа, а второе — все его висячие вершины. Предложена процедура, которая по заданной паре множеств либо строит соответствующий ей Д-граф, либо показывает, что по этой паре Д-граф построить
 невозможно. Найдены процедура построения минимальной (канонической) определяющей пары для графа
 и процедура преобразования произвольной определяющей пары графа к канонической. Полученные результаты являются распространением соответствующих задач теории автоматов на графы с помеченными
 вершинами и позволяют задействовать новые методы и алгоритмы для решения задач анализа графов с помеченными вершинами. У роботі введено лінгвістичне зображення Д-графів, у яких в околі кожної вершини всі вершини мають
 різні мітки, визначальною парою множин слів, перша з яких описує цикли графа, а друга — усі його висячі
 вершини. Запропоновано процедуру, яка за заданою парою множин або будує відповідний їй Д-граф, або
 показує, що за цією парою неможливо побудувати Д-граф. Знайдено процедуру побудови мінімальної
 (канонічної) визначальної пари для графа та процедуру перетворення довільної визначальної пари графа
 до канонічної. Одержані результати є розповсюдженням відповідних задач теорії автоматів на графи з
 поміченими вершинами та дозволяють використовувати нові методи та алгоритми для розв'язання задач
 аналізу графів з поміченими вершинами. 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. ru Видавничий дім "Академперіодика" НАН України Доповіді НАН України Інформатика та кібернетика Лингвистическое представление графов с помеченными вершинами Лінгвістичне зображення графів з поміченими вершинами Linguistic representation of vertex-labeled graphs Article published earlier |
| spellingShingle | Лингвистическое представление графов с помеченными вершинами Сапунов, С.В. Сенченко, А.С. Інформатика та кібернетика |
| title | Лингвистическое представление графов с помеченными вершинами |
| title_alt | Лінгвістичне зображення графів з поміченими вершинами Linguistic representation of vertex-labeled graphs |
| title_full | Лингвистическое представление графов с помеченными вершинами |
| title_fullStr | Лингвистическое представление графов с помеченными вершинами |
| title_full_unstemmed | Лингвистическое представление графов с помеченными вершинами |
| title_short | Лингвистическое представление графов с помеченными вершинами |
| title_sort | лингвистическое представление графов с помеченными вершинами |
| topic | Інформатика та кібернетика |
| topic_facet | Інформатика та кібернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/162647 |
| 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 |