Stepkin A. Graphs exploration with the help of the collective of agents.

The thesis is devoted to the actual problem of graph exploration by the collective of agents, that are moved by edges of the graph. A new method of graph exploration with the help of constructing of implicit numbering on its nodes is proposed. On the basis of this method the basic algorithm is developed. For the first time, along with time and space complexities and the number of agent's transitions by edges, the communication complexity is studied. This complexity is determined by the quantity and capacity of messages, which are essential to be exchanged by agents for the graph exploration. It has been proved, that the algorithm has cubic from amount of the graph's nodes, time and communication complexities, quadratic space complexity and cubic upper bound of the number of transitions by edges. Tree modifications of the basic algorithm has been built, which reduce the upper bound of the concerned complexities. A problem of one of an agent's standstill in case when their location doesn't allow to explore the graph in equal parts and one of the agents has to stand while another agent continues the exploration, is considered for the first time. A procedure of the solution of this problem with the help of agents' search of unexplored subgraphs has been proposed.