Finding Cut-Edges and the Minimum Spanning Tree via Semi-Tensor Product Approach

Xujiao FAN; Yong XU; Xue SU; Jinhuan WANG

doi:10.21078/JSSI-2018-459-14

PDF(200 KB)

Journal of Systems Science and Information ›› 2018, Vol. 6 ›› Issue (5) : 459-472. DOI: 10.21078/JSSI-2018-459-14

Finding Cut-Edges and the Minimum Spanning Tree via Semi-Tensor Product Approach

Author information +

History +

Abstract

Using the semi-tensor product of matrices, this paper investigates cycles of graphs with application to cut-edges and the minimum spanning tree, and presents a number of new results and algorithms. Firstly, by defining a characteristic logical vector and using the matrix expression of logical functions, an algebraic description is obtained for cycles of graph, based on which a new necessary and sufficient condition is established to find all cycles for any graph. Secondly, using the necessary and sufficient condition of cycles, two algorithms are established to find all cut-edges and the minimum spanning tree, respectively. Finally, the study of an illustrative example shows that the results/algorithms presented in this paper are effective.

Key words

semi-tensor product / cycle / cut-edge / minimum spanning tree

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations

Xujiao FAN , Yong XU , Xue SU , Jinhuan WANG. Finding Cut-Edges and the Minimum Spanning Tree via Semi-Tensor Product Approach. Journal of Systems Science and Information, 2018, 6(5): 459-472 https://doi.org/10.21078/JSSI-2018-459-14

1 Introduction

Spanning tree constitutes a skeleton of connected network, which has important influence on topological property and dynamic behavior of a network^[1]. A spanning tree of an undirected graph is a subgraph that includes all of the vertices of the original graph. The concept of spanning tree can be directly extended to weighted-undirected graphs. Although the number of edges of each spanning tree remains the same, the weights of each spanning tree may not be the same, and the spanning tree with the sum of the minimum weights is called the minimum spanning tree. The minimum spanning tree is not necessarily unique. If the weights of all edges are different from each other in a connected graph, then the graph must have the unique minimum spanning tree^[2]. Cut-edges are closely related to spanning tree. Although many of algorithms work well on certain classes of graphs in cut-edges and the minimum spanning tree, none of them is demonstrated to perform well for a general graph. Thus, it is necessary for us to establish a new formulation and algorithm to solve or approximate the cut-edge and the minimum spanning tree problems for general graphs.

Recently, a new powerful matrix product, called semi-tensor product of matrices was proposed by [3, 4]. This new matrix product has been successfully applied to express and analyze Boolean control networks, and up to now many fundamental and landmark results have been presented on calculating fixed points and cycles of Boolean networks^{[5, 6]}, on the controllability and observability of Boolean network^[7-10], on their control design problems^[11], on the synchronization of Boolean networks^[12-18], on the maximum principle for single-input Boolean control networks^[19], on the controllability of Boolean control networks with time delays in states^[20], and so on. Thus, semi-tensor product is a powerful mathematical tool, and it is quite mature in the application of Boolean networks.

This paper is mainly based on Boolean network framework to study cycles of graphs with application to cut-edges and the minimum spanning tree problems by using the semi-tensor product of matrices, and presents a new formulation to deal with cycles problems. Firstly, by defining a characteristic logical vector and using the matrix expression of logical functions, an algebraic description is obtained for cycles of graph, based on which a new necessary and sufficient condition to find all cycles is established for any graph. Secondly, using the necessary and sufficient condition of cycles, two algorithms are established to find all cut-edges and the minimum spanning tree. Finally, the study of illustrative an example shows that the results/algorithms presented in this paper are effective.

The main contributions of this paper are as follows. (i) A new mathematical formulation has been established to deal with cycles, and a set of new theoretical results has been presented under this formulation. (ii) The new theoretical result have been used to find all cut-edges and the minimum spanning tree. According to our method, to check whether an edge subset is part of a cycles, one only needs to compute a kind of structural matrix, with which the conclusion can be easily obtained. Our method expresses cycles in such a clear way that it is very helpful to study of the cut-edge and the minimum spanning tree problems for general graphs. Moreover, for a given graph with the number of cycles not too large, one can easily use our algorithms to find all cut-edges and the minimum spanning tree. It should be pointed out that the advantage of our approach lies in the mathematical formulation and exact results.

The rest of the paper is framed as follow. In Section 2, we give some preliminaries on the semi-tensor product, the pseudo-Boolean function and graph theory. In Section 3, we present a new necessary and sufficient condition to find all cycles of a graph, based on which two new algorithms to find all cut-edges and the minimum spanning tree is designed for any graph. In Section 4, we give an illustrative example to show our new results. The conclusion is given in Section 5.

2 Preliminaries

In this section, we give an outline of semi-tensor product of matrices, pseudo-Boolean function and graph theory, which will be used in the following sections.

Definition 1 (see [21]) For a

n \times m

matrix

A

and a

p \times q

matrix

B

. Then the semi-tensor product of

A

and

B

is defined as follows:

A ⋉ B = (A \otimes I_{ℓ / n}) (B \otimes I_{ℓ / p}),

where

ℓ

is the least common multiple of

n

and

p

, and

\otimes

is the Kronecker product.

Here, the semi-tensor product is consistent with the product of ordinary matrix, when

n = p

is called

A, B

to satisfy the condition of the equal dimension. Therefore, semi-tensor product of matrices is generalized to convention matrix product.

A

and

B

satisfies the condition of the multiple dimension, say,

n = p t

(or

n t = p)

and denote it as

A ≻_{t} B

(or

A ≺_{t} B)

Definition 2 (see [21]) 1) Let

X

be a row vector of dimension

n p

, and

Y

be a column vector with dimension

p

. Split

X

into

p

equal-size blocks as

X^{1}, X^{2}, \dots, X^{p}

, which are

1 \times n

row vectors. We define the (left) semi-tensor product, denoted by

⋉,

