Improved similarity measure in neutrosophic environment and its application in finding minimum spanning tree

Abstract

Minimum spanning tree finds its huge application in network designing, approximation algorithms for NP-hard problems, clustering problems and many more. Many research works have been done to find minimum spanning tree due to its various applications. But, till date very few research works are available in finding minimum spanning tree in neutrosophic environment. This paper contributes significantly by defining the weight of each network edge using single valued neutrosophic set (SVNS) and introduce a new approach using similarity measure to find minimum spanning tree in neutrosophic environment. Use of SVNS makes the problem realistic as it can describe the uncertainty, indeterminacy and hesitancy of the real world in a better way. We introduce two new and simple similarity measures to overcome some disadvantages of existing Jaccard, Dice and Cosine similarity measures of SVNSs for ranking the alternatives. Further from the similarity measures we have developed two formulas for the entropy measure proving a fundamental relation between similarity measure and entropy measure. The new entropy measures define the uncertainty more explicitly in comparison to other entropy measure existing in the literature which has been established using an example.

Keywords

1 Introduction

A minimum spanning tree of a weighted graph G as discussed by Bang Ye Wu and Kun-Mao Chao in [2] is a spanning tree of G whose edges sum to minimum weight. In other words, a minimum spanning tree is a tree formed from a subset of the edges in a given undirected graph, with two properties: (1) it spans the graph, i.e., it includes every vertex in the graph, and (2) it is minimum, i.e., the total weight of all the edges is as low as possible. The minimum spanning tree problem is very important since it arises in many applications, it is an important example where greedy algorithms always deliver an optimal solution and clever data structures are necessary to make it work efficiently.

Zadeh in 1965 defined the fuzzy set (FS) [17] which is an extension of ordinary or crisp set by introducing the degree of membership/truth (t). The elements in the fuzzy set are characterised by the grade of membership to the set. Atanasov introduced the concept of intuitionistic fuzzy set (IFS) [18] in 1986 as an extension of FS considering membership and non membership degrees of an element to the set. Smarandache first introduced the degree of indeterminacy/neutrality as independent component in 1995 (published in 1998) and defined the neutrosophic set (NS) [19]. He has coined the words neutrosophy and neutrosophic. Neutrosophy means knowledge of neutral thought while neutrosophic means having the nature of, or having the characteristic of Neutrosophy. In 2013 he refined the NS to n components: t₁, t₂, …, t_j; i₁, i₂, …, i_k; f₁, f₂, …, f_l, with j + k + l = n > 3. NS generalizes the concept of crisp set, FS, IFS as the elements in the NS are characterised by the grade of truth membership, indeterminacy membership and falsity membership. It can effectively solve uncertainty problems involving indeterminate and inconsistent information.

In [20] Zhang-peng Tian et al. solved green product design selection problems using neutrosophic linguistic information. Xiao-hui Wu et al. [21] established ranking methods for simplified neutrosophic sets based on prioritized aggregation operators and cross-entropy measures to solve multi criteria decision making (MCDM) problem. Interval neutrosophic linguistic aggregation operators were developed and applied to the medical treatment selection process [22] by Yin-xiang Ma et al. Zhang-peng Tian, Hong-yu Zhang et al. [23] established a MCDM method based on cross entropy. Several similarity measures for NS were defined by Broumi and Smarandache [24]. They also defined weighted interval valued neutrosophic sets (IVNSs) [11] and found a cosine similarity measure between two IVNSs. They applied it to problems related to pattern recognition. Jun Ye introduced in [4] a generalized single-valued neutrosophic weighted distance measure and presented two distance-based similarity measures in a single-valued neutrosophic setting. He established a single-valued neutrosophic clustering algorithm on the basis of the two similarity measures. He further generalized the Jaccard, Dice, and cosine similarity measures between two vectors in simplified neutrosophic sets (SNSs) [9]. He then applied the three similarity measures to a MCDM problem in the simplified neutrosophic setting. In [3] Jun Ye defined a generalized single-valued neutrosophic weighted distance and proposed the single valued minimum spanning tree (MST) clustering algorithm. Many research works have been done on the spanning trees [12 , 32] so far, but very few of them are in neutrosophic environment. The weights in the graph may not be known with certainty in real life problems and so can not be defined precisely. Using NS the uncertainty in defining the parameters can be solved in a more efficient manner. In [3] Jun Ye established a method to find MST of a graph where nodes i.e. samples are represented in the form of SVNSs and distance between two nodes which represents the dissimilarity between the corresponding samples has been derived. But in this paper we at first introduce two new similarity measure functions to overcome some disadvantages of existing Jaccard, Dice and cosine similarity measures of SVNSs discussed in [9] for ranking alternatives. Using those new similarity measure formulae, a method to find optimum spanning tree is developed considering the weight of each edge in the graph as SVNS. This paper considers a network problem with multiple criteria which are represented by weight of each edge in NS and finds the optimum spanning tree in neutrosophic environment.

Entropy is also an important conception to measure uncertainty. Eulalia Szmidt and Janusz Kacprzyk introduced a measure of entropy for an IFS in [1]. Hung and Yang discussed a new entropy measure in IFS and compared the degree of fuzziness with different entropy measures in [7]. Ali Aydogdu studied on similarity and entropy of IVNS in [28]. Pinaki Majumdar and S.k. Samanta [5] introduced similarity measure and entropy measure of SVNSs. A relationship between similarity measure and entropy measure was investigated in [25] for IFS and for interval valued IFS in [26]. In this paper a fundamental relation between similarity measure and entropy measure of SVNS has been established and thereby, two new entropy measures have been posed. With an example it has also been proved that the new entropy measures give more meaningful result.

