Определение хроматического множества нечеткого темпорального графа
Понятие хроматического множества как инварианта нечеткого темпорального графа. Влияние хроматического множества на наибольшую степень разделимости вершин темпорального нечеткого графа, при их окраске в заданное число цветов в любой момент времени.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 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Теоретическое обоснование теории графов. Методы нахождения медиан графа. Задача оптимального размещения насосной станции для полива полей. Алгоритм Флойда, поиск суммарного расстояния до вершин. Функция нахождения индекса минимального значения в массиве.
курсовая работа [336,8 K], добавлен 28.05.2016Характеристика методов нечеткого моделирования и изучение системы кластеризации в пакетах прикладных программ. Разработка и реализация алгоритма для оптимизации базы правил нечеткого классификатора с помощью генетического алгоритма аппроксимации функции.
дипломная работа [1,9 M], добавлен 21.06.2014Корректность определения кратчайших путей в графе и рёбра отрицательной длины. Анализ алгоритмов Дейкстры, Беллмана-Форда, Флойда-Уоршелла. Вычисление кратчайших расстояний между всеми парами вершин графа. Топологическая сортировка ориентированного графа.
презентация [449,3 K], добавлен 19.10.2014Создание программного обеспечения для реализации алгоритма, позволяющего находить кратчайшее расстояние от одной из вершин графа до всех остальных, при условии, что ребра графа не имеют отрицательного веса. Примеры выполнения алгоритма Дейкстра.
курсовая работа [1,1 M], добавлен 11.01.2015Программа формирования матрицы смежности по заданному списку окрестностей вершин ориентированного графа. Формирование динамического списка дуг ориентированного графа по заданному списку окрестностей. Анализ временной и емкостной сложности алгоритма.
курсовая работа [8,1 M], добавлен 07.09.2012Постановка задачи. Математическое обоснование. Последовательность разбиений множества. Язык программирования. Реализация алгоритмов. Генерирование разбиений множества. Генерирование всех понятий.
курсовая работа [29,9 K], добавлен 20.06.2003Общая методика решения задачи определения связанного множества пикселей с помощью функции bwlabel, в языке моделирования Matlab. Возможности оптимизации программы по временным характеристикам для возможности использования функции в анализе видеопотока.
статья [894,5 K], добавлен 11.03.2009Программный комплекс по обработке заданного множества данных в динамической памяти компьютера. Запросы к массиву записей множества данных – групп в детском саду. Функция сортировки массива по числовому полю. Использование главной программы MAINPRO.
курсовая работа [419,3 K], добавлен 23.07.2014Решение задач по информатике, перебор различных комбинаторных конфигураций объектов и выбор наилучшего, с точки зрения условия задачи. Генерация k-элементных подмножеств, всех подмножеств данного множества, всех перестановок n-элементного множества.
реферат [44,0 K], добавлен 03.01.2010Засвоєння засобів аналізу трудомісткості обчислювальних алгоритмів. Побудова графа алгоритму з отриманої блок-схеми. Мінімізація графа, його подання у вигляді стохастичної матриці. Знаходження кількості звернень до файлів за допомогою Microsoft Excel.
лабораторная работа [681,5 K], добавлен 02.06.2011