{\begin{cases} X ⋉ Y = \sum_{i = 1}^{p} X^{i} y_{i} \in R^{n}, \\ Y^{T} ⋉ X^{T} = \sum_{i = 1}^{p} y_{i} (X^{i})^{T} \in R^{n}, \end{cases}

(1)

where

y_{i} \in R

is the

i

th component of

Y .

2) Let

A \in M_{m \times n}, B \in M_{p \times q}

and

A ≻_{t} B (A ≺_{t} B) .

We define the semi-tensor product of

A

and

B

, denoted by

C = (C^{i j})

, as follow:

C

consists of blocks and each block is defined as

C^{i j} = A^{i} ⋉ B_{j}, i = 1, 2, \dots, m, j = 1, 2, \dots, q,

where

A^{i}

is the

i

th row of

A

and

B_{j}

is the

j

th column of

B .

In fact, the properties of the traditional matrix product are maintained when it is generalized to semi-tensor product. Thus, we can omit the symbol "

⋉

", if no confusion arises in the following discussion.

Suppose

δ_{n}^{i}

denotes the column of the identity matrix

I_{n}

and "

\sim

" stands for "identity" or "equivalence". Set

△_{n} := {δ_{n}^{i} | 1 \leq i \leq n}

, and for notational ease, let

△ := △_{2}

and

△ \sim D := {1, 0} .

n \times t

matrix

M

is called a logical matrix if

M = [δ_{n}^{i_{1}} δ_{n}^{i_{2}} \dots δ_{n}^{i_{t}}],

and for compactness, we express

M

briefly as

M = δ_{n} [i_{1} i_{2} \dots i_{t}] .

The set of

n \times t

logical matrices is denoted by

L^{n \times t}

Definition 3 (see [21]) A swap matrix

W_{[m, n]}

is an

m n \times m n

matrix, defined as follows:

\begin{matrix} W_{[m, n]} = δ_{m n} [1, m + 1, 2 m + 1, \dots, (n - 1) m + 1, \\ 2, m + 2, 2 m + 2, \dots, (n - 1) m + 2, \\ \dots \\ m, 2 m, 3 m, \dots, n m] . \end{matrix}

The swap matrix can be constructed according to the following steps: label its columns by the following sequence

(I, J) = (11, 12, \dots, 1 n, \dots, m 1, m 2, \dots, m n)

and similarly label its rows by the following sequence

(i, j) = (11, 21, \dots, m 1, \dots, 1 n, 2 n, \dots, m n) .

Then its element in the position

[(i, j), (I, J)]

is assigned as

