Россия
Большое разнообразие проблем в различных областях, в том числе проблем построения различного рода оптимальных решений, может быть сформулировано на языке теории графов в виде задач поиска на заданных графах специального вида оптимальных путей. Ныне получено много результатов в этих направлениях, относящихся к классической теории графов. В этой теории граф предполагается детерминированным объектом и в его описании и описании процесса его функционирования не содержится никаких неопределенностей (нечеткостей). Ныне наука подошла к осознанию того, что большинство наших знаний и связей с внешним миром не соответствуют сложившимся ранее классическим представлениям о них. Сейчас разрабатываются новые подходы к этим направлениям, которые предполагают принципиальную невозможность обойтись без «нечеткостей», которые принимаются как реальность человеческого существования. Это требует разработки комплекса понятий и методов, в которых эта «нечеткость» должна быть реально учтена в практических приложениях. В предлагаемой статье рассматриваются задачи поиска оптимальных по некоторым критериям путей в рамках принятой ныне модели нечеткого графа. При решении задачи о кратчайших путях введено и мотивировано правило выбора «лучшей» дуги. Предложен метод решения задачи с использованием конструкции ориентированного дерева путей графа. Введено понятие реализуемости пути в нечетком графе, которая оценивается как вероятность его реального существования в заданном графе. Предложен метод вычисления реализуемости пути, основанный на сведении степени принадлежности каждой дуги в пути графа к его вероятности. На этой основе решается задача о поиске пути с максимальной реализуемостью.
теория графов, нечеткие графы, поиск кратчайших путей, реализуемость пути в нечетком графе, поиск пути с максимальной реализуемостью
1. Берж К. Теория графов и ее применения / К. Берж. - М.: Иностранная литература, 1962. -320 с.
2. Оре О. Теория графов / О. Оре. - М.: Наука, 1980. - 336 с.
3. Харари Ф. Теория графов / Ф. Харари. - М.: Мир, 1973. - 301 с.
4. Зыков А. А. Основы теории графов / А. А. Зыков. - М.: Вузовская книга, 2004. - 664 с.
5. Zadeh L. A. Fuzzy sets / L. A. Zadeh // Inf. Contro. - 1965. - № 8. - Pp. 338-353.
6. Кофман А. Введение в теорию нечетких множеств / А. Кофман. - М.: Радио и связь, 1982. -432 с.
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. Сперанский Д. В. Тестирование нечетких линейных автоматов / Д. В. Сперанский // Изв. Сарат. ун-та. Нов. сер. Математика. Механика. Информатика. - 2019. - Т. 19:2. - С. 233-240.
10. Стефанюк В. П. Поведение конечного автомата в нечеткой среде: теория и приложения / В. П. Стефанюк // Искусственный интеллект и принятие решений. - 2014. - № 3. - С. 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. Хорохорин М. А. Применение распределенных информационных систем для оценки живучести нечетких графов / М. А. Хорохорин, А. А. Долгов, М. Ауад и др. // Информация и безопасность. - 2012. - Т. 15. - № 2. - C. 245-248.
18. Боженюк А. В. Определение доминирующего множества интуиционистского нечеткого графа / А. В. Боженюк, С. А. Беляков, О. В. Косенко и др. // Инженерный вестник Дона. - 2019. - № 3(54). - С. 11-13.
19. Петрунина У. В. Нечеткие графы в функционально-логическом моделировании гетерогенных систем / У. В. Петрунина // Международный журнал прикладных и фундаментальных исследований. - 2012. - № 7. - С. 78-79.
20. Боженюк А. В. Оценка информационной надежности сложных систем с помощью нечетких графов / А. В. Боженюк, С. А. Беляков, О. В. Косенко // Наука и технология железных дорог. - 2012. - Т. 3. - № 4. - С. 65-74.
21. Берштейн Л. С. Нечеткие инварианты нечетких графов и гиперграфов / Л. С. Берштейн, А. В. Боженюк // Нечеткие графы и мягкие вычисления. - 2011. - Т. 6. - № 1. - С. 43-54.
22. Майника Э. Алгоритмы оптимизации на сетях и графа / Э. Майника // М.: Мир, 1981. - 324 с.
23. Гмурман В. Е. Теория вероятностей и математическая статистика / В. Е. Гмурман // М.: Высшая школа, 2003. - 479 с.
