## 4 Reduction to Graph Problems  
Consider an infinite weighted periodic graph \(G_{\infty}\), which is constructed as follows: \(G_{\infty}=(N_{\infty},\,A_{\infty})\), where \(N_{\infty}\) is an infinite set of nodes and \(A_{\infty}\) is an infinite set of arcs. In this graph, node \(i_{k}\in N_{\infty}\) represents the \(k\)th iteration of task \(J_{i}\). A directed arc \((i_{k},j_{l})\in A_{\infty}\) leads from node \(i_{k}\) to node \(j_{l}\) if the vehicle is able to carry out the \(l\)th iteration of task \(J_{i}\) after it has completed the \(k\)th iteration of task \(J_{i}\). The weight of the arc \((i_{k},j_{l})\) represents the profit \(e_{ij}\) collected by the vehicle from serving the task \(J_{i}\) following the task \(J_{i}\). Let us formulate all profits \(e_{ij}\) in the form of the \(n\times n\) matrix \(\mathbf{E}=\|e_{ij}\|\). Consider a periodic directed chain in graph \(G_{\infty}\). Note that the period of such a chain can span several periods, \(p\), as defined in the previous section. The chain determines the schedule of an individual vehicle visiting a sequence of tasks, and the sum of its arc weights \(e_{ij}\) determines the profit earned by that vehicle during that period. The set of directed chains in \(G_{\infty}\) covering all nodes determines the total number of required vehicles, their schedule,and the total environmental benefit obtained. Thus, the original allocation Problem **1** is reduced to the following graph-theoretic problem on the infinite graph \(G_{\infty}\):  
**Problem 2**. : _Find a periodic infinite chain cover of graph \(G_{\infty}\) that maximizes the following average environmental benefit (profit) obtained by the UAV fleet:_  
\[E/K\ =\ \frac{\text{Total environmental profit obtained by the UAV fleet in period $p$}}{\text{Number of vehicles required}}\ =\ \frac{\text{Sum of arc weights $e_{ij}$ in chain cover in period $p$}}{\text{Number of directed chains covering nodes}}\]  
The next step is to transform the infinite graph \(G_{\infty}\) into an equivalent finite graph. Due to the periodicity of the graph \(G_{\infty}\), we can roll it up into the so-called finite _generating graph_, \(G_{gen}=(N_{gen},A_{gen})\), defined as follows: node \(i\in N_{gen}\) represents all periodic implementations of task \(I_{j}\); in other words, all nodes \(i_{k}\in N_{\infty}\), \(0\leq k<\infty\), of the infinite graph \(G_{\infty}\) are \"packed\" into one node \(i\) of the graph \(G_{gen}\). Similarly, all arcs \((i_{k},I_{j})\in A_{\infty}\) are \"packed\" into one arc \((i,j)\)\(\in A_{gen}\). Thus, every infinite, periodically repeated arc chain in graph \(G_{\infty}\) can be transformed into a corresponding directed cycle in graph \(G_{gen}\). Knowing the generating graph \(G_{gen}\), we can transform Problem **2** of covering graph \(G_{\infty}\) with chains into the following Problem **3** of covering the nodes of the graph \(G_{gen}\) with cycles. Let \(\mathbf{c}\) denote a set of such cycles. **Problem 3**. : _Find a covering of the nodes of the graph \(G_{gen}\) with a set of cycles \(\mathbf{c}\) so as to maximize the ratio._  
\[E/K\ =\ \frac{\sum_{(i,j)\in\mathbf{c}}\ e_{ij}}{\text{Number of required vehicles}}\]  
Next, we associate two weights with each arc \((i,j)\in A_{gen}\). The first weight is the profit \(e_{ij}\) introduced above. The second weight, denoted \(k_{ij}\), is needed to calculate the required number of vehicles. It is defined similarly to the model in [20]; namely, \(k_{ij}\) is the number of periods \(p\) that must exist between an arbitrary departure iteration \(k(i)\) of a flight \(J_{i}\) and the departure iteration \(l(j)\) of the flight \(J_{j}\) that is closest to \(J_{i}\) in the graph \(G_{\infty}\), provided that the two flights are operated by the same aircraft; it is possible that \(j=i\). Then,  
\[k_{ij}=l(j)-k(i). \tag{1}\]  
For the reader's convenience, consider the definition of the weight \(k_{ij}\) in more detail.