VI Международная студенческая научная конференция Студенческий научный форум - 2014

Введение

На сегодняшний день графы широко используются для представления данных и знаний в различных областях, таких как: электротехника, строительство и логистика, компьютерные и социальные сети, лингвистика и многие другие.

Теоретико-графовые конструкции (сети Петри, синтаксические деревья, модель программы в виде управляющего графа и др.) имеют существенное значение в развитие программирования и средств его автоматизации. Многие задачи анализа программ, возникающие при оптимизации, трансляции, проверке правильности, тестировании и т.д. значительно упрощаются, если рассматривать их на теоретико-графовых моделях.

Использование планарных графов

Планарные графы широко используются для решения задач, связанных с представлением планов помещений, карт и т.п.

Одним из примеров использования планарных графов является моделирование среды, в которой будет развиваться робот. Например, возьмём знаменитый «умный» пылесос. Робот должен учитывать «представление о мире», которое включает такую информацию как номера комнат и их топологии, возможность перейти непосредственно из одной комнаты в соседнюю, использование дверей и обходы запрещенных номеров. В этом случае, секторы в плоском графе представляют номера, а вершины – углы; если два номера соединены дверью, они имеют общее ребро в графе; а «запрещённые» номера помечены как невидимые (рис. 1), [].

Если робот достаточно «умён», он, возможно, построит эту модель самостоятельно. Именно эта модель будет «руководить» его работой: в соответствии с ней будет строиться план уборки помещений.

а) б)

Рис. 1. Моделирование среды для робота: а) план помещения изображён (запрещённые комнаты отмечены специальным символом); б) планарный граф, представляющий помещение (серое пространство – видимые комнаты, белое – невидимые)

Ориентированные графы

Орграфы широко применяются в программировании как способ описания систем со сложными связями. Например, одна из основных структур, используемых при разработке компиляторов, для представления компьютерных программ, – граф потоков данных.

Рис. 2. Пример ориентированного графа

Поскольку информация, которую желательно визуализировать, постоянно усложняется, увеличивается её объём, возникает всё больше ситуаций, в которых требуются более мощные графовые формализмы для представления информационных моделей, имеющих, в частности, иерархическую структуру. Для их представления используются, например, хиграфы (hi-графы) и составные графы. Хиграфы являются обобщением понятия гиперграфа и представляют сложные отношения, используя многоуровневые “блобы”, которые могут содержать друг друга и пересекаться между собой. Составные графы являются расширением класса ориентированных графов за счет введения между вершинами дополнительного отношения включения и представляют собой менее общий формализм, чем хиграфы. Одним из современных неклассических формализмов являются кластерные графы. Кластерный граф состоит из неориентированного графа и рекурсивного разбиения его вершин на подмножества, называемые кластерами. Это относительно общий графовый формализм, который может использоваться во многих приложениях и хорошо приспособлен, в частности, для решения задач визуализации, рисования графов [].

Метаграфы

Метаграфы – обобщение концепций графических структур, используемых в различных областях. В метаграфе есть элементы и орграфов, и гипеграфов. Сам метаграф выстраивается на основе иерархического графа. Формально метаграф – это множество , где V – множество вершин, MV – множество метавершин, E – множество ребер, ME – множество метаребер [].

Впервые понятие вложенного метаграфа было использовано при описании состояний нечеткой ситуационной сети [], посредством которой моделировались неопределенные бизнес-процессы (рис. 3).

Ещё одним приложением вложенных метаграфов является организация семантического поиска в глобальных и корпоративных сетях или электронных библиотеках. В частности, сегодня при наличии огромного количества неструктурированных документов, наблюдается тенденция к формированию семантического Web. Метаграфы представляют мощный формализм, позволяющий решать задачи создания моделей документов и их систем, семантической разметки.

Метаграфы в настоящее время широко используются в решении задач планирования и управления организациями []. Представление бизнес-процесса как метаграфа – основа различных подходов к решению задач оптимизации ежедневной производственной деятельности организаций, в той или иной степени подверженных влиянию среды и неконтролируемых условий. В моделировании процессов с использованием метаграфов удобно применять принципы идемпотентной математики.

В работе [] был представлен разработанный авторами и реализованный программно алгоритм поиска метапути наименьшего веса в метаграфе, являющийся модификацией алгоритма Дейкстры с применением элементов идемпотентной математики.

Рис. 3. Фрагмент ситуационной сети бизнес-процесса

Ещё одна задача, решаемая с использованием метаграфов, – маршрутизация в IP-сетях с использованием [].

Иерархия архитектуры сетей может быть отражена с помощью метаграфов. В работе [] рассматривается протокол внутреннего шлюза OSPF (Open Shortest Path First, алгоритмы предложены Дейкстрой), который представляет собой протокол состояния маршрута (в качестве метрики для оценки используется коэффициент качества обслуживания).