The rest of the paper is structured as follows: Section 2 introduces some concepts of NSs and simplified neutrosophic sets. Section 3 describes the basic concept of the graph and minimum spanning trees. In Section 4 we define a new similarity measure and entropy function to compare the NSs. Section 5 presents algorithm for finding optimum spanning tree in neutrosophic environment. In Section 6, a numerical example demonstrates the application and effectiveness of the proposed similarity measure in decision-making problems and the solution approach to find minimum spanning tree in neutrosophic environment. We conclude the paper in Section 7.

2 Neutrosophic sets

2.1 Definition [19]

Let U be an universe of discourse then the neutrosophic set A is defined as A = {〈x : T_A (x), I_A (x), F_A (x) 〉, x ∈ U}, where the functions T, I, F: U →] ⁻0, 1⁺ [define respectively the degree of membership (or Truth), the degree of indeterminacy and the degree of non-membership (or falsehood) of the element x ∈ U to the set A with the condition ⁻0 ≤ T_A (x) + I_A (x) + F_A (x) ≤ 3⁺.

To apply NS to science and technology, we consider the NS which takes the value from the subset of [0, 1] instead of ] ⁻0, 1⁺ [; i.e., we consider SNS as defined by Ye in [14].

2.2 Simplified neutrosophic set

Let X be a space of points (objects) with generic elements in X denoted by x. An NS A in X is characterized by a truth-membership function T_A (x), an indeterminacy membership function I_A (x), and a falsity-membership function F_A (x), if the functions T_A (x) , I_A (x) , F_A (x) are singletone subintervals/subsets in the real standard [0, 1], i.e., T_A (x) : X → [0, 1], I_A (x) : X → [0, 1] and F_A (x) : X → [0, 1]. Then a simplification of the NS A is denoted by $A = \{〈x, T_{A} (x), I_{A} (x), F_{A} (x)〉, x ∊ X\}$ .

2.3 Single valued neutrosophic sets (SVNS)

Let X be a space of points (objects) with generic elements in X denoted by x. A SVNS A in X is characterized by a truth-membership function T_A (x), an indeterminacy membership function I_A (x) and a falsity-membership function F_A (x), for each point x ∈ X, T_A (x) , I_A (x) , F_A (x) ∈ [0, 1]. Therefore, a SVNS A can be written as $A_{S V N S} = \{〈x, T_{A} (x), I_{A} (x), F_{A} (x)〉, x ∊ X\}$ . For two SVNSs, $A_{S V N S} = \{〈x, T_{A} (x), I_{A} (x), F_{A} (x)〉, x ∊ X\}$ and $B_{S V N S} = \{〈x, T_{A} (x), I_{A} (x), F_{A} (x)〉, x ∊ X\}$ , the following expressions are defined in [15] as follows: A_NS ⊆ B_NS if and only if T_A (x) ≤ T_B (x), I_A (x) ≥ I_B (x), F_A (x) ≥ F_B (x).

A_NS = B_NS if and only if T_A (x) = T_B (x), I_A (x) = I_B (x), F_A (x) = F_B (x).

A^c = 〈x, F_A (x), 1 − I_A (x), T_A (x) 〉.

For convenience, a SVNS A is denoted by $A = 〈T_{A} (x), I_{A} (x), F_{A} (x)〉$ for any x in X. For two SVNSs A and B, the operational relations are definedby [15]: $\begin{matrix} A \cup B = & 〈 max (T_{A} (x), T_{B} (x)), \\ min (I_{A} (x), I_{B} (x)), \\ min (F_{A} (x), F_{B} (x)) 〉 \end{matrix}$ (1) $\begin{matrix} A \cap B = & 〈 min (T_{A} (x), T_{B} (x)), \\ max (I_{A} (x), I_{B} (x)), \\ max (F_{A} (x), F_{B} (x)) 〉 \end{matrix}$ (2)

3 Graph and minimum spanning trees

A graph G consists of a set V of vertices and a collection E (not necessarily a set) of unordered pairs of vertices, called edges. A graph is symbollically represented as G = (V, E). The order of a graph is the number of its vertices, and its size is the number of its edges. A graph may be of two types: an undirected graph and a directed graph. Each edge in the undirected graph is an unordered pair v_i, v_j, whereas each edge in the directed graph is an ordered pair v_i, v_j, where the vertices v_i and v_j are called the end points of an edge. A sequence of edges and vertices that can be traveled between two different vertices is called a path.

3.1 Weighted graphs

A weighted graph is a graph, in which each edge has a weight (some real number).

3.2 Weight of a graph

The sum of the weights of all edges of a graph G is the weight of that graph.

3.3 Subgraphs

The graph H = (W, F) is a subgraph of the graph G = (V, E) if W is a subset of V and F is a subset of E.

3.4 Connected graphs

A pair of vertices in a graph is a connected pair if there is a path between them. A graph is a connected graph if every pair of vertices in G is a connected pair, otherwise it is disconnected graph.

3.5 Cycle

A closed walk in a graph is a walk between a vertex and itself. A closed walk in which no edges repeat is a circuit. A cycle is a circuit with no repeatedvertices.

3.6 Acyclic graph

An acyclic graph is a graph with no cycles. A tree is a connected acyclic graph.

3.7 Spanning tree

A connected acyclic graph that contains all nodes of G is called a spanning tree of the graph. Any set of straight line segments connecting pairs of nodes such that

no closed loops occur,

each node is visited by at least one line, and

a tree is connected is also called a spanning tree of the graph.

3.8 Minimum Spanning Tree

Minimum spanning tree in an undirected connected weighted graph is a spanning tree of minimum weight (among all spanning trees).

4 Similarity measure

4.1 Definition 1

As stated in [9], [10], [11] similarity measure S for SVNS(X) is a real function on universe X such that S : SVNS (X) × SVNS (X) → [0, 1] and satisfies the following properties:

0 ≤ S (A, B) ≤1, ∀ A, B ∈ SVNS (X),

S (A, B) = S (B, A) , ∀ A, B ∈ SVNS (X),

S (A, B) =1, when A = B, ∀ A, B ∈ SVNS (X).

We state the additional two properties (iv) and (v) for the similarity measure.

S (A, A^c) =0 if A is a crisp set, ∀A ∈ P (X),

4.2 Jaccard, Dice and cosine similarity measures

Jaccard, Dice, cosine weighted similarity measures between two SVNSs A and B as discussed by Jun Ye in [9] are

$\begin{matrix} WJ (A, B) \\ = \sum_{i = 1}^{n} w_{i} \frac{T_{A} (x_{i}) T_{B} (x_{i}) + I_{A} (x_{i}) I_{B} (x_{i}) + F_{A} (x_{i}) F_{B} (x_{i})}{\begin{matrix} (T_{A} (x_{i}))^{2} + (I_{A} (x_{i}))^{2} + (F_{A} (x_{i}))^{2} + \\ (T_{B} (x_{i}))^{2} + (I_{B} (x_{i}))^{2} + (F_{B} (x_{i}))^{2} - \\ T_{A} (x_{i}) T_{B} (x_{i}) - I_{A} (x_{i}) I_{B} (x_{i}) - F_{A} (x_{i}) F_{B} (x_{i}) \end{matrix}} \\ WD (A, B) \\ = \sum_{i = 1}^{n} w_{i} \frac{2 (T_{A} (x_{i}) T_{B} (x_{i}) + I_{A} (x_{i}) I_{B} (x_{i}) + F_{A} (x_{i}) F_{B} (x_{i}))}{\begin{matrix} (T_{A} (x_{i}))^{2} + (I_{A} (x_{i}))^{2} + \\ (F_{A} (x_{i}))^{2} + (T_{B} (x_{i}))^{2} + (I_{B} (x_{i}))^{2} + (F_{B} (x_{i}))^{2} \end{matrix}} \\ WC (A, B) \\ = \sum_{i = 1}^{n} w_{i} \frac{T_{A} (x_{i}) T_{B} (x_{i}) + I_{A} (x_{i}) I_{B} (x_{i}) + F_{A} (x_{i}) F_{B} (x_{i})}{\begin{matrix} \sqrt{(T_{A} (x_{i}))^{2} + I_{A} (x_{i}))^{2} + F_{A} (x_{i}))^{2}} \\ \sqrt{(T_{B} (x_{i}))^{2} + I_{B} (x_{i}))^{2} + F_{B} (x_{i}))^{2}} \end{matrix}} \end{matrix}$

