Second Minimum Weight Spanning Tree of A Network with Triangular Intuitionistic Fuzzy Number As Edge Weight

Second Minimum Weight Spanning Tree of A Network with Triangular Intuitionistic Fuzzy Number As Edge Weight

B. Rajesh*

Department of Mathematics University College of Engineering Pattukkottai, Tamil Nadu, India.

1. Ismail Mohideen

   PG and Research Department of Mathematics,

   Jamal Mohamed College, Tiruchirappalli, Tamil Nadu, India.

   1. Senthilkumar

      Department of Computer Science and Engineering,

      University College of Engineering Pattukkottai, Tamil Nadu, India.

      Abstract Determination of minimum weight spanning tree of a network is very significant in the field of operations research. The next option for minimum weight spanning tree is second minimum weight spanning tree. In this paper a new algorithm to find the second minimum weight spanning tree of a network has been suggested where edge weights are considered as triangular intuitionistic fuzzy number.

      Keywords Network, Spanning tree, Minimum Weight Spanning Tree, Triangular intuitionistic fuzzy number.

      1. INTRODUCTION

         Computing minimum weight spanning tree of a network is one of the most fundamental algorithmic problems in graph theory. In 1957, Prim [10] proposed the method for determining the minimal spanning tree of a network. The determination of the optimal path tree was efficiently determined by Bellman [2], Ford [5] and Moore [9]. Hassan

         [6] presents a new algorithm based on the distance matrix to solve the least-cost minimum spanning tree problem in 2012. In real world applications, it is not always possible to use the Minimum weight spanning tree. In such situations, second MWST is of equal importance to MWST. In crisp environment, it is assumed that the decision maker is certain about the parameters like distance, cost, time etc. But in real situations there always exists uncertainty about the parameters. In such cases, parameters can be represented by triangular intuitionistic fuzzy numbers. Second Minimum weight spanning tree of a network with crisp values as edge weight was discussed by Ismail Mohideen and Rajesh [7].

         1. A is normal, (i.e.) there exists an element x0 such that

            A (x0) = 1

         2. A is fuzzy convex, (i.e.)

            A [x1 + (1 )x2]

            A (x1)A (x2), x1, x2 R, [0,1]

         3. A is upper continuous and

         4. SuppA is bounded, where Supp A = {x R:A (x) > 0}.

         1. Fuzzy tree

            Fuzzy tree is a tree in which the weight of the edges constituting the tree is considered as fuzzy number.

         2. Weight of a fuzzy tree

            Weight of a fuzzy tree is a fuzzy number with each of its component representing the sum of the corresponding components of the fuzzy number of the edges constituting the tree.

         3. Intuitionistic fuzzy number

         Let A = {(x, A (x), A (x)), xX} be an intuitionistic fuzzy set, then the pair (A (x), A (x) is refered here as an intuitionistic fuzzy number.

         2.3. Triangular intuitionistic fuzzy number

         A triangular intuitionistic fuzzy number A in R, written as (a , b , c ; a , b , c ) where a a b

         Applications of Minimum Weight Spanning Tree (MWST)

         1 1 1 1 1 1

         1 1 1

         were found in Foulds [4]. The concept of intuitionistic fuzzy

         c1 c1 has the membership function

         sets was proposed by Atanassov [1] in 1986. In 2004, Mitchell [8], proposed a method to solve intuitionistic fuzzy numbers. In 2010, Deng Feng Li et al. [3] proposed a

         x a1

         b1 a1

         x c1

         a1 x b1

         ranking method for triangular intuitionistic fuzzy number.

      2. PRELIMINARIES

         2.1 Fuzzy numbers

         A fuzzy subset of the real line R with membership function is called a fuzzy number if

         A (x) = b1 c1 b1 x c1

         0 othererwise

         {

         and non-membership function of A is given by

         b1 x

         a x b

         Step 7:

         b1 a1 1 1

         x b

         Minimum of (( )), = 1 1, is found and its corresponding is the second MWST.

         A (x) =

         1

         c1 b1

         b1 x c1

         1 othererwise.

         {

      3. ALGORITHM

         Following is the algorithm to find second minimum weight spanning tree of a network, where triangular intuitionistic fuzzy number is considered as weight of the edges.

         Step 1: Initialization

         Let k = 0. Let be the set of all edges and n be the number of nodes of a network where n 3.

         Let be the weight of the edge (, ). Let be the MWST of a network .

         For all (, ) , where ,

         let = (d1, 2, 3; 1, 2, 3)

         Step 2: Value of the membership function of the triangular intuitionistic fuzzy number

         If = (d1, 2, 3; 1, 2, 3) and

         = (d1, 2, 3; 1, 2, 3) be two edge weight of fuzzy network with triangular intuitionistic fuzzy number, then the value of the membership function of the triangular intuitionistic fuzzy number can be calculated as follows

         If ( ) >() then > If ( ) <() then < If ( ) = () then =

         Where () = (d1, 2, 3; 1, 2, 3)

         = 1/6 (d1 + 4 2+ 3)

         Step 3:

         Using step 2, select an edge (, ) from such that () is minimum. Tie can be broken arbitrarily. Remove this edge (, ) from and include it as a part of unless it creates a

         Step 8:

         Path = < > Path

         Let =

         Go to step 7.

         Step 9:

         Let = + 1

         If = 0, then

         {Path = < s > Path

         If , go to step 6 Else Terminate}

         Else go to step 7.

      4. COMPUTATIONAL COMPLEXITY

         In 2012, Zhan Ning and Wu Longshu [11] discussed the computational complexity of finding a spanning tree in a network with minimum total expenses. In the proposed algorithm of section III, from step1 to step3, the computational complexity for determining the MWST of a given network is (2) . According to step 4 and step 5, MWST is found for (n-1) networks. Therefore the computational complexity involved from step1 to step 6 is

         (3). Therefore the computational complexity of the proposed algorithm in Section III is (3).

      5. NUMERICAL ILLUSTRATION

         Consider a simple undirected network given in figure 5.1 with six vertices and nine edges. Here triangular intuitionistic fuzzy numbers are considered as weight of the edges and is given in table 5.1.

         .

         cycle with the edges already in . 2 4

         Step 4:

         If has 1 edges, then store its weight in ( ) and go

         to step 5. 1 6

         Else go to step 3.

         Step 5:

         If = 1 then go to step 7. Else go to step 6

         Step 6:

         Let = + 1

         Arbitrarily select an edge (, ) from.

         = (, ) and = 0 (, ). Go to step 3.

         3 5

         Fig 5.1 Network 0

         Edge	Weight of the edge
         (1, 2)	(40, 45, 50; 35, 45, 55)
         (1, 3)	(50, 52, 56; 48, 52, 58)
         (2, 3)	(5, 10, 15; 4, 10, 17)
         (2, 4)	(15, 20, 24; 13, 20, 30)
         (2, 5)	(60, 64, 70; 58, 64, 75)
         (3, 5)	(12, 18, 20; 10, 18, 25)
         (4, 5)	(10, 14, 16; 8, 14, 20)
         (4, 6)	(30, 34, 40; 25, 34, 45)
         (5, 6)	(22,28, 30; 20, 28, 34)

         Edge	Weight of the edge
         (1, 2)	(40, 45, 50; 35, 45, 55)
         (1, 3)	(50, 52, 56; 48, 52, 58)
         (2, 3)	(5, 10, 15; 4, 10, 17)
         (2, 4)	(15, 20, 24; 13, 20, 30)
         (2, 5)	(60, 64, 70; 58, 64, 75)
         (3, 5)	(12, 18, 20; 10, 18, 25)
         (4, 5)	(10, 14, 16; 8, 14, 20)
         (4, 6)	(30, 34, 40; 25, 34, 45)
         (5, 6)	(22,28, 30; 20, 28, 34)

      6. CONCLUSION

In this paper a new algorithm is proposed to find the second minimum weight spanning tree of a given network with triangular intuitionistic fuzzy numbers as edge weights. Computational complexity of the proposed algorithm in section III is O(3). An example to illustrate the method is provided.

REFERENCES

Table 5.1 Edge weights of the Network 0 corresponding to fig 5.1

Weight of MWST of the given network is

(89, 115, 131; 77, 115, 151) and its edges are

(2,3), (4,5), (3,5), (5,6) (1,2)

For constructing network 1, the edge (1, 2) is removed from the network 0.

Edges of MWST 1 corresponding to Network 1 are (2,3), (4,5), (3,5), (5,6)(1,3). Weight of 1 is (1) = (99, 122, 137; 90, 122, 154)

For constructing network 2, the edge (2, 3) is removed from the network 0.

Edges of MWST 2 corresponding to Network 2 are (4,5), (3,5), (2,4), (5,6)(1,2). Weight of 2 is (2) = (99, 125, 140; 86, 125, 164)

For constructing network 3, the edge (3, 5) is removed from the network 0.

Edges of MWST 3 corresponding to network 3 are are (2,3), (4,5), (2,4), (5,6)(1,2). Weight of 3 is

(3) = (92, 117, 135; 80, 117, 156)

For constructing network 4, the edge (4, 5) is removed from the network 0.

Edges of MWST 4 corresponding to Network 4 are (2,3),(3,5), (2,4), (5,6)(1,2). Weight of 4 is (4) = (94, 121, 139; 82, 121, 161)

For constructing network 5, the edge (5, 6) is removed from the network 0.

Edges of MWST 5 corresponding to Network 5 are

(2,3), (4,5), (3,5), (4,6)(1,2).

Weight of 5 is (5) = (97, 121, 141; 80, 121, 162)

Hence the second MWST is determined from

1, 2, 3, 4 5. Min of

{( (1)), ((2)), ((3), ((4)), ((5)) }

= ((3)).

Therefore 3 is the second MWST of the given network. Weight of second MWST of the given network is (92, 117, 135; 80, 117, 156) and its edges are

(2,3), (4,5), (2,4), (5,6) (1,2).

1. Atanassov, K.T., Intuitionistic fuzzy sets, Fuzzy sets and system, Vol. 20, no.1, 1986, 87-96.

2. Bellman, R.E., On a routing problem, Quarterly Journal of Applied Mathematics, Vol.16, 1958, 87-90.

3. Deng Feng Li., Jiang Xia Nan. and Mao Jun Zhang., A Ranking Method of Triangular Intuitionistic Fuzzy Numbers and Applications to Decision Making, International Journal of Computational Intelligence Systems, Vol.3, No.5, Oct 2010, 522-530.

4. Foulds, 1992, Graph Theory Applications, Springer- Verlag New York, Inc, 234-236.

5. Ford, L.R., Network flow theory, The Rand corporation report, Santa monica, California, 1956, p-923.

6. Hassan, M.R., An efficient method to solve least cost minimum spanning tree (LC-MST) problem, Journal of King Saud University- Computer and Information Sciences, Vol. 24, Issue 2, July 2012, 101- 105.

7. Ismail Mohideen S and Rajesh B, Second minimum weight spanning tree in a network, Elixir Appl. Math., ISSN: 2229-712X, 40 (2011) 5103-5104.

8. Mitchell, H.B., Ranking intuitionistic fuzzy numbers, International Journal of Uncertainty, Fuzziness and Knowledge Based Systems 12, 2004, 377- 386.

9. Moore. Z.E., The shortest path through a maze, Proceedings of International symposium on theory of switching, Part II, 1957, 258- 292.

10. Prim, R., Shortest connection networks and some generalization, Bell syst, Tech Journal, 36, 1957, 1389-1401.

11. Zhan Ning., Wu Longshu., The Complexity and Algorithm for Minimum Expense Spanning Trees, Procedia Engineering, Vol. 29, 2012, 118-122.