1. Introduction

Motivation of graph theory is present from Leonhard Euler(1730) paper of the problem for seven bridges of köningsberg. Graphs are very important tools for expressing the relationships among units, which are represented by nodes. Relationships among nodes are expressed by connections. In general, any system involving points and lines among them can be represented as a graph. At present, graph theory is a large field of research for theory and applications both. For, further of graph theory, readers may look into ⁶.

Nowadays, graphs do not represent any systems properly due to the uncertainty or haziness of the parameters of systems. For example, a social network may be expressed as a graph where nodes express an account (person, institution, etc.) and edges represent the relation between the accounts. If the relations among accounts are measured as good or bad according to the frequency of contacts among the accounts, fuzzyness can be added for such representation. This and many other problems lead to define fuzzy graphs. The first concept of a fuzzy graph was established by Kaufmann ⁸ in 1973. But, it was Rosenfeld²⁵ who discussed relations on fuzzy sets and improved the theory of fuzzy graphs in 1975. Using this concept of fuzzy graph, Koczy ¹⁰ used fuzzy graphs in the optimization of networks. For further details of fuzzy graphs, readers may look in ^{7,9,11,12,15,16,17,18,19,20,21,22,23,27}.

There are several types of fuzzy graphs available in the literature. Intuitionistic fuzzy graph ¹⁴, interval-valued fuzzy graphs ¹, and bipolar fuzzy graphs ² are some of them. In all these fuzzy graphs, there is a common property that edge membership value is less than to the minimum of it’s end node membership values. Suppose, a social network is to be represented as fuzzy graphs. Here, all social units are taken as fuzzy nodes. The membership values of the nodes may depend on several parameters. Suppose, the membership values are measured according to the sources of knowledge. The relation between the units is represented by fuzzy edge. The membership value is measured according to the transfer of knowledge. But, transfer of knowledge may be greater than one of the social actors/units as more knowledgeable person informs less knowledgeable person. But, this concept can not be represented in fuzzy graphs as edge membership value should be less than membership values of the end nodes. Thus, all images/networks can not be represented by fuzzy graphs. To remove the restriction, generalized fuzzy graphs are introduced.

In 1999, Sunitha ²⁴ et al characterized the fuzzy trees. They have used the concept of strong edges. This concept depends on all edges of a graph. But, it is comparative and hard to compute for an edge to be strong or not. In this paper, effective edges are defined. Effective edges are easy to compute and non-comparative. According to the effectiveness, trees are defined here. For further details of tree, readers may look into ^13,26. Akram et al. ^3,4,5 defined different types of trees namely soft trees, fuzzy soft tress and bipolar soft trees.

After introductory section, some basic notions are discussed in Section 3. In that section, Generalized fuzzy graphs of type 1 and type 2 (GFG1, GFG2) [Section 3.1] are described with suitable examples. In Section 3.2, generalized fuzzy directed graphs are described. In Section 4, generalized fuzzy trees are introduced. After that, in Section 5, distance function and distance between two nodes are discussed. In Section 6, strongly connected GFGs are described with suitable examples. Here, bridges are also defined. In Section 7, generalized fuzzy directed trees are introduced and some properties are proved. Insights of this study are discussed in the Section 8. At last, conclusion is drawn in Section 9.

2. Problem definition of this work

This study focuses on generalization of fuzzy trees (GFTs) and generalized fuzzy directed trees (GFDTs). In this paper, it is considered that any generalized fuzzy graph (GFG) which is a cycle in crisp sense may be considered as a tree if it fulfills the criteria of trees. Length between two nodes in GFT is to be measured. Also, Strongly connected GFTs will be discussed. Also, the sufficient rule for a cycle to be a GFT will be established.

3. Preliminaries

A fuzzy graph ξ =(U, σ, μ) is a non-void set V with a pair of mappings σ : V → [0, 1] and μ: U × U → [0, 1] as if for each x, y ∈ V, μ(x, y) ⩽ σ(x) ∧ σ(y).

Underline crisp graph of a fuzzy graph ξ = (U, σ, μ) is |ξ| =(U, E) with E = {(x, y)|μ(x, y) ⩾ 0}.

3.2. Generalized fuzzy directed graphs (GFDGs)

The generalized directed fuzzy graph of first kind (GDFG1) is defined below.

Definition 3.