w_{(i, j), (I, J)} = δ_{i, j}^{I, J} = {\begin{cases} 1, I = i a n d J = j, \\ 0, o t h e r w i s e, \end{cases}

when

m = n

, we denote

W_{[n, n]}

W_{[n]}

W_{[m]} .

By Definition 3 is easy to get:

W_{[m, n]} X Y = Y X, \forall X \in R^{m}, Y \in R^{n} .

(2)

Let "1" and "0" represent the logical "True" and "False", respectively. In this paper, we can use the following two logical vectors to represent then:

T := 1 \sim δ_{2}^{1}, F := 0 \sim δ_{2}^{2} .

Similarly, a

k

-valued logical variable

A \in D_{k}

can be equivalently represented with the following vectors:

\frac{k - i}{k - 1} \sim δ_{k}^{i}, i = 1, 2, \dots, k,

where

D_{k} = {1, \frac{k - 2}{k - 1}, \dots, \frac{1}{k - 1}, 0} .

Lemma 1 (see [21]) Let $f (x_{1}, x_{2}, \dots, x_{s})$ be a Boolean function. Then, there exists a unique matrix $M_{f} \in L^{2 \times 2^{s}}$ such that

f (x_{1}, x_{2}, \dots, x_{s}) = M_{f} ⋉_{i = 1}^{s} x_{i}, x_{i} \in △,

(3)

for every $(x_{1}, x_{2}, \dots, x_{s}) \in (△_{2})^{s} .$ $M_{f}$ is called the structure matrix of $f (x)$ .

The first row of the structural matrix

M_{f}

corresponds to the truth values of the logical function

f (x_{1}, x_{2}, \dots, x_{s}) .

Here, we show the structure matrices of some basic Boolean operators (Negation:

\neg, M_{n} = δ_{2} [2 1];

Conjunction:

Λ, M_{c} = δ_{2} [1 2 2 2];

Dummy operator

(σ_{d}) : E_{d} = δ_{2} [1 2 1 2]

), which has the following property: for any two logical variables

u, v \in △, E_{d} u v = v o r E_{d} W_{[2, 2]} u v = u .

Definition 4 (see [22]) An

n

-ary pseudo-Boolean function

f (x_{1}, x_{2}, \dots, x_{n})

is a mapping form

D^{n}

R,

where

D^{n} := \underset{n}{\underset{⏟}{D \times D \times \dots \times D}} .

A graph

G

consists of a vertex set

V = {v_{1}, v_{2}, \dots, v_{n}}

and an edge set

E \subset V \times V,

denoted by

G = {V, E} .

For node

v_{i}

its neighbor set,

N_{i},

is defined as

N_{i} := {v_{j} | e_{i j} = (v_{j}, v_{i}) \in E} .

(4)

Definition 5 (see [23]) If a path has the same starting point and end point, and the starting point and the internal vertex are different from each other, this path is called cycle.

The edge

e

is the cut-edge of

G

if and only if it is not included in a cycle. Graph that do not contain cycle is called acyclic graph, and connected acyclic graph are called trees. The spanning tree is called the minimum spanning tree when the sum of its weights is least.

3 Main Results

In this section, we investigate cut-edges and the minimum spanning trees of the weighted-connected graph by the semi-tensor product method, and present the main results of this paper. First, we consider whether a simple weighted-connected graph has cycles.

Consider a graph

G

with

n

nodes

V = {v_{1}, v_{2}, \dots, v_{n}} .

Assume that the adjacency matrix

A = [a_{i j}]

G

is given as

a_{i j} = {\begin{cases} w_{i j}, v_{j} \in N_{i}, \\ 0, v_{j} \notin N_{i}, \end{cases}

where

w_{i j}

is weight.

In this paper, we study simple weighted-undirected graphs. So, let

a_{i i} = 0, i = 1, 2, \dots, n .

Given a vertex subset

S_{p} \subseteq V

define a vector

V_{S_{p}} = [x_{1}, x_{2}, \dots, x_{n}],

called the characteristic logical vector of

S_{p}

as follows:

x_{i} = {\begin{cases} 1, v_{i} \in S_{p}, \\ 0, v_{i} \notin S_{p} . \end{cases}

Theorem 1 For a graph $G = {V, E}$ the graph $G$ exist cycles. $S_{p}, p = 1, 2, \dots, m$ are all permutation of the vertex of the same cycle in all cycles, if and only if the equation

\sum_{i = 1}^{n} \sum_{j \neq i} φ (b_{i j}) x_{i} x_{j} = 0

(5)

is solvable and exist solutions $x_{i}, i = 1, 2, \dots, n$ of nonzero numbers greater than or equal to $3$ . Where

φ (x) := {\begin{cases} 0, x \geq 2, \\ 1, o t h e r w i s e \end{cases}

and $B = [b_{i j}],$ the $b_{i j}$ express the simple path numbers that $i$ to $j$ simple paths do not have the same edges. The simple paths satisfies: $1)$ $a_{i i_{1}} a_{i_{1} i_{2}} a_{i_{2} i_{3}} \dots a_{i_{r - 1} i_{r}} a_{i_{r} j} \neq 0, l = (i, i_{1}, i_{2}, \dots, i_{r}, j),$ $2)$ the elements in $l$ are different from each other, $3)$ any two paths do not have the same $a_{q t}, q \neq t, q, t \in l .$ Because $i \neq j,$ let $b_{i i} = 2, i = 1, 2, \dots, n .$

Proof (

\Rightarrow

) There are cycles, no rings and heavy edges in the graph, so each cycle contains at least three vertices. In a cycle, taking different vertices

v_{i}, v_{j}, v_{k},

these vertices are one of all permutation of the vertex in the cycle. We have

b_{i j} \geq 2, b_{i k} \geq 2.

Then

φ (b_{i j}) = 0,

thus

φ (b_{i j}) x_{i} x_{j} = 0.

Therefore, we can be advisable to

x_{i} = x_{j} = 1,

similarly,

x_{k} = 1.

Namely, there is a solution whose nonzero number is greater than or equal to 3.

(

\Leftarrow

) Suppose the equation (5) has a solution and that the nonzero number is greater than or equal to 3. Might as well be

x_{i} = x_{j} = 1.

Based on

φ (b_{i j}) x_{i} x_{j} = 0,

we can obtain

φ (b_{i j}) = 0,

which implies that

b_{i j} \geq 2

holds, that is, there is a simple path between

v_{i}

and

v_{j},

and the number of the simple path and the simple path without the same edge is greater than or equal to 2. Therefore,

v_{i}

and

v_{j},

are in the same cycle, similarly,

v_{i}

and

v_{k},

are in the same cycle, so there is a cycle in the graph and

S_{p}

is not empty.

In fact, finding the cut-edges and the minimal spanning of connected graphs, we can find the set of edges in all cycles first. First, we find the sets whose cardinality is greater than or equal to 3 in the

S_{p}, p = 1, 2, \dots, m,

where

S_{p}, p = 1, 2, \dots, m

are all permutation of the vertex of the same cycle in all cycles. Next, we combine the edges in each vertex set

S_{p}

to obtain the set of edges of all cycles in the graph. Therefore, the following theorem is made.

Theorem 2 For each vertex $v_{i} \in V,$ design its characteristic vector by $x_{i} \in D$ and let $y_{i} = [x_{i}, {\bar{x}}_{i}]^{T}, Y_{S_{p}} := ⋉_{i = 1}^{n} y_{i} .$ Then there are cycles in the graph $G,$ and the set of edges of all the cycles is

S = ⋃_{p = 1, | S_{p} | \geq 3}^{m} E (S_{p}),

if and only if the $k_{p} t h$ component of fist row of matrix $H$ is zero, when $Y_{S_{p}} = δ_{2^{n}}^{k_{p}}, S_{p}$ is a solution of the equation

J_{1} H Y_{S_{p}} = 0

(6)

and exists $p$ such that $| S_{p} | \geq 3,$ where

{\begin{cases} H = \sum_{i = 1}^{n} \sum_{j \neq i} φ (b_{i j}) H_{i j}, \\ H_{i j} = H_{j i} = M_{c} (E_{d})^{n - 2} W_{[2^{j}, 2^{n - j}]} W_{[2^{i}, 2^{j - i - 1}]}, i < j, \end{cases}

(7)

$| S_{p} |$ is cardinality of $S_{p},$ and $E (S_{p})$ is edges of the set $S_{p}$ of the vertex. Furthermore the number of zero components of $J_{1} H$ is just the number of solutions of the equation $(6)$ , that is, $m .$

Proof (

\Rightarrow

) If there are cycles in the graph, then

S_{p}, p = 1, 2, \dots, m

are all permutation of the vertex of the same cycle in all cycles. By Theorem 1, the equation (5) holds. Since

x_{i} x_{j} = x_{j} x_{i} = (x_{i} \land x_{j}),

without loss of generality, we assume that

i < j .

Then, using (1), (2), and the dummy operator

(E_{d}),

we have

\begin{matrix} y_{i} y_{j} = (E_{d})^{n - 2} y_{j + 1} \dots y_{n} y_{i + 1} \dots y_{j - 1} y_{1} \dots y_{i - 1} y_{i} y_{j} \\ = (E_{d})^{n - 2} W_{[2^{j}, 2^{n - j}]} y_{i + 1} \dots y_{j - 1} y_{1} \dots y_{i} y_{j} y_{j + 1} \dots y_{n} \\ = (E_{d})^{n - 2} W_{[2^{j}, 2^{n - j}]} W_{[2^{i}, 2^{j - i - 1}]} y_{1} \dots y_{i} y_{i + 1} \dots y_{j - 1} y_{j} \dots y_{n}, \end{matrix}

where the product is

" ⋉ " .

Thus,

x_{i} \land x_{j} = J_{1} H_{i j} ⋉_{i = 1}^{n} y_{i},

where

J_{1} = [1, 0]

and

H_{i j} = M_{c} (E_{d})^{n - 2} W_{[2^{j}, 2^{n - j}]} W_{[2^{i}, 2^{j - i - 1}]} .

So, the equation (5) can be expressed as

0 = \sum_{i = 1}^{n} \sum_{j \neq i} φ (b_{i j}) x_{i} x_{j} = J_{1} \sum_{i = 1}^{n} \sum_{j \neq i} φ (b_{i j}) H_{i j} ⋉_{i = 1}^{n} y_{i} = J_{1} H Y_{S_{p}},

(8)

which implies that satisfies the equation (8). Noticing that

Y_{S_{p}} = δ_{2^{n}}^{k_{p}} \in Δ_{2^{n}},

the

k_{p}

th component of

J_{1} H

much be zero, that is, the

k_{p}

th component of fist row of matrix

H

is zero. Because the graph is a simple graph, we can find

p

such that

| S_{p} | \geq 3.

So, the necessity is proved.

(

\Leftarrow

) If the

k_{p}

th,

p = 1, 2, \dots, m

component of fist row of matrix

H

are zero, then it can be seem form the assumption on

Y_{S_{p}} = δ_{2^{n}}^{k_{p}},

that

J_{1} H Y_{S_{p}} = 0.

The equation (5) has solutions

S_{p}, p = 1, 2, \dots, m,

and exist

p

such that

| S_{p} | \geq 3.

Noticing

x_{i} \in D

and

φ (b_{i j}) \geq 0,

we know form the equation (5) that

φ (b_{i j}) x_{i} x_{j} = 0.

So, existing

i \neq j \neq k

such that

φ (b_{i j}) \neq 0, φ (b_{i k}) \neq 0, φ (b_{j k}) \neq 0,

that is,

b_{i j} < 2, b_{i k} < 2, b_{j k} < 2,

which implies that there are simple paths for any two different vertices in the

{v_{i}, v_{j}, v_{k}},

and the number of the simple path and the simple path without the same edge is greater than or equal to 2. According to the definition of the cycles, there are cycles in the graph and the collection of edges of all cycles is

S = ⋃_{p = 1, | S_{p} | \geq 3}^{m} E (S_{p}) .

So, the sufficiency is proved.

By Theorem 2, the resulting set

S

contains the edges of all cycles in the graph. Structural matrices

H_{i j}

and

H

are easily computed using a computer. On the basis of finding the edge set of all cycles in the graph, the Algorithm 1 and Algorithm 2 are designed to find all the cut edges and the minimum spanning tree in the weighted-connected graph.

Algorithm 1 For a weighted-connected graph

G = {V, E}

with

n

vertices. Assume that its adjacency matrix is

A = [a_{i j}] .

Let

B = [b_{i j}],

the

b_{i j}

express the simple path numbers that

i

j

simple paths do not have the same edges.. For each vertex

v_{i}

with its characteristic logical vector

x_{i} \in D,

then let

y_{i} = [x_{i}, {\bar{x}}_{i}]^{T} .

To find all the cut edges of graph

G,

we can take the following steps.

1) Compute the matrix

H = \sum_{i = 1}^{n} \sum_{j \neq i} φ (b_{i j}) H_{i j},

where

H_{i j} = M_{c} (E_{d})^{n - 2} W_{[2^{j}, 2^{n - j}]} W_{[2^{i}, 2^{j - i - 1}]} .

2) Take out the first row of

