An Algorithm for Recognizing Undirected Graphs by a Multiagent System

The problems of graph recognition by multi-agent systems are considered. An algorithm for recognizing simple undirected graphs by a team of agents consisting of two agents of different types: a researcher agent and an experimenter agent is proposed. A researcher agent can move around the graph, read and change the color of graph elements, and exchange messages with another agent. The experimenter agent is an agent that is outside the graph and can exchange messages with the research agent, based on which it builds a map of the graph in its memory in the form of lists of edges and vertices. The researcher agent has a finite memory and uses only one paint. The experimental agent has a finite and unlimitedly growing memory at each step, the amount of which depends on the graph's dimension. The algorithm has quadratic time, capacity, communication complexity, and the number of edge transitions made by the research agent. The algorithm is based on the depth-first method.