betaFeedback

WorksMathematics

A complete classification for n-species Lotka-Volterra stably dissipative systems based on a generalized AHU algorithm

Abstract

This paper proposes a generalized AHU algorithm based on tree isomorphism theory and applies it to the complete classification of n-dimensional stably dissipative Lotka-Volterra systems.

Introduction

Consider the following nn-species Lotka-Volterra system

x˙i=xi(ri+∑j=1naijxj),i=1,…,n.(1)\dot{x}_{i}=x_{i}\left(r_{i}+\sum_{j=1}^{n}a_{ij}x_{j}\right),\quad i=1,\ldots,n. \tag*{(1)}

Here, rir_i and aija_{ij} are real constants. We focus on solutions residing in R+n\mathbb{R}^n_+.

It is well established that the global dynamics of system (1) is governed by its interaction matrix A=(aij)n×nA=(a_{ij})_{n\times n} [2, 3, 7, 21, 22, 30] (Lu and Takeuchi 1995). For matrix AA, there is an important concept which determines the dynamical behavior of the system [1, 3, 7, 23].

Definition 1. Matrix AA is Volterra-Lyapunov (semi-) stable, if there is a positive diagonal matrix C=diag⁡(c1,…,cn)C=\operatorname{diag}(c_1,\ldots,c_n) such that CA+ATCCA+A^T C is negative (semi-) definite.

Suppose that system (1) admits a unique positive equilibrium x∗=(x1∗,…,xn∗)x^*=(x^*_1,\ldots,x^*_n). Then system (1) can be reformulated as

x˙i=xi∑j=1naij(xj−xj∗),i=1,…,n.(2)\dot{x}_i=x_i\sum_{j=1}^{n}a_{ij}(x_j-x^*_j),\quad i=1,\ldots,n. \tag*{(2)}

By employing the Volterra-Lyapunov function

V(x)=∑i=1nci(xi−xi∗−xi∗ln⁡xixi∗),(3)V(x)=\sum_{i=1}^{n}c_i(x_i-x_i^*-x_i^*\ln\frac{x_i}{x_i^*}), \tag*{(3)}

and applying LaSalle’s invariance principle [13, 5, 7, 10], we obtain the following results:

Lemma 1. If AA is Volterra-Lyapunov semi-stable, then every solution of system (2) converges to the maximal invariant set MM contained in the set

E={x∈int⁡R+n∣(x−x∗)T(CA+ATC)(x−x∗)=0}.(4)E=\{x\in\operatorname{int}\mathbb{R}^n_+\mid(x-x^*)^T(CA+A^T C)(x-x^*)=0\}. \tag*{(4)}

Here, MM denotes the LaSalle’s invariant set of system (2). Specifically, if the matrix AA is Volterra-Lyapunov stable, MM reduces to a singleton {x∗}\{x^*\}, thereby implying that x∗x^* is globally asymptotically stable.

However, when AA is merely Volterra-Lyapunov semi-stable (but not stable), the LaSalle’s invariant set MM contained in EE typically extends well beyond a single point x∗x^*. In such cases, characterizing the geometric or algebraic structure of MM becomes a formidable challenge.

To address this, several intermediate notions of stability—positioned between Volterra-Lyapunov semi-stability and stability—have been explored in the literature. These stability conditions are strictly weaker than Volterra-Lyapunov stability yet stronger than semi-stability.

In this context, Lu and Takeuchi 1995 proposed a conjecture regarding these properties, which was subsequently proven to hold for the case n=3n = 3.

Conjecture 1. If AA is Volterra-Lyapunov semi-stable and diag⁡(x∗)A\operatorname{diag}(x^*)A is stable, then x∗x^* is globally stable for system (2).

Following the foundational work of Samuelson [25], Lancaster [11, 12], Gorman [4], Quirk and Ruppert [20] provided a detailed qualitative stability analysis for general matrices. Subsequently, Jeffries [9, 8] established a complete set of criteria for qualitative stability using graph methods and color test notation. Based on a theorem by Redheffer [22], Lu and Takeuchi [Lu and Takeuchi 1994] proved that the qualitative stability of the interaction matrix AA of system (2) implies its global stability. Furthermore, any irreducible matrix possessing qualitative stability must be Volterra-Lyapunov semi-stable.

In a series papers [14, 15, 16], Lotka-Volterra prey-predator chain systems were extensively investigated.

Definition 2. Lotka-Volterra system (2) is defined as a prey-predator cycle, if its interaction matrix A=(aij)A = (a_{ij}) satisfies the following conditions:

  1. aii≤0a_{ii} \le0 for all i=1,…,ni = 1, \ldots, n, with at least one strict inequality holding;

  2. aijaji≤0a_{ij}a_{ji} \le0 and aij=0a_{ij} = 0 if and only if aji=0a_{ji} = 0, i≠ji \ne j, i,j=1,…,ni, j = 1, \ldots, n;

  3. there are distinct indices i1,…,imi_1, \ldots, i_m (m≥3m \ge3) such that none of the element ai1i2,ai2i3,…,aimi1a_{i_1i_2}, a_{i_2i_3}, \ldots, a_{i_mi_1} vanish.

