Cycle index of uncertain random graph

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. [15]), traveling salesman problem (Ma et al. [35]), vertex coloring problem (Chen et al. [12]), 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 Bondy and Murty [11].

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 arising: how to deal with these vagueness phenomena? On one hand, many researchers regarded that vagueness phenomena belonged to the fuzziness phenomena, and 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 [1], intuitionistic fuzzy hypergraphs [5], strong intuitionistic fuzzy graphs [4], $N$ -hypergraphs [3], fuzzy soft graphs [7], bipolar fuzzy digraphs [2], regular interval-valued fuzzy graphs [40], generalized fuzzy hypergraphs [19], domination in m-polar fuzzy graphs [8], neutrosophic graphs [9], and fuzzy graph coloring [40].

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 [18], also by Gilbert [26] at nearly the same time. They thought that whether 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. [10], Gilmer and Kopparty [27] 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 [5], Akram and Nawaz [7]). In order to model these imprecise quantities, Liu [28] 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 [41] discussed the Euler tour in an uncertain graph. In addition, Gao [23] proposed a method to calculate the tree index, path index, and star index, and Gao et al. [25] discussed the diameter for an uncertain graph. Different from the coloring problem of classical graph, Rosyida et al. [39] introduced a new approach to color an uncertain graph based on an α-cut of the uncertain graph. Chen et al. [12] 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 and uncertain graph. The fuzzy graph $\tilde{G} (V, \tilde{E})$ is a generalization of classical graph based on fuzzy set theory. It contains a fuzzy edge set $\tilde{E}$ with a membership function $μ_{\tilde{E}}$ 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 $μ_{\tilde{E}} (uv)$ . If $μ_{\tilde{E}} (uv) = 0,$ then the vertices u and v are not connected by an edge. Different from this point of view, the uncertain graph $\overset{ˇ}{G} = (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 v_i and v_j are connected by an edge, then ξ ({v_iv_j}) =1 with the belief degree $M {ξ_{ij} = 1} = α_{ij}$ where α_ij ∈ [0, 1]. Otherwise, if v_i and v_j are not connected by an edge, then ξ ({v_iv_j}) =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 [32] 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 [32]. As an important contribution to chance theory, Liu [32] presented an operational law of uncertain random variables. After that, chance theory was developed steadily and applied widely. Based on the chance theory, Liu [31] 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 [31], the connectivity index of an uncertain random graph was investigated. Recently, Zhang et al. [42] 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. [43] 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. [6]). A tour in traveling salesman problem is one of the representations of cycle in classical graph. The traveling salesman problem has been constructed in an uncertain environment [35]. Meanwhile, Gao [22] investigated the cycle index 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.

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.

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 [17], supply chain management [13, 34], portfolio selection [16], transportation problem [14], contract theory [44, 45], and supplier selection [36, 37]. In this subsection, we briefly state some basic concepts and results about uncertainty theory, which are introduced by Liu [28 –30] and will be used throughout the paper.

Given a nonempty set Γ and let $L$ be a σ-algebra over Γ. Each element $Λ \in L$ is called an event. An uncertain measure $M$ : $L \to [0, 1],$ is a set function, which satisfies the following three axioms (Liu [28]):

AxiomI. (Normality) $M {Γ} = 1$ for the universal set Γ.

AxiomII. (Duality) $M {Λ} + M {Λ^{c}} = 1$ for any event Λ.

AxiomIII. (Subadditivity) For every countable sequence of events Λ₁, Λ₂, …, we have $M ξ ⋃_{i = 1}^{\infty} Λ_{i}} ⩽ \sum_{i = 1}^{\infty} M {Λ_{i}} .$

The triplet $(Γ, L, M)$ is said to be an uncertainty space. In order to define the product uncertain measure, Liu [29] gave the following product axiom of uncertain measure.

AxiomIV. (Product) Let $(Γ_{k}, L_{k}, M_{k})$ be uncertainty spaces for k = 1, 2, … The product uncertain measure $M$ is an uncertain measure satisfying $M ξ \prod_{k = 1}^{\infty} Λ_{k}} = ⋀_{k = 1}^{\infty} M_{k} {Λ_{k}},$ where Λ_k are arbitrarily chosen events from $L_{k}$ 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 [28]). In order to characterize an uncertain variable in practice, the uncertainty distribution Φ: $R \to [0, 1]$ of an uncertain variable ξ was defined by Liu [28] as follows $Φ (x) = M ξ ξ ⩽ x}, \forall x \in R .$

