Размещено на http://www.allbest.ru/

Содержание

ВВЕДЕНИЕ

1. ОПИСАНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ

1.1 История развития теории графов

1.2 Применение теории графов

1.4. Основные термины и теоремы теории графов

1.4 Задачи на графах

1.5 Обзор аналогов

Выводы

2. ПРОЕКТИРОВАНИЕ ПРОГРАММНОГО КОМПЛЕКСА

2.1 Математическое описание графов

2.2 Матрица достижимости

2.1 Определение возможностей редактора

2.2 Разработка интерфейса программного комплекса

2.3 Диаграмма использования

2.4 Диаграмма деятельности

2.5 Определение классов и модулей программы

Выводы

3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ РЕДАКТОРА ИЗУЧЕНИЯ ТЕОРИИ ГРАФОВ

3.1 Выбор программной платформы и среды разработки

3.2 Программная реализация редактора изучения теории графов

Выводы

4. АНАЛИЗ КАЧЕСТВА РАЗРАБОТАННОГО ПРОГРАММНОГО КОМПЛЕКСА

4.1 Система показателей качества

4.2 Результаты тестирования

4.3 Предложения по улучшению качества ПО

Выводы

5. ЭРГОНОМИКА ПРОГРАММНОГО ПРОДУКТА

5.1 Описание пользовательского интерфейса

5.2 Охрана труда и производственная санитария

5.3 Правила по технике безопасности

Выводы

6. ТЕХНИКО-ЭКОНОМИЧЕСКОЕ ОБОСНОВАНИЕ

6.1 Расчет стоимости выполнения работ

6.2 Составление календарного плана выполнения работ

Выводы

ЗАКЛЮЧЕНИЕ

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

ПРИЛОЖЕНИЯ



ВВЕДЕНИЕ

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

Целью проекта является разработка редактора изучения теории графов.

Для достижения поставленной цели были поставлены и решены следующие задачи:

· Проведен анализ литературы

· Определены функциональные возмжности редактора

· Разработан интерфейс редактора

· Разработана архитектура программного комплекса

· Выбраны средства реализации проекта

· Программно реализован Редактор изучения теории графов

· Подготовлена пояснительная записка к дипломному проекту

Объектом исследования проекта являются теория графов, его инструментарий.

Предметом исследования является редактор изучения теории графов

Значимость проекта определяется возможностью применения «Редактора изучения теории графов» в процессе обучения студентов по дисциплине «Дискретная математика» и «Моделирование». Теория графов является важным разделом дисциплины «Дискретная математика». Хорошие знания по теории графов позволяют применять их при решении сложных задач на старших курсах. Теория графов является инструментом формлизации структурных отношений между объектами сложной системы. Знание способов представления графов важно при решении задач, данные которых имеют древовидную структуру.

Отличительной осбенностью редактора является возможность примениения различной окраски.

Пояснительная записка к дипломной работе выполнена на __ страницах машинописного текста, содержит __ рисунка и __ таблиц. Состоит из введения, шести разделов и заключения. Список использованной литературы содержит _ наименований работ отечественных авторов.

В первом разделе «Описание предметной области» приводится актуальность разработки редактора, терминология, основные положения теории графов, области применения.

Во втором разделе «Проектирование программного комплекса» приводится описание общей структуры редактора, определяются функции и возможности редактора, определяется архитектура программы.

В третьем разделе «Реализация программного комплекса» описываются

использованные методы программирования; среда программирования; интерфейсы программных компонентов; приводятся тексты программных компонентов на языке программирования и пояснения к ним.

В четвертом разделе «Анализ качества разработанного программного обеспечения» приводится система показателей качества разработанного ПО, результаты тестирования и отладки, достигнутые показатели качества. Кроме того, формулируются предложения по улучшению качества программного обеспечения.

В пятом разделе «Эргономика программного продукта» приводятся требования к пользовательскому интерфейсу ПО, и рассматриваются вопросы реализации пользовательского интерфейса.

В шестом разделе «Технико - экономическое обоснование» приводятся расчеты срока окупаемости ПО, обосновывается его экономическая эффективность.

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

В приложении дается текст разработанной программы.



1. ОПИСАНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ

1.1 История развития теории графов