H,

and denote it by

β = [b_{1}, b_{2}, \dots, b_{2^{n}}] .

If for all

i, b_{i} \neq 0,

then graph

G

has no the cycle and the algorithm is stopped, that is, all edges are cut-edges in the graph. Otherwise, find all the zero components of

β,

that is to say,

b_{k_{p}} = 0, p = 1, 2, \dots, m .

3) For each index

k_{p}, p = 1, 2, \dots, m,

consider

⋉_{i = 1}^{n} y_{i} = δ_{2^{n}}^{k_{p}} .

Let^[24]

{\begin{cases} S_{1}^{n} = δ_{2} [\underset{2^{n - 1}}{\underset{⏟}{1 \dots 1}} \underset{2^{n - 1}}{\underset{⏟}{2 \dots 2}}], \\ S_{2}^{n} = δ_{2} [\underset{2^{n - 2}}{\underset{⏟}{1 \dots 1}} \underset{2^{n - 2}}{\underset{⏟}{2 \dots 2}} \underset{2^{n - 2}}{\underset{⏟}{1 \dots 1}} \underset{2^{n - 2}}{\underset{⏟}{2 \dots 2}}], \\ ⋮ \\ S_{n}^{n} = δ_{2} \underset{2^{n - 1}}{\underset{⏟}{[\underset{2}{\underset{⏟}{12}} \dots \underset{2}{\underset{⏟}{12}}]}}, \end{cases}

(9)

then we have

y_{i} = S_{i}^{n} ⋉_{i = 1}^{n} y_{i} = S_{i}^{n} δ_{2^{n}}^{k_{p}}, i = 1, 2, \dots, n .

Noticing that

y_{i} = [x_{i}, {\bar{x}}_{i}]^{T},

we need to check

y_{i}

whether

δ_{2}^{1}

x_{i} .

Let

S (k_{p}) = {v_{i} | y_{i} = δ_{2}^{1}, 1 \leq i \leq n} .

4) If

| S (k_{p}) | < 3

for all

p, p = 1, 2, \dots, m,

then graph

G