A system that does not satisfy the requirements of a prey-predator cycle is referred to as a prey-predator chain system.

It can be verified that the interaction matrix of a prey-predator chain system is necessarily Volterra-Lyapunov semi-stable. In particular, Lotka-Volterra prey-predator chain systems are globally stable for dimensions n(≤4)n(\le4) [24]. Regarding these systems, Chen [16] proposed the following conjecture:

Conjecture 2. Every locally asymptotically stable equilibrium of the nn-dimensional Lotka-Volterra prey-predator chain system (2) is globally stable.

It was previously demonstrated that the Chen conjecture holds true for the nn-species food chain system (2) where n≤8n \le8 [27].

A concept slightly broader than qualitative stability is stable dissipation, introduced by Redheffer[24]. This concept is based on the notion that a perturbation of a matrix A=(aij)n×nA=(a_{ij})_{n\times n} is defined as any matrix Aˉ=(aˉij)n×n\bar{A}=(\bar{a}_{ij})_{n\times n} such that aˉij=0\bar{a}_{ij}=0 if and only if aij=0a_{ij}=0.

Definition 3. (Stably Dissipative Matrix) The interaction matrix AA of System (2) is called stably dissipative, denoted by A∈SDA\in\mathrm{SD}, if every sufficiently small perturbation Aˉ\bar{A} of AA is Volterra-Lyapunov semi-stable: that is, there exists ϵ>0\epsilon>0 such that max⁡ij∣aij−aˉij∣<ϵ⇒Aˉ\max_{ij}|a_{ij}-\bar{a}_{ij}|<\epsilon\Rightarrow\bar{A} is Volterra-Lyapunov semi-stable.

The perturbations considered here are required to preserve the zero pattern of AA, that is, aˉij=0\bar{a}_{ij}=0 if and only if aij=0a_{ij}=0. A Lotka-Volterra system with a stably dissipative interaction matrix is called a stably dissipative system.

Section 3 reviews the properties of stably dissipative matrix and and presents relevant known results, together with several key theorems and lemmas. Section 3 revisits the classical AHU algorithm for encoding rooted and unrooted trees and develops a generalized AHU algorithm that extends the encoding framework to unrooted colored trees with black and white nodes. Build on this generalization, Section 4 presents a comprehensive classification algorithm for nn-dimensional stably dissipative Lotka-Volterra systems and reports computational results on tree isomorphism, with the computations extending up to n=15n=15 for unrooted colored trees and n=21n=21 for uncolored trees. Finally, concluding remarks are offered in Section 5.

Criteria for stably dissipative matrice

If A∈SDA\in\mathrm{SD}, then AA is Volterra-Lyapunov semi-stability, i.e., there is a positive diagonal matrix C=diag⁡(c1,…,cn)C=\operatorname{diag}(c_1,\ldots,c_n) such that CA+ATCCA+A^{T}C is semi-negative definite. Furthermore, if[24]

(x−x∗)(CA+ATC)(x−x∗)T=0(5)(x-x^*)(CA+A^{T}C)(x-x^*)^{T}=0 \tag*{(5)}

then

aii(x−x∗)i=0,i=1,…,n.(6)a_{ii}(x-x^*)_i=0,\quad i=1,\ldots,n. \tag*{(6)}

Here, (5) and (6) imply that in the LaSalle’s invariant set when aii≠0a_{ii}\ne0, xi=xi∗x_i=x_i^*.

If aii<0a_{ii}<0 (i=1,…,ni=1,\ldots,n), then A∈SDA\in\mathrm{SD} if and only if AA is Volterra-Lyapunov stable[24, 30].

Clearly, in this special case for aii<0a_{ii}<0 (i=1,…,ni=1,\ldots,n), the dynamical behavior for system (2) is simple, i.e., globally stable. Therefore the interesting phenomena will appear when some of aiia_{ii} being zero. To deal with this situation, we define as [24] the interaction graph G(A)G(A) of the system (1) or (2) with the n×nn\times n interaction matrix A=(ai,j)n×nA=(a_{i,j})_{n\times n} as follows:

G(A)G(A) consists of nn nodes representing nn populations together with edges representing the interrelations between populations.

A black dot ∙\bullet (when ai,i<0a_{i,i}<0) or white dot ∘\circ (when ai,i=0a_{i,i}=0) will be marked on each node.

There is an edge between ii and jj whenever ai,j≠0a_{i,j}\ne0 and aj,i≠0a_{j,i}\ne0.

In [6], it is shown that if G(A)G(A) is free of loop, then AA is Volterra-Lyapunov stable if and only if −A-A is a P matrix. In [24], it is shown that if A∈SDA\in\mathrm{SD}, ii and jj are the nodes connected to G(A)G(A), then aiiajj>aijajia_{ii}a_{jj}>a_{ij}a_{ji}.

The following strong (weak) connection concept is important to classify the graph of the interaction matrix.

