Fuzzy Graphs and Fuzzy Hypergraphs

Abstract

Graph theory has numerous application to problems in systems analysis, operations research, economics, and transportation. However, in many cases, some aspects of a graph-theoretic problem may be uncertain. For example, the vehicle travel time or vehicle capacity on a road network may not be known exactly. In such cases, it is natural to deal with the uncertainty using the methods of fuzzy sets and fuzzy logic. Hypergraphs (Berge,1989) are the generalization of graphs in case of set of multiarity relations. It means the expansion of graph models for the modeling complex systems. In case of modelling systems with fuzzy binary and multiarity relations between objects, transition to fuzzy hypergraphs, which combine advantages both fuzzy and graph models, is more natural. It allows to realise formal optimisation and logical procedures. However, using of the fuzzy graphs and hypergraphs as the models of various systems (social, economic systems, communication networks and others) leads to difficulties. The graph isomorphic transformations are reduced to redefinition of vertices and edges. This redefinition doesn’t change properties the graph determined by an adjacent and an incidence of its vertices and edges. Fuzzy independent set, domination fuzzy set, fuzzy chromatic set are invariants concerning the isomorphism transformations of the fuzzy graphs and fuzzy hypergraph and allow make theirs structural analysis.

Key Terms in this Chapter

Multiarity Relation: A multiarity relation R between elements of sets A, B, …, C is a subset of A×B×…×C.

Binary Relation: A binary relation R from a set A to a set B is a subset of A×B.

Isomorphic Graphs: Two graphs that have a structure-preserving vertex bijection between them.

Graph Invariant: A property of a graph that is preserved by isomorphisms.

Graph: A graph G = (V, E) is a mathematical structure consisting of two finite sets V and E. The elements of V are called vertices (or nodes), and the elements of E are called edges. Each edge has a set of one or two vertices associated to it, which are called its endpoints.

Binary Symmetric Relation: A relation R on a set A is symmetric if for all x,y?A xRy?yRx.

Fuzzy Set: A generalization of the definition of the classical set. A fuzzy set is characterized by a membership function, which maps the member of the universe into the unit interval, thus assigning to elements of the universe degrees of belongingness with respect to a set.

Membership Function: The membership function of a fuzzy set is a generalization of the characteristic function of crisp sets.

Hypergraph: A hypergraph on a finite set X={x1,x2,…,xn} is a family H={E1,E2,…,Em} of subsets of X such that Ei ? Ø and and .