| 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: 570; Downloads: 167;
|
|