Определение хроматического множества нечеткого темпорального графа
Понятие хроматического множества как инварианта нечеткого темпорального графа. Влияние хроматического множества на наибольшую степень разделимости вершин темпорального нечеткого графа, при их окраске в заданное число цветов в любой момент времени.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 27.07.2017 |
| Размер файла | 134,7 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
9
Размещено на http://www.allbest.ru/
Южный федеральный университет
Определение хроматического множества нечеткого темпорального графа
Л.С. Берштейн, С.Л. Беляков, А.В. Боженюк
Таганрог
Аннотация
В статье введено и рассмотрено понятие хроматического множества как инварианта нечеткого темпорального графа, т.е. такого графа, в котором степень связности вершин изменяется в дискретном времени. Хроматическое множество определяет наибольшую степень разделимости вершин темпорального нечеткого графа, при их окраске в заданное число цветов в любой момент времени. Рассмотрен пример нахождения хроматического множества нечеткого темпорального графа.
Ключевые слова: Нечеткий темпоральный граф, нечеткий суграф, окраска графа, хроматическое множество, степень разделимости.
Введение
Графовые модели привлекают большое внимание специалистов в различных областях знаний. Они используются для моделирования различных сложных объектов и явлений с некоторой выраженной структурой. Кроме того, наряду с применениями графовых моделей в таких науках, как химия, электротехника, физика, они используются и в науках, считавшиеся раньше далекими от них - в экономике, лингвистики, социологии. Графовые модели могут использоваться для задания отношений в структурах различной природы между их элементами [1-4]. В этом случае отношения между элементами (вершинами графа) считаются постоянными и не могут меняться в процессе моделирования. Такие графы в работе [5] были названы статическими. Однако, если отношения между элементами рассматриваемой структуры могут меняться во времени, традиционные графовые модели не подходят для их описания и не могут быть использованы для моделирования процессов во времени. В этом случае, является актуальным рассмотрение графовых моделей, т.е., графов в которых связи вершинами могут изменяться в дискретном (или непрерывном) времени. Такие графы были названы темпоральными [6, 7]. Когда же в темпоральном графе, связи между вершинами являются также частично неопределенными или нечеткими, то приходим к графам, которые были названы нечеткими темпоральными [8-10].
При использовании таких графов как моделей сложных систем актуальным является рассмотрение их инвариантов, т.е. таких характеристик графа, которые не меняются при его изоморфном преобразовании [11]. Для четких графов такими инвариантами являются степень внутренней и внешней устойчивости, хроматическое число, хроматический класс и др. [3]. В данной работе вводится понятие хроматического множества темпорального нечеткого графа, которое и является его инвариантом.
Понятие хроматического множества темпорального нечеткого графа
Обозначим через темпоральный нечеткий граф [10,12], в котором множество X является множеством вершин графа (|X|=n), множество натуральных чисел t={1,2,…,T} определяет дискретное время, а множество задает семейство соответствий, которые отображают вершины X в себя в моменты времени .
Введем в рассмотрение нечеткий суграф , в котором множество вершин X - тоже, что и в исходном темпоральном нечетком графе , множество является нечетким множеством ребер в моменты , а функция есть функция принадлежности, отображающая
Раскрасим каждую вершину нечеткого суграфа , в один из k заранее заданных цветов и выделим подграф , в котором вершины окрашены в одинаковый i-й цвет. Тогда величина согласно [13, 14] определит степень его внутренней устойчивости.
Определение 1. Степенью разделимости нечеткого суграфа при его окраске в k цветов называется величина:
.
Степень разделимости L нечеткого суграфа зависит от числа красок k и от конкретной окраски вершин. Поставим в соответствие нечеткому суграфу семейство нечетких множеств , . Здесь величина задает степень разделимости суграфа при его конкретной окраске в k цветов.
Определение 2. Нечеткое множество назовем хроматическим множеством суграфа , если для любого другого надмножества будет выполняться нечеткое включение .
Иначе говоря, , то есть, хроматическое множество суграфа определяет наибольшие степени его разделимости при окраске его вершин в 1, 2,., n цветов в момент времени t.
Определение 3. Множество назовем хроматическим множеством темпорального нечеткого графа .
Хроматическое множество определяет наибольшую степень разделимости вершин темпорального нечеткого графа, при их окраске в 1, 2,…,n цветов в любой момент времени tT.
Пример. Рассмотрим пример темпорального нечеткого графа , у которого множество вершин X={х1, x2, х4}, время T={1, 2, 3}, а многозначное отображение имеет вид:
, , , , , , , , .
Графическое представление данного графа приведено на Рис.1. Здесь на дугах указаны функции принадлежности в моменты времени t={1,2,3}.
Рис. 1. Нечеткий темпоральный граф
Темпоральный нечеткий граф можно представить как объединение Т нечетких суграфов, заданных на одном и том же множестве вершин Х. Так граф представим в виде , где нечеткие суграфы , и показаны на рис.2-4. Вычисляем хроматические множества нечетких суграфов: в момент t=1 - ; в момент t=2 - ; в момент t=3 - .
Рис.2. Суграф в момент t=1.
Рис.3 Суграф в момент t=2
Рис.4 Суграф в момент t=3
Отсюда хроматическое множество нечеткого темпорального графа определяется как: .
Таким образом, нечеткий темпоральный графа, представленный на рисунке 1, в любой момент времени может быть окрашен в 2 цвета со степенью разделимости не менее 0,6; в 3 цвета со степенью разделимости не менее 0,7 и в 4 цвета со степенью разделимости не менее 1.
хроматическое множество нечеткий темпоральный граф
Выводы
В данной работе мы рассмотрели понятие хроматического множества как инварианта нечеткого темпорального графа, т.е. такого графа, в котором степень связности вершин изменяется в дискретном времени. Хроматическое множество определяет наибольшую степень разделимости вершин темпорального нечеткого графа, при их окраске в заданное число цветов в любой момент времени. Рассмотрен пример нахождения хроматического множества нечеткого темпорального графа.
Статья подготовлена по результатам исследований, выполненных при финансовой поддержке Российского фонда фундаментальных исследований в рамках проекта № 14-01-00032a.
Литература
1. Оре О. Теория графов. М.: Наука, 1980. - 336с.
2. Майника Э. Алгоритмы оптимизации на сетях и графах. - М.: Мир, 1981. - 326с.
3. Берштейн Л.С., Боженюк А.В. Теория графов: учебное пособие. - Ростов-на-Дону: Изд-во ЮФУ, 2014. - 174с.
4. Ерусалимский Я.М. Графы с затуханием на дугах и усилением в вершинах и маршрутизация в информационных сетях // Инженерный вестник Дона. 2015. №1. URL: ivdon.ru/ru/magazine/archive/n1y2015/2782.
5. Kostakos V. Temporal graphs // In Proc. of Physica A: Statistical Mechanics and its Applications. 2008. vol.388. Issue 6. Elsevier. pp.1007-1023.
6. Берштейн Л.С., Боженюк А.В. Использование темпоральных графов как моделей сложных систем // Известия ЮФУ. Технические науки. Таганрог: ТТИ ЮФУ. 2010. №4 (105).С. 198-203.
7. Боженюк, А.В., Герасименко Е.М. Разработка алгоритма нахождения максимального потока минимальной стоимости в нечеткой динамической транспортной сети // Инженерный вестник Дона. 2013. № 1. URL: ivdon.ru/magazine/archive/n1y2013/1583.
8. Берштейн Л.С., Беляков С.Л., Боженюк А.В. Метод Магу для нахождения нечеткого множества баз нечеткого темпорального графа // Известия Южного федерального университета. Технические науки. 2014. № 1. с.70-76.
9. Берштейн Л.С., Боженюк А.В., Розенберг И.Н. Метод нахождения сильной связности нечетких темпоральных графов // Вестник РГУПС. Ростов-на-Дону: РГУПС. 2011. №3 (43). С.15-20.
10. Берштейн Л.С., Беляков С.Л., Боженюк А.В. Использование нечетких темпоральных графов для моделирования в ГИС // Известия ЮФУ. Технические науки. Таганрог: ТТИ ЮФУ. 2012. №1 (126). С.121-127.
11. Боженюк А.В., Гинис Л.А. Алгоритмическая поддержка исследования системных связей в социально-экономической системе на основе нечетких графовых моделей // Экономика и менеджмент систем управления, 2015, №1.1 (15). С.115-122.
12. Bershtein L. S., Bozhenyuk A. V. Fuzzy Coloring for Fuzzy Graphs // Proceedings of the 10th IEEE International Conference on Fuzzy Systems. Melbourne, Australia, December 2-5, 2001. Vol.3, pp.79-81.
13. Bershtein L. S., Bozhenuk A. V. Maghout Method for Determination of Fuzzy Independent, Dominating Vertex Sets and Fuzzy Graph Kernels // International Journal of General Systems. 2001. Т.30. № 1. pp.45-52.
14. Bozheniuk V., Bozhenyuk A., Belyakov S. Optimum allocation of centers in fuzzy transportation networks with the largest vitality degree // Proceedings of the 2015 Conference of the International Fuzzy System Association and the European Society for Fuzzy Logic and Technology. Atlantis Press. 2015. pp.1006-1011.
Размещено на Allbest.ru
Подобные документы
Понятие нечеткого множества и функции принадлежности. Методы дефаззификации (преобразования нечеткого множества в четкое число) для многоэкстремальных функций принадлежности. Нечеткий логический вывод. Примеры выпуклого и невыпуклого нечеткого множества.
презентация [111,7 K], добавлен 16.10.2013Этапы нахождения хроматического числа произвольного графа. Анализ примеров раскраски графа. Характеристика трудоемкости алгоритма раскраски вершин графа Мейниеля. Особенности графов, удовлетворяющих структуру графов Мейниеля, основные классы графов.
курсовая работа [1,1 M], добавлен 26.06.2012Методы поиска подмножеств множества вершин V графа G, удовлетворяющих определенным условиям и свойствам. Понятие независимых множеств и порядок их генерации. Определение доминирующего множества. Основные этапы решения задачи о наименьшем разбиении.
контрольная работа [32,1 K], добавлен 11.03.2010Основные этапы систем нечеткого вывода. Правила нечетких продукций, используемые в них. Нечеткие лингвистические высказывания. Определение алгоритмов Цукамото, Ларсена, Сугено. Реализации нечеткого вывода Мамдани на примере работы уличного светофора.
курсовая работа [479,6 K], добавлен 14.07.2012Начальное представление систем нечеткого вывода: логический вывод, база знаний. Алгоритм Мамдани в системах нечеткого вывода: принцип работы, формирование базы правил и входных переменных, агрегирование подусловий, активизация подзаключений и заключений.
курсовая работа [757,3 K], добавлен 24.06.2011Методы, системы, типы и способы проводимых измерений в автоматизированных системах медицинского обеспечения безопасности на транспорте. Проектирования нечеткого алгоритма предрейсовых медицинских осмотров на основе адаптивной сети нейро-нечеткого вывода.
дипломная работа [6,5 M], добавлен 06.05.2011Исследование проблемы сравнения звуковых файлов и определение степени их схожести. Сравнение файлов с использованием метода нечеткого поиска, основанного на метрике (расстоянии) Левенштейна. Сравнение MIDI-файлов и реализация алгоритмов считывания.
курсовая работа [2,0 M], добавлен 14.07.2012Теория множества, основные операции над множествами, мощность множества. Теорема о сравнении множеств. Размер множества в Turbo Pascal, предельно допустимое количество элементов и их порядок. Выполнение действий объединения, исключения и пересечения.
курсовая работа [376,6 K], добавлен 31.01.2016Математические графы, области их применения. Способы раскраски вершин и ребер графов, задачи на их применение. Разработка алгоритма, работающего на основе операций с матрицей смежности. Описание логической структуры программы. Пример зарисовки графа.
курсовая работа [145,5 K], добавлен 27.01.2013История и термины теории графов. Описание алгоритма Дейкстры. Математическое решение проблемы определения кратчайшего расстояния от одной из вершин графа до всех остальных. Разработка программы на объектно-ориентированном языке программирования Delphi 7.
контрольная работа [646,9 K], добавлен 19.01.2016