has no the cycle and the algorithm is stopped, that is, all edges are cut-edges in the graph. Otherwise, combine the edges of all vertex sets

| S (k_{p}) | \geq 3

to get the set

S

of edges of all cycles, that is to say, the set

S

contains edges of all cycles in the graph

G

corresponding to

b_{k_{p}} = 0

and exist solutions

x_{i}, i = 1, 2, \dots, n

of nonzero numbers greater than or equal to 3. Let

S = {e_{i j} | a_{i j} = a_{j i} \neq 0, i < j, v_{i}, v_{j} \in S_{p}, | S_{p} | \geq 3, p = 1, 2, \dots, m} .

5) Delete all edges in

S

and update the adjacency matrix

A .

Form the definition of the cut-edge, we can see that all the cut-edges are

η = {e_{i j} | a_{i j} = a_{j i} \neq 0, i < j, i, j = 1, 2, \dots, n} .

Similarly, we can obtain the following algorithm.

Algorithm 2 For a weighted-connected graph

G = {V, E}

with

n

vertices. Assume that its adjacency matrix is

A = [a_{i j}] .

Let

B = [b_{i j}],

the

b_{i j}

express the simple path numbers that

i

j

simple paths do not have the same edges. For each vertex

v_{i}

with its characteristic logical vector

x_{i} \in D,

then let

y_{i} = [x_{i}, {\bar{x}}_{i}]^{T} .

To find the minimum spanning tree of graph

G,

we can take the following steps.

1) Compute the matrix

H = \sum_{i = 1}^{n} \sum_{j \neq i} φ (b_{i j}) H_{i j},

where

H_{i j} = M_{c} (E_{d})^{n - 2} W_{[2^{j}, 2^{n - j}]} W_{[2^{i}, 2^{j - i - 1}]} .

2) Take out the first row of

H,

and denote it by

β = [b_{1}, b_{2}, \dots, b_{2^{n}}] .

If for all

i, b_{i} \neq 0,

then graph

G

has no the cycle and the algorithm is stopped, that is, the graph itself is the minimum spanning tree. Otherwise, find all the zero components of

β,

that is to say,

b_{k_{p}} = 0, p = 1, 2, \dots, m .

3) For each index

k_{p}, p = 1, 2, \dots, m,

consider

⋉_{i = 1}^{n} y_{i} = δ_{2^{n}}^{k_{p}} .

By the equation (9), then we have

y_{i} = S_{i}^{n} ⋉_{i = 1}^{n} y_{i} = S_{i}^{n} δ_{2^{n}}^{k_{p}}, i = 1, 2, \dots, n .

Noticing that

y_{i} = [x_{i}, {\bar{x}}_{i}]^{T},

we need to check

y_{i}

whether

δ_{2}^{1}

x_{i} .

Let

S (k_{p}) = {v_{i} | y_{i} = δ_{2}^{1}, 1 \leq i \leq n} .

4) If

| S (k_{p}) | < 3

for all

p, p = 1, 2, \dots, m,

then graph

G

has no the cycle and the algorithm is stopped, that is, the graph itself is the minimum spanning tree. Otherwise, combine the edges of all vertex sets

| S (k_{p}) | \geq 3

to get the set

S

of edges of all cycles, that is to say, the set

S

contains edges of all cycles in the graph

G

corresponding to

b_{k_{p}} = 0

and exist solutions

x_{i}, i = 1, 2, \dots, n

of nonzero numbers greater than or equal to 3. Let

S = {e_{i j} | a_{i j} = a_{j i} \neq 0, i < j, v_{i}, v_{j} \in S_{p}, | S_{p} | \geq 3, p = 1, 2, \dots, m} .

5) Delete the maximum weight of one edge in

S

(If the weights are equal, then the minimum spanning tree is not unique, delete arbitrary one edge) and update the adjacency matrix

A

and the matrix

B,

loop (1) (2) (3) (4) (5), where (3) is only counted once. Every time loop (3), we only need to find the corresponding

S (k_{p})

(5) in the result of the first calculation.

Algorithm 1 and Algorithm 2 respectively find all cut edges and the minimum spanning tree of weighted-connected graph. A weighted connected graph with 5 vertices is given, and the feasibility of Algorithm 1 and Algorithm 2 are illustrated by computing all cut edges and the minimum spanning tree.

4 Illustrative Example

In the section, we give one example to illustrate the feasibility of the Algorithm 1 and the Algorithm 2 obtained in this paper.

Example: Consider the weighted-connected graph

G = {V, E}

shown in Figure 1. We use Algorithm 1 and Algorithm 2 to find all cut edges and the minimum spanning tree of the graph.

Figure 1 The weighted-connected graph

Full size|PPT slide

The adjacency matrix of this graph is as follows:

A = [\begin{array}{ccccc} 0 & 0 & 0 & 0 & 3 \\ 0 & 0 & 6 & 0 & 5 \\ 0 & 6 & 0 & 5 & 4 \\ 0 & 0 & 5 & 0 & 2 \\ 3 & 5 & 4 & 2 & 0 \end{array}] .

(10)

B = [b_{i j}],

the

b_{i j}

express the simple path numbers that

i

j

simple paths do not have the same edges. The simple paths satisfies: 1)

a_{i i_{1}} a_{i_{1} i_{2}} a_{i_{2} i_{3}} \dots a_{i_{r - 1} i_{r}} a_{i_{r} j} \neq 0, l = (i, i_{1}, i_{2}, \dots, i_{r}, j),

2) the elements in

l

are different from each other, 3) any two paths do not have the same

a_{q t}, q \neq t, q, t \in l .

Just find two such paths in the adjacency matrix (10), we can obtain

φ (b_{i j}) = 0

and

C = [φ (b_{i j})_{i j}] = [\begin{array}{ccccc} 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \end{array}] .

For each vertex

v_{i} \in V,

we assign it a characteristic logical variable

x_{i} \in D

and let

y_{i} = [x_{i}, {\bar{x}}_{i}]^{T}, i = 1, 2, \dots, 5.

