## 3 Dynamic Link Establishment of Mega-Constellations
### Optimization Matching Algorithm for Dynamic Links  
This section introduces an optimization matching algorithm based on general graphs in graph theory, aimed at addressing the shortcomings of traditional greedy algorithms in terms of the connection duration and numbers of topology changes [16; 17; 18; 19; 20; 21; 22; 23]. Inter-satellite links are bidirectional, thus the topology of satellites within the constellation at time t can be represented using undirected graphs according to the definition in graph theory, as follows:  
\[G(t)=(V(t),E(t)),0\leq t\leq T \tag{9}\]  
where \(V(t)\) represents the set of vertices, representing the collection of satellite nodes within the constellation at time \(t\); \(E(t)\) represents the set of edges, representing the collection of inter-satellite communication links that can be established at time \(t\). For ease of subsequent discussion, \(V\) and \(E\) are used in the article to denote the sets of vertices and edges within each time slot [21]. Figure 10: The time when the satellite is not connected to a dynamic link. In the previous section, we identified the establishment of dynamic links as analogous to a maximum weight-matching problem in graph-matching algorithms within computer science. While the Hungarian algorithm for bipartite graph maximum weight matching is a common approach for solving such problems, it is challenging in our scenario to partition all of the satellites in the constellation into two sets where no internal connections exist among the satellites within each set. Therefore, we propose employing a general graph maximum weight-matching algorithm instead. However, traditional algorithms like Edmonds' Blossom Algorithm tend to result in frequent link switching [11]. To address this issue, this paper introduces an improved algorithm--the general graph maximum weight-matching algorithm with an elite retention strategy. Next, we will proceed to outline the description of this enhanced algorithmic process. We define an alternating path as starting from an unmatched satellite and traversing connections according to matrix A, alternating between unmatched and matched edges. An augmenting path is an alternating path that terminates at an unmatched satellite. Reversing the matching or non-matching status of the entire path yields a new matching result. In the context of maximum matching in general graphs, there exist odd cycles, which are cycles of odd length. As depicted in Figure 11, such \"odd cycles\" are commonly referred to as a \"flower\" or \"blossom\". In graph theory, a \"blossom\" is a special type of graph structure consisting of a group of an odd number of nodes, each pair of which are connected, forming a cycle, denoted as B, where \(\left\lvert\,\right\rvert\) is odd and \(\left\lvert\,\right\rvert\)\(\geq\) three. This ring is interconnected with other nodes, referred to as \"petals,\" thus creating a distinctive graphical structure. Every point on the odd cycle that possesses an outgoing unmatched edge has the potential to serve as an edge in an augmenting path, where reversing the state of edges within a flower according to the definition of an augmenting path would disrupt the matching pattern inside of the flower. However, as evident from Figure 9, any non-matching edge emanating from any point within a flower can be part of an alternating path originating from the root node; hence, all satellite nodes within a flower can effectively be regarded as a single entity concerning the entire path. Consequently, upon encountering a flower, one can perform a contraction operation that condenses it into a single even-pointed vertex, which then behaves as a single node extending outwardly along the alternating tree until conditions are met for decompressing the flower back into its points. It is noteworthy that there always exists a unique point within the cycle that connects two non-matching edges, and this point serves as the root (or receptacle) of the flower.