Abstract:
Problem of exploration finite undirected graphs by a collective of agents is considered in this work. Two agents-researchers simultaneously move on graph, they read and change marks of graph elements, transfer the information to the agent-experimenter (it builds explored graph representation). It was constructed an algorithm linear (from amount of the graph’s nodes) time complexity, quadratic space complexity andcommunication complexity, that is equal to $O(n^2 \cdot log(n))$. Two agents (which move on graph) need two differentcolors (in total three colors) for graph exploration. An algorithm is based on depth-first traversal method.