Начало теории графов как математической дисциплины было положено Эйлером в его знаменитом рассуждение о Кенигсбергских мостах. Однако эта статья Эйлера 1736 года была единственной в течение почти ста лет. Интерес к проблемам теории графов возродился около середины прошлого столетия и был сосредоточен главным образом в Англии. Имелось много причин для такого оживления изучения графов. Естественные науки оказали свое влияние на это благодаря исследованиям электрических цепей, моделей кристаллов и структур молекул. Развитие формальной логики привело к изучению бинарных отношений в форме графов. Большое число популярных головоломок подавалось формулировкам непосредственно в терминах графов, и это приводило к пониманию, что многие задачи такого рода содержат некоторое математическое ядро, важность которого выходит за рамки конкретного вопроса. Наиболее знаменитая среди этих задач-проблема четырех красок, впервые поставленная перед математиками Де Морганом около 1850 года. Никакая проблема не вызывала столь многочисленных и остроумных работ в области теории графов. Благодаря своей простой формулировке и раздражающей неуловимости она до сих пор остается мощным стимулом исследований различных свойств графов.

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

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

Первые задачи теории графов были связаны с решением математических развлекательных задач и головоломок (задача о Кенигсбергских мостах, задача о расстановке ферзей на шахматной доске, задачи о перевозках, задача о кругосветном путешествии и другие). Одним из первых результатов в теории графов явился критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах.

Правило Эйлера:

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

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

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

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

В 20 в. задачи, связанные с графами, начали возникать не только в физике, химии, электротехнике биологии, экономике, социологии и т.д., но и внутри математики, в таких разделах, как топология, алгебра, теория вероятностей, теория чисел. В начале 20 в. графы стали использоваться для представления некоторых математических объектов и формальной постановки различных дискретных задач; при этом наряду с термином «граф» употреблялись и другие термины, например, карта, комплекс, диаграмма, сеть, лабиринт. После выхода в свет в 1936 году монографии Д. Кёнига термин «граф» стал более употребительным, чем другие. В этой работе были систематизированы известные к тому времени факты. В 1936 году вышла небольшая брошюра Ойстена Оре, содержащая блестящее элементарное введение в теорию графов. В 1962 году в Англии была издана книга французского математика Клода Бержа “Теория графов и её приложение”. Обе книги, безусловно, представляют интерес для любителей занимательной математики. Сотни известных головоломок, на первый взгляд не имеющих ничего общего друг с другом, легко решаются с помощью теории графов.

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

Значительно расширились исследования по теории графов в конце 40-х - начале 50-х годов, прежде всего в силу развития кибернетики и вычислительной техники. Благодаря развитию вычислительной техники, изучению сложных кибернетических систем, интерес к теории графов возрос, а проблематика теории графов существенным образом обогатилась. Кроме того, использование ЭВМ позволило решать возникающие на практике конкретные задачи, связанные с большим объемом вычислений, прежде не поддававшиеся решению. Для ряда экстремальных задач теории графов были разработаны методы их решения, например, один из таких методов позволяет решать задачи о построении максимального потока через сеть. Для отдельных классов графов (деревья, плоские графы и т. д.), которые изучались и ранее, было показано, что решения некоторых задач для графов из этих классов находятся проще, чем для произвольных графов (нахождение условий существования графов с заданными свойствами, установление изоморфизма графов и др.).

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

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

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

где C== 0,534948..., e== 2,95576...

Для числа Gn неизоморфных графов без петель и кратных ребер с n вершинами было показано, что



теория граф программный редактор

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

В другом направлении исследований теории графов изучаются маршруты, содержащие все вершины или ребра графа. Известен простой критерий существования маршрута, содержащего все ребра графа: в связном графе цикл, содержащий все ребра и проходящий по каждому ребру один раз, существует тогда и только тогда, когда все вершины графа имеют четные степени. В случае обхода множества вершин графа имеется только ряд достаточных условий существования цикла, проходящего по всем вершинам графа по одному разу. Характерным специфическим направлением теории графов является цикл задач, связанный с раскрасками графов, в котором изучаются разбиения множества вершин (ребер), обладающие определенными свойствами, например, смежные вершины (ребра) должны принадлежать различным множествам (вершины или ребра из одного множества окрашиваются одним цветом). Было доказано, что наименьшее число цветов, достаточное для раскраски ребер любого графа без петель с максимальной степенью a, равно Зa/2, а для раскраски вершин любого графа без петель и кратных ребер достаточно a+1 цветов.

1.2 Применение теории графов

Теория графов находит широкое применение в различных областях науки и техники:

Графы и информация

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

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

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

Графы и химия

Еще А. Кэли рассмотрел задачу о возможных структурах насыщенных (или предельных) углеводородов, молекулы которых задаются формулой:

CnH2n+2

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

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

Графы и биология

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

Нас будет интересовать лишь один вопрос: в скольких случаях n-е поколение одной бактерии насчитывает ровно k потомков? Рекуррентное соотношение, обозначающее число необходимых случаев, известно в биологии под названием процесса Гальтона-Ватсона. Его можно рассматривать как частный случай многих общих формул.

Графы и физика

