Введение 3
Актуальность работы 3
Цель работы 4
Постановка задачи 4
Структуры данных 4
1 Построение дерева графа 6
1.1 Алгоритм 6
1.2 Обсуждение алгоритма 7
1.3 Пример работы алгоритма 8
2 Построение независимого контура 11
2.1 Алгоритм 11
2.2 Обсуждение алгоритма 13
2.3 Пример работы алгоритма 14
3 Проверка физической реализуемости системы, заданной графом 16
3.1 Метод проверки физической реализуемости 16
3.2 Алгоритм 17
4 Составление системы уравнений независимых контуров 19
4.1 Составление уравнения независимого контура 19
4.2 Составление системы уравнений независимых контуров 20
4.3 Пример составления системы уравнений независимых контуров 22
5 Заключение 23
Список литературы 24
Приложение 25
Купить

Актуальность работы
Теория графов является мощным инструментом моделирования и рас­чета систем различной физической природы. При этом применение методов теории графов встречает некоторые трудности.
Во-первых, отсутствует прямой метод определения физической реали­зуемости системы заданной графом, а именно выполнения фундаменталь­ных законов сохранения последовательной переменной (закона сохранения импульса в механике и закона сохранения заряда в электричестве). В тео­рии физическая реализуемость системы, заданной графом, отражается в так называемой гамильтоновости графа. Граф является гамильтоновым, если он обладает гамильтоновым циклом (или контуром). Гамильтоновым называется цикл графа, проходящий через каждую его вершину без повто­рения вершин (кроме, быть может, совпадающих концевых вершин) и ре­бер. Гамильтонов цикл не обязательно содержит все ребра графа. Очевид­но, что гамильтоновым может быть только связный граф. К сожалению, в отличие от графов Эйлера, где имеется конкретный критерий для гра­фа быть эйлеровым, для гамильтоновых графов подобного критерия нет. Более того, задача проверки существования гамильтонова цикла оказыва­ется NP-полной. Большинство известных утверждений имеет вид: «если граф имеет достаточное количество ребер, то граф является гамильтоно­вым». Таковыми являются теорема Дирака, теорема Оре [1], условие Поша [1], условие Бонди-Хватала [2]. Задача отыскания гамильтонова цикла или эквивалентная задача коммивояжера являются практически востребован­ными, но для нее неизвестен (и, вероятно, не существует) эффективный общий алгоритм решения.
Во-вторых, известные методики построения математических моделей с использованием, например, системы уравнений независимых контуров, на практике используют ручные операции и не могут быть применены для сложных систем.
Таким образом, тема квалификационной выпускной работы является, несомненно, актуальной.
Цель работы
Целью работы является создание алгоритмического и программного обеспечения для получения математической модели системы, заданной гра­фом. Исходной информацией служит матрица смежности A связного ори­ентированного графа G с множеством вершин V = {0,...,m — 1g. В ходе построения математической модели необходимо определить физическую реализуемость системы, заданной графом.
Постановка задачи
Анализ цели работы показал, что для ее достижения необходимо ре­шить следующую совокупность взаимосвязанных и взаимодополняющих задач:
1. Разработка и реализация алгоритма построения дерева графа по мат­рице смежности.
2. Разработка и реализация алгоритма построения совокупности неза­висимых контуров.
3. Разработка и реализация метода и соответствующего алгоритма опре­деления физической реализуемости системы, заданной графом.
4. Разработка и реализация алгоритма построения системы уравнений независимых контуров.
Путем объединения решений поставленных задач будет получен алгоритм, результатом работы которого будет математическая модель системы в виде системы уравнений независимых контуров. В дальнейшем на основе систе­мы уравнений независимых контуров может быть построена система урав­нений с учетом характеристик элементов физической системы, заданной графом [3].
Структуры данных
Высокая скорость работы любого алгоритма достигается за счет опти­мизации операций, которые выполняются на каждом шаге. Кроме того, для повышения производительности необходимо уделить отдельное внима­ние структурам данных, которыми оперирует алгоритм. В данной рабо­те основными структурами данных являются матрицы(двумерные масси­вы), массивы и списки. Массивы лучше использовать тогда, когда струк­тура данных остается неизменной во время работы алгоритма, а доступ к определенному элементу необходимо выполнять достаточно быстро. Спис­ки же будем использовать в том случае, если структура данных во время работы алгоритма изменяется динамически, например, если добавляются новые элементы. При этом скорость доступа к элементу списка, отлич­ного от начального и последнего, не представляет интереса. Стоит отме­тить, что в данной работе практически везде список может быть заме­нен на стек, так как в основном списки используются для вставки эле­ментов в конец списка и удаления элементов из конца списка. Операци­ями над списками будут следующие: операция вставки элементов в ко­нец списка(ризД), операция извлечения элемента из конца списка(рор), операция вставки элементов в начало списка(ип5Дг/£) и операция удале­ния элементов из начала списка(зДг/£). Так как список является мульти­множеством, сохраняющим порядок вхождения элементов, то для упро­щения описания алгоритмов будем использовать язык теории множеств. Например, для инициализации списка S будем использовать запись вида S := 0, которая означает создание пустого списка, где |S| - количество элементов в списке. Так же будем использовать кванторы теории мно­жеств при выборке элементов из массива или списка. Например, выра­жение R := {Vu 2 V : color[u] = WHITE, avu = 0g следует понимать так: «выбрать все элементы u из множества V, для которых выполняется следующее: color[u] = WHITE и avu = 0; результат сохранить в список R». Стоит отметить, что если R не было определено на этапе инициализа­ции алгоритма, то подобная запись используется для компактности, чтобы в одном выражении не было слишком много условий. Это означает, что при программной реализации не обязательно создавать список R, а доста­точно задать условие u 2 V Л color [u] = WHITE Л avu = 0 в условном операторе. Структуры данных будем обозначать прописными латинскими буквами. Для определенного элемента будем использовать соответствую­щие строчные буквы с индексами. Например, если список обозначается S, то его i-тый элемент si. Для правого конца списка S будем использовать обозначение stop. Матрицы будем обозначать жирными буквами. Элементы матрицы A, обозначаются через ai;j. Для обозначения i-й строки матрицы A будем использовать ai;*, а для j-го столбца a*j.
Купить