## 4 Reduction to Graph Problems
Let \(k(i)\) be an arbitrary integer, and the symbol \(k(i)\) denotes that the flight \(J_{i}\) occurs during the \(k(i)\)-th period. Further, suppose that in graph \(G_{\infty}\), there are arcs from the node representing the flight \(J_{i}\) to all other nodes representing iterations (repetitions) of the flight \(J_{j}\); it is clear that then, in our notation, the numbers \(\{k(j)\}\) will denote the numbers showing in which periods those repetitions of \(J_{j}\) occur. Among these numbers, \(k(j)\), choose the minimum one--this number is denoted as \(l(j)\). Then, as stated above, \(k_{ij}=l(j)-k(i)\). In other words, after completing the \(k(i)\)th iteration of task \(J_{i}\), the vehicle does not have enough time to arrive and carry out the \((l(j)-1)\)th iteration of task \(J_{j}\) but has time to successfully perform the \(l(j)\)th iteration of task \(J_{i}\). **Remark 3**. : _Since the process under consideration is periodic, the values \(k_{ij}\) are valid for all task iterations. As we will show shortly, the sum of \(k_{ij}\) over all cycles in any cycle covered in the graph \(G_{gen}\) is equal to the number of vehicles required to meet a given schedule._  
**Remark 4**. : _Formally, the main property of the parameter \(l(j)\) can be presented as follows: Let \(d_{i}\) denote the duration of the flight, \(J_{i}\), that is,_  
\[d_{i}=b_{i}-a_{i}\text{, if }a_{i}<b_{i}\text{ and }\]  
\[d_{i}=b_{i}+p-a_{i}\text{, if }a_{i}>b_{i}.\]_Then, the following inequalities hold:_  
\[a_{j}+(l(j)-1)\cdot p<a_{i}+k(i)\cdot p+d_{i}+r_{ij}\leq a_{j}+l(j)\cdot p.\]  
_Thus, we introduce the \(n\times n\) matrix \(\mathbf{K}=\|k_{ij}\|\) with the entries \(k_{ij}\) just described. If the arc (\(i\), \(j\)) does not exist in the graph \(G_{gen}\), then we set \(e_{ij}=0\) and \(k_{ij}=\infty\). To obtain this matrix, we need \(O(n^{2})\) time._  
Consider a small example to illustrate the above definition of \(k_{ij}\) in Equation (1). Assume that we have three tasks: \(J_{1},J_{2},J_{3};p=10\), \(a(J_{1})=a_{1}=5\), \(b(J_{1})=b_{1}=8\); \(a(J_{2})=a_{2}=9\), \(b(J_{2})=b_{2}=2\); \(a(J_{3})=a_{3}=4\), \(b(J_{3})=b_{3}=9\); \(r_{12}=2\), \(r_{13}=1\), \(r_{21}=1\), \(r_{23}=3\). Let us consider, for example, the \(12 th\) iteration of these tasks, i.e., set \(k(1)=12\), \(k(2)=12\), and \(k(3)=12\); then the task \(J_{1}\) will be executed in the time interval [125; 128], the task \(J_{2}\)--in the time interval [129; 132], and the task \(J_{3}\) in the time interval [129; 124]. Therefore, the nearest iteration of task \(J_{2}\) that can be performed by the same vehicle, which has performed the \(12\)th iteration of \(J_{1}\), will be the \(13\)th iteration. Therefore, the nearest iteration of task \(J_{3}\), which can be performed by the same vehicle following the \(12\)th iteration of \(J_{1}\), will also be the \(13\)th iteration. Hence, \(k_{12}=k_{13}=13-12=1\). Similarly, we obtain that \(k_{23}=14-12=2\); \(k_{21}=1\). At this point, let us recall a remarkable property of the weights \(k_{ij}\) in the periodic minimum-size vehicle problem, discovered by [PERSON] and [PERSON] [18] in 1978 and independently by [PERSON] [20] in 1982, that establishes a direct connection between the _minimum number_ of vehicles required and the _minimum-weight cycle cover_ of the graph \(G_{gen}\), the arc weights of which are the weights \(k_{ij}\) defined by Equation (1). Denote by \(\boldsymbol{c}\) an arbitrary cycle cover of the generating graph \(G_{gen}\), and \(\boldsymbol{S}\) the set of all possible cycle covers of the graph \(G_{gen}\). _The Karzanov-Livshits-Orlin Theorem._ A _minimum-weight_ cycle cover, having the total weight \(min_{\boldsymbol{c}\in\boldsymbol{S}}\sum_{(i,j)\in\boldsymbol{c}}k_{ij}\) provides the _minimum number_ of vehicles \(K_{min}\) required to perform a given task schedule: \(K_{min}=min_{\boldsymbol{c}\in\boldsymbol{S}}\sum_{(i,j)\in\boldsymbol{c}}k_ {ij}\).