Еще недавно одной из наиболее сложных и утомительных задач для радиолюбителей было конструирование печатных схем.

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

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

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

1.3 Графы. Общие сведения

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

При взгляде на географическую карту сразу бросается в глаза сеть железных дорог. Это типичный граф: кружочки обозначают станции - вершины графа, а соединяющие их пути - рёбра.

Граф на рис. 1.1 изображает схему дорог между сёлами М, А, Б, В и Г. Здесь каждые две вершины соединены между собой ребром. Такой граф называется полным. Числа на рисунке указывают расстояние между сёлами по этим дорогам.



Рис.1.1 Граф схема дорог между сёлами М, А, Б, В и Г.

Пусть в селе М находится почта и почтальон должен развести письма в остальные четыре села. Существует много различных маршрутов поездки. Как из них выбрать наикратчайший? Проще всего проанализировать все варианты. Сделать это поможет новый граф (рис. 1, внизу), на котором легко увидеть возможные маршруты. Вершина М вверху - начало маршрутов. Из неё можно начать путь четырьмя различными способами: в А, в Б, в В или в Г. После посещения одного из сёл остаётся три возможности продолжения маршрута, потом две, потом дорога в последнее село и вновь в М. Всего 4 3 2 1 = 24 способа. Все они на этом графе. Расставим вдоль его рёбер цифры, обозначающие расстояния между сёлами, а в конце каждого маршрута напишем сумму этих расстояний по маршруту. Из полученных 24 чисел наименьшим являются два числа по 28 км, соответствующие маршрутам М-В-Б-А-Г-М и М_Г-А-Б-В-М. Заметим, что это один и тот же путь, но пройденный в разных направлениях.

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

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



Рис.1.2 Сетевой график строительства

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

Около вершин графа указаны числа - продолжительность в днях соответствующей работы. Теперь мы можем узнать наименьшую возможную продолжительность строительства. Для этого из всех путей по графу в направлении стрелок нужно выбрать путь, у которого сумма чисел при вершинах наибольшая. Он называется критическим путём (на рис. 2 он выделен жирной линией). В нашем случае получается 170 дней. А если сократить время прокладки электросети с 40 до 10 дней, то и время строительства тоже сократится на 30 дней? Нет. В этом случае критический путь станет проходить не через эту вершину, а через вершины, соответствующие строительству котлована, укладке фундамента и т. д. И общее время строительства составит 160 дней, т. е. срок сократится лишь на 10 дней.

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

В ведре 8 л воды, и имеются две кастрюли ёмкостью 5 и 3 л. Требуется отлить в пятилитровую кастрюлю 4 л воды и оставить в ведре 4 л, т.е. разлить воду поровну в ведро и большую кастрюлю.

Ситуацию в каждый момент можно описать тремя числами (x, y, z), где x -количество литров воды в ведре, y - в большой кастрюле, z - в меньшей. В начальный момент ситуация описывалась тройкой чисел (8, 0, 0), от неё мы можем перейти в одну из двух ситуаций: (3, 5, 0), если наполним водой большую кастрюлю, или (5, 0, 3), если наполним меньшую кастрюлю. В результате получаем два решения: одно в 7 ходов, другое в 8 ходов:

(8,0,0), (3,5,0), (3,2,3), (6,2,0), (6,0,2), (1,5,2), (1,4,3), (4,4,0).

(8,0,0), (5,0,3), (5,3,0), (2,3,3), (2,5,1), (7,0,1), (7,1,0), (4,1,3), (4,4,0).

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

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

Принципы построения программ для игр типа шахмат впервые были сформулированы американским учёным К. Шенноном в 1950 г. Они основаны на исследовании дерева возможных продолжений игры - дерева перебора.

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

Пример дерева перебора приведён на рис. 1.3. Вершинам соответствуют позиции, рёбрам - полуходы (полуход - это ход одного партнёра, каждый ход в партии состоит из двух полуходов).

Рис.1.3 Пример дерева перебора

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

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

Рис.1.4 Фрагмент дерева перебора

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

Для выбора лучшего хода в текущей позиции используется так называемая минимаксная процедура: вводится оценочная функция, при помощи которой присваиваются оценки концевым вершинам и устанавливается правило определения оценки вершины любого уровня по оценкам её дочерних вершин. Чем выгоднее позиция для программы, тем выше должна быть её оценка. Для вершин, не являющихся концевыми, в качестве оценки принимается максимальная из оценок дочерних вершин, если в позиции, соответствующей данной вершине, - ход программы (такие вершины принято называть альфа_вершинами), в противном случае - минимальная из оценок дочерних вершин (бета_вершины). Ход, выбираемый программой, соответствует ребру, идущему из корневой вершины в дочернюю с максимальной оценкой.

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

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

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

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