4.3 The proposed similarity measures for SVNSs

In this paper we propose two new similarity measures for SVNSs. Let U be the universe.

$A = \{〈x_{i} : T_{A} (x_{i}), I_{A} (x_{i}), F_{A} (x_{i})〉, x_{i} ∊ A\}$ and $B = \{〈x_{i} : T_{B} (x_{i}), I_{B} (x_{i}), F_{B} (x_{i})〉, x_{i} ∊ B\}$ are two SVNSs in U. Then Our proposed similarity functions between A and B are: $\begin{matrix} S^{1} (A, B) = \frac{1}{n} \sum_{x_{i} \in X} [1 - {log}_{2} [1 + \frac{1}{4} [| T_{A} (x_{i}) - T_{B} (x_{i}) | \\ + 2 | I_{A} (x_{i}) - I_{B} (x_{i}) | + | F_{A} (x_{i}) - F_{B} (x_{i}) |]]] . \end{matrix}$ (3) $\begin{matrix} S^{2} (A, B) = \frac{1}{n} \sum_{x_{i} \in X} cos (\frac{π}{2} . \frac{1}{4} [| T_{A} (x_{i}) - T_{B} (x_{i}) | \\ + 2 | I_{A} (x_{i}) - I_{B} (x_{i}) | + | F_{A} (x_{i}) - F_{B} (x_{i}) |]) . \end{matrix}$ (4)

The similarity measures defined above are better than existing ones which can be established by the fact given below:

For two SVNSs A and B in X, if T_A (x_i) = I_A (x_i) = F_A (x_i) =0 and/or T_B (x_i) = I_B (x_i) = F_B (x_i) =0 for any x_i in X (i = 1, 2 … , n) Jaccard, Dice and cosine similarity measures are undefined. But our proposed similarity measures (3), (4) overcome this drawback.

4.3.1 Theorem 1

Both the proposed similarity measure functions satisfy the properties as defined in subsection 4.1

Proof. Clearly Sⁱ (A, B) (i=1,2) satisfies the properties (i), (ii), (iii), and (iv). We prove only property (v).

If |T_A (x) − T_B (x) | ≤ |T_A (x) − T_C (x) |, |F_A (x) − F_B (x) | ≤| F_A (x) − F_C (x) |, |I_A (x) − T_B (x) | ≤ |I_A (x) − I_C (x) |, [|T_A (x_i) − T_B (x_i) | + 2|I_A (x_i) − I_B (x_i) | + |F_A (x_i) − F_B (x_i) |] ≤ [|T_A (x_i) − T_C (x_i) | + 2|I_A (x_i) − I_C (x_i) | + |F_A (x_i) − F_C (x_i) |]