By the equation (9) and using the MATLAB Toolbox, we can easily obtain

\begin{matrix} β = [b_{1}, b_{2}, \dots, b_{32}] = J_{1} \times (H_{12} + H_{13} + H_{14} + H_{15} + H_{21} + H_{31} + H_{41} + H_{51}) \\ = [8 6 6 4 6 4 4 2 6 4 4 2 4 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] . \end{matrix}

Then, it is easy to see that the index is zero in

β,

with

k = [16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32] .

For each

k_{p} \in k,

let

⋉_{i = 1}^{5} = δ_{32}^{k_{p}} .

Based on the equation (9), by computing

y_{i} = S_{i}^{5} ⋉_{i = 1}^{5} = S_{i}^{5} δ_{32}^{k_{p}}, i = 1, 2, \dots, 5,

we have

k_{1} = 16 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (1, 0, 0, 0, 0), k_{2} = 17 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (0, 1, 1, 1, 1),

k_{3} = 18 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (0, 1, 1, 1, 0), k_{4} = 19 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (0, 1, 1, 0, 1),

k_{5} = 20 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (0, 1, 1, 0, 0), k_{6} = 21 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (0, 1, 0, 1, 1),

k_{7} = 22 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (0, 1, 0, 1, 0), k_{8} = 23 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (0, 1, 0, 0, 1),

k_{9} = 24 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (0, 1, 0, 0, 0), k_{10} = 25 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (0, 0, 1, 1, 1),

k_{11} = 26 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (0, 0, 1, 1, 0), k_{12} = 27 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (0, 0, 1, 0, 1),

k_{13} = 28 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (0, 0, 1, 0, 0), k_{14} = 29 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (0, 0, 0, 1, 1),

k_{15} = 30 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (0, 0, 0, 1, 0), k_{16} = 31 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (0, 0, 0, 0, 1),

k_{17} = 32 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (0, 0, 0, 0, 0) .

(11)

Thus, we can obtain

\begin{array}{rcl} S (k_{1}) = {v_{1}}, S (k_{2}) = {v_{2}, v_{3}, v_{4}, v_{5}}, S (k_{3}) = {v_{2}, v_{3}, v_{4}}, \\ S (k_{4}) = {v_{2}, v_{3}, v_{5}}, S (k_{5}) = {v_{2}, v_{3}}, S (k_{6}) = {v_{2}, v_{4}, v_{5}}, \\ S (k_{7}) = {v_{2}, v_{4}}, S (k_{8}) = {v_{2}, v_{5}}, S (k_{9}) = {v_{2}}, \\ S (k_{10}) = {v_{3}, v_{4}, v_{5}}, S (k_{11}) = {v_{3}, v_{4}}, S (k_{12}) = {v_{3}, v_{5}}, \\ S (k_{13}) = {v_{3}}, S (k_{14}) = {v_{4}, v_{5}}, S (k_{15}) = {v_{4}}, S (k_{16}) = {v_{5}}, S (k_{17}) = {\emptyset}, \end{array}

where all the sets of elements greater than or equal to three are as follows:

S (k_{2}) = {v_{2}, v_{3}, v_{4}, v_{5}}, S (k_{3}) = {v_{2}, v_{3}, v_{4}}, (k_{4}) = {v_{2}, v_{3}, v_{5}},

S (k_{6}) = {v_{2}, v_{4}, v_{5}}, S (k_{10}) = {v_{3}, v_{4}, v_{5}},

combine the edges of all vertex sets

| S (k_{p}) | \geq 3

to get the set

S

of edges of all cycles.

S

is as follows:

S = {e_{i j} | a_{i j} = a_{j i} \neq 0, i < j, v_{i}, v_{j} \in S_{p}, p = 2, 3, 4, 6, 10} = {e_{23}, e_{25}, e_{34}, e_{35}, e_{45}} .

(12)

All the cut edges of Figure 1 are calculated by Algorithm 1. We delete all edges in

S

and update the adjacency matrix (10). We can obtain

A = [\begin{array}{ccccc} 0 & 0 & 0 & 0 & 3 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 3 & 0 & 0 & 0 & 0 \end{array}] .

(13)

By the adjacency matrix (13), all the cut edges of Figure 1 are as follows:

η = {e_{i j} | a_{i j} = a_{j i} \neq 0, i < j, i, j = 1, 2, \dots, 5} = {e_{12}} .

By Algorithm 1, all edges in Figure 1 are successfully found.

Next, finding the minimum spanning tree in Figure 1, according to Algorithm 2. We delete the maximum weight of one edge

e_{23}

in (12) and update the adjacency matrix (10) and the matrix

B .

We can obtain

A = [\begin{array}{ccccc} 0 & 0 & 0 & 0 & 3 \\ 0 & 0 & 0 & 0 & 5 \\ 0 & 0 & 0 & 5 & 4 \\ 0 & 0 & 5 & 0 & 2 \\ 3 & 5 & 4 & 2 & 0 \end{array}]

(14)

and

C = [φ (b_{i j})_{i j}] = [\begin{array}{ccccc} 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \end{array}] .

For each vertex

v_{i} \in V,

we assign it a characteristic logical variable

x_{i} \in D

and let

y_{i} = [x_{i}, {\bar{x}}_{i}]^{T}, i = 1, 2, \dots, 5.

By the equation (9) and using the MATLAB Toolbox, we can easily obtain

\begin{matrix} β = [b_{1}, b_{2}, \dots, b_{32}] = J_{1} \times (H_{12} + H_{13} + H_{14} + H_{15} + H_{21} + H_{31} + H_{41} + H_{51} \\ + H_{23} + H_{24} + H_{25} + H_{32} + H_{42} + H_{52}) \\ = [14 10 10 6 10 6 6 2 6 4 4 2 4 2 2 0 6 4 4 2 4 2 2 0 0 0 0 0 0 0 0 0] . \end{matrix}

Then, it is easy to see that the index is zero in

β,

