A study on generalized fuzzy graphs

1 Introduction

Nowadays, graphs do not represent all the networks properly due to the uncertainty or haziness of the parameters of networks. For example, a social network may be represented as a graph where vertices represent 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, fuzziness can be added for such representation. This and many other problems lead to define fuzzy graphs. The first definition of a fuzzy graph was by Kaufmann [7] in 1973. But, it was Rosenfeld [21] who considered fuzzy relations on fuzzy sets and developed the theory of fuzzy graphs in 1975. Using this concept of a fuzzy graph, Koczy [8] used fuzzy graphs in the evaluation and optimization of networks. Though fuzzy graphs can represent all systems, Samanta and Pal [18] showed that fuzzy graphs can be used in competition in ecosystems. For further details of fuzzy graphs, readers may look in [1–6, 17]. Applications of fuzzy graph include data mining, image segmentation, clustering, image capturing, networking, communication, planning, scheduling, etc.

Fuzzy graphs have a property that edge membership value is less than to the minimum of its end vertex 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 vertices 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 edges. 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 cannot be represented in fuzzy graphs as edge membership value should be less than membership values of the end vertices. Thus, all images/networks cannot be represented by fuzzy graphs. To remove the restriction, generalized fuzzy graphs (directed and un-directed) are introduced [16, 19] and this graph are suitable to represent images/ networks.

In computer vision, image segmentation is the process of partitioning an image into multiple segments (sets of pixels). The purpose of segmentation is to simplify and to change the representation of an image into a figure that is more meaningful and easier to analyse. Image segmentation is the process of assigning a label to every pixel in an image such that pixels with the same label share certain properties. A segmentation maps each image element to exactly one object class in crisp concept. A fuzzy segmentation allows an image to belong to many different object classes partially. One common way to represent a segmentation is cut in generalized fuzzy graphs.

In this study, the first step in image segmentation, i.e. fuzzy r-cuts on generalized graphs are introduced and analyzed. In Section 3, some basic definitions along with a list of previous works are described. In this section, generalized fuzzy graphs of two kinds, generalized directed fuzzy graphs of two kinds are introduced with examples. Then, estimation of membership values is explained. Also, pipeline networks are represented by generalized directed fuzzy graphs. Fuzzy r-cuts and fuzzy (r₁, r₂, …, r _n )-cuts are introduced in Section 5. In Section 7, image segmentation is analyzed with the help of generalized fuzzy graphs. In Section 8, insights of this study are given. At last, the conclusion is drawn in Section 9.

This study focuses on a generalization of graphs. Flow and cuts are discussed for a pipeline. Also, the relation between the vertex and edge membership values are to be found out. The estimations of membership values are to be done. Fuzzy r-cut in generalized fuzzy graphs are introduced. Also, some area of applications is discussed.

3 Generalized fuzzy graphs

A graph is an ordered pair G = (V, E) comprising a set V of vertices or nodes together with a set E of edges or lines, which are 2-element subsets of V. A fuzzy graph ξ = (V, σ, μ) is a non-empty set V together with a pair of functions σ : V → [0, 1] and μ : V × V → [0, 1] such that for all x, y ∈ V, μ (x, y) ≤ σ (x) ∧ σ (y), where σ (x) and μ (x, y) represent the membership values of the vertex x and of the edge (x, y) in ξ respectively. A loop at a vertex x in a fuzzy graph is represented by μ (x, x) ≠0. An edge is non-trivial if μ (x, y) ≠0. A cofuzzy graph G = (V, σ′, μ′) is a non-empty set V together with a pair of functions σ′ : V → [0, 1] and μ′ : V × V → [0, 1] such that for all x, y ∈ V, μ′ (x, y) ≥ σ′ (x) ∨ σ′ (y).

Here, generalized fuzzy graphs are defined. The membership values of vertices of graphs depend on membership values of the adjacent edges. For isolated vertices, the membership values of vertices are taken as 0. The membership function is defined from a non-empty set to a closed interval [0, 1]. Thus, any linguistic term can be defined by membership values. Sometimes, vertex membership values are considered first and depending on vertex membership values, the edge membership values can be considered. For example, social networks, where social actors and its stability are considered first. Depending on stability, vertex membership values are given. After that, the relation among the actors is considered. The membership values may be taken from the parameter ‘relationship’. Again, in some problems, edges are considered first and depending on edge membership values the vertex membership values are considered. For example, capacities of pipelines can be taken as edge membership values. Depending on the capacities vertex membership values are decided.

Thus, two types of relations are to be considered. In the following, generalized fuzzy graphs of the first kind will be defined. Here, vertex membership values are considered first. Then, depending on vertex membership values, edge membership values are considered.