Definition 4. [24] A connection [i,j][i,j] in G(A)G(A) is called a strong (weak) connection, if aijaji<0a_{ij}a_{ji}<0 (aijaji=0a_{ij}a_{ji}=0).

It is shown [30] that if A∈SDA\in\mathrm{SD}, then each loop in G(A)G(A) has at least one strong connection. Furthermore, we have

Lemma 2. [30] If the graph G(A)G(A) corresponding to AA has only one black node ∙\bullet, then A∈SDA\in\mathrm{SD} if and only if

(i) G(A)G(A) is free of loop and

(ii) If aij≠0a_{ij}\ne0, then aijaji<0a_{ij}a_{ji}<0 is true for all i≠ji\ne j.

Lemma 3. [30] Suppose G(A)G(A) has no less than two black nodes ∙\bullet, i.e., aii<0a_{ii}<0 (i=1,…,ki=1,\ldots,k; k≥2k\ge2) and ajj=0a_{jj}=0 (j=k+1,…,nj=k+1,\ldots,n). Let M=(aij)k×kM=(a_{ij})_{k\times k} (1≤i,j≤k1\le i,j\le k) and Gˉ(A)\bar{G}(A) denote the graphs G(A)G(A) in which all the links [i,j][i,j] are removed (i≤ki\le k, j≤kj\le k) (actually, Gˉ(A)\bar{G}(A) is obtained by removing all strongly connected graphs from G(A)G(A)), then A∈SDA\in\mathrm{SD} if and only if.

(i) Gˉ(A)\bar{G}(A) is free of loop;

(ii) There is a positive diagonal array C=diag⁡(c1,…,cn)C=\operatorname{diag}(c_1,\ldots,c_n) such that C0M+MTC0C_0M+M^{T}C_0 is negative and ciaij+cjaji=0c_i a_{ij}+c_j a_{ji}=0 (i > k, j > k), here C0=diag⁡(c1,…,ck)C_0=\operatorname{diag}(c_1,\ldots,c_k).

According to the two lemmas above, the matrix AA is stably dissipative if and only if the graph G‾(A)\overline{G}(A)—formed by removing all strongly connected components (or strong edges) from G(A)G(A)—is a tree[30]. The sole exception occurs when all diagonal elements of AA are negative, which implies that all edges in G(A)G(A) are strongly connected. Consequently, the problem of system classification based on the interaction matrix AA can be mapped onto the topological classification of its associated graph G(A)G(A). To this end, we have:

Definition 5. The graph G(A)G(A) of matrix AA is called the maximal stably dissipative graph, if A∈SDA\in\mathrm{S_D} but A‾∉SD\overline{A}\notin\mathrm{S_D}. Here A‾\overline{A} is obtained by adding any links between the nodes of G(A)G(A).

Based on this definition, once the set of all maximal stably dissipative graphs for nn-order matrices is determined, the stably dissipative graph G(A)G(A) of any nn-order tolerance matrix AA can be retrieved by removing kk (k≥0k\geq0) strong connections from a maximal graph. Therefore, classifying maximal stably dissipative graphs is essentially equivalent to classifying all stably dissipative graphs. The computational process is straightforward: all stably dissipative graphs can be exhausted by removing subsets of strong connections from the identified maximal graphs.

A complete classification algorithm for nn-dimensional Lotka-Volterra system with maximal stably dissipative matrix is proposed in § 3. Theoretically, for a given nn, the classification of the maximal stably dissipative graph for a n×nn\times n matrix will be determined by a computer program based on the algorithm. A result up to n=15n=15 is presented. In fact, the classification result of the maximal stably dissipative graph is the same as the known conclusion for n=4n=4 and 55[30]. For n=6n=6, [28] obtained 73 classes maximal stably dissipative graphs, but in our case, it should be 76 classes. For n=7n=7, [29] found 229 classes maximal stably dissipative graphs, in our case, it is 235 classes.

Canonical Encoding of Bichromatic Trees

This section presents an algorithm for identifying maximally stably dissipative graphs. We extend the AHU algorithm to accommodate graphs whose nodes are assigned binary colors, namely, black and white. We begin by introducing several fundamental concepts.

Definition 6. [26] The number of edges incident to a node in G(A)G(A) is called the degree of that node, A node with degree 1 is called a leaf.

We assign each node of a tree one of two colors, black or white. A fundamental property of trees is that removing a leaf from an nn-node tree yields a tree with n−1n-1 nodes. Conversely, any nn-node tree can be constructed by attaching a leaf to an (n−1)(n-1)-node tree. This inductive property provides a systematic framework for constructing all stably dissipative trees.

Apart from the inclusion of node coloring (bichromatic node), these trees retain the same structural properties as conventional trees in graph theory. Accordingly, graph isomorphism must account for both the topological structure and the color of each node. Although the AHU algorithm works well for uncolored trees, its direct application to bichromatic trees presents considerable challenges due to the substantially increased complexity of distinguishing non-isomorphic structures. For instance, there are only three non-isomorphic uncolored trees with five nodes; however, when node coloring is considered, the number of distinct isomorphism classes increases to 26.