i.e. 1 − log ₂ $[1 + \frac{1}{4 n}$ ∑_{x_i∈X} [|T_A (x_i) − T_B (x_i) | + 2|I_A (x_i) − I_B (x_i) | + |F_A (x_i) − F_B (x_i) |]] ≥ 1 − log ₂ $[1 + \frac{1}{4 n}$ ∑_{x_i∈X} [|T_A (x_i) − T_C (x_i) | + 2|I_A (x_i) − I_C (x_i) | + |F_A (x_i) − F_C (x_i) |]]

i.e S¹ (A, B) ≥ S¹ (A, C).

And in similar way S² (A, B) also satisfies the property (v).

4.4 Weighted similarity measure

The weighted similarity measure S_w, between two SVNSs A and B satisfies the following properties:

0 ≤ S_w (A, B) ≤1,

S_w (A, B) = S_w (B, A),

S_w (A, B) =1, when A=B,

S_w (A, A^c) =0 when A is a crisp set,

S_w (A, B) ≥ S_w (A, C) when |T_A (x) − T_B (x) | ≤ |T_A (x) − T_C (x) |, |F_A (x) − F_B (x) | ≤ |F_A (x) − F_C (x) | and |I_A (x) − T_B (x) | ≤ |I_A (x) − I_C (x) |.

4.4.1 Proposed weighted similarity function

Let w_i be the weight for each element x_i (i = 1, 2, …, n), w_i ∈ [0, 1] and $\sum_{i = 1}^{n} w_{i} = 1$ . Then our proposed weighted similarity functions are $\begin{matrix} S_{w}^{1} (A, B) & = & \sum_{x_{i} \in X} w_{i} [1 - {log}_{2} [1 + \frac{1}{4} [| T_{A} (x_{i}) \\ - T_{B} (x_{i}) | + 2 | I_{A} (x_{i}) - I_{B} (x_{i}) | \\ + | F_{A} (x_{i}) - F_{B} (x_{i}) |]]] . \end{matrix}$ (5) $\begin{matrix} S_{w}^{2} (A, B) & = & \sum_{x_{i} \in X} w_{i} cos [\frac{π}{2} \frac{1}{4} [| T_{A} (x_{i}) - T_{B} (x_{i}) | \\ + 2 | I_{A} (x_{i}) - I_{B} (x_{i}) | \\ + | F_{A} (x_{i}) - F_{B} (x_{i}) |]] . \end{matrix}$ (6)

4.4.2 Theorem 2

It is very clear that both the proposed weighted similarity measure functions satisfy the properties as defined in subsection 4.4.

4.5 Comparison of new weighted similarity measures of SVNS with the existing measures

Example 1.A = {x₁, (0.2, 0.5, 0.6); x₂ (0.2, 0.4, 0.4)} and B = {x₁, (0.2, 0.4, 0.4); x₂ (0.4, 0.2, 0.3)} with w₁ = 0.55 and w₂ = 0.45. Weighted Jaccarad similarity measure WJ (A, B) = 0.8386. Weighted Dice similarity measure WD (A, B) = 0.9105. Weighted Cosine similarity measure WC (A, B) = 0.9358. $S_{w}^{1} (A, B)$ = 0.8197 and $S_{w}^{2} (A, B)$ = 0.9763;

Example 2.C = {x₁, (0.3, 0.2, 0.3); x₂ (0.5, 0.2, 0.3); x₃, (0.5, 0.3, 0.8)} and D = {x₁, (0.7, 0, 0.1); x₂ (0.6, 0.1, 0.2); x₃, (0.5, 0.3, 0.8)} with w₁ = 0.35, w₂ = 0.25 and w₃ = 0.40. Weighted Jaccarad similarity measure WJ (C, D) =0.8067. Weighted Dice similarity measure WD (C, D) =0.8738. Weighted Cosine similarity measure WC (C, D) =0.8939. $S_{w}^{1} (C, D) = 0.8529$ and $S_{w}^{2} (C, D) = 0.9702$ ;

It may be observed from the above examples that the values of similarity from the new formulae are almost similar to those from the existing measures.

4.6 Entropy measure

Let N(X) be the collection of all SVNS in X. We introduce the entropy as a function E_N : N (X) → [0, 1] which satisfies the following axioms:

E_N (A) =0 if A is a crisp set

E_N (A) =1 if (T_A (x), I_A (x), F_A (x)) = (0.5, 0.5, 0.5) ∀ x ∈ NX

E_N (A) ≤ E_N (B) if A is less fuzzy than B. i.e T_A (x) ≤ T_B (x) and F_A (x) ≥ F_B (x) together with |I_A (x) − I_{A
^c} (x) | ≥ |I_B (x) − I_{B
^c} (x) |, for T_B (x) ≤ F_B (x). or T_A (x) ≥ T_B (x), F_A (x) ≤ F_B (x) together with |I_A (x) − I_{A
^c} (x) | ≥ |I_B (x) − I_{B
^c} (x) |, for T_B (x) ≥ F_B (x).

E_N (A) = E_N (A^c).

Different authors have defined different formulas of entropy for IFS [1 , 26], SVNS [5] and IVNS [28]. In [5] Majumdar and Samanta gave the formula of entropy for SVNS A in X as follows: $\begin{matrix} E (A) & = & 1 - \frac{1}{n} \sum_{x_{i} \in X} (T_{A} (x_{i}) \\ + F_{A} (x_{i})) . | I_{A} (x_{i}) - I_{A^{c}} (x_{i}) | . \end{matrix}$ Now we establish a fundamental relation between similarity measure and entropy measure.

4.7 Theorem

Let S be the similarity measure for SVNS(X) and A ∈ SVNS (X), then S (A, A^c) = E (A).

Proof. We need to prove all the properties of entropy measure defined in 4.4

(P₁) When A is crisp set, i.e., A ∈ P (X), then from definition in 4.1,

