Skip to main content
Springer Nature Link
Log in

Applications of Fuzzy Graphs

  • Chapter
Fuzzy Graphs and Fuzzy Hypergraphs

Part of the book series: Studies in Fuzziness and Soft Computing ((STUDFUZZ,volume 46))

Abstract

Let (V, μ, ρ) be a fuzzy graph. We now provide two popular ways of defining the distance between a pair of vertices. One way is to define the “distance” dis(x,y) between x and y as the length of the shortest strongest path between them. This “distance” is symmetric and is such that dis(x,x) = 0 since by our definition of a fuzzy graph, no path from x to x can have strength greater than μ(x), which is the strength of the path of length 0. However, it does not satisfy the triangle property, as we see from the following example. Let V = {u, v, x, y,z}, ρ(x, u) = ρ(u, v) = ρ(v, z) = 1 and ρ(x, y) = ρ(y, z) = 0.5. Here any path from x to y or from y to z has strength ≤ 1/2 since it must involve either edge (x,y) or edge (y, z). Thus the shortest strongest paths between them have length 1. On the other hand, there is a path from x to z, through u and v, that has length 3 and strength 1. Thus dis(x,z) = 3 > 1 + 1 = dis(x,y) + dis(y, z) in this case.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Bellman, R.E., and Zadeh, L.A., Mgmt Sci., Vol. 17, No. 4, 1970.

    Google Scholar 

  2. Bezdek, J.C. and Harris, J.D., Fuzzy partitions and relations an axiomatic basis for clustering, Fuzzy Sets and Systems 1: 111–127, 1978.

    Article  MathSciNet  MATH  Google Scholar 

  3. Bhattacharya, P., Some remarks on fuzzy graphs, Pattern Recognition Letters 6: 297–302, 1987.

    Article  MATH  Google Scholar 

  4. Bhattacharya, P., and Suraweera, F, An algorithm to compute the supremum of max-min powers and a property of fuzzy graphs, Pattern Recognition Letters 12: 413–420, 1991.

    Article  Google Scholar 

  5. Delgado, M. and Verdegay, J.L., On valuation and optimization problems in fuzzy graphs: A general approach and some particular cases, ORSA J. on Computing 2: 74–83, 1990.

    Article  MATH  Google Scholar 

  6. Ding, B., A clustering dynamic state method for maximal trees in fuzzy graph theory, J. Numer. Methods Comput. Appl. 13: 157–160, 1992.

    MathSciNet  Google Scholar 

  7. Dunn, J.C., A graph theoretic analysis of pattern classification via Tamura’s fuzzy relation, IEEE Trans. on Systems, Man, and Cybernetics 310–313, 1974.

    Google Scholar 

  8. Harary, F., Graph Theoretic Methods in the Management Sciences, Management Science, 5: 387–403, 1959.

    Article  MathSciNet  MATH  Google Scholar 

  9. Harary, F., and R.Z. Norman, Graph Theory as a Mathematical Model in Social Science, Ann Arbor, Mich.: Institute for Social Research, 1953.

    Google Scholar 

  10. Harary, F., R.Z. Norman and Cartwright, D., Structural Models: An Introduction to the Theory of Directed Graphs, John Wiley & Sons, Inc., New York, 1965.

    Google Scholar 

  11. Harary, F., Graph Theory, Addison Wesley, Third printing, October 1972.

    Google Scholar 

  12. Harary, F., and Ross, I.C., The Number of Complete Cycles in a Communication Network, Journal of Social Psychology, 40: 329–332, 1953.

    Article  Google Scholar 

  13. Harary, F., and Ross, I.C., A Procedure for Clique Detention using the Group Matrix, Sociometry, 20: 205–215, 1957.

    Article  MathSciNet  Google Scholar 

  14. Kaufmann, A., Introduction a la Theorie des sons-ensembles flous, Vol. 1, Masson Paris, 41–189, 1973.

    Google Scholar 

  15. Kaufmann, A., Introduction to the Theory of Fuzzy Subsets, Vol. 1, Academic Press, New York, 1975.

    MATH  Google Scholar 

  16. Kiss, A., An application of fuzzy graphs in database theory, Automata, languages and programming systems (Salgotarjan 1990) Pure Math, Appl. Ser. A, 1: 337–342, 1991.

    MathSciNet  Google Scholar 

  17. Kóczy, L.T., Fuzzy graphs in the evaluation and optimization of networks, Fuzzy Sets and Systems 46: 307–319, 1992.

    Article  MathSciNet  MATH  Google Scholar 

  18. Leenders, J.H., Some remarks on an article by Raymond T. Yeh and S.Y. Bang dealing with fuzzy relations: Fuzzy relations, fuzzy graphs, and their applications to clustering analysis, Fuzzy sets and their applications to cognitive and decision processes (Proc. U.S.-Japan Sem.,Univ. Calif., Berkeley, Calif., 1974), 125–149, Simon Stevin 51:93100, 1977/78.

    Google Scholar 

  19. Ling, R.F., On the theory and construction of k-cluster, The Computer J. 15:326–332, 1972.

    Google Scholar 

  20. Liu, W-J., On some systems of simultaneous equations in a completely distributive lattice, Inform. Sci. 50: 185–196, 1990.

    Article  MathSciNet  MATH  Google Scholar 

  21. Matula, D.W., Cluster analysis via graph theoretic techniques, Proc. of Lousiana Conf. on Combinatrics, Graph Theory, and Computing, 199–212, March 1970.

    Google Scholar 

  22. Matula, D.W., k-components, clusters, and slicings in graphs, SIAM J. Appl. Math. 22:459–480, 1972.

    Google Scholar 

  23. Mordeson, J.N. and PengC-S, Fuzzy intersection equations, Fuzzy Sets and Systems 60:77–81, 1993.

    Google Scholar 

  24. Mordeson, J.N. and Peng, C-S, Operations on fuzzy graphs, Inform. Sci. 79: 159–170, 1994.

    Article  MathSciNet  MATH  Google Scholar 

  25. Mori, M. and Kawahara, Y., Fuzzy graph rewritings, Theory of rewriting systems and its applications (Japanese) 918:65–71, 1995.

    Google Scholar 

  26. Morioka, M., Yamashita, H., and Takizawa, T., Extraction method of the difference between fuzzy graphs, Fuzzy information, knowledge representation and decision analysis (Marseille, 1983 ), 439–444, IFAC Proc. Ser., 6, IFAC, Lexenburg, 1984.

    Google Scholar 

  27. Nance, R.E., Korfhage, R.R., and Bhat, U.N., Information networks: Definitions and message transfer models, Tech. Report CP-710011, Computer Science/Operations Research Center, SMU, Dallas, Texas, July 1971.

    Google Scholar 

  28. Ramamoorthy, C.V., Analysis of graphs by connectivity considerations, JACM, 13: 211–222, 1966.

    Article  MathSciNet  MATH  Google Scholar 

  29. Rosenblatt, D., On Linear Models and the Graphs of Minkowski–Leontief Matrices, Econometrica, 25: 325–338, 1957.

    Article  MathSciNet  MATH  Google Scholar 

  30. Rosenfeld, A., Fuzzy graphs, In: L. A. Zadeh, K. S. Fu, M. Shimura, Eds., Fuzzy Sets and Their Applications, 77–95, Academic Press, 1975.

    Google Scholar 

  31. Ross, I.C., and Harary, F., On the Determination of Redundancies in Sociometric Chains, Psychometrika, 17: 195–208, 1952.

    Article  MATH  Google Scholar 

  32. Ross, I.C., and Harary, F., Identification of the Liaison Persons of an Organization using the Structure Matrix, Management Science, 1: 251–258, 1955.

    Article  MathSciNet  MATH  Google Scholar 

  33. Ross, I.C., and Harary, F., A Description of Strengthening and Weakening Members of a Group, Sociometry, 22: 139–147, 1959.

    Article  MathSciNet  Google Scholar 

  34. Sibson, R., Some observation on a paper by Lance and Williams, The Computer J. 14: 156–157, 1971.

    Article  MATH  Google Scholar 

  35. Sunouchi, H. and Morioka, M., Some properties on the connectivity of a fuzzy graph (Japanese), Bull. Sci. Engrg. Res. lab. Waseda Univ. no. 132, 70–78, 1991.

    MathSciNet  Google Scholar 

  36. Takeda, E., Connectvity in fuzzy graphs, Tech. Rep. Osaka Univ. 23: 343–352, 1973.

    MathSciNet  Google Scholar 

  37. Takeda, E. and Nishida, T., An application of fuzzy graph to the problem concerning group structure, J. Operations Res. Soc. Japan 19: 217–227, 1976.

    MathSciNet  MATH  Google Scholar 

  38. Tong, Z. and Zheng, D., An algorithm for finding the connectedness matrix of a fuzzy graph, Congr. Numer. 120: 189–192, 1996.

    MathSciNet  MATH  Google Scholar 

  39. Ullman, J. D., Principles of Database and Knowledge-base Systems, Vol 1–2, Computer Science Press, Rockville, MD., 1989.

    Google Scholar 

  40. Wu, L. G. and Chen, T.P., Some problems concerning fuzzy graphs (Chinese), J. Huazhong Inst. Tech. no 2, Special issue on fuzzy math, iv, 58–60, 1980.

    Google Scholar 

  41. Xu, J., The use of fuzzy graphs in chemical structure research, In: D.H. Rouvry, Ed., Fuzzy Logic in Chemistry, 249–282, Academic Press, 1997.

    Google Scholar 

  42. Yamashita, H., Approximation algorithm for a fuzzy graph (Japanese), Bull. Centre Info, ru. 2: 59–60, 1985.

    Google Scholar 

  43. Yamashita, H., Structure analysis of fuzzy graph and its application (Japanese), Bull. Sci. Engrg. Res. Lab. Waseda Univ. no. 132, 61–69, 1991.

    Google Scholar 

  44. Yamashita, H. and Morioka, M., On the global structure of a fuzzy graph, Analysis of Fuzzy Information, 1:167–176, CRC, Boca Raton, Fla., 1987.

    Google Scholar 

  45. Yeh, R.T. and Bang, S.Y., Fuzzy relations, fuzzy graphs, and their applications to clustering analysis, In: L. A. Zadeh, K. S. Fu, M. Shimura, Eds., Fuzzy Sets and Their Applications, 125–149, Academic Press, 1975.

    Google Scholar 

  46. Zadeh, L.A., Fuzzy Sets, Information and Control, 8: 338–353, 1965.

    Article  MathSciNet  MATH  Google Scholar 

  47. Zadeh, L.A., Similarity relations and fuzzy orderings, Information Sciences, 3: 177–200, 1971.

    Article  MathSciNet  MATH  Google Scholar 

  48. Zhu, R.Y., The critical number of the connectivity degree of a fuzzy graph (Chineses), Fuzzy Math. 2: 113–116, 1982.

    Google Scholar 

  49. Zykov, A.A., On some properties of linear complexes (Russian), Mat. Sbornik 24:163–188, 1949, Amer. Math. Soc. Translations N. 79, 1952.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Center for Research in Fuzzy Mathematics and Computer Science, 68178, Omaha, Nebraska, USA

    John N. Mordeson (Director)

  2. Department of Mathematics and Computer Science, Creighton University, 68178, Omaha, Nebraska, USA

    Premchand S. Nair (Associate Professor)

Authors
  1. John N. Mordeson
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Premchand S. Nair
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Center for Research in Fuzzy Mathematics and Computer Science, 68178, Omaha, Nebraska, USA

    John N. Mordeson (Director) (Director)

  2. Department of Mathematics and Computer Science, Creighton University, 68178, Omaha, Nebraska, USA

    Premchand S. Nair (Associate Professor) (Associate Professor)

Rights and permissions

Reprints and permissions

Copyright information

© 2000 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Mordeson, J.N., Nair, P.S. (2000). Applications of Fuzzy Graphs. In: Mordeson, J.N., Nair, P.S. (eds) Fuzzy Graphs and Fuzzy Hypergraphs. Studies in Fuzziness and Soft Computing, vol 46. Physica, Heidelberg. https://doi.org/10.1007/978-3-7908-1854-3_3

Download citation

  • DOI: https://doi.org/10.1007/978-3-7908-1854-3_3

  • Publisher Name: Physica, Heidelberg

  • Print ISBN: 978-3-7908-2471-1

  • Online ISBN: 978-3-7908-1854-3

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics