## 5 Optimizing the Number of Mobile Sinks and Their Paths
### The Ideal Case  
In the ideal case, as we already have the optimal path finding algorithm in the precedence graph, we will then have a graph with each point marked with a hop number. According to Lemmas 1 and 2, we know that each point will be included in the path only once and points with the same hop number do not have an edge between them. On the other hand, minimizing the number of paths equals to reducing points with a single edge or no edge (maximizing the number of connected points). Thus, we can find the optimal number of mobile sinks. We turn the problem into a maximal weight assignment in the bipartite matching where each edge has an equal weight of 1. Points of the same hop number are grouped together and adjacent hop number groups are listed on the left and right of the bipartite graph. As seen in Figure 6, the \(k\)th and \((k+1)\)th hop number groups are considered, and the Kuhn-Munkras (K-M) algorithm [26] is applied to find the optimal assignment. Some points on the right may remain unsigned in the current round, and then they will be added to the next round for further consideration. Based on this, we propose Algorithm 4, which starts from the groups with hop numbers 1 and 2, then continues to 2 and 3, and so on. After all points are assigned, the algorithm ends with optimal  
Figure 4: Collected data during a period.  
Figure 5: Two paths cross the same mutual point.  
paths. Note that there may exist more than one matching assignment that achieves the maximal total weight for each pair of hop number groups. Therefore, in the optimal case, the path distribution may be different, but the total number of paths are the same.  
```
0: points with hop number
0: optimal number of mobile sinks and the paths
0: Initialize Set the weight of each edge as 1, and start from hop number 1 and 2 (\(k=1\))
0: Assign
1: If there is no point with hop number \(k+1\), the algorithm ends. Otherwise, list points with hop number \(k+1\) on the left of the bipartite graph, and those unsigned with hop number less than \(k\) on the right. Build the weight matrix according to all possible assignments between points derived from the precedence graph.
2: Apply the K-M algorithm, and get the optimal assignment
3: Let \(k=k+1\), repeat step 1
```  
**Algorithm 4** Optimal number of mobile sinks in the ideal case  
We use the graph in Figure 3 as an example to illustrate the algorithm. The algorithm starts from the rightmost point as shown in Figure 7. First, the algorithm handles the point groups with hop number 1 and hop number 2. Then, the point groups with hop numbers 2 and 3 are listed for matching. In this step, there are two ways of assignment that have equal total weight (indicated by green dashed lines), and the algorithm randomly selects one of them. In the next step, there is only one point of hop number 4, and the algorithm also randomly selects one of two points of hop number 3 to assign with the point of hop number 4. In the final step, the unsigned point of hop number 3 joins with the point of hop number 4 to do bipartite matching with two points of hop number 5. Eventually, we get two optimal paths. It is must be noted that the optimal paths solutions are not exclusive.  
**Theorem 4**: _The number derived from the Algorithm 4 is optimal._  
Proof.: The bipartite matching between two groups implies that maximal points are linked together with edges to achieve a minimized number of unconnected points. As shown in Figure 5(b), the incorrect assignment needs three vessels to visit all points (\(a\)-\(b\), \(c\), \(d\)) while, in Figure 5(c), only two are needed (\(a\)-\(d\), \(cb\)). Since the bipartite matching can achieve maximal weight [27], in each pair of point groups that is equivalent to minimal unconnected points, after all points are assigned, the algorithm can find the optimal number of paths.  
Figure 6: Optimal path finding via bipartite matching between points groups.