Рис. 4. Пример метаграфа сети

Ещё одно приложение метаграфов – в реализации экономико-математических методов []. Метаграфы могут применяться и в таких традиционных для теории графов задачах, как транспортная задача и сетевое планирование.

В работе предлагается использовать метаграфы как оптимальный вариант формализации при решении задач создания языковых инструментариев, предназначенных для создания предметно-ориентированных языков [].

Гиперграфы

Гиперграф, есть пара, где – множество вершин , а – множество рёбер ; каждое ребро представляет собой подмножество [].

Одно из приложений – использование гиперграфов для представления онтологий. Пример представления онтологии сетевого оборудования с помощью гиперграфа показан на рис. 5, 6 [].

Рис. 5. Структура разработанной онтологии, описанная с помощью гиперграфа

В последние годы разработка онтологий переходит из мира лабораторий искусственного интеллекта на рабочие столы экспертов по предметным областям. Во всемирной паутине онтологии стали обычным явлением. Онтологии в сети варьируются от больших таксономий, категоризирующих web-сайты (как на сайте Yahoo!), до категоризации продаваемых товаров и их характеристик (как на сайте Amazon.com).

Для разных предметных областей и задач существует спектр языков представления знаний. Для системы, основанной на знаниях, одним из адекватных языков представления знаний является язык гиперграфов, используемых в качестве расширения семантических сетей.

Рис. 6. Образование новых семантических связей в структуре онтологии

В [] вводится понятие рёберного гиперграфа, в [] – м-ациклических и древовидных гиперграфов.

Если «умело» использовать гиперграфовые модели, то их можно применять в достаточно широких пределах.

Гиперграфы широко используются в лингвистической трансляции [], в качестве формальных моделей документов при решении задач информационного поиска и пр.

Аппарат гиперграфов позволяет описывать абзацы и даже полные тексты, не прибегая к использованию «гипертекстовых» технологий. Его можно применять для «метаописания» при определении понятий и отношений самой лингвистической модели и этапов трансляции. Гиперграфы позволяют встраивать специальные механизмы, например, ассоциированных (присоединенных) процедур. Более того, любые синтаксические или семантические отношения проверяются с помощью этих процедур.

Гиперграфовое представление имеет аналогии с семантическими сетями и с фреймами, но фреймы, сложно формализуются, а семантические сети до сих пор не имеют стандартного определения, хотя и возникли из формального понятия сети, которое по определению связано с гиперграфом. Гиперграф же имеет четкое формальное определение и теоретически обоснованную процедуру сопоставления (поиска изоморфизма). Сопоставление при решении задачи установления изоморфизма даёт спектр результатов в зависимости от структуры гиперграфов, степеней вершин и рёбер, их окраски и порядка выбора вершин с одинаковой степенью связности в графе. Таким образом, процедура поиска даёт возможность варьировать параметры при сопоставлении и получать разные результаты исходя из заданных внешних критериев.

Заключение

В настоящее время области научных исследований, связанных с разработкой программного обеспечения, где используются методы теории графов, значительно расширились по сравнению с традиционными приложениями теории графов. Одной из наиболее интересных задач, решение которых актуально для многих областей, традиционно является задача установления изоморфизма графов. Её решение может иметь особенности в зависимости от типа используемых графов и конкретных условий. Цель дальнейших исследований – изучение алгоритмов установления изоморфизма и разработка алгоритмов поиска подграфов, изоморфных заданному графу, в приложении к задачам реализации графовых грамматик.

Библиографический список

1. Астанин С.В., Драгныш Н.В., Жуковская Н.К. Вложенные метаграфы как модели сложных объектов.

2. Быкова В.В. М-ациклические и древовидные гиперграфы.

3. Касьянов В.Н. Применение графов в программировании.

4. Левин А.Г., Тышкевич Р.И. Дискретная математика, т. 5.

5. Погребной В.К. Алгоритм решения задачи определения изоморфизма гиперграфов. Томск.

6. Починский И.А. Использование гиперграфов для представления онтологии сетевого оборудования. Пенза.

7. Починский И.А. Формальное представление семантических гиперграфов и операций над ними. Пенза.

8. Сухов А.О. Анализ формализмов описания визуальных языков моделирования // Современные проблемы науки и образования. – 2012. – № 2; URL: www.science-education.ru/102-5655 (дата обращения: 01.03.2014).

9. Хахалин Г.К. Использование гиперграфов в лингвистической трансляции, 1999.

10. Черных О.О. Метаграфы в прикладной математики и области их применения. Липецк.

11. de la Higuera C. Polynomial algorithms for open plane graph and subgraph isomorphisms, 2013.

 

Код для цитирования: Скопировать