Let V be a non-void set. Two mappings are considered as follows: ρ: V → [0, 1] as well as ω:E→→[0,1] , where E→ be a set of ordered elements of V × V. A={(ρ(x),ρ(y))|ω(x,y)→>0} . The triad (V, ρ, ω) is said to be generalized directed fuzzy graph of first kind (GDFG1) if there exists a mapping ϕ : A → (0, 1] with ω(x,y)→ is equal to ϕ((ρ(x), ρ(y))), where x, y ∈ V.

Example 1.

Let the node set be V = {x, y, z, t} and edge set be {(x,y)→,(x,z),→(t,x)→,(y,t)→} and ρ(x) = 0.2, ρ(y) = 0.9, ρ(z) = 0.3, ρ(t) = 0.8 and ϕ(m, n) = m ∧ n. Here, A = {(0.2, 0.9), (0.2,1.3), (0.8,0.2),(0.9,0.8)}. Then ω(x,y)→=0.2∧0.9=0.2 , ω(x,z)→=0.2 , ω(t,x)→=0.2 , ω(t,y)→=0.8 . The corresponding generalized fuzzy graph is shown in Fig. 1.

Fig. 1.

A generalized directed fuzzy graph of first kind (GDFG1)

Degree of a node x in GDFG1 is the pair (d⁺(x), d⁻(x)) where d⁺(x), out degree of x, is the sum of the generalized membership values of outgoing edges and d^–, in degree of x, is the sum of the generalized membership values of incoming edges. Thus, d+(x)=∑y∈Vω(x,y)→ and d−(x)=∑y∈Vω(y,x)→ . In the Fig. 1, the degree of x is (0.2+0.2, 0.2) which is equal to (0.4, 0.2). The degree of the nodes y, z, t are (0.8, 0.2), (0, 0.2), (0.2, 0.8) respectively.

Note 2 In GDFG1, out degree or in degree of a node may be 0. But, when both are 0 then the node is called null node.

Generalized directed fuzzy graph of second kind (GDFG2) is introduced below.

Definition 4.

Let V be a non-void set. Two mappings are considered as follows: ρ: V → [0, 1] and ω:E→→[0,1] , where E→ be a set of ordered elements of V × V. Also, let B be the range set of ω. The triad (V, ρ, ω) is said to be generalized directed fuzzy graph of second kind (GDFG2) if there exists a mapping ψ: B → (0, 1], for all x ∈ V, ρ(x)= ψ(ω(e_x)) and ex=(x,y)→ or ex=(y,x)→ such that y∈V.

By the Definition, 4 it is true that, if a node has no incoming edge but has outgoing edges, its generalized membership value is 0. Let us discuss this situation with an example.

Example 2.

Now, it is true that V = {a, b, c, d, e}. The edge membership values are given as ((b,a→),0.5) , ((d,a→),0.4) , ((b,c→),0.6) , ((c,d→),0.5) , ((e,c→),0.8) , ((a,e→),0.7) , ((d,e→),0.2) . Here, ψ(x)=max{ω(y,x→)},y∈V . Now, the generalized membership value for such node a is ρ(a) = 0.5 + 0.4 = 0.9 as there are only two directed edges (b,a→),(d,a→) . Similarly, other nodes have the weights as b(0), c(1.4), d(0.5), e(0.9). Thus, the graph of Fig. 2 is GDFG2.

Fig. 2.

A generalized directed fuzzy graph of second kind (GDFG2)

Degree of a node x in GDFG2 (similarly defined) is the pair (d⁺(x), d⁻(x)), where d⁺(x), out degree of x, is the sum of the generalized membership values of outgoing edges and d⁻, in degree of x, is the sum of the generalized membership values of incoming edges. Thus, d+(x)=∑y∈Vω(x,y)→ and d−(x)=∑y∈Vω(y,x→) .

Note 3 In GDFG2, in-degree and (or) out-degree of a node may have chance to be zero. If they are zero, the node is said to null node.

4. Generalized fuzzy trees

In general, if the membership value of an edge is greater than half of its maximum of membership values of its end nodes, the edge is said to be an effective edge. Suppose, someone informs another person about any news. If the transfer of knowledge is greater than to a minimum amount (may be assumed half of the source knowledge), then the second person can be informed effectively. Thus, transfer of knowledge (which indicates the membership value of an edge) helps a person (a node with lower membership value) to get more knowledge from a source (a node with greater membership value). Formal definition of an effective edge is given below.

