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

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

Введение

Теория графов -- один из разделов современной математики, имеющий большое прикладное значение. Проблемы оптимизации тепловых, газовых и электрических сетей, вопросы совершенствования алгоритмов и создание новых химических соединений связаны с фундаментальными свойствами таких абстрактных математических объектов, как графы. Долгое время задачи теории графов решались вручную, с появлением компьютеров появилась возможность написания специальных программ на алгоритмических языках. Позднее появились пакеты аналитических вычислений Mathematica, MATLAB, Mathcad и Maple, позволяющие выполнять аналитические символьные преобразования. Для решения задач, объектами которых являются графы, эти пакеты просто незаменимы. В системе Maple есть еще и специализированная библиотека networks, составленная из операторов для работы с графами.

Целью курсовой работы: построение графов в Maple.

Чтобы достичь цели, нам потребуется решить следующие задачи:

· Изучить теоретические основы графов.

· Показать применение теоретических знаний на практике.

1. Определение графа

Граф (англ. graph) -- совокупность непустого множества вершин и наборов пар вершин (связей между вершинами); основной объект изучения математической теории графов.

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

Теория графов -- один из разделов современной математики, имеющий большое прикладное значение. Проблемы оптимизации тепловых, газовых и электрических сетей, вопросы совершенствования алгоритмов и создание новых химических соединений связаны с фундаментальными свойствами таких абстрактных математических объектов, как графы. Долгое время задачи теории графов решались вручную, с появлением компьютеров появилась возможность написания специальных программ на алгоритмических языках. Позднее появились пакеты аналитических вычислений Mathematica, MATLAB, Mathcad и Maple, позволяющие выполнять аналитические символьные преобразования. Для решения задач, объектами которых являются графы, эти пакеты просто незаменимы. В системе Maple есть еще и специализированная библиотека networks, составленная из операторов для работы с графами.

2. Радиус и диаметр графа

Задается граф и определяются его радиус, диаметр и центр. Исследуется неориентированный граф. Граф задается оператором graph(V,E), где V -- множество вершин графа, E -- множество ребер. В качестве вершин можно использовать произвольные имена в кавычках, например "my nomer" (включая пробелы), переменные, значения которых ранее не определяются, или, что проще, просто номера. В данном случае номера вводятся оператором повторения V:={$1..n}, заменяющим простое перечисление V:={1,2,3,4,5}. Другой оператор повторения, служащий для этих же целей, имеет вид V:={seq(i,i=1..n)}.

Для задания графа можно использовать также операторы new(G), addvertex и addedge.

Оператор вывода рисунка графа на печать имеет три варианта формы вывода вершин: Concentric, Linear и, по умолчанию, равномерно по окружности.

Рис. 1

3. Реберный граф

Рассмотрим граф. Вершины графа задаются перечислением имен (в данном случае, номеров) оператором addvertex, а ребра -- оператором connect. При этом можно сразу задать все ребра, инцидентные одной вершине, например ребра (2, 1), (2, 4), (2, 5): connect(2,{1,4,5},G). В операторе draw для изображения графа дана опция формы рисунка -- Concentric. Список вершин в этой опции указывает на порядок изображения вершин равномерно по окружности против часовой стрелки, начиная с нулевого угла, отложенного от горизонтальной оси координат, направленной направо. По умолчанию оператор draw также использует эту опцию и на первое место помещает вершину с меньшим номером. Для того чтобы изображение появилось на экране, необходимо двоеточие после оператора draw заменить на точку с запятой. Здесь и в некоторых других программах после оператора draw ставится двоеточие, чтобы не дублировать имеющийся в тексте рисунок.

В двойном цикле в соответствии с определением реберного графа формируется множество его ребер. Ребра исходного графа обозначаются в системе Maple как e1, e2.. en. Поэтому для того, чтобы они были доступны, в цикле применяется оператор || «приклеивания» номера к букве e. Полученное множество ребер E1 позволяет создать и изобразить искомый реберный граф G1.

Рис. 2

Рис. 3

4. Компоненты сильной связности графа