with

k = [16 24 25 26 27 28 29 30 31 32] .

For each

k_{p} \in k,

let

⋉_{i = 1}^{5} = δ_{32}^{k_{p}} .

Based on the equation (11), we can obtain

k_{1} = 16 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (1, 0, 0, 0, 0), k_{2} = 24 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (0, 1, 0, 0, 0),

k_{3} = 25 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (0, 0, 1, 1, 1), k_{4} = 26 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (0, 0, 1, 1, 0),

k_{5} = 27 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (0, 0, 1, 0, 1), k_{6} = 28 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (0, 0, 1, 0, 0),

k_{7} = 29 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (0, 0, 0, 1, 1), k_{8} = 30 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (0, 0, 0, 1, 0),

k_{9} = 31 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (0, 0, 0, 0, 1), k_{10} = 32 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (0, 0, 0, 0, 0) .

Thus, we can obtain

S (k_{1}) = {v_{1}}, S (k_{2}) = {v_{2}}, S (k_{3}) = {v_{3}, v_{4}, v_{5}}, S (k_{4}) = {v_{3}, v_{4}}, S (k_{5}) = {v_{3}, v_{5}},

S (k_{6}) = {v_{3}}, S (k_{7}) = {v_{4}, v_{5}}, S (k_{8}) = {v_{4}}, S (k_{9}) = {v_{5}}, S (k_{10}) = {\emptyset},

where all the sets of elements greater than or equal to three are as follows:

S (k_{3}) = {v_{3}, v_{4}, v_{5}},

combine the edges of all vertex sets

| S (k_{p}) | \geq 3

to get the set

S

of edges of all cycles.

S

is as follows:

S = {e_{i j} | a_{i j} = a_{j i} \neq 0, i < j, v_{i}, v_{j} \in S_{p}, p = 3} = {e_{34}, e_{35}, e_{45}} .

(15)

We delete the maximum weight of one edge

e_{34}

in (14) and update the adjacency matrix (10) and the matrix

B .

We can obtain

A = [\begin{array}{ccccc} 0 & 0 & 0 & 0 & 3 \\ 0 & 0 & 0 & 0 & 5 \\ 0 & 0 & 0 & 0 & 4 \\ 0 & 0 & 0 & 0 & 2 \\ 3 & 5 & 4 & 2 & 0 \end{array}]

(16)

and

C = [φ (b_{i j})_{i j}] = [\begin{array}{ccccc} 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 \end{array}] .

For each vertex

v_{i} \in V,

we assign it a characteristic logical variable

x_{i} \in D

and let

y_{i} = [x_{i}, \bar{x_{i}}]^{T}, i = 1, 2, \dots, 5.

By the equation (9) and using the Matlab toolbox, we can easily obtain

\begin{matrix} β = [b_{1}, b_{2}, \dots, b_{32}] = J_{1} \times (H_{12} + H_{13} + H_{14} + H_{15} + H_{21} + H_{31} + H_{41} + H_{51} + H_{23} + H_{24} \\ + H_{25} + H_{32} + H_{42} + H_{52} + H_{34} + H_{35} + H_{45} + H_{43} + H_{53} + H_{54}) \\ = [20 12 12 6 12 6 6 2 12 6 6 2 6 2 2 0 12 6 6 2 6 2 2 0 6 2 2 0 2 0 0 0] . \end{matrix}

Then, it is easy to see that the index is zero in

β,

with

k = [16 24 28 30 31 32] .

For each

k_{p} \in k,

let

⋉_{i = 1}^{5} = δ_{32}^{k_{p}} .

By the equation (11), we can obtain

k_{1} = 16 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (1, 0, 0, 0, 0), k_{2} = 24 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (0, 1, 0, 0, 0),

k_{3} = 28 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (0, 0, 1, 0, 0), k_{4} = 30 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (0, 0, 0, 1, 0),

