Vol. 8, No 1: 15–20.

Mathematics and Mechanics

 2023

Scientific article

UDK 519.16
pdf-version

Sergei S. Masaev
bachelor’s degree, Petrozavodsk State University
(Petrozavodsk, Russia),
masser13@yandex.ru

Combinatorial substitution of the patrol problem on a nonlinear graph

Scientific adviser:
Julia A. Dorofeeva
Paper submitted on: 03/29/2022;
Accepted on: 04/02/2023;
Published online on: 04/15/2023.
 Abstract. The paper presents the task of patrolling in a combinatorial formulation. To implement the task, the algorithms for bypassing the graph in depth and Dijkstra are used. There are two competitors in the task - patrolling and attacking. As a platform for movement, six interconnected graphs are used, each of which is a prototype of one of the microdistricts of the city of Petrozavodsk. As part of the study of the problem, the probability of catching an attacker in each and every district of the city is calculated.
Keywords: graph, Dijkstra's algorithm, depth-first search, patrolling, probability, combinatorics

For citation: Masaev, S. S. Combinatorial substitution of the patrol problem on a nonlinear graph. StudArctic forum. 2023, 8 (1): 15–20.

Displays: 329; Downloads: 88;