Definition 1. [16] Let V be a non-empty set. Two functions are considered as follows. ρ : V → [0, 1] and ω : V × V → [0, 1]. Also, let A = {(ρ (x) , ρ (y)) |ω (x, y) >0}. The triad (V, ρ, ω) is said to be generalized fuzzy graph of first kind (GFG1) if there exists a function φ : A → (0, 1] such that ω (x, y) = φ ((ρ (x) , ρ (y))) where x, y ∈ V. Here ρ (x) , x ∈ V is the membership value of the vertex x and ω (x, y) , x, y ∈ V is the membership value of the edge (x, y).

Now, generalized fuzzy graphs of second kind is defined. Here, the membership values of edges are considered first. Then, depending on edge membership values, vertex membership values of vertices are assigned.

Definition 2. [16] Let V be a non-empty set. Two functions are considered as follows. ρ : V → [0, 1] and ω : V × V → [0, 1]. Also, let B be the range set of ω. The triad (V, ρ, ω) is said to be generalized fuzzy graph of second kind (GFG2) if there exists a function ψ : B → (0, 1] such that for all x ∈ V, ρ (x) = ψ (ω (e _x )) where e _x  = (x, y) such that y ∈ V. Here, ρ (x) , x ∈ V is the membership values of the vertex x and ω (x, y) is the generalized membership value of the edge (x, y).

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

Definition 3. Let V be a non-empty set. Two functions are considered as follows. ρ : V → [0, 1] and ω : 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 function φ : A → (0, 1] such that ω ( x , y ) → = φ ( ( ρ ( x ) , ρ ( y ) ) ) where x, y ∈ V. Here ρ (x) , x ∈ V are membership value of the vertex x and ω ( x , y ) → is the membership value of directed edge ( x , y ) → .

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

Definition 4. Let V be a non-empty set. Two functions are considered as follows. ρ : V → [0, 1] and Let ω : 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 function ψ : B → (0, 1] such that for all x ∈ V, ρ (x) = ψ (ω (e _x )) where e x = ( x , y ) → or e x = ( y , x ) → such that y ∈ V.

4 Estimation of membership functions

One of the problems of fuzzy modelling is how to find best-suited rule base for a certain system. In most cases, there is no human expert. So, some automatic methods to find the fuzzy rule base must be introduced. Some of these methods were found in nature. Apart from the evolutionary methods, in the area of networks, there are algorithms known and these can be applied to fuzzy systems as well. These are useful when there are only numerical data about the problem. Generalized fuzzy graphs are introduced in the Section 3. Membership functions for vertices and edges are defined precisely. These functions will vary for different problems. No automatic method is available to find optimal membership function. Depending on nature of the problems, membership functions can be incorporated empirically. To find the membership functions of vertices and edges and to relate them, the following sequences must be maintained. Firstly, any problem must be represented by crisp graphs. That is, it is to be found out which parts are represented by vertices and which parts are represented by edges. Secondly, the relationship between vertices and edges are clearly specified. Here, the parameter of relationship should be found out. Lastly, the membership functions are constructed.

For GFG1, the relation between edge and vertex membership values are connected by φ : A → (0, 1] such that ω (x, y) = φ ((ρ (x) , ρ (y))) where x, y ∈ V. Here, the domain of φ is the set A of a pair of elements of ρ such that the pair of vertices is adjacent. Now, an element of A is related to an edge membership value. Suppose, an image is to be represented by GFG1. Pixels are taken as vertices and adjacent vertices are connected by edges. Here, vertex membership values are measured by the contrast of the pixels. Now, the question is “how will φ be constructed?" For example, φ can be assumed as φ (x, y) = |x - y| where x, y are the membership values of vertices. This function will measure the difference of the contrast between two adjacent pixels.

For, GFG2, ρ (x) = ψ (ω (x, y)) where y ∈ V. If a pipeline network is to be represented, a crisp graph is constructed first. The capacity of pipelines (taken as edges) is measured according to the demand and supply. Then, the capacity of the connector (taken as vertices) of two or more pipelines depend on the capacity of the pipelines. Thus, membership values of edges are measured according to the capacities of the pipelines. Then, depending on the membership values, vertex membership values are calculated. Let, ψ (x) = max {(x, y) |y ∈ V}. Here, x is a connector and (x, y) is a connecting edge. Thus, connector gets maximum capacity among its connecting edges. The assumption of membership functions and their relations are chosen according to the problems. The estimation is purely empirically and arbitrary.

An example of generalized fuzzy graphs is described below. Here, a pipeline network is represented as generalized fuzzy graphs as follows. Let us consider the source of a pipeline network be s and sink be t. There are some paths from s to t. These paths are connected by some pipelines with some capacities. Our aim is to represent the system in an easier way. Man and computers both have to understand the system. In earlier methods, capacities of pipelines are given by different weights. Thus comparison of capacities among the pipelines is necessary for human understanding. To organise the system, it is to be known that which path is better i.e. which pipeline has large capacities.

