Abstract
It is known that Intuitionistic fuzzy models give more precision, flexibility and compatibility to the system as compared to the classic and fuzzy models. Intuitionistic fuzzy tree has an important role in neural networks, computer networks, and clustering. In the design of a network, it is important to analyze connections between the levels. In addition, the intuitionistic fuzzy tree is becoming increasingly significant as it is applied to different areas in real life. The study proposes the novel concepts of intuitionistic fuzzy graph (IFG) and some basic definitions. We investigate the types of arcs, for example, \(\alpha _{\mu }\)-strong, \(\beta _{\mu }\)-strong, and \(\delta _{\mu }\)-arc in an intuitionistic fuzzy graph, and introduce some of their properties. In particular, the present work develops the concepts of intuitionistic fuzzy bridge (IFB), intuitionistic fuzzy cut nodes (IFCN) and some important properties of an intuitionistic fuzzy bridge. Next, we define an intuitionistic fuzzy cycle (IFC) and an intuitionistic fuzzy tree (IFT). Likewise, we discuss some properties of the IFT and the relationship between an intuitionistic fuzzy tree and an intuitionistic fuzzy cycle. Finally, an application of intuitionistic fuzzy tree is illustrated in other sciences.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
1 Introduction
In 1965, Zadeh [64] introduced the notion of a fuzzy set as a method for representing uncertainty. Since then, the theory of fuzzy sets has become a vigorous area of research in different disciplines including medical and life sciences, management sciences, social sciences, engineering, statistics, graph theory, artificial intelligence, signal processing, multiagent systems, pattern recognition, robotics, computer networks, expert systems, decision making and automata theory.
Ten years after Zadeh’s landmark paper, Rosenfeld [43], and Yeh and Bang [63] introduced the concept of fuzzy graphs. Bhutani et al. [19] defined M-strong fuzzy graphs. The fuzzy relations between fuzzy sets were also considered by Rosenfeld and he developed the structure of fuzzy graphs, obtaining analogs of several graph theoretical concepts. Later on, Bhattacharya [15] gave some remarks on fuzzy graphs, and some operations on fuzzy graphs were introduced by Mordeson and Peng [33]. Mordeson and Nair [34,35,36] studied fuzzy line graphs and cycles and co-cycles of fuzzy graphs. Mathew and Sunitha [31, 32] investigated types of arcs and node connectivity in a fuzzy graph. Domination in fuzzy graphs was introduced by Somasundaram [61]. Bhutani and Rosenfeld introduced the concepts of fuzzy end nodes [17], etc. They showed the existence of a strong path between any two nodes of a fuzzy graph. Fuzzy graph theory is now finding numerous applications in modern sciences and technology especially in the fields of information theory, neural networks, expert systems, cluster analysis, medical diagnosis, and control theory, etc.
Atanassov [5] introduced the concept of an intuitionistic fuzzy set and investigated new results on it [6,7,8]. Research on the theory of intuitionistic fuzzy sets (IFSs) has been witnessing an exponential growth in mathematics and its applications. This ranges from traditional mathematics to information sciences. This leads to consider intuitionistic fuzzy graphs and their applications. The concept of intuitionistic fuzzy graph was introduced in 1994 in [57]. It was an object of some subsequent extensions (see [10, 13, 41, 58]), representations (see [9, 11, 12]), and applications (see [11]). Chountas et al. [21,22,23, 40, 56] discussed an intuitionistic fuzzy version of the special particular case of a graph, the tree, called an intuitionistic fuzzy tree. Alzebdi et al. [4] proposed their approach of using intuitionistic fuzzy trees to achieve an approximate XML query matching by considering a novel approach of matching arcs as the basic units of data schemas. Bujnowski et al. [14] presented a new classifier called an intuitionistic fuzzy decision tree and studied its properties. Thamizhendhi and Parvathi [62] described the concepts of distance, eccentricity, radius, diameter and center of an intuitionistic fuzzy tree. Mahapatra et al. [30] investigated intuitionistic fuzzy fault tree using intuitionistic fuzzy numbers. In [39], some important operations on intuitionistic fuzzy graphs were defined and their properties were studied. Further in [40], IFGs were applied to find the shortest path in networks using dynamic programming problem approach. Nagoor Gani et al. [37, 38] introduced order, size, and double domination on intuitionistic fuzzy graphs.
Pal et al. [42, 48, 49, 51] investigated modern trends in fuzzy graph theory, categorical properties in intuitionistic fuzzy graphs, and new results in interval valued fuzzy graphs. Rashmanlou et al. [44,45,46,47, 50] studied several concepts on vague graphs and bipolar fuzzy graphs. Sahoo et al. [52,53,54] defined intuitionistic fuzzy competition graphs and intuitionistic fuzzy tolerance graphs with an application. Recently, some researches have been conducted by the authors in the continuation of previous works related to intuitionistic fuzzy trees and intuitionistic fuzzy graphs which are mentioned in [1,2,3, 18, 24,25,26,27, 55, 59, 60].
In this paper, we define types of arcs in an intuitionistic fuzzy graphs and intuitionistic fuzzy trees. Also, we study the intuitionistic fuzzy bridge, intuitionistic fuzzy cutnode, intuitionistic fuzzy cycle, intuitionistic fuzzy tree, and examine the relationship between an IFT and IFC. The paper is organized as follows: Section 2 contains basic definitions about IFGs. In Section 3, we introduce the concept of \(\alpha _{\mu }\)-strong, \(\beta _{\mu }\)-strong, \(\delta _{\mu }\)-arc, \(\alpha _{\nu }\)-strong, \(\beta _{\nu }\)-strong, and \(\delta _{\nu }\)-arc (Definition 11). We also define \(\alpha _{\mu }\)-strong, \(\alpha _{\nu }\)-strong and \(\alpha \)-strong path with expression examples (Example 2) and discuss the properties of \(\mu \)-strong, \(\nu \)-strong, \(\mu \)-strongest, and \(\nu \)-strongest path. In Sect. 4, the intuitionistic fuzzy bridge (IFB), intuitionistic fuzzy cutnode (IFCN), intuitionistic fuzzy \(\mu \)-bridge (IF \(\mu \)-bridge) and intuitionistic fuzzy \(\nu \)-bridge (IF \(\nu \)-bridge) are given. In Sects. 5 and 6, we first introduce intuitionistic fuzzy trees (IFT), then intuitionistic fuzzy cycle (IFC), and investigate the types of arcs in an IFC. Also, the relationship between an intuitionistic fuzzy cycle and an intuitionistic fuzzy tree is studied. In Sect. 7, we try to answer some questions. Finally, some applications of intuitionistic fuzzy trees are given. The paper is concluded in Sect. 9.
2 Preliminaries
In this section, we first review some definitions of an intuitionistic fuzzy graph that are necessary for this paper. We define the concepts of \(\mu \)-cycle, \(\nu \)-cycle, \(\mu \)-tree,\(\nu \)-tree, \(\mu \)-path, \(\nu \)-path, \(\mu \)-connected, and \(\nu \)-connected.
Definition 1
[5] Let X be a fixed set. An intuitionistic fuzzy set (IFS) A in X is an object of the form \(A=\lbrace (x,\mu _A(x),\nu _A(x))|~x\in X\rbrace \), where \(\mu _A:X\rightarrow [0,1]\) and \(\nu _A:X\rightarrow [0,1]\) are considered as degree of membership and degree of non-membership of the element \(x\in X\), respectively, and for every \(x\in X\), \(0\le \mu _A(x)+\nu _A(x)\le 1\).
Definition 2
[57] An intuitionistic fuzzy graph (IFG) is of the form \(G=(V,E)\) where
-
(i)
\(V=\lbrace v_0,v_1,\ldots ,v_n\rbrace \) so that \(\mu _1:V\rightarrow [0,1]\) and \(\nu _1:V\rightarrow [0,1]\) denote the degree of membership and non-membership of the element \(v_i\in V\), respectively, and \(\nu _1(v_i)+\mu _1(v_i)\le 1\), for \(v_i\in V\), \((i=1,2,\ldots ,n)\).
-
(ii)
\(E\subseteq V\times V\) where \(\mu _2:V\times V\rightarrow [0,1]\) and \(\nu _2:V\times V\rightarrow [0,1]\) so that
-
(a)
\(\mu _2(v_i,v_j)\le \min [\mu _1(v_i),\mu _1(v_j)]\),
-
(b)
\(\nu _2(v_i,v_j)\ge \max [\nu _1(v_i),\nu _1(v_j)]\),
-
(c)
\(0\le \mu _2(v_i,v_j)+\nu _2(v_i,v_j)\le 1\), for every \((v_i,v_j)\in E\).
-
(a)
Here, the triple \((v_i,\mu _{1i},\nu _{1i})\) denotes the degree of membership and degree of non-membership of the vertex \(v_i\). The triple \((e_{ij},\mu _{2ij},\nu _{2ij})\) denotes the degree of membership and degree of non-membership of the edge \(e_{ij}=(v_i,v_j)\) on V. If we consider arcs of G only with the degree of memberships, then, they are called the \(\mu \)-arcs, and if we consider arcs of G only with the degree of non-memberships, then, they are called \(\nu \)-arcs.
Remark 1
Let \(G=(V,E)\) be an IFG. If we consider all vertices and arcs in G only with the degree of memberships, then we obtain a fuzzy graph. It is clear that all definitions and theorems for a fuzzy graph hold for it.
Definition 3
[57] Let \(G=(V,E)\) be an IFG. An IFG \(H=(V',E')\) is said to be an intuitionistic fuzzy subgraph (IFSG) of G, if \(V'\subseteq V\) and \(E'\subseteq E\) so that for \(x\in V'\), if \(\mu {'}_1(x)>0\) or \(\nu {'}_1(x)>0\), then, \(\mu {'}_1(x)=\mu _1(x)\) and \(\nu {'}_1(x)=\nu _1(x)\) and for \((x,y)\in E'\), if \(\mu {'}_2(x,y)>0\) or \(\nu {'}_2(x,y)>0\), then, \(\mu {'}_2(x,y)=\mu _2(x,y)\) and \(\nu {'}_2(x,y)=\nu _2(x,y)\). Also, H is said to be an intuitionistic spanning fuzzy subgraph (ISFS) of G if \(V'=V\).
Definition 4
We define the underlying graphs \(G^*_{\mu }=(\mu ^*_1,\mu ^*_2)\) and \(G^*_{\nu }=(\nu ^*_1,\nu ^*_2)\), where
-
(i)
\(\mu ^*_1=\lbrace u\in V: \mu _1(u)>0 ~or ~\nu _1(u)>0\rbrace \),
-
(ii)
\(\mu ^*_2=\lbrace (u,v)\in E:\mu _2(u,v)>0\rbrace \),
-
(iii)
\(\nu ^*_1=\lbrace u\in V: \nu _1(u)>0 ~or ~\mu _1(u)>0\rbrace \),
-
(iv)
\(\nu ^*_2=\lbrace (u,v)\in E:\nu _2(u,v)>0\rbrace \).
Definition 5
[24] An IFG \(G=(V,E)\) is strong if for all \((v_i,v_j)\in E\), \(\mu _{2ij}=\min (\mu _{1i},\mu _{1j})\) and \(\nu _{2ij}=\max (\nu _{1i},\nu _{1j})\), and is complete if for all \(v_i,v_j\in V\), \(\mu _{2ij}=\min (\mu _{1i},\mu _{1j})\) and \(\nu _{2ij}=\max (\nu _{1i},\nu _{1j})\).
Remark 2
When \(\mu _{2ij}=\nu _{2ij}=0\) for some i and j, then, there is no edge between \(v_i\) and \(v_j\). Otherwise, there exists an edge between \(v_i\) and \(v_j\).
Definition 6
[3] An IFG \(G=(V,E)\) is a \(\mu \)-tree and also a \(\nu \)-tree, if \(G^*_{\mu }\) and \(G^*_{\nu }\) are trees, respectively. Moreover, G is a tree, if it is both \(\mu \)-tree and \(\nu \)-tree, and \(G^*_{\mu }=G^*_{\nu }\). Also, G is a \(\mu \)-cycle and also a \(\nu \)-cycle, if \(G^*_{\mu }\) and \(G^*_{\nu }\) are cycles, respectively. Furthermore, G is a cycle, if it is both \(\mu \)-cycle and \(\nu \)-cycle, and \(G^*_{\mu }=G^*_{\nu }\).
Remark 3
Let \(G=(V,E)\) be an IFG. If G is a \(\mu \)-cycle, then, an arc (x, y) is said to be the weakest \(\mu \)-arc of G, if \(\mu _{2}(x,y)\) is less than or equal to the degree of membership of all arcs of G. If G is a \(\nu \)-cycle, then, an arc (x, y) is said to be the weakest \(\nu \)-arc of G, if \(\nu _{2}(x,y)\) is greater than or equal to the degree of non-membership of all arcs of G.
Example 1
In Fig. 1, let \(G=(V,E)\) be an IFG so that \(V=\lbrace x,u,v,w\rbrace \), \(E=\lbrace (x,u),(u,v),(v,w),(x,w)\rbrace \). Then, G is a \(\mu \)-tree and \(\nu \)-tree, is not a tree.
Definition 7
[29] Let \(P:x=v_0,v_1,\ldots ,v_n=y\) be a sequence of distinct vertices in an intuitionistic fuzzy graph, then, P is a \(\mu \)-path from x to y, if \(\mu _2(v_{j-1},v_i)>0\), and is a \(\nu \)-path, if \(\nu _2(v_{j-1},v_i)>0\) for \(i=1,2,\ldots ,n\). Also, P is a path, if it is both \(\mu \)-path and \(\nu \)-path, then, P is called a \((x-y)\) path and the length of P is n. If \(x=y\) and \(n>3\), P is called \(\mu \)-cycle, \(\nu \)-cycle and cycle, respectively.
Definition 8
[29] An intuitionistic fuzzy graph \(G=(V,E)\) is \(\mu \)-connected, if there exists a \(\mu \)-path between every pair of vertices in G and is \(\nu \)-connected, if there exists a \(\nu \)-path between every pair of vertices in G. Also, G is called strong connected, if there exists a path between every pair of vertices in G.
Remark 4
In Fig. 1, G is \(\mu \)-connected and \(\nu \)-connected, but it is not connected. There exist a \(\mu \)-path and \(\nu \)-path from x to v, but there is no path between them.
Definition 9
[24, 29] If \(v_i,v_j\in V\subseteq G\), the \(\mu \)-strength of connectedness between \(v_i\) and \(v_j\) is \(\mu _2^{\infty }=\sup \lbrace \mu _2^k(v_i,v_j)|~k=1,2,\ldots , n\rbrace \) and the \(\nu \)-strength of connectedness between \(v_i\) and \(v_j\) is \(\nu _2^{\infty }=\inf \lbrace \nu _2^k(v_i,v_j)|~k=1,2,\cdots , n\rbrace \). \(\mu _2^k(v_i,v_j)\) is defined as \(\sup \lbrace \mu _2(u,v_1)\wedge \mu _2(v_1,v_2)\wedge \cdots \wedge \mu _2(v_{k-1},v)| u,v_1,v_2,\ldots ,v_{k-1},v\in V\rbrace \), if u, v are connected by \(\mu \)-paths of length k. Also, if u, v are connected by \(\nu \)-paths of length k, then, \(\nu _2^k(u,v)\) is defined as \(\inf \lbrace \nu _2(u,v_1)\vee \nu _2(v_1,v_2)\vee \cdots \vee \nu _2(v_{k-1},v)| u,v_1,v_2,\cdots ,v_{k-1},v\in V\rbrace \).
Remark 5
[24, 29] If P is a \(\mu \)-path in \(G=(V,E)\) from x to y, then, the \(\mu \)-strength of P is denoted by \(\mu _P^{\infty }(x,y)\) and if P is a \(\nu \)-path in G, then, the \(\nu \)-strength of P is denoted by \(\nu _P^{\infty }(x,y)\). A path between a pair of vertices x and y is the \(\mu \)-strongest \((x-y)\) path and \(\nu \)-strongest (x, y) path, if the \(\mu \)-strength and \(\nu \)-strength is equal to \(\mu _P^{\infty }(x,y)\) and \(\nu _P^{\infty }(x,y)\), respectively.
3 Types of Arcs and Paths
In this section, we present the types of arcs and paths in an intuitionistic fuzzy graph with an expression of an example (Example 2), and, we investigate some important properties.
Definition 10
An arc (x, y) in an IFG \(G=(V,E)\) is called \(\mu \)-strong and \(\nu \)-strong, if \(\mu _2(x,y)\ge \mu {'}_2^{\infty }(x,y)\) and \(\nu _2(x,y)\le \nu {'}_2^{\infty }(x,y)\), respectively. Also (x, y) is called strong, if it is \(\mu \)-strong or \(\nu \)-strong.
Definition 11
An arc (x, y) in \(G=(V,E)\) is called \(\alpha _{\mu }\)-strong, \(\beta _{\mu }\)-strong, \(\delta _{\mu }\)-arc, \(\alpha _{\nu }\)-strong, \(\beta _{\nu }\)-strong and \(\delta _{\nu }\)-arc, if \(\mu _2(x,y)> \mu {'}_2^{\infty }(x,y)\), \(\mu _2(x,y)= \mu {'}_2^{\infty }(x,y)\), \(\mu _2(x,y)< \mu {'}_2^{\infty }(x,y)\), \(\nu _2(x,y)< \nu {'}_2^{\infty }(x,y)\), \(\nu _2(x,y)= \nu {'}_2^{\infty }(x,y)\) and \(\nu _2(x,y)> \nu {'}_2^{\infty }(x,y)\), respectively.
Example 2
In Fig. 2, let \(G=(V,E)\) be an IFG, so that \(V=\lbrace x,u,v,w,z\rbrace \), \(E=\lbrace (x,u),(x,v),(u,v),(u,w),(v,z),(w,z)\rbrace \). Then, the arc (x, u) is \(\delta _{\mu }\)-arc and \(\alpha _{\nu }\)-strong, the arc (x, v) is \(\alpha _{\mu }\)-strong and \(\delta _{\nu }\)-arc, the arc (u, v) is \(\alpha _{\mu }\)-strong and \(\alpha _{\nu }\)-strong and the arcs (u, w), (v, z) and (w, z) are \(\beta _{\mu }\)-strong and \(\beta _{\nu }\)-strong.
Definition 12
Let \(P:x=v_0,v_1,\ldots , v_n=y\) be a \(\mu \)-path from x to y in an IFG \(G=(V,E)\). P is \(\mu \)-strong (\(\alpha _{\mu }\)-strong), if for \(i=1,2,\ldots ,n\), the arcs \((v_{i-1},v_i)\) are \(\mu \)-strong (\(\alpha _{\mu }\)-strong). Let P be a \(\nu \)-path, then, P is \(\nu \)-strong (\(\alpha _{\nu }\)-strong), if for \(i=1,2,\ldots ,n\), the arcs \((v_{i-1},v_i)\) are \(\nu \)-strong (\(\alpha _{\nu }\)-strong). Let P be a path, then P is strong (\(\alpha \)-strong), if it is \(\mu \)-strong or \(\nu \)-strong (\(\alpha _{\mu }\)-strong or \(\alpha _{\nu }\)-strong).
Remark 6
In Fig. 2, the path P : x, v, u is a \(\alpha _{\mu }\)-strong path and the path \(P':x,u,v\) is a \(\alpha _{\nu }\)- strong path. Hence, P and \(P'\) are \(\alpha \)-strong paths.
Proposition 1
If \(G=(V,E)\) is a \(\mu \)-connected IFG, then, there exists a \(\mu \)-strong path between every pair of vertices of G.
Proof
It is obvious. □
Proposition 2
If \(G=(V,E)\) is a \(\nu \)-connected IFG, then, there exists a \(\nu \)-strong path between every vertex of G.
Proof
Let IFG G be \(\nu \)-connected, hence, there exists \(\nu \)-path between every pair of vertices x, y. If (x, y) is not a \(\nu \)-strong arc, then, we have \(\nu _2(x,y)>\nu {'}_2^{\infty }(x,y)\). Therefore, there exists a \(\nu \)-path P from x to y, of which \(\nu \)-strength is less than \(\nu _2(x,y)\). Now if some arcs of P are not a \(\nu \)-strong, we repeat this argument. Finally, we will have a \(\nu \)-path from x to y, which is \(\nu \)-strong. This completes the proof. □
Proposition 3
If a \(\mu \)-path P from x to y in an IFG \(G=(V,E)\) is \(\alpha _{\mu }\)-strong, then, P is a \(\mu \)-strongest \((x-y)\) path.
Proof
It follows from [31]. □
Remark 7
The converse of Proposition 3 is not true. In Example 2, the path \(P:u-v-z-w\) is a \(\mu \)-strongest \((u-w)\) path, but it is not a \(\alpha _{\mu }\)-strong \((u-w)\) path.
Proposition 4
If a path P from x to y in an IFG \(G=(V,E)\) is \(\alpha _{\nu }\)-strong, then, P is a \(\nu \)-strongest \((x-y)\) path.
Proof
Let \(P:x=v_0,v_1,\ldots ,v_n=y\) be a \(\alpha _{\nu }\)-strong path and suppose that P is not a \(\nu \)-strongest \((x-y)\) path in G. Let \(P':x=v'_0,v'_1,\ldots ,v'_n=y\) be a \(\nu \)-strongest \((x-y)\) path in G. Hence \(\nu _{2}(v'_{i-1},v'_i)<\nu _P^{\infty }(x,y)\), for \(i=1,2,\ldots ,n\). Also, P and \(P'\) form a \(\nu \)-cycle, called C. The weakest \(\nu \)-arc of C is in P. Let (u, v) be the weakest \(\nu \)-arc in P. Let \(P''\) be the \((u-v)\) path in C not including (u, v). It follows that \(\nu _2(u,v)\ge \nu _{P''}^{\infty }(u,v)\ge \nu {'}_2^{\infty }(u,v)\) which implies in which (u, v) is not a \(\alpha _{\nu }\)-strong arc, which contradicts the assumption. Therefore, P is a \(\nu \)-strongest \((x-y)\) path in G. □
Remark 8
The converse of Proposition 4 is not true. In Example 2, the path P : u, v, z, w is \(\nu \)-strongest \((u-w)\) path, but it is not \(\alpha _{\nu }\)-strong \((u-w)\) path.
4 Intuitionistic Fuzzy Bridge and Intuitionistic Fuzzy Cut Vertex
Now we study the intuitionistic fuzzy bridges and intuitionistic fuzzy cut vertices with an expression of an example (Example 3). We show that, if an arc (x, y) in an IFG is an IF \(\mu \)-bridge and an IF \(\nu \)-bridge, then, we have \(\mu _2(x,y)>\mu {'}_2^{\infty }(x,y)\) and \(\nu _2(x,y)<\nu {'}_2^{\infty }(x,y)\), respectively. Also, we examine some other properties of an IF \(\mu \)-bridge, IF \(\nu \)-bridge and IFB.
Definition 13
An arc (x, y) in an IFG \(G=(V,E)\) is said to be an intuitionistic fuzzy \(\mu \)-bridge (IF \(\mu \)-bridge), if deleting (x, y) reduces the \(\mu \)-strength of connectedness among some pairs of vertices. Equivalently, there exists \(u,v\in V\) so that (x, y) is an arc of every \(\mu \)-strongest \((u-v)\) path. An arc (x, y) is said to be an intuitionistic fuzzy \(\nu \)-bridge (IF \(\nu \)-bridge), if deleting (x, y) increases the \(\nu \)-strength of connectedness between some vertices pairs. Equivalently, there exists \(u,v\in V\) so that (x, y) is an arc of every \(\nu \)-strongest \((u-v)\) path. An arc (x, y) is said to be an intuitionistic fuzzy bridge (IFB), if it is an IF \(\mu \)-bridge or IF \(\nu \)-bridge.
Definition 14
A vertex \(x\in V\) in an IFG \(G=(V,E)\) is an intuitionistic fuzzy \(\mu \)-cut vertex (IF \(\mu \)-cut vertex), if deleting it reduces the \(\mu \)-strength of connectedness between some pair of vertices. Equivalently, there exist \(u,v\in V\) so that x is a vertex of every \(\mu \)-strongest \((u-v)\) path. A vertex \(x\in V\) is an intuitionistic fuzzy \(\nu \)-cut vertex (IF \(\nu \)-cut vertex), if deleting it increases the \(\nu \)-strength of connectedness between some pair of vertices. Equivalently, there exists \(u,v\in V\) such that x is a vertex of every \(\nu \)-strongest \((u-v)\) path. A vertex \(x\in V\) is an intuitionistic fuzzy cut vertex (IFCV), if it is an IF \(\mu \)-cut vertex or IF \(\nu \)-cut vertex.
Example 3
In Fig. 3, let \(G=(V,E)\) be an IFG, so that \(V=\lbrace x,u,v,w,z\rbrace \), \(E=\lbrace (x,u),(x,v),(u,v),(u,w),(v,z),(w,z)\rbrace \). Then, the arcs (x, u) and (x, v) are \(\beta _{\mu }\)-strong and \(\alpha _{\nu }\)-strong, the arcs (u, v) and (u, w) are \(\beta _{\mu }\)-strong and \(\delta _{\nu }\)-arc, the arcs (v, z) and (w, z) are \(\alpha _{\mu }\)-strong and \(\alpha _{\nu }\)-strong. Hence, all arcs are strong. Also, the arcs (v, z) and (w, z) are IF \(\mu \)-bridges, and the arcs (x, u), (x, v), (v, z) and (w, z) are IF \(\nu \)-bridges. Hence, all arcs except (u, v) are IFB. Also, z is an IF \(\mu \)-cut vertex and x, z are IF \(\nu \)-cut vertex. Hence, x and z are IFCV.
Theorem 5
Let (x, y) be an arc in an IFG \(G=(V,E)\), then
-
(i)
(x, y) is an IF \(\mu \)-bridge if and only if \(\mu _2(x,y)>\mu {'}_2^{\infty }(x,y)\).
-
(ii)
(x, y) is an IF \(\nu \)-bridge if and only if \(\nu _2(x,y)<\nu {'}_2^{\infty }(x,y)\).
-
(iii)
(x, y) is an IFB if and only if \(\mu _2(x,y)>\mu {'}_2^{\infty }(x,y)\) or \(\nu _2(x,y)<\nu {'}_2^{\infty }(x,y)\).
Proof
(i) It follows from [Theorem 1 of 9] and Definition 11.
(ii) Assume that (x, y) is an IF \(\nu \)-bridge. Hence, there exists \(u,v\in V\) so that \(\forall \) (x, y), there is an arc of \(\nu \)-strongest (u, v) path, which is called P. Now let \(P'\) be a \(\nu \)-path from u to v which does not including (x, y) and the \(\nu \)-strength of it is the minimum between all the \(\nu \)-paths from u to v which does not include (x, y).
Then, P and \(P'\) form a cycle called C and \(C-(x,y)\) is a \(\nu \)-path called \(P''\). We claim that \(P''\) is the \(\nu \)-strongest path between x and y. Let \(P'\) be a \(\nu \)-strongest path between x and y, then, deleting (x, y) does not increase the \(\nu \)-strength of u and v. This contradicts the assumption. Hence \(\nu _{P''}^{\infty }(x,y)=\nu {'}_2^{\infty }(x,y)\). Also, the weakest \(\nu \)-arc of C is on \(P'\), therefore, \(\nu _2(x,y)<\nu _{P''}^{\infty }(x,y)\) implies that \(\nu _2(x,y)<\nu {'}_2^{\infty }(x,y)\). Conversely, if \(\nu _2(x,y)<\nu {'}_2^{\infty }(x,y)\), then, deleting (x, y) increases the \(\nu \)-strength of connectedness between x and y. Hence, (x, y) is an IF \(\nu \)-bridge.
(iii) It follows from (i) and (ii). □
Corollary 6
Let (x, y) be an arc in an IFG \(G=(V,E)\), then,
-
(i)
(x, y) is an IF \(\mu \)-bridge iff is an \(\alpha _{\mu }\)-strong arc.
-
(ii)
(x, y) is an IF \(\nu \)-bridge iff is an \(\alpha _{\nu }\)-strong arc.
-
(iii)
(x, y) is an IFB if it is an \(\alpha _{\mu }\)-strong arc or \(\alpha _{\nu }\)-strong arc.
Corollary 7
Every IFB in an IFG \(G=(V,E)\) is a strong arc.
Remark 9
The converse of Corollary 7 is not true. In Example 2, (u, v) is a strong arc, but it is not an IFB.
Proposition 8
Let (x, y) be an arc in an IFG \(G=(V,E)\). Then, we have:
-
(i)
If (x, y) is \(\mu \)-strong, then, \(\mu _2(x,y)=\mu _2^{\infty }(x,y)\).
-
(ii)
If (x, y) is \(\nu \)-strong, then, \(\nu _2(x,y)=\nu _2^{\infty }(x,y)\).
-
(iii)
If (x, y) is strong, then, \(\mu _2(x,y)=\mu _2^{\infty }(x,y)\) or \(\nu _2(x,y)=\nu _2^{\infty }(x,y)\).
Proof
(i) It is clear.
(ii) In an IFG, we always have \(\nu _2(x,y)\ge \nu _2^{\infty }(x,y)\). Suppose that (x, y) is a \(\nu \)-strong arc, then, \(\nu _2(x,y)\le \nu {'}_2^{\infty }(x,y)\). If \(\nu _2(x,y)= \nu {'}_2^{\infty }(x,y)\), then, \(\nu _2(x,y)=\nu _2^{\infty }(x,y)\). Also, if \(\nu _2(x,y)< \nu {'}_2^{\infty }(x,y)\), then, \(\nu _2(x,y)= \nu _2^{\infty }(x,y)\), which completes the proof.
(iii) It follows from (i) and (ii). □
Proposition 9
An arc (u, v) in an IFG \(G=(V,E)\) is an IF \(\mu \)-bridge if and only if (u, v) is not the weakest \(\nu \)-arc in all cycles in G.
Proof
See [43]. □
Proposition 10
An arc (u, v) in an IFG \(G=(V,E)\) is an IF \(\nu \)-bridge if and only if (u, v) is not the weakest \(\nu \)-arc in every cycle in G.
Proof
Let (u, v) be the weakest \(\nu \)-arc of a cycle C in G and P is the path \(C-(u,v)\) from u to v. Then, \(\nu _2(u,v)\ge \nu _P^{\infty }(u,v)\). Also \(\nu {'}_2^{\infty }(u,v)\le \nu _P^{\infty }(u,v)\) implies that \(\nu _2(u,v)\ge \nu {'}_2^{\infty }(u,v)\). Hence, (u, v) is not a \(\alpha _{\nu }\)-strong arc. Therefore, (u, v) is not an IF \(\nu \)-bridge by Corollary 6. Conversely, let (u, v) be not an IF \(\nu \)-bridge. By Corollary 6, (u, v) is not \(\alpha _{\nu }\)-strong. Thus \(\nu _2(u,v)\ge \nu {'}_2^{\infty }(u,v)\). Let P be a path from u to v in \(G-(u,v)\) such that \(\nu {'}_2^{\infty }(u,v)= \nu _P^{\infty }(u,v)\). Then, \(\nu _2(u,v)\ge \nu _P^{\infty }(u,v)\). The path P with adding the arc (u, v) forms a cycle called C. Clearly (u, v) is the weakest \(\nu \)-arc in C, which contradicts the assumption. □
5 Intuitionistic Fuzzy Trees
In this section, we introduce types of intuitionistic fuzzy trees. We recognize types of arcs in an intuitionistic fuzzy tree. Also, we study necessary conditions that an intuitionistic fuzzy graph can be an IFT.
Definition 15
A \(\mu \)-connected IFG \(G=(V,E)\) is an intuitionistic fuzzy \(\mu \)-tree (IF \(\mu \)-tree), if it has an intuitionistic fuzzy spanning subgraph F, which is a \(\mu \)-tree, so that for all arcs (u, v) which are not in F, \(\mu _2(u,v)<\mu _F^{\infty }(u,v)\). Also, F is called a spanning \(\mu \)-tree of G.
Definition 16
A \(\nu \)-connected IFG \(G=(V,E)\) is an intuitionistic fuzzy \(\nu \)-tree (IF \(\nu \)-tree), if it has an intuitionistic fuzzy spanning subgraph \(F'\), which is a \(\nu \)-tree, so that for all arcs (u, v) which are not in \(F'\), \(\nu _2(u,v)>\nu _{F'}^{\infty }(u,v)\). Also, \(F'\) is called a spanning \(\nu \)-tree of G.
Definition 17
Let \(G=(V,E)\) be a strong connected IFG. Then, G is an intuitionistic fuzzy tree (IFT), if it has an intuitionistic fuzzy spanning subgraph of \(F''\) which is a tree, so that for all arcs (u, v) which are not in \(F''\), \(\mu _2(u,v)<\mu _{F''}^{\infty }(u,v)\) and \(\nu _2(u,v)>\nu _{F''}^{\infty }(u,v)\). Also, \(F''\) is called a spanning tree of G.
Next, we consider the intutionistic fuzzy graph of \(G=(V,E)\) as a strong connected IFG. Obviously, we have the following.
Proposition 11
If \(G=(V,E)\) is an IFT, then, G is an IF \(\mu \)-tree and IF \(\nu \)-tree.
Remark 10
The converse of the Proposition 11, is not true (see Example 4).
Example 4
In Fig. 4, \(G=(V,E)\) is an IF \(\mu \)-tree and IF \(\nu \)-tree, but it is not an IFT, because there is not a spanning tree \(F''\).
Theorem 12
An arc (x, y) in an IF \(\mu \)-tree \(G=(V,E)\) is \(\alpha _{\mu }\)-strong if and only if (x, y) is an arc of the spanning \(\mu \)-tree F of G.
Proof
It is clear. □
Using the Theorem 12, an IF \(\mu \)-tree F consists of all \(\alpha _{\mu }\)-strong arcs. So, we have the following.
Corollary 13
If \(G=(V,E)\) is an IF \(\mu \)-tree, then F is unique spanning \(\mu \)-tree.
Theorem 14
An arc (x, y) in an IF \(\nu \)-tree \(G=(V,E)\) is \(\alpha _{\nu }\)-strong if and only if (x, y) is an arc of the spanning \(\nu \)-tree \(F'\) of G.
Proof
Assume that (x, y) is a \(\alpha _{\nu }\)-strong arc in G, then, by Definition 11, \(\nu _2(x,y)<\nu _{G-(x,y)}^{\infty }(x,y)\). If (x, y) does not belong to \(F'\), then \(\nu _2(x,y)>\nu _{F'}^{\infty }(x,y)\). Also, the spanning \(\nu \)-tree \(F'\) is an ISFS of \(G-(x,y)\). Hence, \(\nu _{F'}^{\infty }(x,y)\ge \nu _{G-(x,y)}^{\infty }(x,y)\). It follows \(\nu _2(x,y)>\nu _{G-(x,y)}^{\infty }(x,y)\), which contradicts the assumption. Hence, (x, y) is in \(F'\). Conversely, let the arc (x, y) belong to \(F'\). If (x, y) is not a \(\alpha _{\nu }\)-strong arc in G, then, \(\nu _2(x,y)\ge \nu _{G-(x,y)}^{\infty }(x,y)\). We consider C as a \(\nu \)-cycle consisting of (x, y). Hence, there exists the arc (u, v) in C, which is not in \(F'\). Therefore, \(\nu _2(u,v)>\nu _{F'}^{\infty }(u,v)\). We have the \(\nu \)-path \(P=C-(u,v)\) from u to v in \(F'\), hence, \(\nu _{P}^{\infty }(u,v)=\nu _{F'}^{\infty }(u,v)\), because \(F'\) is a \(\nu \)-tree. Also, we have \(\nu _{P}^{\infty }(u,v)\ge \nu _2(x,y)\), thus, \(\nu _{F'}^{\infty }(u,v)\ge \nu _2(x,y)\), which implies that \(\nu _2(u,v)>\nu _2(x,y)\). Therefore, (x, y) is not the weakest \(\nu \)-arc of every cycle in G. Hence, (x, y) is an IF \(\nu \)-bridge by Proposition 10. Thus, (x, y) is \(\alpha _{\nu }\)-strong, which completes the proof. □
Corollary 15
If \(G=(V,E)\) is an IF \(\nu \)-tree, then, \(F'\) is a unique spanning \(\nu \)-tree.
Proposition 16
In an IFT \(G=(V,E)\), there exists unique spanning tree \(F''\) so that \(F''=F'=F\).
Proof
If \(G=(V,E)\) is an IFT, then, there exists a spanning tree \(F''\) such that for all arcs (u, v) which are not in \(F''\),
and
By (1), there exists a unique spanning \(\mu \)-tree F so that \(F''=F\) and by (2), there exists a unique spanning \(\nu \)-tree \(F'\) so that \(F''=F'\). Hence, \(F''\) is a unique spanning tree and \(F''=F'=F\). □
Corollary 17
An IFG \(G=(V,E)\) is an IFT if and only if G is an IF \(\mu \)-tree and IF \(\nu \)-tree with \(F=F'\).
Proof
If \(G=(V,E)\) is an IFT, then by Proposition 11, G is an IF \(\mu \)-tree and IF \(\nu \)-tree, and \(F''=F'=F\) by Proposition 16. Conversely, let there exist a spanning \(\mu \)-tree F and spanning \(\nu \)-tree \(F'\) so that \(F=F'\). Consider \(F''=F'=F\). Now for (x, y) which is not found in \(F''=F\), we have \(\mu _2(x,y)<\mu _{F''}^{\infty }(x,y)\) and \(\nu _2(x,y)>\nu _{F''}^{\infty }(x,y)\). Hence, G is an IFT with spanning tree \(F''\). □
Example 5
In Fig. 5, \(G=(V,E)\) is not an IF \(\mu \)-tree, because it has \(\beta _{\mu }\)-strong arcs, but G is an IF \(\nu \)-tree, because it has no any \(\beta _{\nu }\)-strong arcs. Hence, it is not an IFT.
The arcs (u, v) and (u, w) are \(\beta _{\mu }\)-strong and \(\delta _{\nu }\)-strong, the arcs (x, u) and (x, v) are \(\beta _{\mu }\)-strong and \(\alpha _{\nu }\)-strong and the arcs (w, z) and (v, z) are \(\delta _{\mu }\)-arcs and \(\alpha _{\nu }\)-strong.
Corollary 18
An arc (x, y) in an IFT \(G=(V,E)\) is \(\alpha _{\mu }\)-strong if and only if it is \(\alpha _{\nu }\)-strong.
Proof
Let (x, y) be \(\alpha _{\mu }\)-strong, then, (x, y) is in F by Theorem 12. G is an IFT, hence \(F''=F'=F\) and implies that (x, y) is in \(F'\). Therefore, (x, y) is \(\alpha _{\nu }\)-strong by Theorem 14. The converse is similar. □
Proposition 19
Let \(G=(V,E)\) be an IFG, then, we have:
-
(i)
If G is an IF \(\mu \)-tree and the arc (x, y) is not in F, then \(\mu _F^{\infty }(x,y)=\mu {'}_2^{\infty }(x,y)\).
-
(ii)
If G is an IF \(\nu \)-tree and the arc (x, y) is not in \(F'\), then, \(\nu _{F'}^{\infty }(x,y)=\nu {'}_2^{\infty }(x,y)\).
-
(iii)
If G is an IFT and the arc (x, y) is not in \(F''\), then, \(\mu _{F''}^{\infty }(x,y)=\mu {'}_2^{\infty }(x,y)\) and \(\nu _{F''}^{\infty }(x,y)=\nu {'}_2^{\infty }(x,y)\).
Proof
-
(i)
Let P be a \(\mu \)-path from x to y in F. All arcs of P are \(\alpha _{\mu }\)-strong by Theorem 12. Hence, P is a \(\alpha _{\mu }\)-strong path. Thus, by Proposition 3, P is a \(\mu \)-strongest \((x-y)\) path. It follows that \(\mu _{F}^{\infty }(x,y)=\mu {'}_2^{\infty }(x,y)\).
-
(ii)
Let P be a \(\nu \)-path from x to y in \(F'\). All arcs of P are \(\alpha _{\nu }\)-strong by Theorem 14. Hence P is a \(\alpha _{\nu }\)-strong path. Thus by Proposition 4, P is a \(\nu \)-strongest \((x-y)\) path. It follows that \(\nu _{F'}^{\infty }(x,y)=\nu {'}_2^{\infty }(x,y)\).
-
(iii)
It follows obviously from (i) and (ii). □
Example 6
In Fig. 6, \(G=(V,E)\) is an IF \(\mu \)-tree and IF \(\nu \)-tree and also we have \(F=F'\). Hence, G is an IFT.
The arcs (x, v), (u, v), (u, w) and, (w, z) are \(\alpha _{\mu }\)-strong and \(\alpha _{\nu }\)-strong. The arcs (x, u), (v, z), and (v, w) are \(\delta _{\mu }\)-arcs and \(\delta _{\nu }\)-arcs.
6 Intuitionistic Fuzzy Cycles
In this section, we study types of intuitionistic fuzzy cycles. We use types of arcs to study properties of an IFC. Also, we study the relationship between intuitionistic fuzzy cycle and intuitionistic fuzzy tree.
Definition 18
Let \(G=(V,E)\) be a \(\mu \)-cycle. Then, G is an intuitionistic fuzzy \(\mu \)-cycle (IF \(\mu \)-cycle), if it contains more than one weakest \(\mu \)-arcs. Let G be a \(\nu \)-cycle, then, it is an intuitionistic fuzzy \(\nu \)-cycle (IF \(\nu \)-cycle), if it contains more than one weakest \(\nu \)-arcs. Let G be a cycle, then G is an intuitionistic fuzzy cycle (IFC), if it is an IF \(\mu \)-cycle or IF \(\nu \)-cycle.
Proposition 20
Let \(G=(V,E)\) be an IFG. Then, we have:
-
(i)
If G is an IF \(\mu \)-cycle, then, G has no \(\delta _{\mu }\)-arcs.
-
(ii)
If Gis an IF \(\nu \)-cycle, then, G has no \(\delta _{\nu }\)-arcs.
-
(iii)
If G is an IFC, then, G has no \(\delta _\mu \)-arcs or \(\delta _{\nu }\)-arcs.
Proof
-
(i)
If (u, v) is a \(\delta _{\mu }\)-arc in G, then, it becomes the unique weakest \(\mu \)-arc in G, which contradicts the Definition 18.
-
(ii)
If (u, v) is a \(\delta _{\nu }\)-arc in G, then, it becomes the unique weakest \(\nu \)-arc in G, which contradicts the Definition 18.
-
(iii)
It follows the (i) and (ii).
□
Lemma 21
Let \(G=(V,E)\) be an IFG. Then, we have:
-
(i)
If G is a \(\mu \)-cycle, then, G is an IF \(\mu \)-cycle if and only if it has at least two \(\beta _{\mu }\)-strong arcs.
-
(ii)
If G is a \(\nu \)-cycle, then, G is an IF \(\nu \)-cycle if and only if it has at least two \(\beta _{\nu }\)-strong arcs.
-
(iii)
If G is a cycle, then, it is an IFC if and only if it has at least two \(\beta _{\mu }\)-strong arcs or \(\beta _{\nu }\)-strong arcs.
Proof
-
(i)
If G is an IF \(\mu \)-cycle, then, there exist at least two weakest \(\mu \)-arcs that are \(\beta _{\mu }\)-arcs. Hence, G has at least two \(\beta _{\mu }\)-strong arcs. The inverse relation is obvious.
-
(ii)
If G is an IF \(\nu \)-cycle, then there exists at least two weakest \(\nu \)-arcs which are \(\beta _{\nu }\)-arcs. Hence, G has at least two \(\beta _{\nu }\)-strong arcs. The inverse relation is obvious.
-
(iii)
We get from (i) and (ii) directly.
□
Theorem 22
Let an IFG \(G=(V,E)\) be a \(\mu \)-cycle, then, G is an IF \(\mu \)-cycle if and only if it is not an IF \(\mu \)-tree.
Proof
It is easy, see [24]. □
Theorem 23
Let an IFG \(G=(V,E)\) be a \(\nu \)-cycle, then, G is an IF \(\nu \)-cycle if and only if it is not an \(\nu \)-tree.
Proof
If G is an IF \(\nu \)-cycle, then, it has no \(\delta _{\nu }\)-arcs by Proposition 20. Let G be an IF \(\nu \)-tree, then, there exists a unique spanning \(\nu \)-tree \(F'\). If (x, y) is not in \(F'\), \(\nu _2(x,y)>\nu _{F'}^{\infty }(x,y)\) and by Proposition 19, we have \(\nu _{F'}^{\infty }(x,y)=\nu {'}_2^{\infty }(x,y)\). It follows that \(\nu _2(x,y)>\nu {'}_2^{\infty }(x,y)\). Therefore, G is not an IF \(\nu \)-cycle. Conversely, suppose that G is not an IF \(\nu \)-tree. Then, for an arbitrary arc (u, v) in G, there exists a unique \((u-v)\) path \(P=G-(u,v)\) in G so that \(\nu _2(u,v)\le \nu _P^{\infty }(u,v)\). It follows that there is no unique weakest \(\nu \)-arc in G. Hence, G is an IF \(\nu \)-cycle. □
Corollary 24
Let an IFG \(G=(V,E)\) be a cycle. If G is an IFC, then G is not an IFT.
Proof
If G is an IFC, then G is an IF \(\mu \)-cycle or IF \(\nu \)-cycle. Let G be an IF \(\mu \)-cycle, then, G is not an IF \(\mu \)-tree by Theorem 22. Hence, G is not an IFT. Let G be an IF \(\nu \)-cycle, then G is not an IF \(\nu \)-tree by Theorem 23. Hence, G is not an IFT. This completes the proof. □
Remark 11
The converse of Corollary 24 is not true. In Example 7, G is neither an IFT nor an IFC.
Example 7
In Fig. 7, let \(G=(V,E)\) be an IFG, so that \(V=\lbrace x,u,v,w,z\rbrace \), \(E=\lbrace (x,u),(x,v),(u,w),(v,z),(w,z)\rbrace \). Then, the arcs (x, v), (w, z) and (u, w) are \(\alpha _{\mu }\)-strong and \(\alpha _{\nu }\)-strong, the arc (x, u) is \(\delta _{\mu }\)-arc and \(\alpha _{\nu }\)-strong, the arc (v, z) is \(\alpha _{\mu }\)-strong and \(\delta _{\nu }\)-arc. Hence, G is an IF \(\mu \)-tree and IF \(\nu \)-tree, but it is not an IFT, because \(F=F'\). Also, G is not an IFC.
7 Questions
Now we try to answer the following questions:
-
(1)
How can we recognize an intuitionistic fuzzy tree?
-
(2)
How much can we change the degree of membership and non-membership of arcs from an intuitionistic fuzzy tree G until G stops being an IFT?
For Question 1, we can easily recognize by Theorem 25, Theorem 26, and Corollary 27. Also we can obtain a unique spanning \(\mu \)-tree, a unique spanning \(\nu \)-tree, and a unique spanning tree by Proposition 28.
Theorem 25
Let \(G=(V,E)\) be a \(\mu \)-connected IFG. Then, G is an IF \(\mu \)-tree if and only if it has no \(\beta _{\mu }\)-strong arcs.
Proof
It follows from [31]. □
Theorem 26
Let \(G=(V,E)\) be a \(\nu \)-connected IFG. Then, G is an IF \(\nu \)-tree if and only if it has no \(\beta _{\nu }\)-strong arcs.
Proof
Let \(G=(V,E)\) be an IF \(\nu \)-tree and let \(F'\) be the unique spanning \(\nu \)-tree of G. Then, all arcs in \(F'\) are \(\alpha _{\nu }\)-strong by Theorem 14. Suppose that (x, y) is a \(\beta _{\nu }\)-strong arc in G, then, (x, y) is not in \(F'\). Hence, \(\nu _2(x,y)>\nu _{F'}^{\infty }(x,y)\). Also, we have \(\nu _{F'}^{\infty }(x,y)=\nu {'}_2^{\infty }(x,y)\), by Proposition 19. It follows \(\nu _2(x,y)>\nu {'}_2^{\infty }(x,y)\). Hence, (x, y) is a \(\delta _{\nu }\)-arc, which is a contradiction. Therefore, G has no \(\beta _{\nu }\)-strong arcs. Conversely, suppose that G has no \(\beta _{\nu }\)-strong arcs. If G has no \(\nu \)-cycles, then, G is an IF \(\nu \)-tree, by Theorem 23. Now assume that G has \(\nu \)-cycles. Let C be a \(\nu \)-cycle in G. Then, C will contain only \(\alpha _{\nu }\)-strong arcs and \(\delta _{\nu }\)-arcs. Also, all arcs of C can not be \(\alpha _{\nu }\)-strong, thus, there exists one \(\delta _{\nu }\)-arc in C. By deleting \(\delta _{\nu }\)-arcs in G, we have an IFSS, S. We claim that S is a spanning \(\nu \)-tree of G. By Proposition 2, between every vertices of G there exists a \(\nu \)-strong path. Also by deleting \(\delta _{\nu }\)-arcs, we do not have any \(\nu \)-cycles in G. Let (x, y) be not be in S, then, \(\nu _2(x,y)>\nu {'}_2^{\infty }(x,y)\). All arcs in S are \(\alpha _{\nu }\)-strong, hence the \(\nu \)-path between x, y is the \(\nu \)-strongest \((x-y)\) path by Proposition 4. Therefore, \(\nu _S^{\infty }(x,y)=\nu {'}_2^{\infty }(x,y)\). It follows that \(\nu _2(x,y)>\nu _S^{\infty }(x,y)\). Hence, G is an IF \(\nu \)-tree. □
Corollary 27
Let \(G=(V,E)\) be an IFG. If Gis an IFT, then G has no \(\beta _{\mu }\)-strong and \(\beta _{\nu }\)-strong arcs.
Remark 12
The converse of Corollary 27, is not true. In Figure 7, G is an IF \(\mu \)-tree and IF \(\nu \)- tree, hence it has no \(\beta _{\mu }\)-strong and \(\beta _{\nu }\)-strong, but G is not an IFT, because \(F\ne F'\).
Proposition 28
Let \(G=(V,E)\) be an IFG, then,
-
(i)
If G is an IF \(\mu \)-tree, then a unique spanning \(\mu \)-tree F gets from deleting of \(\delta _{\mu }\)-arcs.
-
(ii)
If G is an IF \(\nu \)-tree, then a unique spanning \(\nu \)-tree F gets from deleting of \(\delta _{\nu }\)-arcs.
-
(iii)
If G is an IFT, then a unique spanning tree \(F''\) gets from deleting of \(\delta _{\mu }\)-arcs or \(\delta _{\nu }\)-arcs.
Proof
-
(i)
By Theorem 25, if G is an IF \(\mu \)-tree, then has no \(\beta _{\mu }\)-strong arcs. Also all arcs in F are \(\alpha _{\mu }\)-strong, by Theorem 12. Hence, all arcs are \(\delta _{\mu }\)-arcs and F are achieved by deleting all \(\delta _{\mu }\)-arcs.
-
(ii)
It is similar to (i).
-
(iii)
It follows (i) and (ii).
□
To answer Question 2, we discuss the following propositions. We also consider various cases of arcs in an intuitionistic fuzzy tree.
Proposition 29
Let \(G=(V,E)\) be an intuitionistic fuzzy tree and F be the unique spanning \(\mu \)-tree of G. If IFG \(G'\) is obtained from G by increasing the degree of membership of \((x,y)\in V\times V\setminus F\) up to \(\mu _{G-(x,y)}^{\infty }(x,y)\), then, \(G'\) is IFT.
Proof
For an arc \((x,y)\in V\times V\setminus F\), we consider \(\mu {'}_2(x,y)<\mu _{G-(x,y)}^{\infty }(x,y)\) so that \(\mu {'}_2(x,y)\le 1-\nu _2(x,y)\), which \(\mu {'}_2(x,y)\) is the degree of membership the arc (x, y) in \(G'\). Also, \(\mu _{G-(x,y)}^{\infty }(x,y)=\mu _{G'-(x,y)}^{\infty }(x,y)\) implies that \(\mu {'}_2(x,y)<\mu _{G'-(x,y)}^{\infty }(x,y)\). Thus, (x, y) is a \(\delta _{\mu }\)-arc in \(G'\). Also, for other arcs (u, v) in G, we have \(\mu _{G-(u,v)}^{\infty }(u,v)=\mu _{G'-(u,v)}^{\infty }(u,v)\). Hence, the type of all areas in G does not change with the increase of the degree of membership of (x, y). So, F is a unique spanning \(\mu \)-tree of \(G'\). Thus, \(G'\) is an IFT. This completes the proof. □
Proposition 30
Let \(G=(V,E)\) be an intuitionistic fuzzy tree and F be the unique spanning \(\nu \)-tree of G. If IFG \(G'\) is obtained from G by reducing the degree of non-membership of \((x,y)\in V\times V\setminus F\) down to \(\nu _{G-(x,y)}^{\infty }(x,y)\), then, \(G'\) is IFT.
Proof
For an arc \((x,y)\in V\times V\setminus F\), we consider \(\nu {'}_2(x,y)>\nu _{G-(x,y)}^{\infty }(x,y)\) so that \(\nu {'}_2(x,y)\le 1-\mu _2(x,y)\), in which \(\nu {'}_2(x,y)\) is the degree of non-membership of the arc (x, y) in \(G'\). Also, \(\nu _{G-(x,y)}^{\infty }(x,y)=\nu _{G'-(x,y)}^{\infty }(x,y)\) implies that \(\nu {'}_2(x,y)>\nu _{G'-(x,y)}^{\infty }(x,y)\). Thus (x, y) is a \(\delta _{\nu }\)-arc in \(G'\). Also for other arcs (u, v) in G, we have \(\nu _{G-(u,v)}^{\infty }(u,v)=\nu _{G'-(u,v)}^{\infty }(u,v)\). Hence, the type of all arcs in G does not change with the reduction of the degree of non-membership of (x, y). Hence, \(F'\) is a unique spanning \(\nu \)-tree of \(G'\). Thus, \(G'\) is an IFT. This completes the proof. □
Proposition 31
Let \(G=(V,E)\) be an intuitionistic fuzzy tree and F be the unique spanning \(\mu \)-tree of G. If IFG \(G'\) is obtained from G, replacing \(\mu _{G-(x,y)}^{\infty }(x,y)\) by \(\mu _2(x,y)\), for an arc \((x,y)\in V\times V\setminus F\), so that \(\mu _{G-(x,y)}^{\infty }(x,y)\le 1-\nu _2(x,y)\), then, \(G'\) is not an IFT.
Proof
For the arc \((x,y)\in V\times V\setminus F\), we consider \(\mu {'}_2(x,y)=\mu _{G-(x,y)}^{\infty }(x,y)\). We also have \(\mu _{G-(x,y)}^{\infty }(x,y)=\mu _{G'-(x,y)}^{\infty }(x,y)\). Then, \(\mu {'}_2(x,y)=\mu _{G'-(x,y)}^{\infty }(x,y)\). Hence, there exists a \(\beta _{\mu }\)-strong arc in \(G'\). Thus, \(G'\) is not an IFT, by Theorem 25. □
Proposition 32
Let \(G=(V,E)\) be an intuitionistic fuzzy tree and F be the unique spanning \(\nu \)-tree of G. If IFG \(G'\) is obtained from G, replacing \(\nu _{G-(x,y)}^{\infty }(x,y)\) by \(\nu _2(x,y)\), for an arc \((x,y)\in V\times V\setminus F\), so that \(\nu _{G-(x,y)}^{\infty }(x,y)\le 1-\mu _2(x,y)\), then, \(G'\) is not an IFT.
Proof
For the arc \((x,y)\in V\times V\setminus F\), we consider \(\nu {'}_2(x,y)=\nu _{G-(x,y)}^{\infty }(x,y)\). Also, we have \(\nu _{G-(x,y)}^{\infty }(x,y)=\nu _{G'-(x,y)}^{\infty }(x,y)\). Then, \(\nu {'}_2(x,y)=\nu _{G'-(x,y)}^{\infty }(x,y)\). Hence, there exists a \(\beta _{\nu }\)-strong arc in \(G'\). Therefore, \(G'\) is not an IFT, by Theorem 26. □
8 Applications of Intuitionistic Fuzzy Tree in Other Sciences
8.1 Road Transport Network
Road transport network can be represented by an intuitionistic fuzzy tree, because there exists the labeling data for nodes as location, the degree of importance and etc., and for arcs as length, width, traffic, quality and etc., so the best way to represent a road transport network is using intuitionistic fuzzy tree such that the nodes and the arc, represent points and route between them, respectively. One of the most widely used algorithms in these networks is Dijkstra’s algorithm. Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a road transport network. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published 3 years later. The shortest path algorithm is widely used in network routing protocols. A more common variant of Dijkstra’s algorithm fixes a single node as the “source” node and finds the shortest paths from the source to all other nodes in the graph. Hence here, distance of source node will be very useful because in addition to finding the shortest paths, selected the most valuable them.
8.2 In Stock Markets
Time series data are of growing importance in many new database applications such as data mining. A time series is a sequence of real numbers, each number representing a value at a time point. For example, the sequence could represent stock or commodity prices, sales, exchange rates, weather data, biomedical measurements, etc. For example, we may want to find stocks that behave in approximately the same way (or approximately the opposite way) for hedging; or products that had similar selling patterns during the last year; or years when the temperature patterns in two regions of the world were similar. In queries of this type, approximate, rather than exact, matching is required. Most of the existing data mining techniques are not so efficient to dynamic time series databases. However, mining different queries from huge time-series data is one of the important issues for researchers. Intuitionistic Fuzzy Tree for unpredictable dynamic stock exchange databases has been constructed using weighted fuzzy production rules (WFPR). In WFPR, a weight parameter is assigned to each proposition in the antecedent of a fuzzy production rule (FPR) and a certainty factor (CF) is assigned to each rule. It is based on minimum classification information entropy to select expanded attributes. In similarity-based fuzzy reasoning method, we analyze WFPR’s which are extracted from FDT. The analysis is based on the result of consequent drawn for different given facts (e.g. variables that can affect stock markets) of the antecedent. Certainty factors have been calculated using some important variables (e.g. effect of other companies, effect of other stock exchanges, effect of overall world situation, effect of political situation etc.) in dynamic stock markets. Some advantages, such as accurate stock prediction, efficiency and comprehensibility of the generated WFPR’s rules, are important to data mining. These WFPRs allow us to effectively classify patterns of non-axis parallel decision boundaries using membership functions properly, which is difficult to do using attribute-based classification methods.
8.3 Intrusion Detection Systems (IDS)
Developing effective methods for the detection of intrusions and misuses is essential for assuring system security. Various approaches to intrusion detection are currently being in use with each one having its own merits and demerits. The objective of this study is to test and improve the performance of a new class of decision tree-based IDS, as explained in [38]. The C-fuzzy decision trees are classification constructs that are built on a basis of information granules fuzzy clusters. The way in which these trees are constructed deals with successive refinements of the clusters (granules) forming the nodes of the tree. When growing the tree, the nodes (clusters) are split into granules of lower diversity (higher homogeneity). The performance, robustness, and usefulness of classification algorithms are improved when relatively few features that are involved in the classification. Thus, selecting relevant features for the construction of classifiers has received a great deal of attention. Several approaches to feature selection have been explored. The purpose is to identify best candidate feature subset in building the C-fuzzy decision tree IDS that is computationally efficient and effective. The usefulness of a C-fuzzy decision tree for developing IDS with data partition is based on horizontal fragmentation. The focus is on improving the performance by reducing the number of features and selecting more appropriate data set. It is evident from the results that our data partition and feature selection technique result in an improved C-fuzzy decision tree to build an effective IDS.
9 Conclusion
It is well known that graphs are among the most ubiquitous models of both natural and human made structures. Fuzzy graph theory has numerous applications in modern sciences and technology, especially in the fields of operations research, neural networks, artificial intelligence and decision making. The concepts of intuitionistic fuzzy graphs can be applied in various areas of engineering, computer science: database theory, expert systems, neural networks, signal processing, pattern recognition, robotics, computer networks, and medical diagnosis. In this paper, the concepts of IFT, IFC, IFB, IFCN, and the types of arcs in an IFG have been investigated. We plan to extend our research of fuzzification to connectivity of an IFG.
References
Akram, M., Davvaz, B.: Strong intuitionistic fuzzy graphs. FILOMAT 26(1), 177–196 (2012)
Akram, M.: Level graphs of intuitionistic fuzzy graphs. Ann. Fuzzy Math. Inf. 16(1), 55–70 (2018)
Akram, M., Alshehri, N.: Intuitionistic fuzzy cycles and intuitionistic fuzzy trees. Sci. World J. 305836, 11 (2014)
Alzebdi, M., Chountas, P., Atanassov, K.: Approximate XML query matching and rewriting using intuitionistic fuzzy trees. In: 2012 6th IEEE International Conference Intelligent Systems, vol. 3, IEEE, Sofia, Bulgaria (2012)
Atanassov, K.: Intuitionistic Fuzzy Sets: Theory and Applications. Physica-Verlag, New York (1999)
Atanassov, K.: Research on intuitionistic fuzzy sets in Bulgaria. Fuzzy Sets Syst. 22(1/2), 193 (1987)
Atanassov, K.: Review and new results on intuitionistic fuzzy sets. Preprint IM-MFAIS-1-88, Sofia, (1988)
Atanassov, K.: More on intuitionistic fuzzy sets. Fuzzy Sets Syst. 33(1), 37–45 (1989)
Atanassov, K.: On intuitionistic fuzzy graphs and intuitionistic fuzzy relations. In: Proceedings of the VI IFSA World Congress, Sao Paulo, Brazil, July 1995, 1, 551–554 (1995)
Atanassov, K.: Temporal intuitionistic fuzzy graphs. Notes on IFS 4(4), 59–61 (1998). http://ifigenia.org/wiki/issue:nifs/4/4/59-61
Atanassov, K.: Intuitionistic Fuzzy Sets. Springer Physica-Verlag, Berlin (1999)
Atanassov, K.: Index matrix representation of the intuitionistic fuzzy graphs. In: Fifth Scientific Session of the Mathematical Foundations of Artificial Intelligence Seminar, Sofia, vol 20, pp. 36–41. Preprint MRL-MFAIS-10-94 (1994)
Atanassov, K.: On index matrix interpretations of intuitionistic fuzzy graphs. Notes Intuit. Fuzzy Sets 8(4), 73–78 (2002)
Bujnowski, P., Szmidt, E., Kacprzyk, J.: Intuitionistic fuzzy decision tree: a new classifier. In: Angelov, P., et al. (eds.) Intelligent Systems’2014., Advances in Intelligent Systems and Computing, 322. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-11313-5-68
Bhattacharya, P.: Some remarks on fuzzy graphs. Pattern Recognit. Lett. 6, 297–302 (1987)
Bhutani, K.R.: On automorphism of Fuzzy graphs. Pattern Recognit. Lett. 9, 159–162 (1989)
Bhutani, K.R., Rosenfeld, A.: Fuzzy end nodes in fuzzy graphs. Inf. Sci. 152, 323–326 (2003)
Bhutani, K.R., Rosenfeld, A.: Strong arcs in fuzzy graphs. Inf. Sci. 152, 319–322 (2003)
Bhutani, K.R., Battou, A.: On M-strong fuzzy graphs. Inf. Sci. 155, 103–109 (2003)
Bondy, J.A., Murthy, U.S.R.: Graph Theory with Applications. American Elesevier Publishing Co., New York (1976)
Chountas, P., Alzebdi, M., Shannon, A., Atanassov, K.: On intuitionistic fuzzy trees. Notes Intuit. Fuzzy Sets 15(2), 30–32 (2009)
Chountas, P., Shannon, A., Rangasamy, P., Atanassov, K.: On intuitionistic fuzzy trees and their index matrix interpretation. Notes Intuit. Fuzzy Sets 15(4), 52–56 (2009)
Chountas, P., Alzebdi, M., Shannon, A., Atanassov, K.: On intuitionistic fuzzy trees. In: Thirteenth Int. Conf. on IFSs, Sofia, 9–10 May 2009 NIFS Vol. 15, 2, 30–32 (2009)
Karunambigai, M.G., Parvathi, R.: Intuitionistic fuzzy graphs. In: Proceedings of 9th fuzzy Days International Conference on Computational Intelligence, Advances in Soft Computing: Computational Intelligence, Theory and Applications, Springer-Verlag, 20, 139–150 (2006)
Karunambigai, M.G., Akram, M., Sivasankar, S., Palanivel, K.: Clustering algorithm for intuitionistic fuzzy graphs. Internat. J. Uncertain. Fuzziness Knowl.-Based Syst. 25(3), 367–383 (2017)
Karunambigai, M.G., Akram, M., Buvaneswari, R.: Strong and superstrong vertices in intuitionistic fuzzy graphs. J. Intell. Fuzzy Syst. 30, 671–678 (2016)
Karunambigai, M.G., Parvathi, R., Kalaivani, O.K.: A study on Atanassov intuitionistic fuzzy graphs. In: Conference Paper in IEEE International Conference on Fuzzy Systems June 2011, https://doi.org/10.1109/FUZZY.2011.6007416
Karunambigai, M.G., Rangasamy, P., Atanassov, K., Palaniappan, N.: An intuitionistic fuzzy graph method for finding the shortest paths in networks. In: Castill, O., et al. (eds.) Theoretical Advances and Applications Fuzzy Logic and Soft Computing, pp. 3–10. Springer, Berlin (2007)
Karunambigai, M.G., Parvathi, R., Buvaneswari, R.: Arc in intuitionistic fuzzy graphs. Notes Intuit. Fuzzy Sets 17, 37–47 (2011)
Mahapatra, G.S., Mahapatra, B.S.: Intuitionistic fuzzy fault tree analysis using intuitionistic fuzzy numbers. Int. Math. Forum 5(21), 1015–1024 (2010)
Mathew, S., Sunitha, M.S.: Types of arcs in a fuzzy graph. Inf. Sci. 179(11), 1760–1768 (2009)
Mathew, S., Sunitha, M.S.: Node connectivity and arc connectivity of a fuzzy graph. Inf. Sci. 180(4), 519–531 (2010)
Mordeson, J.N., Peng, C.S.: Operations on fuzzy graphs. Inf. Sci. 79, 159–170 (1994)
Mordeson, J.N.: Fuzzy line graphs. Pattern Recognit. Lett. 14, 381–384 (1993)
Mordeson, J.N., Nair, P.S.: Cycles and co-cycles of fuzzy graphs. Inf. Sci. 90, 39–49 (1996)
Mordeson, J.N., Nair, P.S.: Fuzzy Graphs and Fuzzy Hypergraphs. Physica-Verlag, New York (2000)
Nagoor Gani, A., Shajitha Begum, S.: Degree, order and size in intuitionistic fuzzy graphs. Int. J. Algorithms Comput. Math. 3(3), 11–16 (2010)
Nagoor Gani, A., Akram, M., Shanmugam, A.: Double domination on intuitionistic fuzzy graphs. J. Appl. Math. Comput. 52(1–2), 515–528 (2016)
Parvathi, R., Karunambigai, M.G., Atanassov, K.: Operations on intuitionistic fuzzy graphs. In: Proceedings of IEEE International Conference on Fuzzy Systems (FUZZ-IEEE), 1396–1401 (2009)
Parvathi, R., Shannon, A., Chountas, P., Atanassov, K.: On intuitionistic fuzzy tree-interpretations by index matrices. Notes Intuit. Fuzzy Sets 17(2), 17–24 (2011)
Pasi, G., Yager, Atanassov, K.: Intuitionistic fuzzy graph interpretations of multi-person multi-criteria decision making: generalized net approach. In: Proceedings of Second International IEEE Conference Intelligent Systems, Varna 22–24(2), 434–439 (2004)
Pal, M., Samanta, S., Ghorai, G.: Modern Trends in Fuzzy Graph Theory. Springer, Berlin (2020). https://doi.org/10.1007/978-981-15-8803-7
Rosenfeld, A.: Fuzzy graphs. In: Zadeh, L.A., Fu, K.S., Shimura, M. (eds.) Fuzzy Sets and their Applications to Cognitive and Decision Processes, pp. 77–95. Academic Press, New York (1975)
Rashmanlou, H., Samanta, S., Pal, M., Borzooei, R.A.: Bipolar fuzzy graphs with categorical properties. Int. J. Comput. Intell. Syst. 8(5), 808–818 (2015)
Rashmanlou, H., Samanta, S., Pal, M., Borzooei, R.A.: Product of bipolar fuzzy graphs and their degree. Int. J. Gener. Syst. (2016). https://doi.org/10.1080/03081079.2015.1072521
Rashmanlou, H., Jun, Y.B.: Complete interval-valued fuzzy graphs. Ann. Fuzzy Math. Inf. 6(3), 677–687 (2013)
Rashmanlou, H., Pal, M.: Antipodal interval-valued fuzzy graphs. Int. J. Appl. Fuzzy Sets Artif. Intell. 3, 107–130 (2013)
Rashmanlou, H., Pal, M.: Balanced interval-valued fuzzy graph. J. Phys. Sci. 17, 43–57 (2013)
Rashmanlou, H., Pal, M.: Some properties of highly irregular interval-valued fuzzy graphs. World Appl. Sci. J. 27(12), 1756–1773 (2013). (23)
Rashmanlou, H., Borzooei, R.A.: Product vague graphs and its applications. J. Intell. Fuzzy Syst. 30, 371–382 (2016)
Rashmanlou, H., Samanta, S., Pal, M., Borzooei, R.A.: Intuitionistic fuzzy graphs with categorical properties. Fuzzy Inf. Eng. 7(3), 317–334 (2015)
Sahoo, S., Pal, M.: Intuitionistic fuzzy competition graphs. J. Appl. Math. Comput. 52(1), 37–57 (2016)
Sahoo, S., Pal, M.: Intuitionistic fuzzy tolerance graphs with application. J. Appl. Math. Comput. 55(1), 495–511 (2017)
Sahoo, S., Pal, M.: Product of intuitionistic fuzzy graphs and degree. J. Intell. Fuzzy Syst. 32(1), 1059–1067 (2017)
Sarwar, M., Akram, M.: An algorithm for computing certain metrics in intuitionistic fuzzy graphs. J. Intell. Fuzzy Syst. 30, 2405–2416 (2016)
Shannon, A., Rangasamy, P., Atanassov, K.: On intuitionistic Fuzzy Trees, Developments in Fuzzy Sets, Intuitionistic Fuzzy Sets, Generalized Nets and Related Topics, Vol. I: Foundations, pp. 177–184. SRI Polish Academy of Sciences, Warsaw (2010)
Shannon, A., Atanassov, K.: A first step to a theory of the intuitionistic fuzzy graphs. In: Proc. of the First Workshop on Fuzzy Based Expert Systems (D. Lakov, Ed.), Sofia, Sept. 28–30, 59–61 (1994)
Shannon, A., Atanassov, K.: Intuitionistic fuzzy graphs from \(\alpha \)-, \(\beta \)- and (\(\alpha \); \(\beta \))-levels. Notes on IFS. 1(1), 32–35 (1995). http://ifigenia.org/wiki/issue:nifs/1/1/32-35
Sunitha, M.S., Vijayakumar, A.: A characterization of fuzzy trees. Inf. Sci. 113, 293–300 (1999)
Sunitha, M.S., Vijayakumar, A.: Blocks in fuzzy graphs. J. Fuzzy Math. 13(1), 13–23 (2005)
Somasundaram, A., Somasundaram, S.: Domination in fuzzy graphs-I. Pattern Recogn. Lett. 19, 787–791 (1998)
Thamizhendhi, G., Parvathi, R.: Intuitionistic fuzzy tree center-based clustering algorithm. Int. J. Soft Comput. Eng. (IJSCE) 6(1), 50–65 (2016)
Yeh, R.T., Bang, S.Y.: Fuzzy relations, fuzzy graphs and their applications to clustering analysis. In: Zadeh, L.A., Fu, K.S., Shimara, M. (eds.) Fuzzy Sets and Their Applications to Cognitive and Decision Processes, pp. 129–149. Academic Press, New York (1975)
Zadeh, L.A.: Fuzzy sets. Inf. Control 8, 338–353 (1965)
Funding
This work was supported by the National Key R & D Program of China (No. 2018YFB1005100) and Guanzhou Academician and Expert Workstation (No.20200115-9).
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflicts of interest
The authors declare that they have no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Rao, Y., Kosari, S., Shao, Z. et al. New Concepts of Intuitionistic Fuzzy Trees with Applications. Int J Comput Intell Syst 14, 175 (2021). https://doi.org/10.1007/s44196-021-00028-7
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s44196-021-00028-7