Исследование структуры графа при помощи двух агентов
В работе рассматривается решение задачи распознавания конечных неориентированных графов двумя агентами. Один агент-исследователь передвигается по графу, считывает и изменяет метки элементов графа и передает информацию о своих действиях агенту-экспериментатору, который строит представление исследуемо...
Збережено в:
| Опубліковано в: : | Труды Института прикладной математики и механики |
|---|---|
| Дата: | 2016 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2016
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/140863 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Исследование структуры графа при помощи двух агентов / А.В. Стёпкин // Труды Института прикладной математики и механики НАН Украины. — Слов’янськ: ІПММ НАН України, 2016. — Т. 30. — С. 111-121. — Бібліогр.: 12 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862617740889554944 |
|---|---|
| author | Стёпкин, А.В. |
| author_facet | Стёпкин, А.В. |
| citation_txt | Исследование структуры графа при помощи двух агентов / А.В. Стёпкин // Труды Института прикладной математики и механики НАН Украины. — Слов’янськ: ІПММ НАН України, 2016. — Т. 30. — С. 111-121. — Бібліогр.: 12 назв. — рос. |
| collection | DSpace DC |
| container_title | Труды Института прикладной математики и механики |
| description | В работе рассматривается решение задачи распознавания конечных неориентированных графов двумя агентами. Один агент-исследователь передвигается по графу, считывает и изменяет метки элементов графа и передает информацию о своих действиях агенту-экспериментатору, который строит представление исследуемого графа. Предложен алгоритм квадратической (от числа вершин графа) временной, емкостной и коммуникационной сложностей, который распознает любой конечный неориентированный граф. Для распознавания графа требуется 2 различные краски. Метод основан на методе обхода графа в глубину.
В роботі розглядається розв’язок задачі розпізнавання скінчених неорієнтованих графів двома агентами. Один агент-дослідник рухається графом, зчитує та змінює помітки на елементах графу та передає інформацію про свої дії агенту-експериментатору, який будує уявлення про досліджуваний граф. Пропонується алгоритм квадратичної (від кількості вершин графу) часової, ємнісної та комунікаційної складностей, який розпізнає довільний скінчений неорієнтований граф. Для розпізнавання графу необхідно дві різні фарби. Метод базується на методі обходу графа в глибину.
This paper considers the problem of exploration of finite undirected graphs by two agents. One agentresearcher traverse a graph, read and change labels of graph elements, and send necessary information to the agent-experimenter constructing a representation of the graph being explored. An exploration algorithm is proposed with a quadratic (with respect to the number of nodes) time complexity, space complexity and communication complexity. An algorithm is proposed explored any finite undirected graph. Graph’s exploring needs two different colors. The algorithm is based on the depth-first traversal method.
|
| first_indexed | 2025-12-07T13:12:51Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-140863 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1683-4720 |
| language | Russian |
| last_indexed | 2025-12-07T13:12:51Z |
| publishDate | 2016 |
| publisher | Інститут прикладної математики і механіки НАН України |
| record_format | dspace |
| spelling | Стёпкин, А.В. 2018-07-17T11:35:45Z 2018-07-17T11:35:45Z 2016 Исследование структуры графа при помощи двух агентов / А.В. Стёпкин // Труды Института прикладной математики и механики НАН Украины. — Слов’янськ: ІПММ НАН України, 2016. — Т. 30. — С. 111-121. — Бібліогр.: 12 назв. — рос. 1683-4720 https://nasplib.isofts.kiev.ua/handle/123456789/140863 519.7 В работе рассматривается решение задачи распознавания конечных неориентированных графов двумя агентами. Один агент-исследователь передвигается по графу, считывает и изменяет метки элементов графа и передает информацию о своих действиях агенту-экспериментатору, который строит представление исследуемого графа. Предложен алгоритм квадратической (от числа вершин графа) временной, емкостной и коммуникационной сложностей, который распознает любой конечный неориентированный граф. Для распознавания графа требуется 2 различные краски. Метод основан на методе обхода графа в глубину. В роботі розглядається розв’язок задачі розпізнавання скінчених неорієнтованих графів двома агентами. Один агент-дослідник рухається графом, зчитує та змінює помітки на елементах графу та передає інформацію про свої дії агенту-експериментатору, який будує уявлення про досліджуваний граф. Пропонується алгоритм квадратичної (від кількості вершин графу) часової, ємнісної та комунікаційної складностей, який розпізнає довільний скінчений неорієнтований граф. Для розпізнавання графу необхідно дві різні фарби. Метод базується на методі обходу графа в глибину. This paper considers the problem of exploration of finite undirected graphs by two agents. One agentresearcher traverse a graph, read and change labels of graph elements, and send necessary information to the agent-experimenter constructing a representation of the graph being explored. An exploration algorithm is proposed with a quadratic (with respect to the number of nodes) time complexity, space complexity and communication complexity. An algorithm is proposed explored any finite undirected graph. Graph’s exploring needs two different colors. The algorithm is based on the depth-first traversal method. ru Інститут прикладної математики і механіки НАН України Труды Института прикладной математики и механики Исследование структуры графа при помощи двух агентов Дослідження структури графа за допомогою двох агентів Exploration of the graph structure by two agents Article published earlier |
| spellingShingle | Исследование структуры графа при помощи двух агентов Стёпкин, А.В. |
| title | Исследование структуры графа при помощи двух агентов |
| title_alt | Дослідження структури графа за допомогою двох агентів Exploration of the graph structure by two agents |
| title_full | Исследование структуры графа при помощи двух агентов |
| title_fullStr | Исследование структуры графа при помощи двух агентов |
| title_full_unstemmed | Исследование структуры графа при помощи двух агентов |
| title_short | Исследование структуры графа при помощи двух агентов |
| title_sort | исследование структуры графа при помощи двух агентов |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/140863 |
| work_keys_str_mv | AT stepkinav issledovaniestrukturygrafapripomoŝidvuhagentov AT stepkinav doslídžennâstrukturigrafazadopomogoûdvohagentív AT stepkinav explorationofthegraphstructurebytwoagents |