k_{5} = 31 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (0, 0, 0, 0, 1), k_{6} = 32 \sim (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (0, 0, 0, 0, 0) .

Thus, we can obtain

S (k_{1}) = {v_{1}}, S (k_{2}) = {v_{2}}, S (k_{3}) = {v_{3}}, S (k_{4}) = {v_{4}}, S (k_{5}) = {v_{5}}, S (k_{6}) = {\emptyset} .

There is no set of elements greater than or equal to three, and the adjacency matrix of the calculation is a minimum spanning tree's adjacency matrix. Its image is shown as Figure 2.

Figure 2 The minimum spanning tree of graph $G$

Full size|PPT slide

Using Algorithm 2, we successfully find the minimum spanning tree of Figure 1.

5 Conclusion

In this paper, we have studied how to use semi-tensor product algebra formula all the cycles of the weighted-connected graph, further designed two algorithms to find all the cut edges and the minimum spanning tree in the graph. The traditional construction method of cutting property and cycle properties of graphs based on these two properties are given. This algorithm is based on the split cycles, to determine whether there are the cycles design. Our method expresses cycles in such a clear way that it was very helpful to study of the cut-edge and the minimum spanning tree problems for general graphs. Moreover, for a given graph with the number of cycles not too large, one can easily use our algorithms to find all cut-edges and the minimum spanning tree. It should be pointed out that the advantage of our approach lies in the mathematical formulation and exact decision results.

References

Publishing order | Descend order by publishing year | Descend order by cited within

1	Chung F. Graph theory in the information age. Notices of AMS, 2010, 57(6): 726- 732. Cited in this article [1]

2	Adolfo P M, Alkiviadis K, Victor M E, et al. Wikipedia information flow analysis reveals the scale-free architecture of the semantic space. PLoS One, 2011, 6(2): e17333. https://doi.org/10.1371/journal.pone.0017333 Cited in this article [1]

3	Cheng D Z, Qi H S. Theory and application of matrix semi tensor product. Beijing: Science Press, 2007. Cited in this article [1]

4	Cheng D Z, Qi H S, Li Z Q. Analysis and control of Boolean networks: A semi-tensor product Approach. London: Springer, 2011. Cited in this article [1]

5	Cheng D Z, Qi H S. A linear representation of dynamics of Boolean networks. IEEE Transactions on Automatic Control, 2010, 55(10): 2251- 2258. https://doi.org/10.1109/TAC.2010.2043294 Cited in this article [1]

6	Li H T, Wang Y Z, Liu Z B. Existence and number of fixed points of Boolean transformations via the semi-tensor product method. Applied Mathematics Letters, 2012, 25(8): 1142- 1147. https://doi.org/10.1016/j.aml.2012.02.023 Cited in this article [1]

7	Dmitriy L, Michael M, Guy E. Observability of Boolean networks: A graph theoretic approach. Automatica, 2013, 49(8): 2351- 2362. https://doi.org/10.1016/j.automatica.2013.04.038 Cited in this article [1]

8	Ettore F, Maria E V. Observability, reconstructibility and state observers of Boolean control networks. IEEE Transactions on Automatic Control, 2013, 58(6): 1390- 1401. https://doi.org/10.1109/TAC.2012.2231592

9	Liu Y, Chen H W, Lu J Q, et al. Controiiability of probabilistic Boolean control networks based on transition probability matrices. Automatica, 2015, 52, 340- 345. https://doi.org/10.1016/j.automatica.2014.12.018

10	Liu Y, Lu J Q, Wu B. Some necessary and sufficient conditions for the out put controllability of temporal Boolean control networks. ESAIM Control Optimisation and Calculus of Variation, 2014, 20(1): 158- 173. https://doi.org/10.1051/cocv/2013059 Cited in this article [1]

11	Cheng D Z, Qi H S. Controllability and observability of Boolean control networks. Automatica, 2009, 45(7): 1659- 1667. https://doi.org/10.1016/j.automatica.2009.03.006 Cited in this article [1]

12	Zhong J, Lu J Q, Liu Y, et al. Synchronization in an array of outputcoupled Boolean networks with time delay. IEEE Transactions on Neural Networks and Learning Systems, 2014, 25(12): 2288- 2294. https://doi.org/10.1109/TNNLS.2014.2305722 Cited in this article [1]

13	Zhong J, Lu J Q, Huang T W, et al. Synchronization of master-slave Boolean networks with impulsive effects: Necessary and sufficient criteria. Neurocomputing, 2014, 143, 269- 274. https://doi.org/10.1016/j.neucom.2014.05.065

14	Lu J Q, Zhong J, Tang Y, et al. Synchronization in output-coupled temporal Boolean networks. Scientific Reports, 2014, 4, 6292. https://doi.org/10.1038/srep06292

15	Li R, Chu T G. Complete synchronization of Boolean networks. IEEE Transactions on Neural Networks and Learning Systems, 2012, 23(5): 840- 846. https://doi.org/10.1109/TNNLS.2012.2190094

16	Li F F. Synchronization of coupled large-scale Boolean networks. Chaos, 2014, 24(1): 013115. https://doi.org/10.1063/1.4863858

17	Cheng D Z. Disturbance decoupling of Boolean control networks. IEEE Transactions on Automatic Control, 2010, 20(3): 561- 582.

18	Cheng D Z, Li Z Q, Qi H S. Realization of Boolean control networks. Automatica, 2010, 46(1): 62- 69. https://doi.org/10.1016/j.automatica.2009.10.036 Cited in this article [1]

19	Laschov D, Margaliot M. A maximum principle for single-input boolean control networks. IEEE Transactions on Automatic Control, 2011, 56(4): 913- 917. https://doi.org/10.1109/TAC.2010.2101430 Cited in this article [1]

20	Li F F, Sun J T. Controllability of Boolean control networks with time delays in states. Automatica, 2011, 47(3): 603- 607. https://doi.org/10.1016/j.automatica.2011.01.040 Cited in this article [1]

21	Cheng D Z, Qi H S, He F G. Mapping and dynamic process on finite set use matrix semi tensor product method. Beijing: Science Press, 2015. Cited in this article [4]

22	Liu Y C, Zhang W. Boolean methodology. Shanghai: Shanghai Technology Literature Press, 1993. Cited in this article [1]

23	Reinhard D. Graph Theory, Graduate Texts in Mathematics. Fourth Edition New York: Springer, 2010. Cited in this article [1]

24	Wang Y Z, Zhang C G, Liu Z B. A matrix approach to graph maximum stable set and coloring problems with application to multi-agent systems. Automatica, 2012, 48(7): 1227- 1236. https://doi.org/10.1016/j.automatica.2012.03.024 Cited in this article [1]

Funding

the Natural Science Foundation of Hebei Province(61203142)

PDF(200 KB)

172

Accesses

Citation

Detail

Sections

Recommended

Abstract
Key words
Cite this article
1 Introduction
2 Preliminaries
3 Main Results
4 Illustrative Example
Figure 1 The weighted-connected graph
Figure 2 The minimum spanning tree of graph $G$
5 Conclusion
References
Funding

Received	Accepted	Published
2017-07-17	2018-03-06	2018-10-25
Issue Date
2018-10-25

Please choose a citation manager

Content to export

Abstract

Key words

Cite this article

1 Introduction

2 Preliminaries

3 Main Results

4 Illustrative Example

Figure 1 The weighted-connected graph

Figure 2 The minimum spanning tree of graph $G$

5 Conclusion

{{custom_sec.title}}

{{custom_sec.title}}

References

{{custom_fnGroup.title_en}}

Footnotes

Funding

Share

模态框（Modal）标题

Please choose a citation manager

Content to export

Abstract

Key words

Cite this article

1 Introduction

2 Preliminaries

3 Main Results

4 Illustrative Example

Figure 1 The weighted-connected graph

Figure 2 The minimum spanning tree of graph G

5 Conclusion

{{custom_sec.title}}

{{custom_sec.title}}

References

{{custom_fnGroup.title_en}}

Footnotes

Funding

Figure 2 The minimum spanning tree of graph $G$