сотрудник
Большое разнообразие проблем в различных областях, в том числе проблем построения различного рода оптимальных решений, может быть сформулировано на языке теории графов в виде задач поиска на заданных графах специального вида оптимальных путей. Ныне получено много результатов в этих направлениях, относящихся к классической теории графов. В этой теории граф предполагается детерминированным объектом и в его описании и описании процесса его функционирования не содержится никаких неопределенностей (нечеткостей). Ныне наука подошла к осознанию того, что большинство наших знаний и связей с внешним миром не соответствуют сложившимся ранее классическим представлениям о них. Сейчас разрабатываются новые подходы к этим направлениям, которые предполагают принципиальную невозможность обойтись без «нечеткостей», которые принимаются как реальность человеческого существования. Это требует разработки комплекса понятий и методов, в которых эта «нечеткость» должна быть реально учтена в практических приложениях. В предлагаемой статье рассматриваются задачи поиска оптимальных по некоторым критериям путей в рамках принятой ныне модели нечеткого графа. При решении задачи о кратчайших путях введено и мотивировано правило выбора «лучшей» дуги. Предложен метод решения задачи с использованием конструкции ориентированного дерева путей графа. Введено понятие реализуемости пути в нечетком графе, которая оценивается как вероятность его реального существования в заданном графе. Предложен метод вычисления реализуемости пути, основанный на сведении степени принадлежности каждой дуги в пути графа к его вероятности. На этой основе решается задача о поиске пути с максимальной реализуемостью.
теория графов, нечеткие графы, поиск кратчайших путей, реализуемость пути в нечетком графе, поиск пути с максимальной реализуемостью
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 с.