Here, capacities of pipelines are taken as membership values of edges of the proposed generalized fuzzy graphs. As the edges are considered first, the proposed graph is a GDFG2. The co-domain set of ρ is taken as [0,1]. The capacities as membership values are shown along the pipelines (edges) in Fig. 1. Here, ψ ( x ) = max { ω ( y , x ) → } . According to the conditions, generalized membership values of vertices are obtained. These membership values denote the maximum capacity of the vertex (connector).

OPEN IN VIEWER

Fig.1

A pipeline network (the numbers near the edges represent capacity).

5 Fuzzy r-cut in generalized fuzzy graphs

A cut C = (S, T) is a partition of V of a graph G = (V, E) into two subsets S and T. The cut-set of a cut C = (S, T) is the set {(u, v) ∈ E|u ∈ S, v ∈ T} of edges that have one endpoint in S and the other endpoint in T. If s and t are specified vertices of the graph G, then an st cut is a cut in which s belongs to the set S and t belongs to the set T. The capacity of an s-t cut is defined by the sum of the capacity of each edge in the cut-set. Capacity (S, T) = sum of weights of edges leaving S. A cut is a minimum if the size or weight of the cut is not larger than the size of any other cut. In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge.

Cut into graphs splits the vertex set into two subsets. The cut is the set of edges whose one end vertex is connected to source and other end vertex is connected to sink. Now, in pipeline networks, reduction of flow is more effective than stopping of flow. Thus, the fuzzy cut is more effective. Here, fuzzy r-cut is introduced.

Definition 5. Let r ∈ [0, 1] be any real number. A fuzzy r-cut C = ( S , T ) in generalized fuzzy graphs G = (V, ρ, ω) (GFG1, GFG2, GDFG1 and GDFG2) is a partition of V of a generalized fuzzy graph G = (V, ρ, ω) into two subsets S and T. The cut-set of a cut C = ( S , T ) is the set C = {(u, v) |ω (u, v) ≥0, u ∈ S, v ∈ T} of edges that have one endpoint in S and the other endpoint in T. The value of the fuzzy r-cut is r × ∑_(u,v)∈Cω (u, v).

Now, the cuts in generalized directed fuzzy graphs (GDFG1, GDFG2) are exemplified. At a cut, only the edges which are directed towards destination are considered. The sum of the generalized membership values of the cut in Fig. 2 is 1+ 4 15 + 1 2 + 3 10 = 31 15 . (The directed edge ( f , b ) → is not considered). Let r = 0.75. Then, fuzzy 0.75-cut value is 0.75 × 31 10 = 2.325 . Let us check another cut in the same graph. The cut is shown by dotted line in the Fig. 3. Here, the sum of the generalized membership values of the edges of the cut is 14 15 . Thus, fuzzy 1-cut value is 0.93. This amount is less than the previous cut. Thus, where to apply the cut is an important task. Sometimes, little efforts make better results.

OPEN IN VIEWER

Fig.2

A cut in a pipeline network of Figure 1

OPEN IN VIEWER

Fig.3

Another cut of the pipeline network of Figure 1

Sometimes, in a pipeline network multi-cut is required. Here, n-tuple fuzzy r-cut is introduced where n is the number of cuts applied to a network and r ∈ [0, 1].

Definition 6. Let r₁, r₂, …, r _n  ∈ [0, 1]. A fuzzy (r₁, r₂, …, r _n )-cut C _n  = {(S₁, T₁) , (S₂, T₂) , …, (S _n , T _n )} in generalized fuzzy graphs (GFG1, GFG2, GDFG1 and GDFG2) is a collection of partitions of V of a generalized fuzzy graph G = (V, ρ, ω) into two subsets S₁; T₁, S₂; T₂,…S _n ; T _n . The cut-set of a cut C ₁ = {(S₁, T₁)} is the set C₁ = {(u₁, v₁) |ω (u₁, v₁) ≥0, u₁ ∈ S, v₁ ∈ T} of edges that have one end point in S₁ and the other end point in T₁. Similarly, C 2 = { ( S 2 , T 2 ) } is the set C₂ = {(u₂, v₂) |ω (u₂, v₂) ≥0, u₂ ∈ S, v₂ ∈ T} and so on. The value of the fuzzy (r₁, r₂, …, r _n )- cut is (r₁ × ∑_(u1,v1)∈C ω (u₁, v₁) , r₁ × r₂ × ∑_(u2,v2)∈C ω (u₂, v₂) , …, r₁ × r₂ × r₃ × … × r _n ∑_{(u n ,v n )∈C} ω (u _n , v _n )).

Fuzzy (0.75, 0.5)-cut on the graph of Fig. 1 is shown in Fig. 4). The value of the (0.75, 0.5)-cut is (0.75 × 0.93, 0.75 × 0.5 × 0.97) = (0.7, 0.37).

