Russian Federation
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.
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.