Рассмотрим орграф, содержащий, очевидно, три компоненты сильной связности: (1, 2), (3, 4), (5, 6). Дуги задаются списком, например [1, 2], а не множеством, как в неографе: {1, 2}. К сожалению, в Maple рисунки орграфа и неографа не отличаются Рис. 1 (дуги стрелками не выделяются). Поэтому рисунок, полученный оператором draw(G), непохож на рис. 1 (дуги туда и обратно сливаются в одну). В программе определяется матрица достижимости M, несимметричная для орграфа. Строки матрицы соответствуют вершинам, от которых идет путь, а столбцы -- вершинам, в которые путь приходит. Рассматривая матрицу M, замечаем, что из вершин 1 и 2 достижимы все вершины графа (строки 1 и 2 не содержат нулей), сами же вершины 1 и 2 достижимы из множества {1, 2}. Пересечением множеств {1, 2, 3, 4, 5, 6} и {1, 2} является множество {1, 2}. Это множество и является компонентой сильной связности графа. Операция пересечения множеств эквивалентна замене элементов матрицы достижимости произведением элементов и их симметричных образов. Это и выполнено в программе в двойном цикле по i и j. Начальные значения переменных цикла from и шаг by, по умолчанию равные 1, по обыкновению, не пишутся. В полученной матрице в последнюю строку дописываются номера вершин. Следует отметить характерную для Maple конструкцию определения и одновременного вызова функции, создающей последовательность номеров вершин: (j) -> j. Ориентация вектора номеров создается опцией row . Далее, просматривая первую строку получившейся матрицы, заносим в первый список связности номера столбцов с ненулевыми элементами и вычеркиваем соответствующие строки и столбцы. Эта операция повторяется в цикле по j до исчерпания матрицы. Используются операторы DeleteColumn и DeleteRow из пакета LinearAlgebra. Эти опера- торы не могут вычеркивать последние строку и столбец из матрицы, поэтому в программу введен условный оператор if nV1<>n.

Рис 4

Рис. 5

5. Изображение орграфа

Недостатком процедуры draw системы Maple является то, что орграфы изображаются, как неографы.

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

Рис. 6

Рис. 7

6. Кратчайший путь в орграфе

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

Рис. 8

7. Распаковка десятичного кода

Сначала десятичный код преобразуется в список нулей и единиц, соответствующий двоичной записи числа справа налево. Затем вычисляется длина списка и список обращается, превращаясь в привычную запись двоичного числа. Переменная Z имеет тип последовательности exprseq . В процессе работы цикла по всем элементам последовательности различаются два случая: текущий элемент равен 1 или 0. В случае, когда элемент равен 1, в множество ребер графа добавляется ребро {v1,v2}, где номер v2 всякий раз увеличивается, а v1 принимает каждый следующий раз значение v2 либо вычисляется при встрече нуля (или нулей) в ряду элементов. При движении вперед, когда список ребер растет, растет и временный список пройденных вершин F. При движении назад (к корню) список ребер не меняется, а список пройденных вершин F уменьшается посредством удаления последнего элемента. Функцию удаления выполняет присваивание F:=F[1..-2] с перечислением элементов от первого до предпоследнего. Последний элемент списка длиной n имеет вид F[n] или F[-1]. Последняя запись удобна в том случае, когда неизвестна длина списка. Полученный список ребер вносится обычным образом в граф, изображение графа выводится на экран. В программе проявляется особенность алгоритма десятичной кодировки, в которой не сохраняется нумерация вершин. Для сохранения нумерации вершин дерева необходима другая кодировка, менее компактная и принципиально почти не отличающаяся от десятичной. В такой кодировке вместо единиц нужно ставить номера вершин.

Рис. 9

Рис. 10

8. Распаковка кода Прюфера

По заданному коду Прюфера программа определяет множество ребер и рисует закодированное дерево. Сначала оператор nops вычисляет число вершин (их на 2 больше числа элементов кода), затем, в соответствии с алгоритмом, в цикле по i производится набор ребер. Последнее ребро составляется из двух чисел (номеров вершин), оставшихся во вспомогательном множестве N, состоящем изначально из всех вершин дерева. Запись P:=P[2..-1] означает, что список P укорачивается на один первый элемент. Минус один в качестве последнего элемента в перечислении означает конец списка. Отдельно рассмотрим строку x1:=N minus convert(P,set). Код Прюфера не является множеством, да и не может быть им, так как в нем есть повторяющиеся элементы. Поэтому перед выполнением вычитания minus производится конвертация. Другой вариант этой строки имеет вид x1:=select(sq,N), где введена пользовательская функция проверки наличия аргумента функции в P: sq:=x->is(not member(x,T)). Функция select производит выбор из N всех тех элементов, которые удовлетворяют этому условию. Наблюдается некоторая неестественность использования функции «без аргумента», однако это характерно для Maple в таких операциях.

Рис. 11

9. Код Гапта

