Mann-Whitney’s Minimal Spanning Tree Algorithm of Critical Path Network Analysis Using Fermatean Pentagonal Fuzzy Numbers

C. Dilly Rani^* and R. Nagarajan
^*Correspondence: C. Dilly Rani, Department of Mathematic, J.J College of Engineering and Technology (Sowadambikaa Group of Institution) Trichirappali, Tamil nadu, India, Email:

Keywords

Fuzzy set • Fuzzy number • Validity • Defuzzification • Fermeatean fuzzy soft set • Minimal spanning tree • Pentagonal matrix • Connected graph • Algorithm • Score function • Accuracy function

Introduction

A minimum spanning tree is a spanning tree that has the lowest possible weight. The MST is a spanning tree T of graph G which has the minimum cost among all the spanning tree of graph G. The MST problem is a fundamental and well known combinatorial optimization problem in the area of graph theory. It is widely applied in various fields of science and engineering, e.g., road network application, transportation, routing in communication channels and scheduling problems. In real life problems, edge costs are used to represent the parameter costs, capacities, demands, time, etc. Although in classical graph theory, real numbers are used in a MST problem to express the arc lengths of a connected weighted graph. We generally consider the classical MST problem as network optimization problem. In the classical MST problem, we assume the arc lengths (time, cost, distance, nature of connectivity between nodes, etc.) is certain. However, in real world problems, the information about any MST problems is generally not exact or precise due to several reasons such as incomplete data or insufficient data, less evidence, imperfect statistical [1]. For e.g., in a weighted connected graph, the arc length may describe the traversing time between two nodes. This traveling time depends on traffic jam, accident, weather etc., each of the criteria differ from day to day. Therefore, it becomes difficult for the DM to estimate exactly the edge cost. Several papers have been done on the uncertainty MST. The work by Itoh and Ishii is first work on this uncertainty domain and worked a MST problem with fuzzy costs as a chance constrained programming based on the necessity measure. Following that, some methods based on the ranking index for arc weights of FMST were proposed by Chang and Lee. Almeida et al. described the fuzzy MST problem with uncertainty costs and introduced an algorithmic method to solve this FMST. Zadeh introduce the idea of fuzzy set. They introduced a genetic algorithm founded on uncertainly logic and probability theory to compute the FMST with fuzzy weights. In, they described possibility theory to describe the minimum of edge of the fuzzy graph and to find a spanning tree where the fuzzy arc weights are in fuzzy intervals. Liu introduced the credibility theory including pessimistic value, credibility measure and expected value as fuzzy ranking methods. Senapati. T, R.R.Yager, introduced the concept of fermeatean fuzzy set in 2019(a). Soft set theory is discussed, based on the credibility theory, Gao and Lu studied the fuzzy quadratic minimum spanning tree problem and formulated it as expected value model, chance-constrained programming and dependent chance programming according to different decision criteria. In this paper a new algorithm for searching defuzzification approach for validity of minimal spanning tree in a network having pentagonal fermeatean fuzzy soft edge length is presented. The proposed algorithm is based on a matrix approach to design undirected fermeatean fuzzy soft weighted connected graph. Also, we provide a numerical example to check the validity of the proposed algorithm [2].

Literature Review

Preliminaries

In this section, the concept of fermeatean fuzzy soft set and pentagonal fermeatean fuzzy soft numbers is presented to deal with uncertainty data, which can be defined as follows.