In the following section, we develop a generalization of the AHU algorithm for determining isomorphism among bichromatic trees. We begin by formally introducing the distinctions among rooted trees, unrooted trees and colored trees.

The Generalized AHU Algorithm

The original AHU algorithm employs a recursive nested-parenthesis encoding scheme to generate canonical strings for trees. In this study, we propose a generalized AHU algorithm, with the initial focus on a unique canonical encoding for rooted trees, as defined in § 3.2 (Definitions 7 and 8). For unrooted trees, we use their graph centers to determine the root structure, thereby reducing the problem to rooted-tree encoding. It can be formally proved that the proposed encoding is canonical: two trees are isomorphic if and only if they have the same encoding.

Note that the center of a tree consists of either a single node or a pair of adjacent nodes. To address the latter case, we generate separate encodings for each node in the central pair and concatenate them in a lexicographical (sorted) order. This approach maintains the uniqueness of the encoding for all unrooted trees. Finally, we incorporate node coloring by assigning positive and negative signs to represent black and white nodes, respectively. This extension ensures that the final encoding remains a canonical form for bicolored trees.

Encoding of Rooted Trees

Definition 7. Let T=(V,E,r)T = (V, E, r) be a rooted tree with nn nodes, where VV is the set of nodes, EE is the set of edges, and rr is the root of the tree. For any node v∈Vv \in V, its encoding is defined as the following sequence of integers,

code⁡(v)={[size⁡(v),op⁡(code⁡(w1)),⋯ ,op⁡(code⁡(wk))]v is a non-leaf node,[1]v is a leaf node.(7)\operatorname{code}(v) = \begin{cases} [\operatorname{size}(v), \operatorname{op}(\operatorname{code}(w_1)), \cdots, \operatorname{op}(\operatorname{code}(w_k))] & v\text{ is a non-leaf node}, \\ [1] & v\text{ is a leaf node}. \end{cases} \tag*{(7)}

where size⁡(v)\operatorname{size}(v) denotes the total number of nodes in the subtree rooted at vv in TT, and w1,⋯ ,wkw_1, \cdots, w_k are the children of vv, arranged in ascending order according to their encodings. Here, op⁡(code⁡(wj))(j=1,⋯ ,k)\operatorname{op}(\operatorname{code}(w_j)) (j = 1, \cdots, k), denotes the sequence of integers obtained from the encoding of wjw_j by removing the outermost pair of square brackets. The function op⁡(⋅)\operatorname{op}(\cdot) is the op function in Maple, which is used to extract the operands of an expression.

Definition 8. Let T=(V,E,r)T = (V, E, r) be a rooted tree with nn nodes, where VV is the set of nodes, EE is the set of edges, and rr is the root of the tree. The encoding of tree TT is defined as the encoding of its root rr, that is,

code⁡(T)=code⁡(r).(8)\operatorname{code}(T) = \operatorname{code}(r). \tag*{(8)}

Example 1. Consider the rooted tree with four nodes and root v1v_1, as shown in Figure 1. The encoding process starts at the leaf node v4v_4 and proceeds upward toward the root. Although v1v_1 has degree one, it is not treated as a leaf in this encoding process, because it serves as the root. The encoding steps are as follows:

Step-by-step encoding of a rooted tree with four nodes

Figure 1. Step-by-step encoding of a rooted tree with four nodes.

  • The encoding of v4v_4 is obtained as [1], where 1 represents the total number of nodes in the subtree rooted at v4v_4. This encoding is then passed to its parent node v3v_3 as [[1]] (temporarily stored, not the final encoding);

  • Considering the removal of the subtree rooted at the previous leaf node v4v_4, we now select a new leaf node v3v_3. The total number of nodes in the subtree rooted at v3v_3 is 2. We then concatenate this with the encoding [1] of the previously temporarily stored child node v4v_4, resulting in the encoding [2,1] for node v3v_3. Simultaneously, we pass this encoding to its parent node v2v_2, becoming [[2,1]];

  • Continuing as above, we now select another new leaf node v2v_2. The total number of nodes in the subtree rooted at v2v_2 is 3. We then concatenate this with the encoding [2,1] of its child node, resulting in the encoding [3,2,1] for node v2v_2. Simultaneously, we pass this encoding to its parent node v1v_1, becoming [[3,2,1]];

  • Following the same steps as mentioned above, we obtain the encoding [4,3,2,1] for the root node v1v_1.

Example 2. As shown in Figure 2, we have another four-node tree where v3v_3 is the root node. The encoding process starts from the leaf nodes v4v_4 and v1v_1. The encoding process is as follows,

  • The encoding of both v1v_1 and v4v_4 is [1], and this encoding is passed to their respective parent nodes v2v_2 and v3v_3, resulting in [[1]] for both;

  • Considering the removal of the previously encoded subtree rooted at nodes v1v_1 and v4v_4, we now select a new leaf node v2v_2. The total number of

Step-by-step encoding of another rooted tree with four nodes

Figure 2. Step-by-step encoding of another rooted tree with four nodes.

nodes in the subtree rooted at v2v_2 is 2. We then concatenate the encoding [1] of its child node v1v_1, resulting in the encoding [2,1] for node v2v_2. It should be noted that although v3v_3 is also a new leaf node, it has been designated as the root node, so no final encoding is performed at this point. Instead, the encoding [2,1] received from v2v_2 as a child node is temporarily stored together with the previously stored temporary encoding [1], resulting in a new temporary encoding for v3v_3 as [[1],[2,1]].

  • Following the same steps described above, we continue by removing the leaf nodes from the previous step, leaving only the root node v3v_3. Its encoding is then obtained as [4,1,2,1], where the leading 4 is the total number of nodes in the subtree rooted at v3v_3, and the remaining 1, 2, and 1 are the encodings of its child nodes, [1] and [2,1], sorted and concatenated after stripping the square brackets.

From Figure 1 and 2, it can be observed that although they are structurally identical four-node trees, their encodings are different due to the specification of different root nodes. The reason for this lies in the fact that along different root nodes, the subtrees of each node will vary, resulting in different encodings.

Encoding of Unrooted Trees

For an unrooted tree T(V,E)T(V,E) with a unique center node cc, we transform it into a rooted tree T′(V,E,c)T'(V,E,c). If TT has a bicentral structure (a two-node center {c1,c2}\{c_1,c_2\}), we remove the edge connecting these two nodes to decompose TT into two rooted subtrees Ti′(Vi,Ei,ci)T'_i(V_i,E_i,c_i) for i∈{1,2}i \in\{1,2\}, where the roots cic_i correspond to the original center nodes.

Definition 9. Let T=(V,E)T=(V,E) be an unrooted tree with nn nodes. Its encoding is defined as follows:

code⁡(T)={code⁡(T′(V,E,c))The center of T is a single-node c,[op⁡(code⁡(T1′)),op⁡(code⁡(T2′))]The center of T consists of two nodes, c1 and c2.The two subtrees T1 and T2, with c1 and c2 astheir root nodes, are encoded in ascending orderbased on dictionary sequence.(9)\operatorname{code}(T)= \begin{cases} \operatorname{code}(T'(V,E,c)) & \text{The center of }T\text{ is a single-node }c,\\ [\operatorname{op}(\operatorname{code}(T'_1)),\operatorname{op}(\operatorname{code}(T'_2))] & \text{The center of }T\text{ consists of two nodes, }c_1\text{ and }c_2.\\ & \text{The two subtrees }T_1\text{ and }T_2,\text{ with }c_1\text{ and }c_2\text{ as}\\ & \text{their root nodes, are encoded in ascending order}\\ & \text{based on dictionary sequence.} \end{cases} \tag*{(9)}

Here T′(V,E,c)T'(V,E,c), T1′(V1,E1,c1)T'_1(V_1,E_1,c_1), and T2′(V2,E2,c2)T'_2(V_2,E_2,c_2) are derived from the original tree TT, as discussed in the preceding definitions. op⁡(code⁡(Ti′(Vi,Ei,ci)))\operatorname{op}(\operatorname{code}(T'_i(V_i,E_i,c_i))) (i=1,2i=1,2) represents extracting the sequence of integers from the encoding of Ti′(Vi,Ei,ci)T'_i(V_i,E_i,c_i) (i.e., removing a pair of square brackets [ ] from the encoding of Ti′(Vi,Ei,ci)T'_i(V_i,E_i,c_i)).