In order to measure the size of an uncertain variable ξ, the expected value of ξ was defined by Liu [28] as the following form, $E [ξ] = \int_{0}^{+ \infty} M {ξ ⩾ x} dx - \int_{- \infty}^{0} M {ξ ⩽ 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 [30] proved the linearity property of expected value, i.e., $E [a_{1} ξ + a_{2} η] = a_{1} E [ξ] + a_{2} E [η]$ for any real numbers a₁ and a₂. Assumed that uncertain variable ξ has a finite expected value, the variance of ξ was defined by [28] as $V [ξ] = E [(ξ - E [ξ])^{2}] .$

Liu [29] introduced the concept of independent uncertain variables. The uncertain variables ξ₁, ξ₂, …, ξ_n are called independent if $M ξ ⋂_{i = 1}^{n} (ξ_{i} \in B_{i})} = ⋀_{i = 1}^{n} M {ξ_{i} \in B_{i}}$ for any Borel sets B₁, B₂,…, B_n of real numbers.

When the uncertain variables ξ₁, ξ₂, …, ξ_n are represented by uncertainty distributions, the operational law was given by Liu [30] as follows. Assume that ξ₁, ξ₂, …, ξ_n are independent uncertain variables with regular uncertainty distributions Φ₁, Φ₂, …, Φ_n, respectively. If the function f (x₁, x₂, …, x_n) is strictly increasing with respect to x₁, x₂, …, x_m and strictly decreasing with respect to x_m+1, x_m+2, …, x_n, then the uncertain variable $ξ = f (ξ_{1}, ξ_{2}, \dots, ξ_{n})$ has an inverse uncertainty distribution $\begin{matrix} Ψ^{- 1} (α) = f (Φ_{1}^{- 1} (α), \dots, \\ Φ_{m}^{- 1} (α), Φ_{m + 1}^{- 1} (1 - α), \dots, Φ_{n}^{- 1} (1 - α)) . \end{matrix}$

2.2 Chance theory

In many cases, uncertainty and randomness appear simultaneously in a complex system. In order to describe this phenomenon, Liu [32] first proposed the chance theory, which is a mathematical methodology for modeling complex systems with both uncertainty and randomness. As an application of chance theory, Liu [33] 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. [20]) and uncertain random system (Gao and Yao [21]).

Assume that $(Γ, L, M)$ is an uncertainty space, and $(Ω, A, \Pr)$ is a probability space. The product $(Γ, L, M) \times (Ω, A, \Pr)$ is called a chance space. Each element $Θ \in L \times A$ is called an event in the chance space. The chance measure of event Θ was defined by Liu [32] as $\begin{matrix} Ch {Θ} \\ = \int_{0}^{1} \Pr {ω \in Ω ∣ M {γ \in Γ ∣ (γ, ω) \in Θ} \geq x} d x . \end{matrix}$

Based on chance space, an uncertain random variable was introduced by Liu [32] as follows. The uncertain random variable ξ is a function from a chance space $(Γ, L, M) \times (Ω, A, \Pr)$ to the set of real numbers such that {ξ ∈ B} is an event in $L \times 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 {ξ ≤ x} for any real number $x \in R$ [32]. As an important contribution to the chance theory, Liu [33] provided the following operation law to determine the chance distribution of uncertain random variable. Assume that η₁, η₂, ⋯, η_m are independent random variables with probability distributions Ψ₁, Ψ₂, ⋯, Ψ_m, respectively, and τ₁, τ₂, ⋯, τ_n are uncertain variables, then the chance distribution of the uncertain random variable ξ = f (η₁, η₂, ⋯, η_m, τ₁, τ₂, ⋯, τ_n) can be presented as $\begin{matrix} Φ (x) \\ = \int_{R^{m}} F (x; y_{1}, y_{2}, \dots, y_{m}) d Ψ_{1} (y_{1}) \dots d Ψ_{m} (y_{m}), \end{matrix}$ where F (x ; y₁, y₂, ⋯, y_m) is the uncertainty distribution of f (y₁, y₂, ⋯, y_m, τ₁, τ₂, ⋯, τ_n) for any real numbers y₁, y₂, ⋯, y_m.