S (A, A^c) =0, i.e., E (A) =0

(P₂) When A = (0.5, 0.5, 0.5), A^c = (0.5, 0.5, 0.5), i.e., A = A^c, i.e., S (A, A^c) =1, i.e., (P₂) is satisfied.

(P₃)

Case 1: For T_B (x) ≤ F_B (x) A is less fuzzy than B, when T_A (x) ≤ T_B (x) and F_A (x) ≥ F_B (x) together with |I_A (x) − I_{A
^c} (x) | ≥ |I_B (x) − I_{B
^c} (x) |; Now from relations of T_A, F_A, T_B and F_B defined above, we get T_A (x) ≤ T_B (x) ≤ F_B (x) ≤ F_A (x); this implies |F_B (x) − T_B (x) | ≤ |F_A (x) − T_A (x) |, i.e. $| T_{B} - T_{B}^{c} | \leq | T_{A} - T_{A}^{c} |$ and $| F_{B} - F_{B}^{c} | \leq | F_{A} - F_{A}^{c} |$ , as $T_{A}^{c} (x) = F_{A} (x)$ and $F_{A}^{c} (x) = T_{A} (x)$ and same holds for T_B (x) and F_B (x). Now these three relations $| T_{B} - T_{B}^{c} | \leq | T_{A} - T_{A}^{c} |$ , $| F_{B} - F_{B}^{c} | \leq | F_{A} - F_{A}^{c} |$ and |I_B (x) − I_{B
^c} (x) | ≤ |I_A (x) − I_{A
^c} (x) | confirm S (A, A^c) ≥ S (B, B^c).

Case 2: For T_B (x) ≥ F_B (x), A is less fuzzy than B,when T_A (x) ≥ T_B (x), F_A (x) ≤ F_B (x) together with |I_A (x) − I_{A
^c} (x) | ≥ |I_B (x) − I_{B
^c} (x) |. From above we get F_A (x) ≤ F_B (x) ≤ T_B (x) ≤ T_A (x); this implies |T_B (x) − F_B (x) | ≤ |T_A (x) − F_A (x) |, i.e. $| T_{B} - T_{B}^{c} | \leq | T_{A} - T_{A}^{c} |$ and $| F_{B} - F_{B}^{c} | \leq | F_{A} - F_{A}^{c} |$ . Also |I_B (x) − I_{B
^c} (x) | ≤ |I_A (x) − I_{A
^c} (x) | holds and results in S (A, A^c) ≥ S (B, B^c).

4.8 Formulation of entropy measure

From similarity measure functions as proposed in 4.3, we get two formulae of entropy measure: $\begin{matrix} E^{1} (A) & = & \frac{1}{n} \sum_{x_{i} \in X} [1 - {log}_{2} [1 + \frac{1}{2} | T_{A} (x_{i}) - F_{A} (x_{i}) | \\ + | I_{A} (x_{i}) - I_{A^{c}} (x_{i}) |]] . \end{matrix}$ (7) $\begin{matrix} E^{2} (A) & = & \frac{1}{n} \sum_{x_{i} \in X} cos [\frac{π}{2} \frac{1}{2} (| T_{A} (x_{i}) - F_{A} (x_{i}) | \\ + | I_{A} (x_{i}) - I_{A^{c}} (x_{i}) |)] . \end{matrix}$ (8) Formulae (7) and (8) clearly satisfy the axioms (i), (ii) and (iv).

To prove the axiom (iii), let A is less fuzzythan B.

Case 1. When T_B (x) ≤ F_B (x), T_A (x) ≤ T_B (x) and F_A (x) ≥ F_B (x) together with |I_B (x) − I_{B
^c} (x) | ≤ |I_A (x) − I_{A
^c} (x) |,