Definition: A uncertainty set in characterized by its membership function taking value from the domain space or universe of discourse mapped into the interval (0,1). A uncertainty set D in the universal set X is defined us D={(x,α_D(x)/x∈X}. Here α_D:D→(0,1) is the grade of membership function and α_D(x) is the grade value of x ∈ X in the fuzzy set D [3].

Example: Let D={a, b, c, d}be a set on X then α_D(x) is defined as clearly ‘D’ is an uncertainty set on X.

Definition: Let X be an initial universe. P(X) be the power set of X, E be the set of all parameters and D ⊆ E. A soft set (α_D(x), E) on the universe X is defined by the set of ordered pairs (α_D(x),E)={e, (α_D(e))|e ∈ E, α_D(e) ∈ p(α)} where α_D:E→P(X) such that α_D(e)=Φ if e ∈ D. Here α_D is called an approximate of the soft set [4].

Example: Let X={x₁, x₂, x₃, x₄} be a set of four shirts and E={white (e₁), red (e₂), blue (e₃)} be a set of parameters. If D={e₁, e₂} ⊆ E.

Let α_D(e₁)={x₁, x₂, x₃, x₄} and α_D(e₂)={x₁, x₂, x₃}. Then we write the soft (α_D,E)={(e₁, x₁, x₂, x₃, x₄), (e₂, x₁, x₂, x₃, x₄)} over X which describe the “colour of the shirts” which Mr.’Z’ is going to buy.

Definition: An uncertainty set ‘D’ is called normal if there exist an element x∈ X whose membership value is 1. (i.e.) α_D(x)=1.

Definition: A fuzzy number ‘D’ is a subset of real line R, with membership function α_D satisfying the following properties:

• α_D (x) is piecewise continuous in its domain.
• ‘D’ is normal (i.e.) α_D(x)=1 for all x ∈X
• ‘D’ is convex (i.e.) C(λx₁+(1-λ)x₂)=min{α_D(x₁), α_D(x₂)},for all x₁, x₂ ∈ X.

Due to wide application of the fuzzy number, two types of fuzzy numbers, namely:

• Triangular fuzzy number.
• Trapezoidal fuzzy number are introduced in the field of fuzzy algebra.

Due to error in measuring techniques, instrumental faultiness etc., some data in our observation cannot impress or accurently defined.

Let us consider that we measure whether temperatures and humidity. Simultaneously the temperature is approximately 35ºC with normal humidity [5].

The variation in temperature also affects the percentage of humidity. This is phenonmenous happens in general. This concept of variation leads to a new type of fuzzy number called the “Pentagonal Fuzzy Number” (PFN).

Generally, a pentagonal is a S-tuple subset of a real number ‘R’ having five parameters.

A pentagonal fuzzy number ‘D’ is denoted as D={a₁, a₂, a₃, a₄, a₅} where a₃ is the middle point and (a₁,a₂) and (a₄,a₅) are the left and right side points of a₃ respectively.

Now we define the mathematical construction of a pentagonal fuzzy number.

Definition: A fuzzy number D=(a₁, a₂, a₃, a₄, a₅) is called Pentagonal Fuzzy Number (PFN) where the membership has the form (Figure 1).

Remarks

• When w₁=w₂=D, then the PFN is reduced to TFN.
• When w₁=w₂=1, then the PFN become a to Trapezodial fuzzy number.

Definition: Fermeatean fuzzy soft set: Let ‘X’ be a universe of discourse A. Fermeatean fuzzy soft set “F” in X is an object having the form F={⟨x, m_F(x), n_F(x)⟩/x∈ X}, Where m_F(x): X→ (0,1) and n_F(x): X → (0,1), including the condition 0 ≤ (m_F(x))³ + (n_F(x))³ ≤ 1, for all x ∈ X. The numbers m_F(x) signifies the level (degree) of membership and n_F(x)indicate the nonmembership of the element ‘x’ in the set F. All through this paper, we will indicate a fermeatean fuzzy soft set is FFSS [6]. For any FFSS ‘F’ and x∈X, π_F(x)=³√1−(m_F(x))²-(n_F(X))² is to find out as the degree of indeterminacy of ‘x’ to F. For convenience, senapathi and yager called (m_F(x), n_F(x)) a Fermatean Fuzzy Soft Number (FFSN) denoted by F=(m_F, n_F) (Figure 2).

We will explain the Membership Grades (MG’s) related Fermeatean uncertainty collections as Fermeatean membership grades.

Theorem: The collections of FMG’s is higher than the set of Pythagorean Membership Grades (PMG’s) and Bi–Fuzzy Membership Grades (BMG’s) [7-10].

Proof: This improvement can be evidently approved in the following Figure 3.

Discussion

Operation on pentagonal fuzzy soft number

In this section, we study some arithmetic operations of pentagonal fermeatean fuzzy soft numbers. Let A={a₁, a₂, a₃, a₄, a₅} and B={b₁, b₂, b₃, b₄, b₅} be two pentagonal fermeatean fuzzy soft set. Then

• Addition: A+B={a₁+b₁,a₂+b₂, a₃+b₃,a₄+b₄,a₅+b₅}
• Subtraction: A-B={a₁-b₁, a₂-b₂, a₃-b₃, a₄-b₄, a₅-b₅}
• Scalar multiplication: αA={αa₁, αa₂, αa₃, αa₄, αa₅}
• Multiplication: AB={a₁b₁, a₂b₂, a₃b₃, a₄b₄, a₅b₅}
• Inverse: A-1={1/a₅, 1/a₄, 1/a₃, 1/a₂, 1/a₁}
• Division: A/B={a₁/b₅, a₂/b₄, a₃/b₃, a₄/b₂, a₅/b₁}

Mann-Whitney’s algorithm of fermeatean pentagonal fuzzy soft numbers

Input: The weight matrix D=(dij)_mxn for which is constructed for indirect weight fermeatean soft graph.

Step-1: Input pentagonal fermeatean fuzzy soft adjacency matrix.

Step-2: Construct pentagonal fermeatean fuzzy soft number matrix inti a score matrix (sij) mxn by the using the score fun.

Step-3: Repeat step-4,step-5 up to time that all non-zero elements are marked 0 in alternative saying all (n-1) entries matrix of S are either marked or a set to zero.

Step-4: There are two ways to find out the weight matrix D that one is column-wise and another one is row-wise in order to determine the unmarked minimum entries S_ij beside it determines the weight of the corresponding edge e_ij in D.

Step-5: Set S_ij=0 else mark S_ij provided the corresponding edge e_ij of selected S_ij, generate cycle with the proceeding marked entries of the score matrix S.

Step-6: Construct the graph T including the only marked entries from the score matrix S which shall be desired minimum cost spanning tree of G.

Step-7: Stop the iterations.

Defintion: Let B be a pentagonal fermeatean fuzzy soft variable denoted as B={(a₁, a₂, a₃, a₄, a₅),(b₁, b₂, b₃, b₄, b₅),(c₁, c₂, c₃, c₄, c₅)}.

Hence the score function and the accuracy function of pentagonal fermeatean fuzzy soft variables are denoted as below;

Score of (B) or S(B)=1/15 (10+(a₁+a₂+a₃+a₄+a₅)− (b₁+b₂+b₃+b₄+b₅)–(c₁+c₂+c₃+c₄+c₅)) ......................................(1)

Accuracy of (B) or H(B)=1/5 ((a₁+a₂+a₃+a₄+a₅)−(c₁+c₂+c₃+c₄+c₅)) ........................................................................(2)

Definition: Let B₁ and B₂ be two pentagonal fermeatean fuzzy soft numbers variable defined on the set of real numbers. Hence the ranking method is defined as follows [11].

• S (B₁)<S(B₂), then B₁>B₂, i.e. B₁ is superior to B₂.
• S (B₁)=S(B₂), then H(B₁)>H(B₂), then B₁ is superior to B₂.

Numerical example: In this section, a numerical example of fermeatean pentagonal fuzzy soft numbers minimal spanning tree is used to demonstrate of the proposed algorithm. Steps involved in the construction of the minimum cost spanning tree are described as follows [12,13].

Step-1: The pentagonal fuzzy soft number adjacency matrix corresponding to the given Figure 4 (Tables 1 and 2).

Table 1. Pentagonal Fuzzy soft number edge weights.

Table 2. The values of edges weights.

Step-2: The score matrix (S_ij) is obtained by using score function (by equation (1)) (Table 3).

Table 3. Score matrix.

From the above score matrix, we observe that the minimum value 0.480 is selected and the corresponding edge e₂₄ (V₂ → V₄) is marked with box (Figure 5 and Table 4). The reduced undirected pentagonal fermeatean fuzzy soft graph is the next non-zero minimum entries in step-2 is 0.513 and the corresponding edges e₁₃ (V₁ → V₃) the minimum value is (Figure 6).

Table 4. The reduced undirected pentagonal fermeatean fuzzy edge weights.

Repeat the process until the iteration exists in the given Table 5 [14]. The next non-zero minimum entries in the given score matrix (step-2) is 0.520 and the corresponding edge e₃₅ (V₃ → V₅) (Table 5).

Table 5. Repeat the process until the iteration exists.

Hence the pentagonal fermeatean fuzzy soft graph for the corresponding minimum entries is an illustration of the marked edge. Based on the procedure of matrix approach applied to undirected pentagonal fuzzy soft graph (Figures 7 and 8).

The final path of minimum cost of spanning tree is:

Hence the length of the minimal spanning tree of pentagonal fermeatean fuzzy soft graph is V₁→ V₃ →V₅ → V₆ → V₇ and whose edge values represented as 0.513 → 0.546 →0.520→0.553 (Table 6).

Table 6. The accuracy function of the length of the minimal spanning tree.

Therefore the validity of the minimal spanning tree occurs in V₆ → V₇. Hence the maximum accuracy function occurs in edge is e₆₇ and value is 0.08.

Conclusion

The main purpose of this paper is to propose a fermeatean fuzzy soft version of mann whitney’s algorithm based in the matrix approach for reaching the cost minimum spanning tree in a network having pentagonal fermeatean fuzzy soft edge weighted validity of with accuracy function.

References

1. Dey, Arindam, and Anita Pal. "Prim’s algorithm for solving minimum spanning tree problem in fuzzy environment." Ann Fuzzy Math Inform 12 (2016): 419-430.
2. Dey, Arindam, Said Broumi, Le Hoang Son, and Assia Bakali, et al. "A new algorithm for finding minimum spanning trees with undirected neutrosophic graphs." Granul Comput 4 (2019): 63-69.

   [Google Scholar]

3. de Almeida, TA, Yamakami, A, and Takahashi, MT. "An evolutionary approach to solve minimum spanning tree problem with fuzzy parameters." In International Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce (CIMCA-IAWTIC'06), Vienna, Austria: IEEE, (2005).

   [Google Scholar]

4. Chang, PT, and ES Lee. "Fuzzy decision networks and deconvolution." Comput Math with Appl 37 (1999): 53-63.

   [Crossref] [Google Scholar]

5. Gao, Jinwu, and Mei Lu. "Fuzzy quadratic minimum spanning tree problem." Appl Math Comput 164 (2005): 773-788.

   [Crossref] [Google Scholar] [PubMed]

6. Itoh, Takeshi, and Hiroaki Ishii. "An approach based on necessity measure to the fuzzy spanning tree problems." J Oper Res Soc Japan 39 (1996): 255-256.

   [Google Scholar]

7. Janiak, Adam, and Adam Kasperski. "The minimum spanning tree problem with fuzzy costs." Fuzzy Optim Decis Making 7 (2008): 105-118.

   [Crossref] [Google Scholar]

8. Liu, Baoding, and Baoding Liu. "Mathematical programming." Theory and Practice of Uncertain Programming, Germany: Physica, Heidelberg, (2002).

   [Crossref] [Google Scholar]

9. Liu, Baoding. "Uncertainty theory: an introduction to its axiomatic foundation." Germany: Springer Berlin, Heidelberg, (2004).

   [Crossref] [Google Scholar]

10. Molodtsov, Dmitriy. "Soft set theory-first results." Comput Math with Appl 37 (1999): 19-31.

    [Crossref] [Google Scholar]

11. Senapati, Tapan, and Ronald R Yager. "Fermatean fuzzy sets." J Ambient Intell Humaniz Comput 11 (2020): 663-674.
12. Zhou, Jian, Lu Chen, and Ke Wang. "Path optimality conditions for minimum spanning tree problem with uncertain edge weights." Int J Uncertain Fuzziness Knowlege-Based Syst 23 (2015): 49-71.

    [Crossref] [Google Scholar]

13. Zhou, Jian, Qina Wang, and Xiang Zhang. "The Inverse Spanning Tree of a Fuzzy Graph Based on Credibility Measure." J Commun 8 (2013): 566-571.
14. Zadeh, Lotfi A. "Fuzzy sets." Inf Control 8 (1965): 338-353.

    [Crossref] [Google Scholar]