About Search of Optimal Paths in Fuzzy Graphs

Dmitry Speranskiy

doi:10.20295/2412-9186-2022-8-04-418-426

UDC

681.518

ABOUT SEARCH OF OPTIMAL PATHS IN FUZZY GRAPHS About Search of Optimal Paths in Fuzzy Graphs

АА Аа

Published in Transport automation research · Pages 418–426 · Rubric: TECHNICAL DIAGNOSTICS AND CONTROLLABLE SYSTEMS

DOI: https://doi.org/10.20295/2412-9186-2022-8-04-418-426

Received: 12.12.2022 Accepted: 12.12.2022 Published: 12.12.2022

Authors

Dmitry Speranskiy

Academic degree: doctor of technical sciences

Russian University of Transport (MIIT) Professor · Department of Management Systems for Transport Infrastructure · Russian Federation

ABSTRACT

A large variety of problems in different fields, including the problems of the creation of optimal solutions of different kinds, can be formulated in graph theory language in the form of search tasks at given graphs of optimal paths of special character. Many results in these courses are now obtained which refer to classical graph theory. In this theory, a graph is assumed to be a deterministic object and there are no any uncertainties (fuzzinesses) in its description and in the description of its functioning process. Nowadays, science has come to the realization that the majority of our knowledge and links with the external world do not correspond to formerly established classical notions about them. New approaches to these areas are now being developed, which imply principal impossibility to do without fuzzinesses that are accepted as a reality of human existence. This requires the development of complex of concepts and methods which in, this fuzziness should be taken into account really in practical applications. In the proposed article, the tasks of searching optimal paths according to some criteria in the frames of currently accepted fuzzy graph model are considered. When solving the problem of the shortest paths, the rule of choosing the “best” arc is introduced and motivated. The method of solving the tasks with the use of the design of oriented graph path tree is proposed. The notion of path feasibility in fuzzy graph is introduced, the feasibility is evaluated as the probability of path real existence in given graph. The method for calculation of path feasibility, based on the reduction of belonging degree of each arc in the path of graph path to its probability, is proposed. The task on the search of path with maximum feasibility is solved on this basis.

KEYWORDS

graph theory, fuzzy graphs, shortest path search, path feasibility in fuzzy graph, search of path with maximal feasibility

1. Berzh K. Teoriya grafov i ee primeneniya / K. Berzh. - M.: Inostrannaya literatura, 1962. -320 s.

2. Ore O. Teoriya grafov / O. Ore. - M.: Nauka, 1980. - 336 s.

3. Harari F. Teoriya grafov / F. Harari. - M.: Mir, 1973. - 301 s.

4. Zykov A. A. Osnovy teorii grafov / A. A. Zykov. - M.: Vuzovskaya kniga, 2004. - 664 s.

5. Zadeh L. A. Fuzzy sets / L. A. Zadeh // Inf. Contro. - 1965. - № 8. - Pp. 338-353.

6. Kofman A. Vvedenie v teoriyu nechetkih mnozhestv / A. Kofman. - M.: Radio i svyaz', 1982. -432 s.

7. Dubots D. Fuzzy sets and systems: theory and applications / D. Dubots, H. Prade. - New York: Academy Press, 1980. - 393 p.

8. Speranskiy D. V. Experiments with fuzzy state machine / D. V Speranskiy. // Automation and Remote Control. - 2015. - Vol.76:2. - Pp. 278-291.

9. Speranskiy D. V. Testirovanie nechetkih lineynyh avtomatov / D. V. Speranskiy // Izv. Sarat. un-ta. Nov. ser. Matematika. Mehanika. Informatika. - 2019. - T. 19:2. - S. 233-240.

10. Stefanyuk V. P. Povedenie konechnogo avtomata v nechetkoy srede: teoriya i prilozheniya / V. P. Stefanyuk // Iskusstvennyy intellekt i prinyatie resheniy. - 2014. - № 3. - S. 54-71.

11. Rosyida L. On construction of fuzzy chromatic number of cartesian product of paths and other fuzzy graphs / L. Rosyida, Widodo, D. Indriati et al. // Journal of Intelligent and Fuzzy Graphs. - 2020. - Vol. 39. - № 1. - Pp. 1073-1080.