Note 4 It is obvious that for GFG1, ω(x, y) = ϕ(x, y). Now, if an edge of a generalized fuzzy graph is effective, then other edges may not be effective. The following is the analytic description of this statement. Let ξ be a GFG1 and it has the node set {a(0.8), b(0.2), c(0.3)} and the edge set {(a, b), (b, c)} and ϕ(x, y) = min{x, y}. Then ϕ(a, b) = 0.2, ϕ(b, c)= 0.2. The edge (b, c) is effective as ϕ(b,c)=0.2>12max{b,c}=1.5 . Thus, the edge (a, b) is not effective.

A GFG ξ′ =(V′, ρ′, ω′) is a subgraph of ξ = (V, ρ, ω), if V′ ⊂ V, ρ′: V′ → [0, 1] as well as ω′: E′→ [0,1], where E′ ⊂ V′ × V′ such that ρ′ (x) ⩽ ρ(x) as well as ω′ (x, y) ⩽ ω(x, y). Spanning subgraphs contain all nodes of the graph. If all the edges of the spanning subgraph are effective, then the sub-graph is called effective spanning subgraph. Now, the definition of generalized fuzzy trees (GFTs) is introduced below. In this study, if a GFG is mentioned, it is connected in crisp sense, i.e. all nodes are connected by a path whether the edges of the path may be effective or not.

Fig. 3.

A GFT (dotted lines are not effective).

In classical theory of graphs, crisp trees with n nodes have n − 1 edges. But, GFT of n nodes may contain more than n − 1 edges. The graph may contain a cycle in crisp sense. The following statement describes the consequence of the theorem of classical theory.

Note 5 A GFT of n nodes contains n − 1 effective edges.

The reverse of the statement is not true. A graph may have n − 1 effective edges but still not GFT. For example, in Fig. 4, there are 3 effective edges of a GFG with 4 nodes. As an effective spanning sub-graph is not found in the graph, the graph can not be a GFT.

Fig. 4.

A GFG with 4 nodes and 3-effective edges but not GFT

If underline graph of a GFG is a crisp cycle, then the GFG is called a cycle. Every such cycle may be a GFT. This statement can be established from the following theorem.

Conversely, let ξ =(V, ρ, ω) be a cycle and it has only one non-effective edge. If the non-effective edge is removed from the cycle, it becomes a tree in crisp sense. Also, all the edges of the spanning subgraph are effective and it includes all the nodes of the graph. Hence, ξ is a GFT.

Note 6 The converse of the statement is not correct. Suppose a GFG has 4 nodes, then it may have maximum 6 edges. If it has (4−1)(4−2)2=6 non-effective edges, it may not be GFT.

5. Length between two nodes in GFT

The definition of distance mapping is given below.

Paths are very important and useful concept in graphs. One node may not be connected directly. By different paths, many nodes may be connected. In fuzzy graphs, paths are of different types. A path is said to be strong if all edges of the path are effective. Otherwise, i.e. at least one edge is not effective, the path is called weak path. Now, the lengths between two nodes are stated as follows:

Note 7 Triangle inequality does not hold for fuzzy length.

This statement is verified in the Example 4. Here, D(b, d) = 0.62, D(b, c) = 0.285, D(c, d) = 0.333. Thus, D(b, d) = D(b, c) + D(c, d).

The centre of a GFG is defined below. Let ξ = (V, ρ, ω) be a GFG. The centre of the GFG is the set of nodes whose lengths from farthest nodes are minimum. Now for large networks, it is convenient that the nodes with approximately same lengths from farthest nodes are to be considered. Before the formal definition of centre, definition of farthest nodes from a node are defined here.

Radius and diameter are also defined. Radius is the length from the center(s) to the farthest node in a GFG. On the other hand, diameter is the length measurement between two end nodes of a longest path (a path with maximum length).

6. Strongly connected GFG and spanning GFT

In this paper, it is assumed that a tree may contain effective and non-effective edges. It is known that a spanning tree includes all nodes of the graph.

Thus, every GFG may or may not contain spanning tree. Here, connectivity of a graph is represented in terms of spanning tree. The following study introduces two concepts namely, strongly connected and nearly disconnected GFG.