Example 3. Figure 3 illustrates an unrooted four-node tree, where the encoding process initiates from leaf nodes v4v_4 and v1v_1 through the following steps:

  • Leaf-to-Parent Propagation: The initial encodings for leaf nodes v1v_1 and v4v_4 are both [1]. These encodings are propagated to their respective parent nodes, v2v_2 and v3v_3, resulting in the intermediate string [[1]] for each.

  • Identification of the Graph Center: After pruning the encoded leaves v1v_1 and v4v_4, the remaining structure contains exactly two nodes, namely v2v_2 and v3v_3. Hence the center of the original tree is identified as the node pair (v2,v3)(v_2,v_3), which now act as the leaves of the surviving subtree. Following the procedure in the previous example, both v2v_2 and v3v_3 yield the encoding [2, 1]. Note that the edge e2,3e_{2,3} between them is excluded here, as required by the definition of unrooted tree encoding.

Trees with four nodes

Figure 3. Trees with four nodes

  • Canonical Concatenation: The encodings of the two central nodes are sorted in ascending (lexicographical) order, yielding [[2,1],[2,1]][[2,1],[2,1]]. By removing the outer brackets of each individual encoding and concatenating the sequences, we derive the string 2,1,2,12,1,2,1. Thus, the final canonical encoding for the original unrooted tree is code⁡(T)=[2,1,2,1]\operatorname{code}(T)=[2,1,2,1].

For single-center unrooted trees, the process is relatively straightforward and precludes the need for additional examples. The method employs an iterative pruning strategy: leaf nodes of the subtree are successively encoded and removed until only the central structure remains. This procedure, reminiscent of the classical algorithm for locating a tree’s center, naturally converges to one or two remaining nodes. By integrating center identification directly into the encoding sequence, the requirement for pre-identifying centers is eliminated, thereby optimizing the algorithm’s computational efficiency.