1. Граф - Пара объектов G = ( X , Г ) ,где Х - конечное множество ,а Г -конечное подмножество прямого произведения Х*Х . При этом Х называется множеством вершин , а Г - множеством дуг графа G .

2. Любое конечное множество точек (вершин), некоторые из которых попарно соединены стрелками , (в теории графов эти стрелки называются дугами), можно рассматривать как граф.

3. Если в множестве Г все пары упорядочены, то такой граф называют ориентированным .

4. Дуга- ребро ориентированного графа.

5. Граф называется вырожденным, если у него нет рёбер.

6. Вершина Х называется инцидентной ребру G , если ребро соединяет эту вершину с какой-либо другой вершиной.

7. Подграфом G(V1, E1) графа G(V, E) называется граф с множеством вершин V1 ?V и множеством ребер (дуг) E E, - такими, что каждое ребро (дуга) из E1 инцидентно (инцидентна) только вершинам из V1 . Иначе говоря, подграф содержит некоторые вершины исходного графа и некоторые рёбра (только те, оба конца которых входят в подграф).

8. Подграфом, порождённым множеством вершин U называется подграф, множество вершин которого - U, содержащий те и только те рёбра, оба конца которых входят в U.

9. Подграф называется остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа.

10. Вершины называются смежными , если существует ребро , их соединяющее.

11. Два ребра G1 и G2 называются смежными, если существует вершина, инцидентная одновременно G1 и G2.

12. Каждый граф можно представить в пространстве множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам (или дугам - в последнем случае направление обычно указывается стрелочками). - такое представление называется укладкой графа.

13. Доказано, что в 3-мерном пространстве любой граф можно представить в виде укладки таким образом, что линии, соответствующие ребрам (дугам) не будут пересекаться во внутренних точках. Для 2-мерного пространства это, вообще говоря, неверно. Допускающие представление в виде укладки в 2-мерном пространстве графы называют плоскими (планарным).
Другими словами, планарным называется граф, который может быть изображен на плоскости так, что его рёбра не будут пересекаться.

14. Гранью графа, изображенного на некоторой поверхности, называется часть поверхности, ограниченная рёбрами графа.

Данное понятие грани, по - существу, совпадает с понятием грани многогранника. В качестве поверхности в этом случае выступает поверхность многогранника. Если многогранник выпуклый, его можно изобразить на плоскости, сохранив все грани. Это можно наглядно представить следующим образом: одну из граней многогранника растягиваем, а сам многогранник «расплющиваем» так, чтобы он весь поместился внутри этой грани. В результате получим плоский граф. Грань, которую мы растягивали «исчезнет», но ей будет соответствовать грань, состоящая из части плоскости, ограничивающей граф.

Таким образом, можно говорить о вершинах, рёбрах и гранях многогранника, а оперировать соответствующими понятиями для плоского графа.

15. Пустым называется граф без рёбер. Полным называется граф, в котором каждые две вершины смежные.

16. Конечная последовательность необязательно различных рёбер E1,E2,...En называется маршрутом длины n, если существует последовательность V1, V2, ... Vn необязательно различных вершин, таких, что Ei = (Vi-1,Vi ).

17. Если совпадают, то маршрут замкнутый.

18. Маршрут, в котором все рёбра попарно различны, называется цепью.

19. Замкнутый маршрут, все рёбра которого различны, называется циклом. Если все вершины цепи или цикла различны, то такая цепь или цикл называются простыми.

20. Маршрут, в котором все вершины попарно различны, называется простой цепью.

21. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называется простым циклом.

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

23. Любой максимальный связный подграф (то есть, не содержащийся в других связных подграфах) графа G называется компонентой связности. Несвязный граф имеет, по крайней мере, две компоненты связности.

24. Граф называется k - связным (k - реберно - связным), если удаление не менее k вершин (ребер) приводит к потере свойства связности.

25. Маршрут, содержащий все вершины или ребра графа и обладающий определенными свойствами, называется обходом графа.

26. Длина маршрута (цепи, простой цепи) равна количеству ребер а порядке их прохождения. Длина кратчайшей простой цепи, соединяющей вершины vi и vj в графе G, называется расстоянием d (vi, vj) между vi и vj.

27. Степень вершины - число ребер, которым инцидентна вершина V, обозначается D(V).

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

Среди одноместных операций наиболее употребительны: удаление и добавление ребра или вершины, стягивание ребра (отождествление пары смежных вершин), подразбиение ребра (т.е. замена ребра (u, v) на пару (u, w), (w, v), где w - новая вершина) и др.

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