i.e., (T_A (x) − F_A (x)) ≤ (T_B (x) − F_B (x) ≤0 and |I_B (x) − I_{B
^c} (x) | ≤ |I_A (x) − I_{A
^c} (x) |,

i.e., |T_A (x) − F_A (x) | ≥ |T_B (x) − F_B (x) | and |I_A (x) − I_{A
^c} (x) | ≥ |I_B (x) − I_{B
^c} (x) |,

i.e., E¹ (A) ≤ E¹ (B) and also E² (A) ≤ E² (B).

Case 2. When T_B (x) ≥ F_B (x), T_A (x) ≥ T_B (x) and F_A (x) ≤ F_B (x) together with |I_A (x) − I_{A
^c} (x) | ≥ |I_A (x) − I_{A
^c} (x) |,

i.e., (T_A (x) − F_A (x)) ≥ (T_B (x) − F_B (x) ≥0 and |I_A (x) − I_{A
^c} (x) | ≥ |I_B (x) − I_{B
^c} (x) |,

i.e., |T_A (x) − F_A (x) | ≥ |T_B (x) − F_B (x) | and |I_A (x) − I_{A
^c} (x) | ≥ |I_B (x) − I_{B
^c} (x) |,

i.e., E¹ (A) ≤ E¹ (B) and also E² (A) ≤ E² (B).

4.8.1 Example

Let X ={ a, b, c, d } be the universe and A be a SVNS in X defined as: $\begin{matrix} A & = & {(a, 〈 0.5, 0.2, 0.9 〉), (b, 〈 0.8, 0.4, 0.2 〉), \\ (c, 〈 0.3, 0.8, 0.7 〉), (d, 〈 0.6, 0.3, 0.5 〉)} . \end{matrix}$

E (A) =0.48, E¹ (A) =0.493024, E² (A) =0.786984.

4.9 Analysis of entropy measures

Example 1. On a surface with cracks there is a chance that a coin while flipping, falls into a crack and gets stuck on its edge [31]. In this case if A is an event of getting head then A can be written as (0, 1, 0) (chance(Head), indeterminacy, chance(Tale)) in neutrosophic environment. Entropy measure defined in [5] gives the following result: E (A) =1. But E¹ (A) =0.415 and E² (A) =0.707. Considering the event some certainty is there as the position is neither head nor tail for sure. But immediately some factors like wind or severe rain that may turn the coin down to either head or tail or keep it in indeterminate position. Though it is certainly an indeterminacy case but natural factors may pour the uncertainty to it and it is not sure what the result will be among head, tail and indeterminacy. The event seems to be a certain one but uncertainty may arise due to the existence of some factors. So the event is a mix of certainty and uncertainty. So uncertainty measure should be neither 1 nor 0, rather it should be between 0 and 1. So the results from our entropy measures are more meaningful.

5 Algorithm for finding optimum spanning tree in neutrosophic environment

Let A ={ A₁, A₂, …, A_n } be a set of nodes of a network. e_ij (i, j = 1, 2, …, n) are the collection of SVNSs which express the weightage of the path A_iA_j. Let for each of the path A_iA_j there be m criteria c₁, c₂, …, c_m which are represented by weight of each edge, where each c_k are in neutrosophic form and $c_{k} = {T_{e_{ij}}^{k}, I_{e_{ij}}^{k}, F_{e_{ij}}^{k}}$ , (k = 1, 2, … m). In this case each e_ij (i, j = 1, 2, …, n) is represented by the following form of a SVNS: $e_{i j} = \{〈c_{k}, T_{e_{i j}}^{k}, I_{e_{i j}}^{k}, F_{e_{i j}}^{k}〉, c_{k} ∊ \{c_{1}, c_{2}, \dots, c_{m}\}\}$ . Assume that the weight of the criterion c_k (k = 1, 2, …, m), entered by the decision-maker, is w_k, w_k ∈ [0, 1] and $\sum_{k = 1}^{m} w_{k} = 1$ . We propose a method to derive the single valued neutrosophic optimum spanning tree through the algorithm given below:

Step 1: Calculate the ideal weight O^* among all the edges e_ij as per the criteria to be considered. Generally, the evaluation criteria can be categorized into two types: benefit criteria and cost criteria. Let K be a set of benefit criteria and M be a set of cost criteria. In the proposed decision-making method, an ideal edge can be identified by using a maximum operator for the benefit criteria and a minimum operator for the cost criteria to determine the best value of each criterion among all alternatives. So $O^{*} = {c_{1}^{*}, c_{2}^{*}, c_{3}^{*}, \dots, c_{m}^{*}}$ where for a benefit criterion ${c_{k}}^{*} = {max_{ij} T_{e_{ij}}^{k}, min_{ij} I_{e_{ij}}^{k}, min_{ij} F_{e_{ij}}^{k}}$ , while for a cost criterion, ${c_{k}}^{*} = {min_{ij} T_{e_{ij}}^{k}, max_{ij} I_{e_{ij}}^{k}, max_{ij} F_{e_{ij}}^{k}}$

Step 2: Establish the weighted similarity matrix S_w = (S_wij) _n×n = (S_w (e_ij, O^*)) _n×n using formulae (5) and (6) to measure the similarity between the weight of each edge and the ideal weight.

Step 3: Construct the optimum spanning tree of the single valued neutrosophic graph G(A,E) by Kruskal algorithm [27].

Arrange the edges of the weighted graph in decreasing order by similarity measure values from the similarity matrix S_w and set a subgraph S of G to be empty set.

At each step choose the edge e with greatest similarity measure value to be added to the subgraph S, where the end point of e is disconnected.

Repeat step 2 until S spans all the vertices.

6 Numerical example

A cable TV company is planning to lay cable to a new neighborhood (Fig. 1). It is constrained to bury the cable only along certain paths as shown in the graph. It wants to avoid some of those paths which might be more expensive, because they are longer, or require the cable to be buried deeper. It wants to use those paths using of which will cost less and signal will reach faster. A spanning tree for that graph would be a subset of those paths that has no cycles but still connects to every house. There might be several spanning trees possible. A optimum spanning tree would be one with the lowest total cost and least signal-flow time.

A decision maker evaluates the time and cost of each path in SVNSs which are given by matrix T and matrix C respectively. The weight vectors of time and cost are 0.45 and 0.55 respectively. We use the newly introduced approach to obtain the optimum spanning tree from the decision matrix for time T = (T_ij) _n×n = (T (A_i, A_j)) _n×n and decision matrix for cost C = (C_ij) _n×n = (C (A_i, A_j)) _n×n where T (A_i, A_j) and C (A_i, A_j) denote the time and cost for the path A_iA_j respectively.

Step 1: Time and cost are cost criteria and they are to be minimum. From matrix T and C we can obtain the following ideal weight: $O^{*} = {(0.2, 0.4, 0.5), (0.3, 0.5, 0.6)}$

Step 2: calculate the weighted similarity matrix S_w=(S_wij) _n×n = (S_w (e_ij, O^*)) _n×n. Here, $S_{w}^{1}$ and $S_{w}^{2}$ are the two similarity matrices which have been obtained by using equations (5) and (6) respectively.

$T = [\begin{matrix} Decision matrix for time (information given by DM) \\ - & (0.7, 0.2, 0.15) & (0.6, 0.2, 0.1) & (0.3, 0.2, 0.5) & (0.4, 0.3, 0.3) & (0.55, 0.2, 0.25) \\ (0.7, 0.2, 0.15) & - & (0.4, 0.3, 0.35) & (0.5, 0.1, 0.4) & (0.2, 0.3, 0.3) & (0.6, 0.3, 0.3) \\ (0.6, 0.2, 0.1) & (0.4, 0.3, 0.35) & - & (0.55, 0.2, 0.25) & (0.4, 0.2, 0.4) & (0.2, 0.4, 0.4) \\ (0.3, 0.2, 0.5) & (0.5, 0.1, 0.4) & (0.55, 0.2, 0.25) & - & (0.4, 0.2, 0.4) & (0.9, 0.2, 0) \\ (0.4, 0.3, 0.3) & (0.2, 0.3, 0.3) & (0.4, 0.2, 0.4) & (0.44, 0.2, 0.35) & - & (0.5, 0.15, 0.35) \\ (0.55, 0.2, 0.25) & (0.6, 0.3, 0.3) & (0.2, 0.4, 0.4) & (0.9, 0.2, 0) & (0.5, 0.15, 0.35) & - \end{matrix}]$ $C = [\begin{matrix} Decision matrix for cost (information given by DM) \\ - & (0.6, 0.3, 0.2) & (0.7, 0.2, 0.1) & (0.6, 0.3, 0.1) & (0.8, 0.1, 0.1) & (0.57, 0.2, 0.15) \\ (0.6, 0.3, 0.2) & - & (0.8, 0.1, 0.1) & (0.7, 0.1, 0.1) & (0.3, 0.2, 0.6) & (0.5, 0.4, 0.2) \\ (0.7, 0.2, 0.1) & (0.8, 0.1, 0.1) & - & (0.7, 0.1, 0.15) & (0.8, 0.2, 0.1) & (0.4, 0.5, 0.1) \\ (0.6, 0.3, 0.1) & (0.7, 0.1, 0.1) & (0.7, 0.1, 0.15) & - & (0.6, 0.2, 0.2) & (0.8, 0.2, 0.1) \\ (0.8, 0.1, 0.1) & (0.3, 0.2, 0.6) & (0.8, 0.2, 0.1) & (0.6, 0.2, 0.2) & - & (0.75, 0.1, 0.2) \\ (0.57, 0.2, 0.15) & (0.5, 0.4, 0.2) & (0.4, 0.5, 0.1) & (0.8, 0.2, 0.1) & (0.75, 0.1, 0.2) & - \end{matrix}]$

$\begin{matrix} S_{w}^{1} & = & [\begin{matrix} 1 & 0.630684 & 0.576982 & 0.715352 & 0.614436 & 0.628848 \\ 0.630684 & 1 & 0.621531 & 0.574103 & 0.8227225 & 0.736966 \\ 0.576982 & 0.621531 & 1 & 0.581094 & 0.628318 & 0.873071 \\ 0.715352 & 0.574103 & 0.581094 & 1 & 0.659693 & 0.514573 \\ 0.614436 & 0.827225 & 0.628318 & 0.659693 & 1 & 0.587619 \\ 0.628848 & 0.736966 & 0.873071 & 0.514573 & 0.587619 & 1 \end{matrix}] \\ S_{w}^{2} & = & [\begin{matrix} 1 & 0.896447 & 0.858401 & 0.931475 & 0.85593 & 0.893599 \\ 0.896447 & 1 & 0.857906 & 0.84782 & 0.979284 & 0.951106 \\ 0.858401 & 0.857906 & 1 & 0.854415 & 0.878184 & 0.984472 \\ 0.931475 & 0.84782 & 0.854415 & 1 & 0.908482 & 0.809204 \\ 0.85593 & 0.979284 & 0.878184 & 0.908482 & 1 & 0.857713 \\ 0.893599 & 0.951106 & 0.984472 & 0.809204 & 0.857713 & 1 \end{matrix}] \end{matrix}$

Step 3. Establish the optimum spanning tree of the single-valued neutrosophic graph G(A,E) by Kruskal algorithm [27].

Sort the edges of G in decreasing order by weights from matrix $S_{w}^{1}$ .

$S_{w}^{1} 36 > S_{w}^{1} 52 > S_{w}^{1} 62 > S_{w}^{1} 41 > S_{w}^{1} 54 > S_{w}^{1} 21 > S_{w}^{1} 61 > S_{w}^{1} 53 > S_{w}^{1} 32 > S_{w}^{1} 51 > S_{w}^{1} 65 > S_{w}^{1} 43 > S_{w}^{1} 31 > S_{w}^{1} 42 > S_{w}^{1} 64$ .

Sort the edges of G in decreasing order by weights from matrix $S_{w}^{2}$ .

$S_{w}^{2} 36 > S_{w}^{2} 52 > S_{w}^{2} 62 > S_{w}^{2} 41 > S_{w}^{2} 54 > S_{w}^{2} 61 > S_{w}^{2} 21 > S_{w}^{2} 53 > S_{w}^{2} 31 > S_{w}^{2} 32 > S_{w}^{2} 65 > S_{w}^{2} 51 > S_{w}^{2} 43 > S_{w}^{2} 42 > S_{w}^{2} 64 .$

Keep an empty subgraph S of G and add the edge e with the greatest weight to S, where the end point of e is disconnected; thus we choose e₃₆ between A₃ and A₆ in both cases.

Repeat process (2) until the subgraph S spans six nodes in both cases. Thus, the same optimum spanning tree of the single-valued neutrosophic graph G(A,E) is obtained in both the cases, as shown in Fig. 2.

7 Conclusion

This paper proposes a solution approach of the optimum spanning tree problems considering the inconsistency, incompleteness and indeterminacy of the information. The approach shows how to fulfill a network problem with multiple criteria optimally to get the optimum spanning tree in neutrosophic environment. Additionally, this paper proposes a couple of similarity measure methods which can be used to compare between NSs. Also we deduce a couple of entropy measure approaches which give meaningful result as already discussed in the paper while determining the uncertainty of events.

Acknowledgments

The authors are grateful to National Institute of Durgapur for financial support.

References

Szmidt

, and Kacprzyk

, Entropy for intuitionistic fuzzy sets, Fuzzy Sets and Systems118 (2001), 467–477.

B.Y.

, and Chao

K.-M.

, Spanning Trees and Optimization Problems, Chapman and Hall/CRC PressUSA, 2004.

, Single-valued neutrosophic minimum spanning tree and its clustering method, Journal of Intelligent Systems23 (2014), 311–324.

, Clustering methods using distance-based similarity measures of single-valued neutrosophic sets, Journal of Intelligent Systems23 (2014), 379–389.

Majumdar

, and Samanta

S.K.

, On similarity and entropy of neutrosophic sets, Journal of Intelligent and Fuzzy Systems26 (2014), 1245–1252.

Zadeh

, Fuzzy entropy and conditioning, Information Sciences40 (1986), 165–174.

Hung

W.-L.

, and Yang

M.-S.

, Fuzzy entropy on intuitionistic fuzzy sets, International Journal of Intelligent Systems21 (2006), 443–451.

Broumi

, and Smarandache

, On similarity and entropy of neutrosophic sets, Neutrosophic Sets and Systems1 (2013), 54–62.

, Vector similarity measures of simplified neutrosophic sets and their application in multicriteria decision making, International Journal of Fuzzy Systems16 (2014), 204–215.

10.

Mukherjee

, and Sarkar

, Several similarity measures of neutrosophic soft sets and its application in real life problems, Annals of Pure and Applied Mathematics7 (2014), 1–6.

11.

Broumi

, and Smarandache

, Cosine similarity measure of interval valued neutrosophic sets, Neutrosophic Sets and Systems5 (2014), 15–20.

12.

Vijayalakshmir

Dr. , and Kalaivani

, Minimum cost spanning tree using matrix algorithm, International Journal of Scientific and Research Publications4 (2014), 3319–3323.

13.

Zhang

, Zhou

, and Zhong

, Models for inverse minimum spanning tree problem with fuzzy edge weights, Journal of Intelligent and Fuzzy Systems27 (2014), 2691–2702.

14.

, A multicriteria decision-making method using aggregation operators for simplified neutrosophic sets, Journal of Intelligent and Fuzzy Systems26 (2014), 2459–2466.

15.

Wang

, Smarandache

, Zhang

Y.Q.

, and Sunderraman

, Single valued neutrosophic sets, in Multispace and Multistructure4 (2010), 410–413.

16.

Prim

R.C.

, Shortest connection networks and some generalizations, Bell System Technical Journal36 (1957), 389–1401.

17.

Zadeh

L.A.

, Fuzzy sets, Information and Control8 (1965), 338–353.

18.

Atanassov

, Intuitionistic fuzzy sets, Fuzzy Sets and Systems (1986), 87–96.

19.

Smarandache

, Neutrosophy/Neutrosophic Probability, Set, and Logic, In: Amer Res PressRehoboth, USA, 1998, p.105.

20.

Zhang-Peng

T.J.

, Wang , Wang

J.-Q.

, and Zhang

H.-Y.

, Simplified neutrosophic linguistic multicriteria group decision-making approach to product development, Group Decision and Negotiation4 (2016), 1–31.

21.

X.-H.

, Wang

J.-Q.

, Peng

J.-J.

, and Chen

X.-H.

, Cross-entropy and prioritized aggregation operator with simplified neutrosophic sets and their application in multi-criteria decision-making problems, International Journal of Fuzzy System (2016), 1–13.

22.

Y.-X.

, Wang

J.-Q.

, Wang

, and Wu

, An interval neutrosophic linguistic multi-criteria group decision-making method and its application in selecting medical treatment options, Neural Computer & Application, 1–21.

23.

Tian

Z.-P.

, Zhang

H.-Y.

, Wang

J.-Q.

, and Chen

X.-H.

, Multi-criteria decisionmaking method based on a cross-entropy with interval neutrosophic sets, International Journal of Systems Science (2015) doi: 10.1080/00207721.2015.1102359

24.

Broumi

, and Smarandache

, Several similarity measures of neutrosophic sets, Neutrosophic Sets and Systems1 (2013), 54–62.

25.

, Deng

, Li

, and Zeng

, The relationship between similarity measure and entropy of intuitionistic fuzzy sets, Information Sciences188 (2012), 314–321.

26.

, and Li

, The entropy and similarity measure of interval valued intuitionistic fuzzy sets and their relationship, International Journal of Fuzzy Systems15(3) (2013).

27.

Kruskal

J.B.

, On the shortest spanning subtree of a graph and the traveling salesman problem, Proc Am Math Soc7 (1956), 48–50.

28.

Aydogdu

, On entropy and similarity measure of interval valued neutrosophic sets, Neutrosophic Sets and Systems9 (2015), 47–49.

29.

Abhilasha

, Minimum cost spanning tree using prims algorithm, International Journal of Advance Research in Computer Science and Management Studies1(1) (2013).

30.

Gabow

H.N.

, Galil

, Spencer

, and Tarjan

R.E.

, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Combinatorica6(2) (1986), 109–122.

31.

Smarandache

, Introduction to Neutrosophic Measure, Neutrosophic Integral, and Neutrosophic Probability, Sitech, 2013.

32.

Saravanan

, and Madheswaran

, A hybrid optimized weighted minimum spanning tree for the shortest intrapath selection in wireless sensor network, Mathematical Problems in Engineering2014 (2014), Article ID 713427.