Encoding Unrooted Colored Trees

We now extend the encoding approach to unrooted trees whose nodes are colored black or white. Unlike the uncolored trees considered above, these trees must be distinguished by both their structures and their node colors. To develop an encoding for unrooted colored trees, we first define the encoding of rooted colored trees and then extend it to the unrooted case.

Definition 10. Let T=(V,E,r)T=(V,E,r) be a rooted tree whose nodes are colored black or white, where VV is the set of nodes, EE is the set of edges, and rr is the root node of the tree. For any node v∈Vv\in V, its encoding is defined as the following sequence of integers,

code⁡(v)={[sign⁡(v)×size⁡(v),op⁡(code⁡(w1)),⋯ ,op⁡(code⁡(wk))]v is non-leaf node,[sign⁡(v)×1]v is leaf node,(10)\operatorname{code}(v)= \begin{cases} [\operatorname{sign}(v)\times\operatorname{size}(v),\operatorname{op}(\operatorname{code}(w_1)),\cdots,\operatorname{op}(\operatorname{code}(w_k))] & v\text{ is non-leaf node},\\ [\operatorname{sign}(v)\times1] & v\text{ is leaf node}, \end{cases} \tag*{(10)}

where

sign⁡(v)={−1v is black node,1v is white node,\operatorname{sign}(v)= \begin{cases} -1 & v\text{ is black node},\\ 1 & v\text{ is white node}, \end{cases}

Where size⁡(v)\operatorname{size}(v), w1,⋯ ,wkw_1,\cdots,w_k, and op⁡(code⁡(wj))\operatorname{op}(\operatorname{code}(w_j)) (j=1,⋯ ,k)(j=1,\cdots,k) are defined in Definition 7.

Following the approach used in the earlier definition of unrooted tree encoding, as outlined in 9, the encoding of unrooted trees with black and white nodes can be naturally extended. Below, we present an illustrative example.

Example 4. Consider the unrooted tree with black and white nodes shown in 4. The encoding procedure initiates from the leaf nodes v1v_1, v2v_2, v6v_6, v7v_7, v9v_9, and v11v_{11}, and proceeds as follows:

  • Initialization: The white leaf nodes {v1,v7,v9,v11}\{v_1, v_7, v_9, v_{11}\} are assigned the encoding [1][1], while the black leaf nodes {v2,v6}\{v_2, v_6\} are encoded as [−1][-1]. These values are propagated to their respective parent nodes {v3,v4,v5,v10,v8}\{v_3, v_4, v_5, v_{10}, v_8\}. Notably, since v2v_2 and v7v_7 share a common parent v4v_4, the parent node initially stores the aggregate encoding [[−1],[1]][[-1], [1]].

  • Iteration 1: Upon pruning the initial leaf nodes, a reduced subtree emerges where v4v_4 and v10v_{10} become the new leaves. For the black node v4v_4, we apply Definition 4 to derive the encoding [−3,−1,1][-3, -1, 1]. Here, the negative sign denotes the node’s black color, and the magnitude 3 indicates the total number of nodes in the subtree rooted at v4v_4. The sequence [−1,1][-1, 1] represents the sorted, serialized encodings of its children. Similarly, the white node v10v_{10} is encoded as [2,1][2, 1]. These results are passed to parents v3v_3 and v8v_8, which concatenate these new values with previously stored encodings (e.g., [[1]][[1]]). Consequently, the temporary encodings for v3v_3 and v8v_8 are updated to [[1],[−3,−1,1]][[1], [-3, -1, 1]] and [[1],[2,1]][[1], [2, 1]], respectively.

  • Iteration 2: Following the removal of the processed nodes, v3v_3 and v8v_8 become the leaf nodes of the remaining subtree. Applying Definition 4, we obtain the encodings [5,−3,−1,1,1][5, -3, -1, 1, 1] for v3v_3 and [4,1,2,1][4, 1, 2, 1] for v8v_8. These are transmitted to their common parent, v5v_5, which then stores the cumulative temporary encoding [[−1],[5,−3,−1,1,1],[4,1,2,1]][[-1], [5, -3, -1, 1, 1], [4, 1, 2, 1]].

  • Termination: In the final stage, only node v5v_5 remains, representing both the leaf of the current subtree and the center node of the original tree TT. By sorting the encodings of its children in ascending order and concatenating them, we derive the final representation of the original unrooted tree:

code⁡(T)=[11,−1,4,1,2,1,5,−3,−1,1,1]\operatorname{code}(T) = [11, -1, 4, 1, 2, 1, 5, -3, -1, 1, 1]

Figure 4. The Encodings of Black and White Trees with 11 Nodes

Algorithm and Main Results

Algorithm Steps

Input: Adjacency matrix of a tree $T$
Output: Encoding $R$ of $T$
▷ Initialize encoding variables
1  $C \leftarrow \operatorname{vector}(n,0)$
2  $R \leftarrow [\ ]$
▷ Prune leaves to the tree center
3  while $\operatorname{remain}(T)>2$ do
4    foreach $i \in \operatorname{getLeaves}(T)$ do
5      $C[i] \leftarrow \operatorname{genCode}(C[i])$                         ▷ Encode the leaf node $v_i$
6      $p \leftarrow \operatorname{parent}(i,T)$                              ▷ Find the parent of $v_i$
7      ▷ Update the parent’s code
8      if $C[p]=0$ then
9        $C[p] \leftarrow \{C[i]\}$
10     else
11       $C[p] \leftarrow \{\operatorname{op}(C[p]),C[i]\}$
12       $C[p] \leftarrow \operatorname{sort}(C[p])$
13   $T \leftarrow \operatorname{removeLeaves}(T)$                             ▷ Remove processed leaves
▷ Encode the center node(s)
14 foreach $j \in \operatorname{getNodes}(T)$ do
15   $C[j] \leftarrow \operatorname{genCode}(C[j])$                             ▷ Encode the center node $v_j$
16   if $\operatorname{nops}(R)=0$ then
17     $R \leftarrow C[j]$
18   else
19     $R \leftarrow \{\operatorname{op}(R),C[j]\}$
20     $R \leftarrow \operatorname{sort}(R)$
21 return $R

Algorithm 1: Encoding a Tree, code⁡(T)\operatorname{code}(T)

Any tree with nn nodes can be constructed by appending a single node to an existing tree with n−1n-1 nodes. This recursive property allows for the systematic organization of topological classifications for trees containing both black and white nodes. The specific procedure is as follows:

  • Case n=1n = 1: We start with the simplest case, in which the tree consists of a single node. Since the node can be either black or white, there are two possible colored trees, with encodings ([−1])([-1]) and ([1])([1]), respectively.

  • Case n=2n = 2: Starting from the two colored trees obtained for (n=1)(n=1), we construct candidate trees by attaching a new node, either black or white, to an existing node. Although there are four possible combinations, applying the encoding and deduplication via Algorithm code⁡(T)\operatorname{code}(T) yields only two distinct cases: [−1,1][-1,1] and [1,1][1,1]. Notably, [−1,−1][-1,-1] is omitted, since the problem constraints forbid connecting two black nodes.

  • Case n=3n = 3: We extend the colored trees obtained for (n=2)(n=2) by attaching a new node, either black or white, to an existing node of each tree. Applying Algorithm code⁡(T)\operatorname{code}(T) to identify isomorphic trees and eliminate duplicates, we obtain four distinct colored trees up to isomorphism, with encodings ([3,1,1])([3,1,1]), ([3,−1,1])([3,-1,1]), ([3,−1,−1])([3,-1,-1]), and ([−3,1,1])([-3,1,1]).

By repeating this iterative expansion and deduplication process, we can determine the total number of heterogeneous tree classifications for any specified value of nn.

Due to the recursive architecture of the algorithm and the intensive deduplication of encodings, the process involves significant computational complexity. To address this, we optimized the implementation using both Maple and Python to handle encoding calculations efficiently.

Under current optimizations, the algorithm successfully computes encodings for trees with up to n=15n = 15 nodes when considering both black and white node variations. In the simplified case where node colors are not introduced, the computational reach extends to n=21n = 21. The following two tables summarize the experimental results and corresponding execution times of our Python implementation.

Number of Nodes (nn)23456789
Number of Tree Types241026752347682647
Running Time (mm:ss)00:0000:0000:0000:0000:0000:0000:0000:00
Number of Nodes (nn)101112131415
Number of Tree Types94663481813114950364019655527777081
Running Time (mm:ss)00:0100:0500:2301:4306:3425:16

Table 1. Classification Results and Computational Time for Trees with Black and White Nodes

Number of Nodes (nn)23456789
Number of Tree Types11236112347
Running Time (mm:ss)00:0000:0000:0000:0000:0000:0000:0000:00
Number of Nodes (nn)1011121314151617
Number of Tree Types1062355511301315977411932048629
Running Time (mm:ss)00:0000:0000:0000:0000:0000:0000:0100:02
Number of Nodes (nn)18192021
Number of Tree Types1238673179558230652144505
Running Time (mm:ss)00:3301:2904:0411:25

Table 2. Classification Results and Running Time for Uncolored Trees

Discussion

With the help of the generalized AHU algorithm promoted by the present article, we have completed a algorithmic classification of general nn-dimensional Lotka-Volterra stably dissipative systems. And specific classification results were provided when n≤15n \le15. At the same time, we also corrected the erroneous results in existing literature regarding n=6n=6, and 7. When nn is relatively small (n<8n < 8), the dynamic behavior of low dimensional systems can be divided into the following four categories:

(1) If the LaSalle’s invariant set for a system contains only a positive equilibrium, then the system is globally stable.[3, 7]

  1. If all the diagonal elements aiia_{ii} of the interaction matrix A=(aij)A = (a_{ij}) are zero, then the system has non-canonical Hamiltonian formulation. [19, 30]

  1. If a positive equilibrium is not unique, then every orbit has a limit depends on its initial value. [24, 30]

  1. If the LaSalle’s invariant sets of the systems are composed of differential algebraic equations, the dynamical behavior of the systems are determined by the structures of the LaSalle’s invariant sets whether they contain periodic orbits or not. [16, 27]

We speculate that for the general nn-dimensional systems, there should not be any situations outside of the above four categories.

References

  1. [1]Cross, G. W. (1978). Three types of matrix stability. Linear Algebra and Its Applications 20(3): 253–263.DOI
  2. [2]Duarte, P., R. L. Fernandes, and V. M. Oliva (1998). Dynamics of the Attractor in the Lotka-Volterra. Journal of Differential Equations 149(1): 143–189.
  3. [3]Goh, B. S. (1977). Global stability in many-species systems. Amer. Nat. 111(977): 135–143.DOI
  4. [4]Gorman, W. M. (1964). More scope for qualitative economics. Econ. Stud. 31(1): 65–68.DOI
  5. [5]Harrison, G. W. (1979). Global stability of food chains. Amer. Nat. 114(3): 455–457.DOI
  6. [6]Hofbauer, J. and K. Sigmund (1998). Evolutionary Games and Population Dynamics. Cambridge University Press, Cambridge.
  7. [7]Hsu, S. B. (1978). The application of the Poincaré-transform to the Lotka-Volterra model. J. Math. Biol. 6(1): 67–73.DOI
  8. [8]Jeffries, C. (1974). Qualitative stability and digraphs in model ecosystems. Ecology 55(6): 1415–1419.DOI
  9. [9]Jeffries, C. (1988). Eigenvalues, stability, and color tests. Linear Algebra Appl. 107: 65–76.DOI
  10. [10]Krikorian, N. (1979). The Volterra model for three species predator-prey systems: boundedness and stability. J. Math. Biol. 7(2): 117–132.DOI
  11. [11]Lancaster, K. J. (1962). The scope of qualitative economics. Rev. Econ. Stud. 29(2): 99–123.DOI
  12. [12]Lancaster, K. J. (1964). Partitionable systems and qualitative economics. Rev. Econ. Stud. 31(1): 69–72.DOI
  13. [13]LaSalle, J. P. (1960). Some extensions of Liapunov’s second method. IRE Trans. Circuit Theory 7(4): 520–527.DOI
  14. [14]Liu, L., Z. Lu, and D. Wang (1991). The structure of LaSalle’s invariant set for Lotka-Volterra systems. Science in China 34: 783–790.
  15. [15]Lu, Z. (1988). On the LaSalle’s invariant set for six-dimensional Lotka-Volterra prey-predator chain systems. J. Sichuan Univ.Nat. Sci. Ed. 25(2): 145–150.DOI
  16. [16]Lu, Z. (1989). On the LaSalle’s invariant set for five-dimensional Lotka-Volterra prey-predator chain. Acta Mathematica Sinica 5(3): 214–218.DOI
  17. [19]Plank, M. (1995). Hamiltonian structures for the n-dimensional Lotka-Volterra equations. J. Math. Phys. 36(7): 3520–3534.DOI
  18. [20]Quirk, J. and R. Ruppert (1965). Qualitative economics and the stability of equilibrium. Rev. Econ. Stud. 149(1): 143–189.
  19. [21]Redheffer, R. (1985). Volterra multipliers, II. SIAM J. Alg. Disc. Math. 6: 612–623.DOI
  20. [22]Redheffer, R. (1989). A new class of Volterra differential equations for which the solutions are globally asymptotically stable. J. Differential Equations 82(2): 251–268.DOI
  21. [23]Redheffer, R. and Z. Zhou (1981). Global asymptotic stability for a class of many-variable Volterra prey-predator systems. J. nonlinear Math. Appl. 5(12): 1303–1329.DOI
  22. [24]Redheffer, R. and Z. Zhou (1982). A class of matrix connected with Volterra prey-predator equation. SIAM J. Alg. Math 3(1): 122–134.DOI
  23. [25]Samuelson, P. A. (1947). Foundations of Economic Analysis, Harvard Economic Studies. Harvard University Press, Cambridge.
  24. [26]Valiente, G. (2002). Algorithms on Trees and Graphs. Springer.DOI
  25. [27]Yang, M. et al. (2019). The LaSalle’s invariant sets for a class of Lotka-Volterra prey-predator chain systems. J. Math. Anal. Appl. 475(1): 985–998.DOI
  26. [28]Yu, C. (2011). The generation of stably dissipative matrix and its application in dynamict systems. MA thesis. Jinhua, Zhejiang, China: ZheJiang Normal University.
  27. [29]Zhang, J. (2011). Research on properties of seven-dimensional stably dissipative LV systems. Journal of Zhejiang Normal University(Nat. Sci.) 34(4): 361–367.
  28. [30]Zhao, X. and J. Luo. (2010). Classification and dynamics of stably dissipative Lotka-Volterra systems. Inter. J. Nonlinear Mech. 45(6): 603–607.DOI

Paper details

vlnc:W_vve6xj3x
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents