БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Выпускная работа по
«Основам информационных технологий»

Магистрант кафедры численных методов и программирования

Жигмонт Андрей Владимирович

Руководители:

кандидат физ.-мат. наук Суздаль С.В.

доцент Кожич Павел Павлович

Минск – 2010 г.

Список обозначений ко всей выпускной работе

AI – искусственный интеллект

ИТ – информационные технологии.

СВГ – системы визуализации графов

ТГ – теория графов

ЭВМ – электронная вычислительная машина

Реферат на тему «Применение ИТ при решении задач теории графов»

Введение

Начало теории графов как математической дисциплины было положено Эйлером в его знаменитом рассуждение о Кенигсбергских мостах. Однако эта статья Эйлера 1736 года была единственной в течение почти ста лет. Интерес к проблемам теории графов возродился около середины 19 века и был сосредоточен главным образом в Англии. Имелось много причин для такого оживленного изучения графов. Естественные науки оказали свое влияние на это благодаря исследованиям электрических цепей, моделей кристаллов и структур молекул.

20-е столетие было свидетелем неуклонного развития теории графов, которая за последние десять – двадцать лет вступила в новый период интенсивных разработок. В этом процессе явно заметно влияние запросов новых областей: теории игр и программирования, теории передачи сообщений, электрических сетей и контактных цепей, а также проблем психологии и биологии.

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

Одним из примеров использования теории графов является проектирование сетей и передача информации. Для этой задачи надежность является основным принципом функционирования. Сеть должна быть спроектирована таким образом, чтобы при выходе из строя её отдельных элементов функциональность сети не нарушалась. Естественным образом возникает задача нахождения реберно-непересекающихся цепей между выделенными узлами. Стоимость всей сети должна быть минимальна при условии её надежности. Таким образом, при решении задачи проектирования возникают следующие подзадачи:

o Построение кратчайшей пары реберно-непересекающихся путей между двумя вершинами;

o Построение K(K>2) кратчайшего множества реберно-непересекающихся путей между двумя вершинами.

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

Глава 1 Базовые понятия теории графов

1.1 Основные определения

Термин «граф» впервые появился в книге выдающегося венгерского математика Д. Кёнига в 1936г.

Пусть V — непустое множество, V⁽²⁾ — множество всех его двухэлементных подмножеств. Пара (V, Е), где Е — произвольное подмножество множества V⁽²⁾, называется графом (неориентированным графом).

В этой работе рассматриваются только конечные графы, т. е. множество V предполагается конечным, хотя в определении графа конечность этого множества не требуется. Элементы множества V называются вершинами графа, а элементы множества E — ребрами. Итак, граф — это конечное множество V вершин и множество E ребер, EÍV⁽²⁾. Множества вершин и ребер графа G обозначаются символами VG и EG соответственно. Вершины и ребра графа называются его элементами. Число |VG| вершин графа G называется его порядком и обозначается через |G|. Если |G| = n, |EG| = m, то G называют (n, m)-графом.

Говорят, что две вершины u и v графа смежны, если множество {и, v} является ребром, и не смежны в противном случае. Если e = {и, v} — ребро, то вершины u и v называют его концами. В этой ситуации говорят также, что ребро e соединяет вершины u и v. Такое ребро обозначается символом uv.

Два ребра называются смежными, если они имеют общий конец.

Вершина u и ребро e называются инцидентными, если v является концом ребра e (т. е. e = иv), и не инцидентными в противном случае.

Заметим, что смежность есть отношение между однородными элементами графа, тогда как инцидентность является отношением между разнородными элементами.

Множество всех вершин графа G, смежных с некоторой вершиной v, называется окружением вершины v и обозначается через N_G(v) или просто N(v).

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

Иногда приведенное выше определение графа оказывается недостаточным и приходится рассматривать более общие объекты, в которых две вершины могут соединяться более чем одним ребром. Так возникает понятие «мультиграф». Мультиграф — это пара (V, E), где V — непустое множество (вершин), а E — семейство подмножеств множества V⁽²⁾ (ребер). Употребление термина «семейство» вместо «множество» означает, что элементы множества V⁽²⁾ могут в E повторяться, т. е. допускаются кратные ребра.

Дальнейшее обобщение состоит в том, что кроме кратных ребер допускаются еще петли, т. е. ребра, соединяющие вершину саму с собой. Псевдограф — это пара (V, E), где V — непустое множество (вершин), а E —некоторое семейство неупорядоченных пар вершин (ребер), не обязательно различных. На следующих рисунках изображены мультиграф и псевдограф.

Изучаются также ориентированные графы. Тогда множество V⁽²⁾ двухэлементных подмножеств заменяется декартовым квадратом V², состоящим из упорядоченных пар элементов множества V. Итак, ориентированный граф (или орграф) — это пара (V, A), где V — множество вершин, A — множество ориентированных ребер, которые называются дугами, A

V². Если a = (v₁, v₂) — дуга, то вершины v₁ и v₂ называются ее началом и концом соответственно. На рисунке дуги отмечаются стрелками, указывающими направление от начала к концу. Аналогично определяется ориентированный мультиграф. Рассматриваются также смешанные графы, у которых есть и дуги, и неориентированные ребра.

Простой граф, в котором каждая пара вершин смежна называется полным. Полные графы обозначаются K_n. На рисунке ниже изображены полные графы K₁, K₂, K₃, K₄.

Граф называется двудольным, если существует такое разбиение его вершин на две части (доли) такие, что концы каждого ребра принадлежат разным частям. Полный двудольный граф, доли которого состоят из p и q вершин, обозначается символом K_p_,_q. На рисунке ниже изображены полные двудольные графы K_1,4, K_3,3.

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

Глава 2 Анализ GraphMagic: системы работы с графовыми моделями и алгоритмами

2.1 Основные преимущества системы GraphMagic

2.1.1 Дополняемость

Ключевым моментом в системе GraphMagic является возможность лёгкого расширения и дополнения новыми модулями – «плагинами». Плагины могут быть разработаны и использованы без участия разработчиков самой системы, так как система предоставляет для этого интерфейс. Более подробно интерфейс будет описан в разделе Архитектура системы Примерный процесс включения дополнения в приложение определяется так:

«Применение ит при решении задач теории графов» (стр. 1 из 4)

Оглавление