28. Два графа G1=(V1;E1), G2=(V2;E2),называются изоморфными, если существует взаимнооднозначное соответствие между множествами вершин V1 и V2 и между множествами рёбер Е1 и Е2, такое, чтобы сохранялось отношение инцидентности.

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

Теорема 1.

Пусть задан граф G=(V;E),где V - множество вершин, E - множество рёбер, тогда 2[E]=У(V), т.е. удвоенное количество рёбер равно сумме степеней вершин.

Теорема 2. (Лемма о рукопожатиях)

В конечном графе число вершин нечетной степени чётно.

Теорема 3.

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

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

Свойства связных графов.

1. Связный граф остается связным после удаления ребра тогда и только тогда, когда это ребро содержится в цикле.

2. Связный граф , имеющий К вершин , содержит по крайней мере К-1 ребро.

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

4. В графе с N вершинами и К компонентами связности число рёбер не превышает 1/2(N-K)(N-K+1).

5. Пусть у графа G есть N вершин . Пусть D(G)- минимальная из степеней вершин этого графа . Тогда D(G) > 1/2 (N-1).

29. Связный граф без циклов называется деревом.

Эквивалентные определения дерева.

1. Связный граф называется деревом, если он не имеет циклов.

2. Содержит N-1 ребро и не имеет циклов.

3. Связный и содержит N-1 ребро.

4. Связный и удаление одного любого ребра делает его несвязным.

5. Любая пара вершин соединяется единственной цепью.

6. Не имеет циклов и добавление одного ребра между любыми двумя вершинами приводит к появлению одного и только одного цикла.

1.4 Задачи на графах

Описание различных задач на графах.

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

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

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

Задача о кратчайшей цепи

замена оборудования

составление расписания движения транспортных средств

размещение пунктов скорой помощи

размещение телефонных станций

Задача о максимальном потоке

анализ пропускной способности коммуникационной сети

организация движения в динамической сети

оптимальный подбор интенсивностей выполнения работ

синтез двухполюсной сети с заданной структурной надежностью

задача о распределении работ

Задача об упаковках и покрытиях

оптимизация структуры ПЗУ

размещение диспетчерских пунктов городской транспортной сети

Раскраска в графах

распределение памяти в ЭВМ

проектирование сетей телевизионного вещания

Связность графов и сетей

проектирование кратчайшей коммуникационной сети

синтез структурно-надежной сети циркуляционной связи

анализ надежности стохастических сетей связи

Изоморфизм графов и сетей

структурный синтез линейных избирательных цепей

автоматизация контроля при проектировании БИС

Изоморфное вхождение и пересечение графов

локализация неисправности с помощью алгоритмов поиска МИПГ

покрытие схемы заданным набором типовых подсхем

Автоморфизм графов

конструктивное перечисление структурных изомеров для

производных органических соединений

синтез тестов цифровых устройств

1.5 Обзор аналогов

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

Возможно так же применение встроенных средств рисования многих редакторов, но при этом нет возможности строить матрицы инценденций и смежности и обращатся к вершинам и ребрам как к объектам.

Выводы

o Начало теории графов как математической дисциплины было положено Эйлером в его знаменитом рассуждение о Кенигсбергских мостах.

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

o Теория графов находит широкое применение в различных областях науки и техники:

o Разновидностью графов являются деревья. Связный граф без циклов называется деревом.

o Из всех математических объектов графы занимают одно из первых мест в качестве формальных моделей реальных систем.



2. ПРОЕКТИРОВАНИЕ ПРОГРАММНОГО КОМПЛЕКСА

2.1 Математическое описание графов

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

Граф G = (X, A) задаётся парой конечных множеств X и A. Элементы первого множества x1, x2, ..., xn называются вершинами графа (при графическом представлении им соответствуют точки). Элементы второго множества a1, a2, ..., am называются рёбрами. Каждое ребро определяется парой вершин (при графическом представлении ребро соединяет две вершины графа). Если рёбра графа G определяются упорядоченными парами вершин (т.е. указывается, какая вершина является первой, какая - второй какая - третьей и т.д.), то G называется ориентированным графом (на чертеже при изображении ориентированного графа на каждом ребре ставят стрелку, указывающую его направление).

Ориентированный граф с пятью вершинами и семью рёбрами изображён на рисунке 2.1.

Рис. 2.1Ориентированный граф Рис. 2.2 Неорентированный граф

Если две вершины соединены двумя или более рёбрами, то все эти рёбра называются параллельными (например, рёбра a4 и a5). Если начало и конец ребра совпадают, то такое ребро называется петлёй (например, ребро a7). Граф без петель и параллельных рёбер называется простым.