OPEN IN VIEWER

Fig.4

Fuzzy (0.75,0.5)- cut of the pipeline Figure 1

Flow amount depends on the capacity of a pipeline. Here, flow amounts in the network are incorporated in the described pipeline (Fig. 1). The flow amount is given as weight to generalized fuzzy graphs. The bold numbers in Fig. 5 denotes the amount of flow. The flow amount transferred from the source s is 4 5 . The amount is subdivided into the pipelines. In Fig. 6 it is shown that the amount of flow is increased to 14 15 . Now, a cut of the graph of Fig. 6 is shown in Fig. 7. Here, the fuzzy 1-cut value is 14 15 which is equal to the flow.

OPEN IN VIEWER

Fig.5

An example of flow associated to each edge in GDFG2

OPEN IN VIEWER

Fig.6

Flow value 14 15 .

OPEN IN VIEWER

Fig.7

Max-flow min-cut.

An application of generalized fuzzy graphs in image processing is described below. Image segmentation divides an image into meaningful pieces or segments with perceptually same features and properties. The aim is to simplify and to represent an image as more meaningful and easier to understand for a computer. A graph representing the measure of pixels is constructed using brightness, colour and texture profiles of an image at the same time. Graph-based image segmentation techniques generally represent the problem in terms of a graph G = (V  E) where each node v _i  ∈ V corresponds to a pixel in the image, and the edges in E connect certain pairs of neighbouring pixels. A weight is associated with each edge based on some property of the pixels that it connects, such as their image intensities. Depending on the method, there may or may not be an edge connecting each pair of vertices. The earliest graph-based methods use thresholds and local measures in computing a segmentation. For image segmentation the edge weights in the graph are based on the differences between pixel intensities, whereas for point clustering the weights are based on distances between points.

Work by Wu and Leahy [23] introduced such a cut criterion, but it was for finding small components. This limitation was addressed with the normalized cut criterion developed by Shi and Malik [20], which tells into account self-similarity of regions. The normalized cut criterion provides an advance over the previous work in [23]. While Shi and Malik develop approximation methods for computing the minimum normalized cut, the error in these approximations is not well understood. In practice, these assumptions are still hard to compute, limiting the method to relatively small images or requiring computation times of several minutes. Recently, Weiss [22] has shown how the eigenvector-based approximations developed by Shi and Malik relate to partitioning methods on graphs. However, all such methods are too slow for many practical applications. There are different ways to measure the quality of a segmentation but in general, the elements in a component is to be similar, and elements in different components are to be dissimilar. This means that edges between two vertices in the same component should have relatively low weights, and edges between vertices in different components should have higher weights.

Now, an image is assumed as generalized fuzzy graphs. Here, each pixel is assumed as vertex and neighbouring pixels are connected by edges. Let us define a function ρ from set of pixels to a closed interval [0,1]. This function measures the intensity of vertices. The values are taken as generalized vertex membership values. The dissimilarity of pixels is measured by another function ω which represents the generalized edge membership value. These two functions are related by another function φ. The weight has to be the way that the minimal cut goes along the borders of the object is to be segmented. In Ford-Fulkerson algorithm, min-cut/max-flow is based on energy function. In generalized fuzzy graphs, φ represents the energy function. Therefore, the cost of a cut has to be high inside the object or the background and low at the borders of the object. To segment the object, edges with very high weights from the source to the user seeds in the object and from the background user seeds to the sink are set. This ensures a flow via these edges in the maximal flow solution. Applying the MAX FLOW - software gives the minimal cut of this graph. The main goal is now to find the pixels of the object by comparing their intensity.

8 Insights for this study

Edge restrictions on fuzzy graphs are removed. This will help to represent any system as graphs.

9 Conclusion

In this study, two types of generalized fuzzy graphs namely GFG1, GFG2 were discussed. Also, the generalized directed fuzzy graphs, GDFG1, GDFG2 were defined. These graphs can be assumed as the generalisation of graphs as well as fuzzy graphs. A method to compute membership functions was discussed. Then, fuzzy r-cuts were introduced and extended to fuzzy n tuple cut. Any networks and images can be represented by the generalized fuzzy graphs. Image segmentation has many modern techniques. One of the graph based methods is graph cuts. Ford-Fulkerson algorithm is one of the important algorithms regarding graph cuts. But, Ford-Fulkerson algorithm cannot be applied to generalized fuzzy graphs as the main assumption of the algorithm is that all capacities are integers. Different energy functions are defined as edge weights for graph cuts. If images are represented as generalized fuzzy graphs, energy functions are not required as edge membership values and vertex membership values are related by another function (namely, φ). This function should be defined properly for fast computation of algorithms. In near future, algorithms on cuts of GDFG1, GDFG2 are to be established. Also, max-cut/ Min-flow problem can be solved using this GFG.