В следующей программе решается задача составления кода Гапта. Граф задается обычным образом: сначала создается список вершин, затем в операторе connect указываются соединения. Для того чтобы не повторять список вершин-листьев, используется обозначение v:=$5..12. Некоторой особенностью ввода данных является обозначение части вершин буквами, а части -- цифра- ми. Это вполне допустимо. Более того, буквы в Maple могут выполнять роль идентификаторов, им можно присваивать значения, в том числе даже слова. Например, если в начале программы, сразу после restart, задать A:=`корень`, то программа не воспримет это как ошибку; ответ будет тот же, а на рисунке вершина A будет подписана. Оператор shortpathtree алгоритма Дейкстры используется здесь не совсем по назначению. Он только превращает граф в корневое дерево с корнем в вершине A. Основой программы являются оператор daughter, определяющий список сыновей вершины дерева, и оператор nops, вычисляющий длину z списка. Эта длина и записывается слева в код Гапта: kod:=z,kod.

Рис. 12

Рис. 13

10. Топологическая сортировка сети

граф программный топологический алгоритм

В алгоритме используется удобная функция delete, позволяющая удалять список вершин и соответствующие дуги. Каждый уровень организуется в виде списка для того, чтобы использовать результаты в операторе Linear топологически упорядоченной сети. После формирования списка вершин одного уровня эти вершины удаляются из графа. Работа цикла while NV<>0 do продолжается до тех пор, пока множество вершин не станет пустым. Счетчик числа вершин -- NV. Копия графа H выводится на экран по полученным уровням. Если граф содержит цикл, то на очередном этапе поиска вершины с нулевой полустепенью захода список уровня окажется пустым и произойдет досрочный выход из цикла с помощью оператора break. К графу достаточно добавить, например, дугу [3,4], для того чтобы образовался контур и топологическая сортировка оказалась невозможной.

Рис. 14

Рис. 15

11. Паросочетание

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

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

Рис. 16

Рис. 17

12. Остов наименьшего веса

Приведем независимую программу решения задачи. Сначала определяется число остовов, затем для отыскания остова используется оператор из пакета networks. Число остовов. В специализированном пакете networks имеется функция counttrees(G) для определения числа остовов графа. Другой способ -- вычисление алгебраического дополнения любого элемента матрицы Кирхгофа, полученной по формуле (4.1) со с. 77. Для выполнения операций с матрицами (перемножения, умножения на число, вычитания, транспонирования) необходимо подключить. пакет LinearAlgebra. Чтобы не дублировать вывод результатов, уже приведенных на с. 77, операторы вычисления матриц инцидентности (incidence) и смежности (adjacency) завершаются двоеточием. Перемножить матрицы в Maple можно с помощью точки 1 (In.Transpose(In)-2*A), сразу получив матрицу, либо с помощью комбинации знаков &* и функции evalm: > B:=evalm(In&*Transpose(In)-2*A); В последнем случае результат не имеет тип Matrix, в чем можно убедиться, применяя оператор type(B,Matrix) проверки типа. Поэтому для дальнейших действий необходима конвертация: B:=convert(B,Matrix). Кроме того, для перемножения матриц A и B в пакете LinearAlgebra есть оператор MatrixMatrixMultiply(A,B). Если матрица Кирхгофа строится по формуле (4.2), то сначала надо получить какую-либо ориентацию графа. Это делается заменой фигурных скобок { } множества на квадратные скобки [ ] упорядоченной пары в описании ребер. Оператор op снимает фигурные скобки, после чего результат заключается в квадратные скобки. Все это выполняется в цикле по i: E1:=seq([op(ends(edges(G)[i],G))],i=1..n). Имея список дуг E1 и вершин, можно создать новый (уже ориентированный) граф и для него получить матрицу инцидентности. Параметр r введен для описания формата вывода рисунка графа в операторе draw. Отметим, что в 10-й версии Maple оператор Minor по умолчанию выдает значение определителя, поэтому дополнительного использования Determinant не требуется.

Рис. 18

Литература

1. Кирсанов М.Н. Графы в Maple Физмат 2007. - 168 с.

2. Носов В.А. Комбинаторика и теория графов. -- М.: МГУ, 1999. - 177 с.

3. Фляйшнер Г. Эйлеровы графы и смежные вопросы. -- М.: Мир, 2002. - 335 с.

4. Харари Ф. Теория графов. -- М.: Едиториал УРСС, 2003 - 296 с.

Размещено на Allbest.ru