12. Rosyida L. Fuzzy chromatic number of union of fuzzy graphs. An algorithm. Properties and its application / L. Rosyida, Widodo, D. Indriati et al. // Journal of Intelligent and Fuzzy Graphs // Fuzzy Sets and Systems. - 2020. - Vol. 38. - Pp. 115-131.

13. Samanta S. Fuzzy colouring of fuzzy graphs / S. Samanta, T. Paramanic, V. Pal // Africa Matematica. - 2016. - Vol. 27. - № 1-2. - Pp. 37-50.

14. Maharatra R. Application of coloring of fuzzy graphs / R. Maharatra, M. Pal, S. Samanta // Informatica. - 2020. - Vol. 31. - № 2. - Pp. 313-330.

15. Al-Humaidi H. M. A fuzzy logic approach to model delays in construction projects using rotational fuzzy fault tree models / H. M. Al-Humaidi, F. H. Hudripriono Tan // Civil Engineering and Environmental Systems. - 2019. - Vol. 27. - № 4. - 2019. - Pp. 329-351.

16. Sambariya D. K. A novel fuzzy rule matrix design for fuzzy logic based power system stabilizer / D. K. Sambariya, R. Prasad // Power Components and Systems. - 2017. - Vol. 45. - № 1. - Pp. 34-48.

17. Horohorin M. A. Primenenie raspredelennyh informacionnyh sistem dlya ocenki zhivuchesti nechetkih grafov / M. A. Horohorin, A. A. Dolgov, M. Auad i dr. // Informaciya i bezopasnost'. - 2012. - T. 15. - № 2. - C. 245-248.

18. Bozhenyuk A. V. Opredelenie dominiruyuschego mnozhestva intuicionistskogo nechetkogo grafa / A. V. Bozhenyuk, S. A. Belyakov, O. V. Kosenko i dr. // Inzhenernyy vestnik Dona. - 2019. - № 3(54). - S. 11-13.

19. Petrunina U. V. Nechetkie grafy v funkcional'no-logicheskom modelirovanii geterogennyh sistem / U. V. Petrunina // Mezhdunarodnyy zhurnal prikladnyh i fundamental'nyh issledovaniy. - 2012. - № 7. - S. 78-79.

20. Bozhenyuk A. V. Ocenka informacionnoy nadezhnosti slozhnyh sistem s pomosch'yu nechetkih grafov / A. V. Bozhenyuk, S. A. Belyakov, O. V. Kosenko // Nauka i tehnologiya zheleznyh dorog. - 2012. - T. 3. - № 4. - S. 65-74.

21. Bershteyn L. S. Nechetkie invarianty nechetkih grafov i gipergrafov / L. S. Bershteyn, A. V. Bozhenyuk // Nechetkie grafy i myagkie vychisleniya. - 2011. - T. 6. - № 1. - S. 43-54.

22. Maynika E. Algoritmy optimizacii na setyah i grafa / E. Maynika // M.: Mir, 1981. - 324 s.

23. Gmurman V. E. Teoriya veroyatnostey i matematicheskaya statistika / V. E. Gmurman // M.: Vysshaya shkola, 2003. - 479 s.

GOST

Speranskiy D. V. About Search of Optimal Paths in Fuzzy Graphs // . 2022. pp. 418-426. DOI: https://doi.org/10.20295/2412-9186-2022-8-04-418-426. (Date of access 20.08.2026).

MLA

Dmitry Speranskiy. "About Search of Optimal Paths in Fuzzy Graphs." (2022): 418-426. DOI: https://doi.org/10.20295/2412-9186-2022-8-04-418-426.

APA

Speranskiy D. V. (2022). About Search of Optimal Paths in Fuzzy Graphs. , 418-426. https://doi.org/10.20295/2412-9186-2022-8-04-418-426

Chicago

Dmitry Speranskiy. "About Search of Optimal Paths in Fuzzy Graphs." , no. (2022): 418-426. https://doi.org/10.20295/2412-9186-2022-8-04-418-426.

WIKI

{{cite journal | author = Speranskiy D. V. | title = About Search of Optimal Paths in Fuzzy Graphs | journal = | year = 2022 | pages = 418-426 | doi = 10.20295/2412-9186-2022-8-04-418-426 }}

Copy

Export: BibTeX EndNote RefMan RusMARC

ABOUT SEARCH OF OPTIMAL PATHS IN FUZZY GRAPHS About Search of Optimal Paths in Fuzzy Graphs

Confirmation