Если ребро ak определяется вершинами xi и xj (будем обозначать этот факт следующим образом: ak = (xi, xj), то говорят, что ребро ak инцидентно вершинам xi и xj.

Последовательность вершин xi1, xi2, ..., xik, таких, что каждая пара (xij-1, xij) при 1 < j k определяет ребро, называется маршрутом в графе G. Вершины xi1, xik называются концевыми вершинами маршрута, все остальные входящие в него вершины - внутренними.

Маршрут, в котором все определяемые им рёбра различны, называется цепью. Цепь называется замкнутой, если её концевые вершины совпадают. Замкнутая цепь, в которой все вершины (за исключением концевых) различны, называется циклом. Незамкнутая цепь, в которой все вершины различны, носит название путь.

Две вершины xi и xj называются связанными в графе G, если в нём существует путь, для которого эти вершины являются концевыми (его называют xi xj - путём). Граф G называется связным, если каждые две вершины в нём являются связанными. На рисунке 2 изображён простой, неориентированный, связный граф. Последовательность вершин x1, x3, x4, x5, x2 определяет, например, x1 x2 - путь, а последовательность вершин x3, x7, x5, x4, x3 - цикл.

На рисунке 2.3 изображён ориентированный взвешенный граф. Направление каждого ребра указано стрелкой. Числа указывают веса рёбер. Вершины, обозначенные буквой x (с индексами), рёбра - буквой a (с индексами).



Рис. 2.3 Ориентированный взвешенный граф

Для ориентированного графа G = (X, A), имеющего n вершин, матрицей смежности называется квадратная матрица M = (mij) размерности n x n, элементы которой определяются следующим образом:

Такое название матрицы связано с тем, что две вершины графа, являющиеся концевыми для некоторого ребра, называются смежными. Таким образом, матрица смежности вполне определяет структуру связей вершин графа. Количество единиц в i_ой строке матрицы M равно числу рёбер исходящих из вершины xi. Количество единиц в j_ом столбце матрицы M равно числу рёбер, входящих в вершину xj.

Приведём матрицу смежности для графа, изображённого на рис.2.3.

	x1	x2	x3	x4	x5	x6	x7	x8
x1	0	1	0	1	0	0	1	0
x2	0	0	0	1	0	0	0	0
x3	0	1	0	1	1	1	0	0
x4	0	0	0	0	1	0	0	1
x5	0	0	0	0	0	0	0	1
x6	0	0	0	0	1	0	0	0
x7	0	0	0	1	0	0	0	0
x8	0	0	0	0	0	1	1	0



Для неориентированного графа элемент mij матрицы смежности M равен 1 тогда и только тогда, когда существует ребро, инцидентное вершинам xi и xj (т. е. когда эти вершины являются смежными). Легко видеть, что матрица смежности неориентированного графа является симметрической.

2.2 Матрица достижимости

Будем говорить, что вершина xi ориентированного графа G достижима из вершины xj, если в G существует ориентированный xi xj путь.

Для ориентированного графа G = (X, A), имеющего n вершин, матрицей достижимости называется квадратная матрица C = (cij) размерности n x n, в которой элемент cij=1 тогда и только тогда, когда вершина xj достижима из вершины xi. В противном случае cij=0.

Так, например, для графа, изображённого на рисунке, элемент c76 его матрицы достижимости равен единице, так как существует x7 x6 - путь, проходящий через вершины x4, x8. Элемент c83 этой матрицы равен нулю, поскольку в вершину x3 нельзя попасть из вершины x8.

Приведём матрицу достижимости для графа, изображённого на рис.2.3.

	x1	x2	x3	x4	x5	x6	x7	x8
x1	0	1	0	1	1	1	1	1
x2	0	0	0	1	1	1	1	1
x3	0	1	0	1	1	1	1	1
x4	0	0	0	0	1	1	1	1
x5	0	0	0	1	0	1	1	1
x6	0	0	0	1	1	0	1	1
x7	0	0	0	1	1	1	0	1
x8	0	0	0	1	1	1	1	0



2.2 Алгоритм построения матрицы достижимости графа G, исходя из матрицы смежности этого графа

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

Будем разрабатывать требуемый алгоритм в расчёте на его выполнение с помощью ЭВМ.

Это значит, что алгоритм должен содержать следующие основные шаги:

Ввести в ЭВМ матрицу смежности M;

Преобразовать матрицу M в матрицу достижимости;

Вывести матрицу достижимости.

Детализацию предписаний о вводе и выводе матрицы мы отложим до момента рассмотрения конкретного языка общения с ЭВМ. Ууточним этап преобразования матрицы:

Возьмём вершину xk исходного графа.

Будем один за другим просматривать пути, входящие в вершину xk.

Пусть выбран один из них: xi-xk_путь. Теперь просматриваем пути, исходящие из вершины xk.

Пусть xk-xi_путь любой из них. Мы можем констатировать наличие в рассматриваемом графе xi-xj_пути (проходящего через вершину xk). Следовательно в матрице достижимости графа элемент cij должен равняться единице. Поскольку мы строим матрицу достижимости на месте матрицы смежности M, мы должны положить mij=1.

Описанную процедуру просмотра всех путей, входящих в вершину xk и выходящих из неё, а также внесение единиц в матрицу M на назовём обработкой вершины xk.

Можно строго доказать (опускаем это доказательство), что, последовательно обрабатывая каждую вершину исходного графа от x1 до xn, мы в итоге получим требуемую матрицу достижимости.

Таким образом, предписание “Преобразовать матрицу M в матрицу достижимости” может быть заменено предписанием:

для k=1 до n выполнять (Обработать вершину xk).

Для дальнейшей детализации алгоритма необходимо описать процедуру обработки вершины xk в терминах манипулирования элементами преобразуемой матрицы M.

Для того чтобы рассматривать пути, входящие в вершину xk, необходимо последовательно перебирать элементы k_го столбца матрицы M (организовать цикл по i от 1 до n).

Если элемент mik=1, то существует xi-xk_путь. Далее, зафиксировав взятое i, необходимо рассмотреть все пути, исходящие из вершины xk. Для этого нужно просмотреть все элементы k-ой строки (организовать цикл по j).

Если элемент mk=1, то существует xk-xj_путь. Получается, что существует (происходящий через вершину xk) xi-xj_путь. В таком случае следует положить mi=1.

Теперь предписание “Обработать вершину xk“ будет выглядеть так:

для i=1 до n выполнять

(если (mik=1) то

(если j=1 до n выполнять

(если (mki=1) то (mij=1))))

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

В рассматриваемом примере мы продемонстрировали пошаговую разработку алгоритма на основе структурного подхода. На каждом шаге уточняются, детализируются, заменяются новыми одно или несколько предписаний. Для организации действий используются только выделенные управляющие структуры. Шаги детализации продолжаются до тех пор, пока все подлежащие выполнению действия не сведутся к действиям, допустимым для предполагаемого исполнителя алгоритма. В качестве исполнителя разрабатываемого нами алгоритма должна выступать ЭВМ, “вооружённая” транслятором с алгоритмического языка высокого уровня.

Алгоритм для вычисления матрицы достижимости Path по заданной матрицы смежности Adj, рис.2.4.



Рис.2.4 Алгоритм построения матрицы достижимости

2.1 Определение возможностей редактора

Идея разработки редактора изучения графов, возникла из за потребности иметь инструментарий для моделирования связей систем и органов человека, в рамках различных направлений исследования. При этом необходимо иметь возможность указывать различные типы связей: управляет, контролирует, подчинятеся, подавляет. Для того что бы иметь возможность визуально различать связи, необходимо обеспечить возможность определения различных связей дугами различных цветов. При этом необходимо обепечить возможность накладывать графы друг на друга, и просматривать нужные связи. (возможно на разных слоях, либо блокируя, разрешая связи определенного цвета).

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

С учетом вышесказанного перечислим требования к разрабатываемому редактору:

o возможность создавать граф выбором вершин и дуг, соединяющих вершины;

o возможность выбора различных цветов для разных дуг;

o автоматическое генерирование матрицы инцинденции и матрицы смежности всех вершин и дуг графа;

o автоматическое генерирование матрицы инцинденции и матрицы смежности вершин и дуг определенного цвета графа;

o вычисление числовых характеристик графа;

o возможность сохранения созданного графа;

o возможности определения длины пути мужду выбранными вершинами

o возможность вывести граф, и матрицы на печать.

2.2 Разработка интерфейса программного комплекса

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

· выделить

· цвет

· ориентированная дуга

· неорентированная дуга

· вершина

Рис.2.1 Структура программы



2.3 Диаграмма использования

Рис.2. 2 Диаграма использования редактора

2.4 Диаграмма деятельности

Детализация поведения системы осуществляется последовательно при разработке диаграмм состояний, последовательности и деятельности. Диаграмма деятельности редактора приведена на рис.2. 3



Рис.2. Диаграмма деятельности

2.5 Определение классов и модулей программы

Редактор разрабатывается с учетом объектно-ориентированного подхода. Для реализации программы определены следующие классы:

Interface Summary
Interface	Description
Edge	ребро в графе
Node	узел в графе.
Class Summary
Class	Description
AbstractEdge	класс, обеспечивающий удобство реализации для ряда методов в интерфейсе типа Ребро
AbstractNode	класс, который обеспечивает удобство реализации для ряда методов в интерфейсе типа Узел
AdjacencyListGraph
CircleNode	круглый окрашенный узел
CircularNode	круглый узел, заполняемый цветом.
ColorEditor
EnumEditor	редактор свойств для перечисляемых типов.
FontEditor
Graph	граф, состоящий из выбираемых вершин и ребер.
GraphFrame	эта форма показывает панель инструментов и граф.
GraphPanel	панель рисования графа
LineEdge	ребро, которое имеет форму прямой линии.
Main	программа для редактирования графов.
NoteNode
PointNode	невидимый узел, который использует в панели инструментов, чтобы создать ребро.
PropertySheet	компонент заполненения редактора для всех редактируемых свойств объекта.
SimpleGraph	простой граф с круглыми узлами и прямыми ребрами.
SquareNode
ToolBar	панель инструментов, которая содержит иконки узлом и ребер. одна и та же иконка может быть выбрана несколько раз.
Enum Summary
Enum	Description
ArrowHead	Этот класс определеяет направленые ребра различных форм
LineStyle	этот класс определяет стиль линий различной формы.

Опишем некоторые используемые функции



Method Summary

Methods
Modifier and Type	Method and Description
void	adjacency() Выводит окно с матрицей смежности
boolean	checkLabel() Проверяет, имеют ли все компоненты графа метки
void	clearAll() очистка всех узлов и ребер в этой панель графа.
static void	drawGrabber(java.awt.Graphics2D g2, double x, double y) рисование одного "grabber"
void	editSelected()
int	getEdgeIndex(java.lang.String label) Возврашает индекс компонента графа
int	getNodeIndex(java.lang.String s) Возврашает индекс компонента графа
java.awt.Dimension	getPreferredSize() возврат предпочтительного размера графа.
void	incidence() Создает фрейм с матрицей инциденции графа
void	paintComponent(java.awt.Graphics g) рисует на панели компоненты графа.
void	removeSelected() удаление выбранного узла или ребра
void	reverseEdges() реверсирует все ребра

Для работы в редакторе создана следующая иерархия классов

Class Hierarchy

o java.lang.Object

o grapheditor.AbstractEdge (implements grapheditor.Edge)

o grapheditor.LineEdge

o grapheditor.AbstractNode (implements grapheditor.Node)

o grapheditor.CircleNode

o grapheditor.CircularNode

o grapheditor.NoteNode

o grapheditor.PointNode

o grapheditor.SquareNode

o java.awt.Component (implements java.awt.image.ImageObserver, java.awt.MenuContainer, java.io.Serializable)

o java.awt.Container

o javax.swing.JComponent (implements java.io.Serializable)

o grapheditor.GraphPanel

o javax.swing.JPanel (implements javax.accessibility.Accessible)

o grapheditor.PropertySheet

o grapheditor.ToolBar

o java.awt.Window (implements javax.accessibility.Accessible)

o java.awt.Frame (implements java.awt.MenuContainer)

o javax.swing.JFrame (implements javax.accessibility.Accessible, javax.swing.RootPaneContainer, javax.swing.WindowConstants)

o grapheditor.GraphFrame

o grapheditor.Graph (implements java.io.Serializable)

o grapheditor.SimpleGraph

o grapheditor.AdjacencyListGraph

o grapheditor.Main

o java.beans.PropertyEditorSupport (implements java.beans.PropertyEditor)

o grapheditor.ColorEditor

o grapheditor.EnumEditor

o grapheditor.FontEditor

Interface Hierarchy

o java.lang.Cloneable

o grapheditor.Edge (also extends java.io.Serializable)

o grapheditor.Node (also extends java.io.Serializable)

o java.io.Serializable

o grapheditor.Edge (also extends java.lang.Cloneable)

o grapheditor.Node (also extends java.lang.Cloneable)

Enum Hierarchy

o java.lang.Object

o java.lang.Enum<E> (implements java.lang.Comparable<T>, java.io.Serializable)

o grapheditor.ArrowHead

o grapheditor.LineStyle

Выводы

o В памяти ЭВМ графы хранятся в виде матриц

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

o Редактор должен позволять строить ориентированный и неорентирвоанный графы.

o Необходимо реализовать возможность создания ребер и вершин различных цветов.

o Редактор также должен строить матрицы смежности и инцендентности графов.



3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ РЕДАКТОРА ИЗУЧЕНИЯ ТЕОРИИ ГРАФОВ

3.1 Выбор программной платформы и среды разработки

Программа разрабатывалась с на языке программирования
JAVA.

Язык программирования Java - это высокоуровневый объектно-ориентированный язык, разработанный в компании Sun Microsystems.

...