Исследование структуры графа при помощи двух агентов

Исследование структуры графа при помощи двух агентов

В работе рассматривается решение задачи распознавания конечных неориентированных графов двумя агентами. Один агент-исследователь передвигается по графу, считывает и изменяет метки элементов графа и передает информацию о своих действиях агенту-экспериментатору, который строит представление исследуемо...

Full description

Saved in:
Bibliographic Details
Published in:Труды Института прикладной математики и механики
Date:2016
Main Author: Стёпкин, А.В.
Format: Article
Language:Russian
Published: Інститут прикладної математики і механіки НАН України 2016
Online Access:https://nasplib.isofts.kiev.ua/handle/123456789/140863
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:Исследование структуры графа при помощи двух агентов / А.В. Стёпкин // Труды Института прикладной математики и механики НАН Украины. — Слов’янськ: ІПММ НАН України, 2016. — Т. 30. — С. 111-121. — Бібліогр.: 12 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-140863
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
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Исследование структуры графа при помощи двух агентов
spellingShingle Исследование структуры графа при помощи двух агентов
Стёпкин, А.В.
title_short Исследование структуры графа при помощи двух агентов
title_full Исследование структуры графа при помощи двух агентов
title_fullStr Исследование структуры графа при помощи двух агентов
title_full_unstemmed Исследование структуры графа при помощи двух агентов
title_sort исследование структуры графа при помощи двух агентов
author Стёпкин, А.В.
author_facet Стёпкин, А.В.
publishDate 2016
language Russian
container_title Труды Института прикладной математики и механики
publisher Інститут прикладної математики і механіки НАН України
format Article
title_alt Дослідження структури графа за допомогою двох агентів
Exploration of the graph structure by two agents
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.
issn 1683-4720
url https://nasplib.isofts.kiev.ua/handle/123456789/140863
citation_txt Исследование структуры графа при помощи двух агентов / А.В. Стёпкин // Труды Института прикладной математики и механики НАН Украины. — Слов’янськ: ІПММ НАН України, 2016. — Т. 30. — С. 111-121. — Бібліогр.: 12 назв. — рос.
work_keys_str_mv AT stepkinav issledovaniestrukturygrafapripomoŝidvuhagentov
AT stepkinav doslídžennâstrukturigrafazadopomogoûdvohagentív
AT stepkinav explorationofthegraphstructurebytwoagents
first_indexed 2025-12-07T13:12:51Z
last_indexed 2025-12-07T13:12:51Z
_version_ 1850855308968067072

Similar Items