A function is said to be a Boolean function if it is a mapping from {0, 1} ⁿ 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 [33]) Assume that η₁, η₂, ⋯, η_m are independent Boolean random variables, i.e., $η_{i} = {\begin{matrix} 1 with probability measure a_{i} \\ 0 with probability measure 1 - a_{i} \end{matrix}$ for i = 1, 2, ⋯, m and the variables τ₁, τ₂, ⋯, τ_n are independent Boolean uncertain variables, i.e., $τ_{j} = {\begin{matrix} 1 with uncertain measure b_{j} \\ 0 with uncertain measure 1 - b_{j} \end{matrix}$ for j = 1, 2, ⋯, n. If f is a Boolean function, then $ξ = f (η_{1}, \dots, η_{m}, τ_{1}, \dots, τ_{n})$ is a Boolean uncertain random variable such that $\begin{matrix} Ch {ξ = 1} \\ = \sum_{(x_{1}, \dots, x_{m}) \in {0, 1}^{m}} (\prod_{i = 1}^{m} μ_{i} (x_{i})) f^{*} (x_{1}, \dots, x_{m}), \end{matrix}$ where $\begin{matrix} f^{*} (x_{1}, \dots, x_{m}) \\ = {\begin{matrix} sup_{f (x_{1}, \dots, x_{m}, y_{1}, \dots, y_{n}) = 1} min_{1 \leq j \leq n} ν_{j} (y_{j}), \\ if sup_{f (x_{1}, \dots, x_{m}, y_{1}, \dots, y_{n}) = 1} min_{1 \leq j \leq n} ν_{j} (y_{j}) < 0.5 \\ 1 - sup_{f (x_{1}, \dots, x_{m}, y_{1}, \dots, y_{n}) = 0} min_{1 \leq j \leq n} ν_{j} (y_{j}), \\ if sup_{f (x_{1}, \dots, x_{m}, y_{1}, \dots, y_{n}) = 1} min_{1 \leq \leq n} ν_{j} (y_{j}) \geq 0.5, \end{matrix} \\ μ_{i} (x_{i}) = {\begin{matrix} a_{i}, & if x_{i} = 1 \\ 1 - a_{i}, & if x_{i} = 0 \end{matrix} (i = 1, 2, \dots, m), \\ ν_{j} (y_{j}) = {\begin{matrix} b_{j}, & if y_{j} = 1 \\ 1 - b_{j}, & if y_{j} = 0 \end{matrix} (j = 1, 2, \dots, n) . \end{matrix}$

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 [11].

Definition 2.2. (Bondy and Murty [11]) 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) = {v₁, v₂, ⋯, v_n} and the edge set E (G) = {e₁, e₂, ⋯, e_m}. The adjacency matrix of G is the n × n matrix $D = (\begin{matrix} d_{11} & d_{12} & \dots & d_{1 n} \\ d_{21} & d_{22} & \dots & d_{2 n} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ d_{n 1} & d_{n 2} & \dots & d_{nn} \end{matrix}),$ where $d_{ij} = {\begin{matrix} 1, & if v_{i} and v_{j} are adjacent \\ 0, & otherwise . \end{matrix}$

A graph is called disconnected if its vertex set can be partitioned into two subsets, V₁ and V₂, that have no common element, in such a way that there is no edge with one endpoint in V₁ and the other one in V₂. 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

Recently, Liu [31] 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 [31].

Let $V$ be a set of n vertices, that is, $V = {v_{1}, v_{2}, \dots, v_{n}} .$

Let us define two collections of edges: $\begin{matrix} U = {(v_{i}, v_{j}) | (v_{i}, v_{j}) are uncertain edges}, \\ R = {(v_{i}, v_{j}) | (v_{i}, v_{j}) are random edges} . \end{matrix}$ for 1 ≤ i < j ≤ n.

Then $V \cup R = {(v_{i}, v_{j}) | 1 \leq i < j \leq n}$ . We call the matrix $T = (\begin{matrix} α_{11} & α_{12} & \dots & α_{1 n} \\ α_{21} & α_{22} & \dots & α_{2 n} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ α_{n 1} & α_{n 2} & \dots & α_{nn} \end{matrix})$ an uncertain random adjacency matrix if α_ij represent the truth values in uncertain measure or probability measure that the edges between vertices v_i and v_j 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.

Definition 2.3. (Liu [31]) 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}, \dots, ξ_{1 n}, \dots, ξ_{(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 \subset U \cup R$ . Let ɛ = {(i, j) |1 ≤ i < j ≤ n and 0 < α_ij < 1} and |ɛ| = m. It follows from Gao et al. [25] that $G$ has 2^m realizations. We can call a realization as model.

Example 1. Consider an uncertain random graph $G$ in Fig. 1.

Fig.1

Uncertain random graph $G$ .

The edges of uncertain random graph $G$ is $\begin{matrix} U = {(v_{1}, v_{2}), (v_{1}, v_{4})}, \\ R = {(v_{2}, v_{3}), (v_{1}, v_{3}), (v_{3}, v_{4})} . \end{matrix}$

The uncertain random graph $G$ has uncertain random adjacency matrix as follows: $T = (\begin{matrix} 0 & 0.2 & 1 & 0.6 \\ 0.2 & 0 & 0.5 & 0 \\ 1 & 0.5 & 0 & 0.8 \\ 0.6 & 0 & 0.8 & 0 \end{matrix}) .$

The uncertain random graph $G$ has 2⁴ models. Some models of $G$ are presented in Fig. 2.

Fig.2

Some realizations of the uncertain random graph $G$ in Fig. 1.

Similar to Liu [31], we first assume that $X = (\begin{matrix} x_{11} & x_{12} & \dots & x_{1 n} \\ x_{21} & x_{22} & \dots & x_{2 n} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ x_{n 1} & x_{n 2} & \dots & x_{nn} \end{matrix})$ (1) and $X = {X | \begin{matrix} x_{ij} = 0 or 1, if (v_{i}, v_{j}) \in R \\ x_{ij} = 0, if (v_{i}, v_{j}) \in U \\ x_{ij} = x_{ji}, i, j = 1, 2, \dots, n \\ x_{ii} = 0, i = 1, 2, \dots, n \end{matrix}} .$ (2)

Next, given a matrix $Y = (\begin{matrix} y_{11} & y_{12} & \dots & y_{1 n} \\ y_{21} & y_{22} & \dots & y_{2 n} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ y_{n 1} & y_{n 2} & \dots & y_{nn} \end{matrix}),$ (3) we define the extension class of Y as $Y^{*} = {X | \begin{matrix} x_{ij} = y_{ij}, if (v_{i}, v_{j}) \in R \\ x_{ij} = 0 or 1, if (v_{i}, v_{j}) \in U \\ x_{ij} = x_{ji}, i, j = 1, 2, \dots, n \\ x_{ii} = 0, i = 1, 2, \dots, n \end{matrix}} .$ (4)

In order to show how likely an uncertain random graph is connected, a connectivity index was defined by Liu [31] as follows.

Definition 2.4. (Liu [31]) The connectivity index of an uncertain random graph is the chance measure that the uncertain random graph is connected.

For a given uncertain random graph, Liu [31] proposed a method to obtain the connectivity index of the graph. The main results can be summarized as follows.

Theorem 2.5. (Liu [31]) Let $G = (V, U, R, T)$ be an uncertain random graph. If all edges are independent, then the connectivity index of $G$ is $ρ (G) = \sum_{Y \in X} (\prod_{(v_{i}, v_{j}) \in R} ν_{ij} (Y)) f^{*} (Y),$ where

$\begin{matrix} F = sup_{X \in Y^{*}, f (X) = 1} min_{(v_{i}, v_{j}) \in U} ν_{ij} (X), \\ f^{*} (Y) = {\begin{matrix} sup_{X \in Y^{*}, f (X) = 1} min_{(v_{i}, v_{j}) \in U} ν_{ij} (X), & if F < 0.5 \\ 1 - sup_{X \in Y^{*}, f (X) = 0} min_{(v_{i}, v_{j}) \in U} ν_{ij} (X), & if F \geq 0.5, \end{matrix} \\ ν_{ij} (X) = {\begin{matrix} α_{ij}, & if x_{ij} = 1 \\ 1 - α_{ij}, & if x_{ij} = 0 \end{matrix} (v_{i}, v_{j}) \in U, \\ f (X) = {\begin{matrix} 1, & if I + X + X^{2} + \dots + X^{n - 1} > 0 \\ 0, & otherwise . \end{matrix} \end{matrix}$

3 Cycle index of uncertain random graph

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}, \dots, ξ_{m}}$ . The cycle function of $G$ is denoted as: $C (E (G)) = {\begin{matrix} 1, & ifgraph G is cycle \\ 0, & otherwise . \end{matrix}$

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.

Definition 3.2. cyc-index A cycle index of an uncertain random graph $G$ is the chance measure that the uncertain random graph is cycle, i.e., $μ (G) = Ch {C (E (G)) = 1} .$

A basic problem for us is how to calculate the cycle index when an uncertain random graph is given. The following theorem can completely solve this problem for an uncertain random graph.

Theorem 3.3. teo1 Let $G = (V, U, R, T)$ be an uncertain random graph. If all edges are independent, then the cycle index of $G$ is $μ (G) = \sum_{Y \in X} (\prod_{(v_{i}, v_{j}) \in R} ν_{ij} (Y)) C^{*} (Y),$ where $\begin{matrix} H = sup_{X \in Y^{*}, C (X) = 1} min_{(v_{i}, v_{j}) \in U} ν_{ij} (X), \\ C^{*} (Y) = {\begin{matrix} sup_{X \in Y^{*}, C (X) = 1} min_{(v_{i}, v_{j}) \in U} ν_{ij} (X), & if H < 0.5 \\ 1 - sup_{X \in Y^{*}, C (X) = 0} min_{(v_{i}, v_{j}) \in U} ν_{ij} (X), & if H \geq 0.5, \end{matrix} \\ ν_{ij} (X) = {\begin{matrix} α_{ij}, & if x_{ij} = 1 \\ 1 - α_{ij}, & if x_{ij} = 0 \end{matrix} (v_{i}, v_{j}) \in U, \\ ν_{ij} (Y) = {\begin{matrix} α_{ij}, & if y_{ij} = 1 \\ 1 - α_{ij}, & if y_{ij} = 0 \end{matrix} (v_{i}, v_{j}) \in R, \\ C (X) = {\begin{matrix} 1, & if {\begin{matrix} I + X + X^{2} + \dots + X^{n - 1} > 0 \\ \sum_{j = 1}^{n} x_{ij} = 2 for i = 1, 2, \dots, n \end{matrix} \\ 0, & otherwise . \end{matrix} \end{matrix}$

Proof. Note that all random edges are independent Boolean random variables, being represented by $η_{ij} = {\begin{matrix} 1 with probability measure α_{ij} \\ 0 with probability measure 1 - α_{ij} \end{matrix}$ for $(v_{i}, v_{j}) \in R .$

Also, all uncertain edges are independent Boolean uncertain variables, being represented by

$τ_{ij} = {\begin{matrix} 1 with uncertain measure α_{ij} \\ 0 with uncertain measure 1 - α_{ij} \end{matrix}$ for $(v_{i}, v_{j}) \in U .$

Let G be a classical graph of order n with adjacency matrix

$X = (\begin{matrix} x_{11} & x_{12} & \dots & x_{1 n} \\ x_{21} & x_{22} & \dots & x_{2 n} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ x_{n 1} & x_{n 2} & \dots & x_{nn} \end{matrix}),$ where x_ij ∈ {0, 1}, and X is a symmetric matrix with x_ii = 0, i = 1, 2, ⋯, n. Then the graph $G$ is connected if and only if

$I + X + X^{2} + \dots + X^{n - 1} > 0 .$

The degree of a vertex v_i 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,

$C (X) = {\begin{matrix} 1, & if {\begin{matrix} I + X + X^{2} + \dots + X^{n - 1} > 0 \\ \sum_{j = 1}^{n} x_{ij} = 2 for i = 1, 2, \dots, n \end{matrix} \\ 0, & otherwise . \end{matrix}$

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) = \sum_{X \in X} (\prod_{1 \leq i < j \leq n} ν_{ij} (X)) C (X),$ where

$X = {X | \begin{matrix} x_{ij} = 0 or 1, i, j = 1, 2, \dots, n \\ x_{ij} = x_{ji}, i, j = 1, 2, \dots, n \\ x_{ii} = 0, i = 1, 2, \dots, n \end{matrix}} .$

Remark 3.5. If the uncertain random graph $G$ becomes an uncertain graph, then the cycle index of $G$ is

$\begin{matrix} μ (G) \\ = {\begin{matrix} sup_{X \in X, C (X) = 1} min_{1 \leq i < j \leq n} ν_{ij} (X), & if H < 0.5 \\ 1 - sup_{X \in X, C (X) = 0} min_{1 \leq i < j \leq n} ν_{ij} (X), & if H \geq 0.5, \end{matrix} \end{matrix}$ where $\begin{matrix} H = sup_{X \in Y^{*}, C (X) = 1} min_{(v_{i}, v_{j}) \in U} ν_{ij} (X), \\ X = {X | \begin{matrix} x_{ij} = 0 or 1, i, j = 1, 2, \dots, n \\ x_{ij} = x_{ji}, i, j = 1, 2, \dots, n \\ x_{ii} = 0, i = 1, 2, \dots, n \end{matrix}}, \end{matrix}$ which is equivalent to the result that presented in Gao [22].

It is quite well known that if a graph is cycle then it must be connected. Thus we have Corollary 3.

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 to determine the cycle index of uncertain graph, which was given by Gao [22], 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) = {v_{1}, v_{2}, \dots, v_{n}}$ and the edge set $E (G) = {ξ_{1}, ξ_{2}, \dots, ξ_{n}}$ . Let $ℂ$ be a spanning cycle with $V (ℂ) = {v_{1}, v_{2}, \dots, v_{n}}$ and $E (ℂ) = {ξ_{c_{1}}, ξ_{c_{2}}, \dots, ξ_{c_{n - 1}}}$ . The cycle index of $G$ is $μ (G) = \sum_{Y \in X} (\prod_{(v_{i}, v_{j}) \in R} ν_{ij} (Y)) ℂ^{*} (Y),$ where $ℂ^{*} (Y) = \begin{matrix} sup_{ℂ (X) = 1} min_{(v_{i}, v_{j}) \in U} \\ {μ (ℂ), 1 - max_{(v_{i}, v_{j}) \in E (G) \ E (ℂ))} α_{ij}} . \end{matrix}$ (5)

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 [22], Equation (5) can be obtained directly. □

Given an uncertain random graph $G = (V, U, R, T)$ , $U = {(v_{i}, v_{j}) | (v_{i}, v_{j}) are uncertain edge}$ , $R = {(v_{i}, v_{j}) | (v_{i}, v_{j}) 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.

Algorithm 1. Algorithm for calculating the cycle index of uncertain random graph Step 1. Set Q = {∅}, k = 0, μ′ = 0. If there exists an adjacency matrix X_k = [x_ij] such that $G$ is a cycle, then go to Step 2. Otherwise, stop, $μ (G) = 0$ . Step 2. for each X_k, determine matrix Y_k = [y_ij]. The element y_ij = 1 if (v_i, v_j) in $R$ , and otherwise, y_ij = 0. Step 3. Determine the value ν_ij (Y_k), where ν_ij (Y_k) = α_ij if y_ij = 1, and ν_ij (Y_k) =1 - α_ij if y_ij = 0 for all $(v_{i}, v_{j}) \in R$ . Calculate $δ = \prod_{(v_{i}, v_{j}) \in R} ν_{ij} (Y_{k})$ . Step 4. Calculate $min_{(v_{i}, v_{j}) \in U} ν_{ij} (X_{k}),$ where ν_ij (X_k) = α_ij if x_ij = 1, and ν_ij (X_k) =1 - α_ij if x_ij = 0 for $(v_{i}, v_{j}) \in U$ .Set $μ^{'} = sup {μ^{'}, min_{(v_{i}, v_{j}) \in U} ν_{ij} (X_{k})}$ , Q = Q ∪ {X_k} and k = k + 1.Step 5. if there exists other adjacency matrix $X_{k} \in \bar{Q}$ such that $G$ is a cycle, then go to Step 3. Otherwise, stop, and calculate $μ (G) = \sum_{X_{k} \in 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, where $\begin{matrix} U & = & {(v_{2}, v_{3}), (v_{2}, v_{4}), (v_{3}, v_{4})}, \\ R & = & {(v_{1}, v_{2}), (v_{1}, v_{3}), (v_{1}, v_{4})} . \end{matrix}$

The uncertain random adjacency matrix of $G$ is $T = (\begin{matrix} 0 & 0.7 & 0.6 & 0.1 \\ 0.7 & 0 & 0.3 & 0.7 \\ 0.6 & 0.3 & 0 & 0.2 \\ 0.1 & 0.7 & 0.2 & 0 \end{matrix}) .$

The route needed by the salesman is a cycle of the uncertain random graph $G$ . What is the truth value 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. [25] that $G$ has 2⁶ realizations (models). Among 64 models, if a model has one of the following three adjacency matrices $X_{0} = (\begin{matrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{matrix}), X_{1} = (\begin{matrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{matrix}),$ $X_{2} = (\begin{matrix} 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \end{matrix}),$ then it is cycle. Otherwise, the model is not a cycle.

In Step 2, we determine a matrix Y_k for each X_k.

For $X_{0} = (\begin{matrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{matrix})$ , the matrix Y₀ is $(\begin{matrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{matrix}) .$

In Step 3, we determine ν_ij (Y_k) as follows: ν₁₂ (Y₀) =0.7, ν₁₃ (Y₀) =0.4, ν₁₄ (Y₀) =0.1. After that, the value $δ = \prod_{(v_{i}, v_{j}) \in R} ν_{ij} (Y_{1}) = 0.7 \times 0.4 \times 0.1 = 0.028$ is obtained.

In Step 4, we calculate $μ^{'} = min_{(v_{i}, v_{j}) \in U} ν_{ij} (X_{1}) = 0.2 .$ Since there exists other adjacency matrix such that $G$ is a cycle, then go back to step 3.

For $X_{1} = (\begin{matrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{matrix})$ , the matrix Y₁ is $(\begin{matrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{matrix}),$ we get $\begin{matrix} δ = \prod_{(v_{i}, v_{j}) \in R} ν_{ij} (Y_{1}) = 0.378, and \\ μ^{'} = min_{(v_{i}, v_{j}) \in U} ν_{ij} (X_{1}) = 0.2 . \end{matrix}$

For $X_{2} = (\begin{matrix} 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \end{matrix}),$ the matrix Y₂ is $(\begin{matrix} 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{matrix}),$ we obtain $\begin{matrix} δ = \prod_{(v_{i}, v_{j}) \in R} ν_{ij} (Y_{2}) = 0.018, and \\ μ^{'} = min_{(v_{i}, v_{j}) \in U} ν_{ij} (X_{2}) = 0.3 . \end{matrix}$

In Step 5, we obtain the cycle index of the uncertain random graph $G$ as follows: $\begin{matrix} μ (G) & = & 0.028 \times 0.2 + 0.378 \times 0.2 \\ + 0.018 \times 0.3 = 0.0866 . \end{matrix}$

The result can be interpreted as follows: the truth value 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 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.

Footnotes

Acknowledgments

This work was supported by 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 of National Natural Science Foundation of China (Nos. 71671135, 61703438), the Key Project of Hubei Provincial Natural Science Foundation (No. 2015CFA144), the 2018 Soft Science Research Project of Technology Innovation in Hubei province (No. 2018ADC044), and the Fundamental Research Funds for the Central Universities (No. 2017IVA067).

References

Akram

, Bipolar fuzzy graphs, Information Sciences 181(24) (2011), 5548–5564.

Akram

, Al-Shehrie

, Davvaz

and Ashraf

, Bipolar fuzzy digraphs in decision support systems, Journal of Multiple-Valued Logic and Soft Computing 27(5-6) (2016), 531–551.

Akram

, Chen

and Davvaz

, On N-hypergraphs, Journal of Intelligent and Fuzzy Systems 26(6) (2014), 2937–2944.

Akram

and Davvaz

, Strong intuitionistic fuzzy graphs, Filomat 26(1) (2012), 177–196.

Akram

and Dudek

, Intuitionistic fuzzy hypergraphs with applications, Information Sciences 218 (2013), 182–193.

Akram

, Farooq

, Saeid

and Shum

, Certain types of vague cycles and vague trees, Journal of Intelligent and Fuzzy Systems 28(2) (2015), 621–631.

Akram

and Nawaz

, Fuzzy soft graphs with applications, Journal of Intelligent and Fuzzy Systems 30(6) (2016), 3619–3632.

Akram

, Waseem

and Davvaz

, Certain types of domination in m-polar fuzzy graphs, Journal of Multiple-Valued Logic and Soft Computing 29(6) (2017), 619–646.

Akram

, Siddique

and Davvaz

, New concepts in neutrosophic graphs with application, Journal of Applied Mathematics and Computing 57(1-2) (2018), 279–302.

10.

Alon

, Bohman

and Huang

, More on the bipartite decomposition of random graphs, Journal of Graph Theory 84(1) (2016), 45–52.

11.

Bondy

, Murty

, Graph Theory with Applications Elsevier, New York, 1976.

12.

Chen

, Peng

and Ralescu

, Uncertain vertex coloring problem, Soft Computing (2017). DOI: 10.1007/s00500-017-2861-7

13.

Chen

, Peng

, Liu

and Zhao

, Pricing and effort decisions for a supply chain with uncertain information, International Journal of Production Research 55(1) (2017), 264–284.

14.

Chen

, Peng

and Zhang

, Uncertain goal programming models for bicriteria solid transportation problem, Applied Soft Computing 51 (2017), 49–59.

15.

Chen

, Peng

, Zhang

and Li

, Uncertain programming model for uncertain minimum weight vertex covering problem, Journal of Intelligent Manufacturing 28(3) (2017), 625–632.

16.

Chen

, Peng

, Zhang

and Rosyida

, Diversified models for portfolio selection based on uncertain semivariance, International Journal of Systems Science 48(3) (2017), 637–648.

17.

Cheng

, Rao

and Chen

, Multidimensional knapsack problem based on uncertain measure, Scientia Iranica, Transactions E: Industrial Engineering 24(5) (2017), 2527–2539.

18.

Erdős

Rényi

, On random graph, Publicacions Matematiques 6 (1959), 290–297.

19.

Farshi

and Davvaz

, Generalized fuzzy hypergraphs and hypergroupoids, Filomat 30(9) (2016), 2375–2387.

20.

Gao

, Sun

and 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.

21.

Gao

and Yao

, Importance index of components in uncertain random systems, Knowledge-Based Systems 109 (2016), 208–217.

22.

Gao

, Cycle index of uncertain graph, Information 16(2) (2013), 1131–1138.

23.

Gao

, Tree index of uncertain graphs, Soft Computing 20(4) (2016), 1449–1458.

24.

Gao

and Gao

, Connectedness index of uncertain graph, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 21(1) (2013), 127–137.

25.

Gao

, Yang

, Li

and Kar

, On distribution function of the diameter in uncertain graph, Information Sciences 296 (2015), 61–74.

26.

Gilbert

, Random graphs, Annals of Mathematical Statistics 30(4) (1959), 1141–1144.

27.

Gilmer

and Kopparty

, A local central limit theorem for triangles in a random graph, Random Structures & Algorithms 48(4) (2016), 732–750.

28.

Liu

, Uncertainty Theory, 2nd edn, Springer-Verlag, Berlin, 2007.

29.

Liu

, Some research problems in uncertainty theory, Journal of Uncertain Systems 3(1) (2009), 3–10.

30.

Liu

, Uncertainty Theory: A Branch of Mathematics for Modeling Human Uncertainty, Springer-Verlag, Berlin, 2010.

31.

Liu

, Uncertain random graphs and uncertain random networks, Journal of Uncertain Systems 8(1) (2014), 3–12.

32.

Liu

, Uncertain random variables: A mixture of uncertainty and randomness, Soft Computing 17(4) (2013), 625–634.

33.

Liu

, Uncertain random programming with applications, Fuzzy Optimization and Decision Making 12(2) (2013), 153–169.

34.

Liu

, Zhao

, Liu

and Chen

, Contract designing for a supply chain with uncertain information based on confidence level, Applied Soft Computing 56 (2017), 617–631.

35.

, Jia

, Zhang

and Sun

, Travelling salesman problem in uncertain environments, The Open Cybernetics and Systemics Journal 9 (2015), 313–317.

36.

Rao

, Goh

, Zhao

and Zheng

, Location selection of city logistics centers under sustainability, Transportation Research Part D: Transport and Environment 36 (2015), 29–44.

37.

Rao

, Xiao

, Xie

, Goh

and Zheng

, Low carbon supplier selection under multi-source and multi-attribute procurement, Journal of Intelligent and Fuzzy Systems 32(6) (2017), 4009–4022.

38.

Rosenfeld

, Fuzzy graph, In: Zadeh

, Fu

and Shimura

, Eds.Fuzzy Sets and Their Applications to Cognitive and Decision Processes, 1975, pp. 77–95.

39.

Rosyida

, Peng

, Chen

, Widodo

, Indrati

Ch.R.

and Sugeng

, An uncertain chromatic number of an uncertain graph based on α-cut coloring, Fuzzy Optimization and Decision Making 17(1) (2018), 103–123.

40.

Rosyida

, Widodo

, Indrati

Ch. R.

and Sugeng

K.A.

, A new approach for determining fuzzy chromatic number of fuzzy graph, Journal of Intelligent and Fuzzy Systems, 28 (2015), 2331–2341.

41.

Talebi

, Rashmanlou

and Davvaz

, New concepts of regular interval-valued fuzzy graphs, Journal of Applied Mathematics and Informatics 35(1-2) (2016), 95–111.

42.

Zhang

and Peng

, Euler index in uncertain graph, Applied Mathematics and Computation 218(20) (2012), 10279–10288.

43.

Zhang

, Peng

and Li

, Euler index of uncertain random graph: Concepts and properties, International Journal of Computer Mathematics 94(2) (2017), 217–229.

44.

Zhang

, Peng

and Li

, Matching index and its algorithm of uncertain random graph, Applied and Computational Mathematics 17(1) (2018), 22–35.

45.

Zhou

, Tang

and Zhao

, An uncertain search model for recruitment problem with enterprise performance, Journal of Intelligent Manufacturing 28(3) (2017), 695–704.

46.

Zhou

, Peng

, Liu

and Dong

, Optimal incentive contracts under loss aversion and inequity aversion, Fuzzy Optimization and Decision Making (2018). DOI: 10.1007/s10700-018-9288-1