1
Undefined 1 (2018) 1–11 IOS Press
Cycle Index of Uncertain Random Graph Lin Chen a , Jin Peng b , Congjun Rao c , and Isnaini Rosyida d,∗ a
College of Management and Economics, Tianjin University, Tianjin 300072, China E-mail: linchen@tju.edu.cn b Institute of Uncertain System, Huanggang Normal University, Hubei 438000, China E-mail: peng@hgnu.edu.cn c School of Science, Wuhan University of Technology, Hubei 430070, China E-mail: cjrao@whut.edu.cn d Department of Mathematics, Universitas Negeri Semarang, Semarang 50229, Indonesia E-mail: isnaini@mail.unnes.ac.id
Abstract. With the increasing of the complexity of a system, there is a variety of indeterminacy in the practical applications of graph theory. We focus on uncertain random graph, in which some edges exist with degrees in probability measure and others exist with degrees in uncertain measure. In this paper, the chance theory is applied to construct the cycle index of an uncertain random graph. Then a method to calculate the cycle index of an uncertain random graph is presented. We also discuss some properties of the cycle index. Keywords: Cycle index, Uncertain random graph, Chance theory, Uncertainty theory
1. Introduction In real life, graph theory is applied to many problems, such as vertex covering problem (Chen et al. [13]), traveling salesman problem (Ma et al. [36]), vertex coloring problem (Chen et al. [14]), and so on. In classical graph theory, these problems are often considered in a determinacy environment, in which all the edges and the vertices can be completely determined. For more research on the theoretical problems and applications of classical graph theory, we may consult Wallis [42]. As the system becomes more complex, different types of vagueness are frequently encountered in practical application of graph theory. Sometimes, it cannot be completely determined whether two vertices are joined by an edge or not. Then, a problem is arise: how to deal with these vagueness phenomena? On one hand, many researchers regarded that vagueness phenomena belonged to the fuzziness phenomena, and * Corresponding author. Isnaini Rosyida, Department of Mathematics, Universitas Negeri Semarang, Semarang 50229, Indonesia, E-mail: isnaini@mail.unnes.ac.id.
they introduced fuzzy set theory into the graph theory. Rosenfeld [38] introduced a fuzzy graph with fuzzy vertex set and fuzzy edge set. The membership function of the fuzzy edge set is employed by Rosenfeld [38] to describe whether two vertices were joined by an edge or not. There are some new concepts related to fuzzy phenomena in graph theory, such as: bipolar fuzzy graphs [2], intuitionistic fuzzy hypergraphs [6], strong intuitionistic fuzzy graphs [5], N hypergraphs [4], fuzzy soft graphs [8], bipolar fuzzy digraphs [3], regular interval-valued fuzzy graphs [41], generalized fuzzy hypergraphs [17], domination in mpolar fuzzy graphs [9], and neutrosophic graphs [10]. Furthermore, the fuzzy phenomena in graph coloring problem has been investigated by Rosyida et al. [39] which developed a method to determine a fuzzy chromatic number of fuzzy graph. On the other hand, some researchers handled the indeterminacy phenomena with randomness phenomena, and they used probability theory into the graph theory. The concept of random graph was first investigated by Erdős and Rényi [16], also by Gilbert [27] at nearly the same time. They thought that whether
c 2018 – IOS Press and the authors. All rights reserved 0000-0000/18/$00.00 ⃝
2
L. Chen et al. / Cycle Index of Uncertain Random Graph
two vertices were joined by an edge or not can be described as a random variable. After that, many researchers, such as Alon et al. [11], Gamarnik and Sviridenko [18], and Gilmer and Kopparty [28] have done a lot of works in this field. Although randomness has been used to characterize the indeterminacy phenomena, some imprecise quantities, such as information and knowledge represented by human language, do not behave like randomness (Akram and Dudek [6], Akram and Nawaz [8]). In order to model these imprecise quantities, Liu [29] founded the uncertainty theory. In the area of graph theory, some researchers have employed the uncertainty theory to deal with imprecise quantities in graphs. The concept of uncertain graph was given by Gao and Gao [24]. In their paper, a connectedness index was introduced to measure the degree that an uncertain graph was connected. After that, Zhang and Peng [43] discussed the Euler tour in an uncertain graph. In addition, Gao investigated the cycle index [21] and the regularity index [22], Gao [23] proposed a method to calculate the tree index, path index, and star index, and Gao et al. [26] discussed the diameter for an uncertain graph. Recently, Gao and Qin [25] concerned with how to calculate the uncertain measure that an uncertain graph was edge-connected. Different from the coloring problem of classical graph, Rosyida et al. [40] introduced a new approach to color an uncertain graph based on an α-cut of the uncertain graph. Chen et al. [14] investigated uncertain vertex coloring problem based on maximum uncertain independent vertex set. In order to propose the usefulness of uncertain graph, we explain the difference between fuzzy graph e and uncertain graph. The fuzzy graph G(V, Ẽ) is a generalization of classical graph based on fuzzy set theory. It contains a fuzzy edge set Ẽ with a membership function µẼ which has the value in [0, 1]. Whether two vertices u and v connected by an edge or not is represented by the membership function µẼ (uv). If µẼ (uv) = 0, then the vertices u and v are not connected by an edge. Different from this point of view, the uncertain graph Ǧ = (V, E, ξ) is a generalization of classical graph based on uncertainty theory. It is a triple consisting of a vertex set V , an edge set E, and an indicator function ξ. The indicator function ξ is a Boolean uncertain variable which is used to indicate the existence of an edge between two vertices with a belief degree in uncertain measure. If two vertices vi and vj are connected by an edge, then ξ({vi vj }) = 1 with the belief degree M{ξij = 1} = αij where
αij ∈ [0, 1]. Otherwise, if vi and vj are not connected by an edge, then ξ({vi vj }) = 0 with the belief degree M{ξij = 0} = 1 − αij . As the system becomes more complex, the uncertainty and randomness are required to be considered simultaneously in a system. Chance theory, which was pioneered by Liu [33] via giving the concepts of uncertain random variable and chance measure, can be employed to deal with such complex system. Some basic concepts of chance theory such as chance distribution, expected value, and variance were proposed by Liu [33]. As an important contribution to chance theory, Liu [33] presented an operational law of uncertain random variables. After that, chance theory was developed steadily and applied widely. It follows from the development of chance theory, Liu [32] initialized the concept of uncertain random graph. In an uncertain random graph, some edges exist with degrees in probability measure and others exist with degrees in uncertain measure. In the paper of Liu [32], the connectivity index of an uncertain random graph was investigated. Recently, Zhang et al. [44] considered the Euler tour in an uncertain random graph. They put forward a formula to calculate the Euler index of the uncertain random graph, and discussed some properties of the Euler index. Zhang et al. [45] investigated the matching index of uncertain random graph and gave an algorithm to compute the matching index and perfect matching index for uncertain random graph. Cycle is one of the basic concepts of graph theory (Akram et al. [7]). A tour in traveling salesman problem is one of the representation of cycle in classical graph. The traveling salesman problem has been constructed in an uncertain environment [36]. Meanwhile, Gao investigated the cycle index [21] of uncertain graph. In order to develop some applications of cycle in uncertain random environment, we need to know whether an uncertain random graph is a cycle or not. What is the truth value that an uncertain random graph being a cycle? In order to answer this problem, we need to investigate the cycle index problem of uncertain random graph. To the best of our knowledge, no prior work has investigated the cycle problem of an uncertain random graph. In view of this fact, this paper focuses on studying the cycle index of an uncertain random graph. In this paper, the concept of the cycle index of an uncertain random graph is firstly proposed. Then a method to calculate the cycle index is presented and discussed within the framework of chance theory. We also present an algorithm to calculate the cycle index.
L. Chen et al. / Cycle Index of Uncertain Random Graph
The remainder of this paper is organized as follows. Section 2 presents some basic concepts and theorems selected from uncertainty theory to chance theory and from classical graph to uncertain random graph. In Section 3, we discuss the results on the cycle index of an uncertain random graph, and give some examples to illustrate how to obtain the cycle index. At the end of the paper, a brief summary is presented.
2. Preliminary At the beginning of this section, we would like to introduce some basic concepts and results about the uncertainty theory and the chance theory, respectively. The former is a branch of axiomatic mathematics for dealing with belief degrees, while the latter is a mathematical methodology for dealing with complex systems with both uncertainty and randomness. We also recall some fundamental definitions and results of classical graph and uncertain random graph in Subsections 2.3 and 2.4, respectively.
certain measure. Axiom IV. (Product) Let (Γk , Lk , Mk ) be uncertainty spaces for k = 1, 2, . . . The product uncertain measure M is an uncertain measure satisfying { M
∫
M
i=1
} Λi
6
∞ ∑
M{Λi }.
} Λk
=
∞ ∧
Mk {Λk },
k=1
where Λk are arbitrarily chosen events from Lk for k = 1, 2, . . . , respectively. As a useful tool for describing uncertain quantity, uncertain variable is defined as a measurable function ξ from an uncertainty space (Γ, L, M) to the set of real numbers, i.e., for any Borel set B of real numbers, the set {ξ ∈ B} is an event (Liu [29]). In order to characterize an uncertain variable in practice, the uncertainty distribution Φ: ℜ → [0, 1] of an uncertain variable ξ was defined by Liu [29] as follows Φ(x) = M {ξ 6 x} , ∀x ∈ ℜ. In order to measure the size of an uncertain variable ξ, the expected value of ξ was defined by Liu [29] as the following form, ∫
+∞
M{ξ > x}dx −
E[ξ] =
{∞ ∪
∞ ∏
k=1
2.1. Uncertainty theory Uncertainty theory is a new mathematical tool to deal with indeterminacy phenomena. Nowadays, uncertainty theory has been applied to network optimization ([15]), supply chain management ([35]), and supplier selection ([37]). In this subsection, we briefly state some basic concepts and results about uncertainty theory, which are introduced by Liu [29,30,31] and will be used throughout the paper. Given a nonempty set Γ and let L be a σ-algebra over Γ. Each element Λ ∈ L is called an event. An uncertain measure M: L → [0, 1], is a set function, which satisfies the following three axioms (Liu [29]): Axiom I. (Normality) M{Γ} = 1 for the universal set Γ. Axiom II. (Duality) M{Λ} + M{Λc } = 1 for any event Λ. Axiom III. (Subadditivity) For every countable sequence of events Λ1 , Λ2 , . . . , we have
3
0
0 −∞
M{ξ 6 x}dx
provided that at least one of the two integrals was finite. In addition, for independent uncertain variables ξ and η with finite expected values, Liu [31] proved the linearity property of expected value, i.e., E[a1 ξ + a2 η] = a1 E[ξ] + a2 E[η] for any real numbers a1 and a2 . Assumed that uncertain variable ξ has a finite expected value, the variance of ξ was defined by [29] as V [ξ] = E[(ξ − E[ξ])2 ]. Liu [30] introduced the concept of independent uncertain variables. The uncertain variables ξ1 , ξ2 , . . . , ξn are called independent if { M
n ∩ i=1
} (ξi ∈ Bi )
=
n ∧
M{ξi ∈ Bi }
i=1
i=1
The triplet (Γ, L, M) is said to be an uncertainty space. In order to define the product uncertain measure, Liu [30] gave the following product axiom of un-
for any Borel sets B1 , B2 ,. . ., Bn of real numbers. When the uncertain variables ξ1 , ξ2 , . . . , ξn are represented by uncertainty distributions, the operational law was given by Liu [31] as follows. Assume that
4
L. Chen et al. / Cycle Index of Uncertain Random Graph
ξ1 , ξ2 , . . . , ξn are independent uncertain variables with regular uncertainty distributions Φ1 , Φ2 , . . . , Φn , respectively. If the function f (x1 , x2 , . . . , xn ) is strictly increasing with respect to x1 , x2 , . . . , xm and strictly decreasing with respect to xm+1 , xm+2 , . . . , xn , then the uncertain variable ξ = f (ξ1 , ξ2 , . . . , ξn ) has an inverse uncertainty distribution
x} for any real number x ∈ ℜ [33]. As an important contribution to the chance theory, Liu [34] provided the following operation law to determine the chance distribution of uncertain random variable. Assume that η1 , η2 , · · · , ηm are independent random variables with probability distributions Ψ1 , Ψ2 , · · · , Ψm , respectively, and τ1 , τ2 , · · · , τn are uncertain variables, then the chance distribution of the uncertain random variable ξ = f (η1 , η2 , · · · , ηm , τ1 , τ2 , · · · , τn ) can be presented as
Ψ−1 (α) = f (Φ−1 1 (α), . . . , −1 −1 Φ−1 m (α), Φm+1 (1 − α), . . . , Φn (1 − α)).
Φ(x) = ∫ ℜm
2.2. Chance theory In many cases, uncertainty and randomness appear simultaneously in a complex system. In order to describe this phenomenon, Liu [33] first proposed the chance theory, which is a mathematical methodology for modeling complex systems with both uncertainty and randomness. Regarding the theoretical aspect, Ahmadzade et al. [1] studied some properties of uncertain random sequences. As an application of chance theory, Liu [34] proposed the uncertain random programming as a branch of mathematical programming involving uncertain random variables. Besides, chance theory was applied into many fields, such as uncertain random optimization (Gao et al. [19]) and uncertain random system (Gao and Yao [20]). Assume that (Γ, L, M) is an uncertainty space, and (Ω, A, Pr) is a probability space. The product (Γ, L, M) × (Ω, A, Pr) is called a chance space. Each element Θ ∈ L × A is called an event in the chance space. The chance measure of event Θ was defined by Liu [33] as
F (x; y1 , y2 , · · · , ym )dΨ1 (y1 ) · · · dΨm (ym ),
where F (x; y1 , y2 , · · · , ym ) is the uncertainty distribution of f (y1 , y2 , · · · , ym , τ1 , τ2 , · · · , τn ) for any real numbers y1 , y2 , · · · , ym . A function is said to be a Boolean function if it is a mapping from {0, 1}n to the set {0, 1}. A random variable (with a probability measure) is said to be Boolean if it takes values either 0 or 1 and an uncertain variable (with an uncertain measure) is said to be Boolean if it takes values either 0 or 1. Theorem 2.1 (Liu [34]) Assume that η1 , η2 , · · · , ηm are independent Boolean random variables, i.e., { ηi =
1 with probability measure ai 0 with probability measure 1 − ai
for i = 1, 2, · · · , m and the variables τ1 , τ2 , · · · , τn are independent Boolean uncertain variables, i.e., { τj =
1 with uncertain measure bj 0 with uncertain measure 1 − bj
Ch{Θ} = ∫
for j = 1, 2, · · · , n. If f is a Boolean function, then
1
Pr{ω ∈ Ω | M{γ ∈ Γ | (γ, ω) ∈ Θ} ≥ x}dx.
ξ = f (η1 , · · · , ηm , τ1 , · · · , τn )
0
Based on chance space, an uncertain random variable was introduced by Liu [33] as follows. The uncertain random variable ξ is a function from a chance space (Γ, L, M)×(Ω, A, Pr) to the set of real numbers such that {ξ ∈ B} is an event in L × A for any Borel set B. In order to describe uncertain random variables in practice, a concept of chance distribution of an uncertain random variable ξ was defined as Φ(x) = Ch{ξ ≤
is a Boolean uncertain random variable such that Ch{ξ = 1} = (∏m
∑ (x1 ,··· ,xm )∈{0,1}m
i=1
) µi (xi ) f ∗ (x1 , · · · , xm ),
where
f ∗ (x1 , · · · , xm ) =
L. Chen et al. / Cycle Index of Uncertain Random Graph
sup min νj (yj ), f (x1 ,··· ,xm ,y1 ,··· ,yn )=1 1≤j≤n if sup min νj (yj ) < 0.5 f (x1 ,··· ,xm ,y1 ,··· ,yn )=1 1≤j≤n 1− sup min νj (yj ), f (x1 ,··· ,xm ,y1 ,··· ,yn )=0 1≤j≤n if sup min νj (yj ) ≥ 0.5, f (x1 ,··· ,xm ,y1 ,··· ,yn )=1 1≤j≤n
{ µi (xi ) =
{ νj (yj ) =
ai , if xi = 1 1 − ai , if xi = 0
(i = 1, 2, · · · , m),
bj , if yj = 1 1 − bj , if yj = 0
(j = 1, 2, · · · , n).
5
A graph is called disconnected if its vertex set can be partitioned into two subsets, V1 and V2 , that have no common element, in such a way that there is no edge with one endpoint in V1 and the other one in V2 . If a graph is not disconnected, then it is called connected. The degree of a vertex v in a graph G, denoted by deg v, is the number of edges that are incident with v. A graph G is called regular if the vertices of G have the same degree. If deg v = k for every vertex v of G, where 0 ≤ k ≤ n − 1, then G is k-regular. A graph G of order n is a cycle if and only if it is connected and 2-regular. This conclusion is very useful in the classical graph theory, which is a necessary and sufficient condition to determine whether a graph is a cycle or not. 2.4. Uncertain random graph
2.3. Classical graph In this subsection, a formal definition of graph and some basic terminologies of graph theory are offered, which are excerpted from Bondy and Murty [12]. Definition 2.2 (Bondy and Murty [12]) A graph G is an order triple (V (G), E(G), ψG ) consisting of a nonempty vertex set V (G), a set E(G) of edges, and an incidence function ψG that associates with each edge an unordered pair of vertices of G. A loop is an edge whose endpoints are equal. Multiple edges are edges having the same pair of endpoints. A simple graph is a graph having no loops or multiple edges. The number of vertices in G is often called the order of G, while the number of edges is called its size. Every graph in this paper is simple graph with finite order. Let G be a graph with the vertex set V (G) = {v1 , v2 , · · · , vn } and the edge set E(G) = {e1 , e2 , · · · , em }. The adjacency matrix of G is the n × n matrix
d11 d12 · · · d1n d d ··· d 2n 21 22 D= .. .. . . .. , . . . . dn1 dn2 · · · dnn where {
1, if vi and vj are adjacent
dij = 0, otherwise.
Recently, Liu [32] presented a concept of uncertain random graph. In uncertain random graph, all edges are independent and some edges exist with degrees in probability measure and others exist with degrees in uncertain measure. We next introduce some denotations in uncertain random graph, which are stemmed from Liu [32]. Let V be a set of n vertices, that is, V = {v1 , v2 , · · · , vn }. Let us define two collections of edges: U = {(vi , vj ) | (vi , vj ) are uncertain edges}, R = {(vi , vj ) | (vi , vj ) are random edges}. for 1 ≤ i < j ≤ n. Then V ∪ R = {(vi , vj ) | 1 ≤ i < j ≤ n}. We call the matrix α11 α12 · · · α1n
α21 T = .. .
α22 · · · α2n .. . . .. . . .
αn1 αn2 · · · αnn
an uncertain random adjacency matrix if αij represent the truth values in uncertain measure or probability measure that the edges between vertices vi and vj exist, i, j = 1, 2, · · · , n, respectively. Note that αii = 0 and αij = αji for i, j = 1, 2, · · · , n, respectively, that is, T is a symmetric matrix.
6
L. Chen et al. / Cycle Index of Uncertain Random Graph
Definition 2.3 (Liu [32]) Assume that V is the collection of vertices, U is the collection of uncertain edges, R is the collection of random edges, and T is the uncertain random adjacency matrix. Then the quartette G = (V, U, R, T ) is said to be an uncertain random graph. From the definition of uncertain random graph, the edge set of uncertain random graph G is a set of Boolean variable E(G) = {ξ12 , · · · , ξ1n , · · · , ξ(n−1)n }, where Ch{ξij = 1} = αij and Ch{ξij = 0} = 1 − αij for any 1 ≤ i < j ≤ n. A realization of the uncertain graph G is a deterministic graph G(V, E) where V = V, E ⊂ U ∪ R. Let ε = {(i, j)|1 ≤ i < j ≤ n and 0 < αij < 1} and |ε| = m. It follows from Gao et al. [26] that G has 2m realizations. We can call a realization as model. Example 1. Consider an uncertain random graph G in Figure 1. 2j @ @ @j 3
1j @ @ j 4
3j
1j @ @ j 4
3j
Figure 2. Some realizations of the uncertain random graph G in Figure 1 Similar to Liu [32], we first assume that
x11 x12 · · · x1n x x ··· x 2n 21 22 X= .. . . .. .. . . . . xn1 xn2 · · · xnn
(1)
and
xij = 0 or 1, if (vi , vj ) ∈ R
x = 0, if (v , v ) ∈ U i j
ij X= X
. (2)
xij = xji , i, j = 1, 2, · · · , n
xii = 0, i = 1, 2, · · · , n
The edges of uncertain random graph G is U = {(v1 , v2 ), (v1 , v4 )}, R = {(v2 , v3 ), (v1 , v3 ), (v3 , v4 )}. The uncertain random graph G has uncertain random adjacency matrix as follows: 0 0.2 1 0.6
1j @ @ j 4
2j
Next, given a matrix
Figure 1. Uncertain random graph G
2j
0.2 0 0.5 0 T = 1 0.5 0 0.8 . 0.6 0 0.8 0
The uncertain random graph G has 24 models. Some models of G are presented in Figure 2.
y11 y12 · · · y1n y y ··· y 2n 21 22 Y = .. .. . . .. , . . . . yn1 yn2 · · · ynn
(3)
we define the extension class of Y as
xij = yij , if (vi , vj ) ∈ R
x = 0 or 1, if (v , v ) ∈ U ij i j
Y∗ = X
. (4)
xij = xji , i, j = 1, 2, · · · , n
xii = 0, i = 1, 2, · · · , n In order to show how likely an uncertain random graph is connected, a connectivity index was defined by Liu [32] as follows. Definition 2.4 (Liu [32]) The connectivity index of an uncertain random graph is the chance measure that the uncertain random graph is connected.
L. Chen et al. / Cycle Index of Uncertain Random Graph
7
For a given uncertain random graph, Liu [32] proposed a method to obtain the connectivity index of the graph. The main results can be summarized as follows.
Definition 3.2 A cycle index of an uncertain random graph G is the chance measure that the uncertain random graph is cycle, i.e.,
Theorem 2.5 (Liu [32]) Let G = (V, U, R, T ) be an uncertain random graph. If all edges are independent, then the connectivity index of G is
µ(G) = Ch{C(E(G)) = 1}.
ρ(G) =
∑
Y ∈X
∏
νij (Y ) f ∗ (Y ),
(vi ,vj )∈R
where F =
sup
min
X∈Y ∗, f (X)=1 (vi ,vj )∈U
νij (X),
A basic problem for us is how to calculate the cycle index when an uncertain random graph is given. The following theorem can be completely solve this problem for an uncertain random graph. Theorem 3.3 Let G = (V, U, R, T ) be an uncertain random graph. If all edges are independent, then the cycle index of G is ∑ ∏ µ(G) = νij (Y ) C ∗ (Y ), Y ∈X
∗
f (Y ) =
sup
1 −
sup
νij (X) =
{
νij (X), if F < 0.5
min
X∈Y ∗, f (X)=0 (vi ,vj )∈U
{
f (X) =
min
X∈Y ∗, f (X)=1 (vi ,vj )∈U
αij ,
where
νij (X), if F ≥ 0.5,
if xij = 1
1 − αij , if xij = 0
H=
(vi , vj ) ∈ U ,
0, otherwise.
∗
C (Y ) =
min
sup
The object of this section is to investigate how likely an uncertain random graph being a cycle. For this purpose, we first give the definition of cycle function for an uncertain random graph as follows. Definition 3.1 Let G be an uncertain random graph with edge set E(G) = {ξ1 , ξ2 , · · · , ξm }. The cycle function of G is denoted as: 1, if graph G is cycle
1 −
sup
{
αij ,
νij (Y ) =
min
if xij = 1
1 − αij , if xij = 0 {
αij ,
νij (X),
νij (X), if H < 0.5
X∈Y ∗, C(X)=0 (vi ,vj )∈U
νij (X) =
if yij = 1
1 − αij , if yij = 0
νij (X), if H ≥ 0.5,
(vi , vj ) ∈ U ,
(vi , vj ) ∈ R,
2 n−1 >0 I + X + X + ··· + X n 1, if ∑ C(X) = xij = 2 for i = 1, 2, · · · , n j=1 0, otherwise.
Proof. Note that all random edges are independent Boolean random variables, being represented by {
0, otherwise.
Obviously, C(E(G)) is a Boolean function. In order to show how likely an uncertain random graph is cycle, a cycle index is given in Definition 3.2.
min
X∈Y ∗, C(X)=1 (vi ,vj )∈U
3. Cycle Index of Uncertain Random Graph
C(E(G)) =
sup
X∈Y ∗, C(X)=1 (vi ,vj )∈U
1, if I + X + X 2 + · · · + X n−1 > 0
{
(vi ,vj )∈R
ηij =
1 with probability measure αij 0 with probability measure 1 − αij
for (vi , vj ) ∈ R.
8
L. Chen et al. / Cycle Index of Uncertain Random Graph
Also, all uncertain edges are independent Boolean uncertain variables, being represented by { 1 with uncertain measure αij τij = 0 with uncertain measure 1 − αij
Remark 3.5 If the uncertain random graph G becomes an uncertain graph, then the cycle index of G is µ(G) =
for (vi , vj ) ∈ U. Let G be a classical graph of order n with adjacency matrix
where xij ∈ {0, 1}, and X is a symmetric matrix with xii = 0, i = 1, 2, · · · , n. Then the graph G is connected if and only if I + X + X 2 + · · · + X n−1 > 0. The degree of a vertex vi is just the sum of entries in the row corresponding to it in X. As we know, a connected graph is a cycle if and only if the graph is 2-regular. That is, I + X + X 2 + · · · + X n−1 > 0 n 1, if ∑ C(X) = xij = 2 for i = 1, 2, · · · , n j=1 0, otherwise. Obviously, the function C(X) is a Boolean function. Then it follows from Theorem 2.5 that the theorem is proved. Remark 3.4 If the uncertain random graph G becomes a random graph, then the cycle index of G is ∑ ∏ µ(G) = νij (X) C(X), X∈X
min
1 −
sup
νij (X), if H < 0.5
min
X∈X,C(X)=0 1≤i<j≤n
νij (X), if H ≥ 0.5,
where H=
x11 x12 · · · x1n x x ··· x 2n 21 22 X= .. . . .. , .. . . . . xn1 xn2 · · · xnn
sup
X∈X,C(X)=1 1≤i<j≤n
sup
min
X∈Y ∗, C(X)=1 (vi ,vj )∈U
νij (X),
xij = 0 or 1, i, j = 1, 2, · · · , n
X = X xij = xji , i, j = 1, 2, · · · , n ,
xii = 0, i = 1, 2, · · · , n which is equivalent to the result that presented in Gao [21]. It is quite well known that if a graph is cycle then it must be connected. Thus we have Corollary 3.6. Corollary 3.6 Let G be an uncertain random graph, then the cycle index of G is less than or equal to the connectivity index of G. A property that can be used to determine the cycle index of uncertain graph, which was given by Gao [21], can be extended into uncertain random graph. Hence, we have Lemma 3.7. Lemma 3.7 Let G be an uncertain random graph with the vertex set V (G) = {v1 , v2 , · · · , vn } and the edge set E(G) = {ξ1 , ξ2 , · · · , ξn }. Let C be a spanning cycle with V (C) = {v1 , v2 , · · · , vn } and E(C) = {ξc1 , ξc2 , · · · , ξcn−1 }. The cycle index of G is
µ(G) =
∑ Y ∈X
∏
νij (Y ) C∗ (Y ),
(vi ,vj )∈R
1≤i<j≤n
where where
xij = 0 or 1, i, j = 1, 2, · · · , n
X = X xij = xji , i, j = 1, 2, · · · , n .
xii = 0, i = 1, 2, · · · , n
sup min C(X)=1 (vi ,vj )∈U C∗ (Y ) = { } µ(C), 1 − max(vi ,vj )∈E(G)\E(C)) αij . (5)
L. Chen et al. / Cycle Index of Uncertain Random Graph
Proof. Based on Theorem 3.3, for any given Y , we only need to prove Equation (5) holds. According to the results presented in Gao [21], Equation (5) can be obtained directly. Given an uncertain random graph G = (V, U, R, T ), U = {(vi , vj )|(vi , vj ) are uncertain edge}, R = {(vi , vj )|(vi , vj ) are random edge} and an uncertain random adjacency matrix T = [αij ]. According to Lemma 3.7, we summarize a method to calculate the cycle index of an uncertain random graph as presented in Algorithm 1.
9
where U = {(v2 , v3 ), (v2 , v4 ), (v3 , v4 )}, R = {(v1 , v2 ), (v1 , v3 ), (v1 , v4 )}. The uncertain random adjacency matrix of G is
0 0.7 0.6 0.1
0.7 0 0.3 0.7 T = 0.6 0.3 0 0.2 . 0.1 0.7 0.2 0
Algorithm 1. Algorithm for calculating the cycle index of uncertain random graph Step 1.
Step 2.
Step 3.
Step 4.
Set Q = {∅}, k = 0, µ′ = 0. If there exists an adjacency matrix Xk = [xij ] such that G is a cycle, then go to Step 2. Otherwise, stop, µ(G) = 0. For each Xk , determine matrix Yk = [yij ]. The element yij = 1 if (vi , vj ) in R, and otherwise, yij = 0. Determine the value νij (Yk ), where νij (Yk ) = αij if yij = 1, and νij (Yk ) = 1 − αij if yij = 0 for all (vi , vj ) ∏ ∈ R. Calculate δ = (vi ,vj )∈R νij (Yk ). Calculate min νij (Xk ), where (vi ,vj )∈U
The route needed by the salesman is a cycle of the uncertain random graph G. What is the belief degree that the salesman can find a cycle in the uncertain random graph G? To answer this problem, we need to determine the cycle index of the uncertain random graph G. In Step 1, we determine an adjacency matrix such that G is a cycle. Since the uncertain random graph G contains ε = {(i, j)|1 ≤ i < j ≤ n and 0 < αij < 1} and |ε| = 6. It follows from Gao et al. [26] that G has 26 realizations (models). Among 64 models, if a model has one of the following three adjacency matrices
0101
′
Set µ = sup µ , Step 5.
min (vi ,vj )∈U
} νij (Xk ) ,
Q = Q ∪ {Xk } and k = k + 1. If there exists other adjacency matrix Xk ∈ Q̄ such that G is a cycle, then go to Step 3. Otherwise, ∑ stop, and δµ′ . calculate µ(G) = Xk ∈G
Next, we give an example to illustrate the application of the theoretical result and the proposed algorithm. Example 3.8 A salesman will travel from a place (vertex) 1, visit another places exactly one times, and back to the place 1. The possible route is presented in the uncertain random graph: G = (V, U, R, T ) of order 4,
0110
1 0 1 0 1 0 0 1 X0 = 0 1 0 1 , X 1 = 1 0 0 1 , 1010
νij (Xk ) = αij if xij = 1, and νij (Xk ) = 1 − αij if xij = 0 for (vi , vj ) ∈ { U. ′
0110
0011
0 0 1 1 X2 = 1 1 0 0 , 1100
then it is cycle. Otherwise, the model is not a cycle. In Step 2, we determine a matrix Yk for each Xk . 0101
0101
1 0 1 0 1 0 0 0 For X0 = 0 1 0 1 , the matrix Y0 is 0 0 0 0 . 1010
1000
In Step 3, we determine νij (Yk ) as follows: ν12 (Y0 ) = 0.7, ν13 (Y0 )∏= 0.4, ν14 (Y0 ) = 0.1. After that, the value δ = (vi ,vj )∈R νij (Y1 ) = 0.7 × 0.4 × 0.1 = 0.028 is obtained.
10
L. Chen et al. / Cycle Index of Uncertain Random Graph
In Step 4, we calculate µ′ =
min (vi ,vj )∈U
νij (X1 ) = 0.2.
Since there exists other adjacency matrix such that G is a cycle, then go back to step 3. 0110
0110
1 0 0 1 1 0 0 0 For X1 = 1 0 0 1 , the matrix Y1 is 1 0 0 0 , 0110
0000
graph. Second, some efficient algorithms can be employed to improve the efficiency in the process of finding the cycle index of an uncertain random graph when the size of the graph becomes larger. Finally, the diameter of uncertain random graph is an uncertain random variable (not a constant number), so studying the distribution function of the diameter of uncertain random graph may be an interesting work in the future.
we get ∏
δ=
Acknowledgments
νij (Y1 ) = 0.378, and
(vi ,vj )∈R
µ′ =
min (vi ,vj )∈U
0011
νij (X1 ) = 0.2.
0011
0 0 1 1 0 0 0 0 For X2 = 1 1 0 0 , the matrix Y2 is 1 0 0 0 , 1100
1000
we obtain ∏
δ=
νij (Y2 ) = 0.018, and
(vi ,vj )∈R
µ′ =
min (vi ,vj )∈U
νij (X2 ) = 0.3.
In Step 5, we obtain the cycle index of the uncertain random graph G as follows: µ(G) = 0.028×0.2+0.378×0.2+0.018×0.3 = 0.0866. The result can be interpreted as follows: the belief degree that the salesman can find a cycle in the uncertain random graph G is 0.0866. 4. Conclusions This paper mainly studied the cycle problem of an uncertain random graph. Firstly, we proposed a cycle index to show the chance measure that an uncertain random graph being a cycle. Following that, a formula for calculating the cycle index was presented. In addition, some simplified forms of the formula were also discussed, and an algorithm for obtaining the cycle index was designed. Finally, a numerical example was given to illustrate the proposed method. Further research will focus on the following aspects. First, we can investigate how likely an uncertain random graph is Hamiltonian and discuss the connectedness strength of two vertices for an uncertain random
This work was supported by the Projects of National Natural Science Foundation of China (Nos. 71671135, 61703438), the Key Project of Hubei Provincial Natural Science Foundation (No. 2015CFA144), China, and the World Class Professor (WCP) Program (No. 291/D2.3/KP/2017), from the Directorate General of Resources, Science, Technology and Higher Education, Ministry of Research Technology and Higher Education of Indonesia. References [1] H. Ahmadzade, Y. Sheng and M. Esfahani, On the convergence of uncertain random sequences, Fuzzy Optimization and Decision Making 16(2)(2017), 205–220. [2] M. Akram, Bipolar fuzzy graphs, Information Sciences 181(24)(2011), 5548–5564. [3] M. Akram, N. Al-Shehrie, B. Davvaz and A. Ashraf, Bipolar fuzzy digraphs in decision support systems, Journal of MultipleValued Logic and Soft Computing 27(5-6)(2016), 531–551. [4] M. Akram, W. Chen and B. Davvaz, On N -hypergraphs, Journal of Intelligent and Fuzzy Systems 26(6)(2014), 2937–2944. [5] M. Akram and B. Davvaz, Strong intuitionistic fuzzy graphs, Filomat 26(1)(2012), 177–196. [6] M. Akram and W. Dudek, Intuitionistic fuzzy hypergraphs with applications, Information Sciences 218(2013), 182–193. [7] M. Akram, A. Farooq, A. Saeid and K. Shum, Certain types of vague cycles and vague trees, Journal of Intelligent and Fuzzy Systems 28(2)(2015), 621–631. [8] M. Akram and S. Nawaz, Fuzzy soft graphs with applications, Journal of Intelligent and Fuzzy Systems 30(6)(2016), 3619– 3632. [9] M. Akram, N. Waseem and B. Davvaz, Certain types of domination in m-polar fuzzy graphs, Journal of Multiple-Valued Logic and Soft Computing 29(6)(2017), 619–646. [10] M. Akram, S. Siddique and B. Davvaz, New concepts in neutrosophic graphs with application, Journal of Applied Mathematics and Computing, DOI: 10.1007/s12190-017-1106-3, 2017. [11] N. Alon, T. Bohman and H. Huang, More on the bipartite decomposition of random graphs, Journal of Graph Theory 84(1)(2016), 45–52. [12] J. Bondy and U. Murty, Graph Theory with Applications, Elsevier, New York, 1976.
L. Chen et al. / Cycle Index of Uncertain Random Graph [13] L. Chen, J. Peng, B. Zhang and S. Li, Uncertain programming model for uncertain minimum weight vertex covering problem, Journal of Intelligent Manufacturing 28(3)(2017), 625–632. [14] L. Chen, J. Peng and D. Ralescu, Uncertain vertex coloring problem, Soft Computing, DOI: 10.1007/s00500-017-2861-7, 2017. [15] L. Cheng, C. Rao and L. Chen, Multidimensional knapsack problem based on uncertain measure, Scientia Iranica, Transactions E: Industrial Engineering 24(5)(2017), 2527–2539. [16] P. Erdős and A. Rényi, On random graph, Publicacions Matematiques 6(1959), 290–297. [17] M. Farshi and B. Davvaz, Generalized fuzzy hypergraphs and hypergroupoids, Filomat 30(9)(2016), 2375–2387. [18] D. Gamarnik and M. Sviridenko, Hamiltonian completions of sparse random graphs, Discrete Applied Mathematics 152(13)(2005), 139–158. [19] R. Gao, Y. Sun and D. Ralescu, Order statistics of uncertain random variables with application to k-out-of-n system, Fuzzy Optimization and Decision Making 16(2)(2017), 159–181. [20] R. Gao and K. Yao, Importance index of components in uncertain random systems, Knowledge-Based Systems 109(2016), 208–217. [21] X. Gao, Cycle index of uncertain graph, Information 16(2)(2013), 1131–1138. [22] X. Gao, Regularity index of uncertain graph, Journal of Intelligent and Fuzzy Systems 27(4)(2014), 1671–1678. [23] X. Gao, Tree index of uncertain graphs, Soft Computing 20(4)(2016), 1449–1458. [24] X. Gao and Y. Gao, Connectedness index of uncertain graph, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 21(1)(2013), 127–137. [25] Y. Gao and Z. Qin, On computing the edge-connectivity of an uncertain graph, IEEE Transactions on Fuzzy Systems 24(4)(2016), 981–991. [26] Y. Gao, L. Yang, S. Li and S. Kar, On distribution function of the diameter in uncertain graph, Information Sciences 296(2015), 61–74. [27] E. Gilbert, Random graphs, Annals of Mathematical Statistics 30(4)(1959), 1141–1144. [28] J. Gilmer and S. Kopparty, A local central limit theorem for triangles in a random graph, Random Structures & Algorithms 48(4)(2016), 732–750. [29] B. Liu, Uncertainty Theory, 2nd edn, Springer-Verlag, Berlin, 2007. [30] B. Liu, Some research problems in uncertainty theory, Journal
11
of Uncertain Systems 3(1)(2009), 3–10. [31] B. Liu, Uncertainty Theory: A Branch of Mathematics for Modeling Human Uncertainty, Springer-Verlag, Berlin, 2010. [32] B. Liu, Uncertain random graphs and uncertain random networks, Journal of Uncertain Systems 8(1)(2014), 3–12. [33] Y. Liu, Uncertain random variables: A mixture of uncertainty and randomness, Soft Computing 17(4)(2013), 625–634. [34] Y. Liu, Uncertain random programming with applications, Fuzzy Optimization and Decision Making 12(2)(2013), 153– 169. [35] Z. Liu, R. Zhao, X. Liu and L. Chen, Contract designing for a supply chain with uncertain information based on confidence level, Applied Soft Computing 56(2017), 617–631. [36] H. Ma, L. Jia, X. Zhang and J. Sun, Travelling salesman problem in uncertain environments, The Open Cybernetics and Systemics Journal 9(2015), 313–317. [37] C. Rao, X. Xiao, M. Xie, M. Goh and J. Zheng, Low carbon supplier selection under multi-source and multi-attribute procurement, Journal of Intelligent and Fuzzy Systems 32(6)(2017), 4009–4022. [38] A. Rosenfeld, Fuzzy graph, In: L. Zadeh, K. Fu and M. Shimura, Eds., Fuzzy Sets and Their Applications to Cognitive and Decision Processes (1975), 77–95. [39] I. Rosyida, W. Widodo, Ch. R. Indrati and K. Sugeng, A new approach for determining fuzzy chromatic number of fuzzy graph, Journal of Intelligent and Fuzzy Systems 28(5)(2015), 2331–2341. [40] I. Rosyida, J. Peng, L. Chen, W. Widodo, Ch. R. Indrati and K. Sugeng, An uncertain chromatic number of an uncertain graph based on α-cut coloring, Fuzzy Optimization and Decision Making, DOI: 10.1007/s10700-016-9260-x, 2016. [41] A. Talebi, H. Rashmanlou and B. Davvaz, New concepts of regular interval-valued fuzzy graphs, Journal of Applied Mathematics and Informatics 35(1-2)(2016), 95–111. [42] W. Wallis, A Beginner’s Guide to Graph Theory, 2nd edn, Birkhauser, Boston, 2007. [43] B. Zhang and J. Peng, Euler index in uncertain graph, Applied Mathematics and Computation 218(20)(2012), 10279–10288. [44] B. Zhang, J. Peng and S. Li, Euler index of uncertain random graph: Concepts and properties, International Journal of Computer Mathematics 94(2)(2017), 217–229. [45] B. Zhang, J. Peng and S. Li, Matching index and its algorithm of uncertain random graph, Applied and Computational Mathematics 17(1)(2018), 22–35.