Let ξ = (V, ρ, ω) be a GFG. If the GFG has a spanning tree, then it is strongly connected (Type 1). If GFG does not contain any spanning tree, then the graph may contain one or more trees as sub-graphs. In that case, two cases may arise. Some nodes are not incident to effective edges. Suppose, every such node, say x, is connected by some non-effective edges, say (x, y₁), (x, y₂), ..., (x, y_m) with the rule ∑i=1mω(x,yi)ρx∨ρ(yi)≥0.5 . Then the graph is strongly connected (Type 2). There is another case, where some non-effective edges connects two trees in a GFG, i.e. one end node of such edges lies in one tree and other in another tree. Suppose the edges are (x₁, y₁), (x₂, y₂), ..., (x_p, y_p). Now, if ∑i=1pω(xi,yi)ρxi∨ρ(yi)≥0.5 , then the GFG is called strongly connected (Type 3).

Fig. 5.

Strongly connected GFGs

On the other hand, weakly connected graphs are the graphs which are not strongly connected. Now, nearly disconnected graphs are defined below. Let ξ = (V, ρ, ω) be a GFG. Let ε be a small positive number such that 0 < ε < 0.5. If the graph contains a spanning GFT, then the graph is strongly connected. If a graph does not contain an effective spanning tree, there may arise two cases. Firstly, some nodes are not incident to effective edges. Suppose, every such node, say x, is connected by some non-effective edges, say (x, y₁), (x, y₂), …, (x, y_m) such that ∑i=1mω(x,yi)ρx∨ρ(yi)≤ɛ . Then, the graph is nearly disconnected. In the last case, there may be some non-effective edges which connects two trees in a GFG, i.e. one end node of such edges lies in one tree and other end in another. Suppose the edges are (x₁, y₁), (x₂, y₂), ..., (x_p, y_p). Now, if ∑i=1pω(xi,yi)ρxi∨ρ(yi)≤ɛ , then also the GFG is called nearly disconnected.

Fig. 6.

An example of nearly disconnected graph

In the theory of graphs, bridges are such edges whose removal disconnects the graphs. Now, bridge in GFG is introduced as follows:

Fig. 7.

A bridge in GFG

It is easy to state that a GFT whose underline graph is cycle, has only one non-effective edge. If another edge is non-effective, then the graph has the following property.

7. Generalized fuzzy directed trees

The definition of generalized fuzzy directed trees (GFDTs) can be similarly introduced. A GFDG is said to be GFDT, if it has effective spanning directed tree.

A GFDT is shown in Fig. 8. Here, dotted lines are non-effective edges. Thus, in GFDT, there is no cycle whose all edges are effective.

Fig. 8.

Generalized directed fuzzy trees

In GFDT, there is one node whose in-degree is less than all other nodes. In GFDT, there is a node in which all effective edges are out-coming and incoming edges are non-effective, if there be any. This special node is known as root of GFDT. The information regarding the in-degree nodes in GFDT, can be found in the following theorem.

8. Insights for this study

• •

  GFTs are introduced. Cycles in crisp sense are not assumed as trees, but in this case if the cycle has one weak edge, it may be assumed as trees.

• •

  Length within nodes in GFT is introduced. Depending on the definition, centre and radius are described.

• •

  Strongly connected trees and spanning trees are discussed. Thus, a cycle may be assumed as spanning tree but strongly connected cycle is not considered as spanning trees. This is the importance of strongly connected graphs.

• •

  The rule of a cycle to be tree is established. The rule of a GFG to be nearly disconnected is also provided.

• •

  Generalized fuzzy bridge is described. Also, GFDTs are defined and some properties are given.

9. Conclusions

This study described a major part of generalized fuzzy graphs known as generalized fuzzy trees. Length between two nodes were assumed as effectiveness of the corresponding edges. Also, the length may be measured by some other ways depending the application and expert opinion. Strongly connected and nearly disconnected graphs were discussed. For nearly disconnected GFG, it was assumed that ε satisfies the inequality 0 < ε ⩽ 0.5. This assumption could be changed as per application. According to different situations ε can be changed. Also, bridges in GFG were discussed. For an image representation, objects were assumed as effective edges, and backgrounds were taken as the non-effective edges in GFGs. In Wassenberg algorithm and earlier algorithms, objects are taken as crisp spanning. So these algorithms are based on backgrounds (taking value 0) and objects (taking value 1). If the image is converted to GFG, then objects are considered as spanning fuzzy tree and backgrounds may be taken as part of GFG which are constructed by non-effective fuzzy edges. Then, steps of the algorithms will be changed. So our aim, in near future, is to modify the algorithms. These theoretical developments will help larger fields of computer vision.