Математические методы

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

высшего образования

«Оренбургский государственный университет»

Университетский колледж

Предметно-цикловая комиссия информационных технологий

С. А. НУРМАНОВА

МАТЕМАТИЧЕСКИЕ МЕТОДЫ

Оренбург

2016

Содержание

1 Инструкционная карта…………………………………………………….....	3
2 Лабораторная работа №1 Матричное представление графа с информационной поддержкой…………………………………………………	5
2.1 Теоретические сведения………………………………………….…………	5
2.2 Задания к лабораторной работе №1……………………………………….	8
2.3 Вопросы к защите лабораторной работы № 1…………………………….	10
3 Лабораторная работа №2 Нахождение кратчайшего остова в графе алгоритмом Краскала……………………………………………………………	10
3.1 Теоретические сведения……………………………………………………	11
3.2 Задание к лабораторной работе№2………………………………………..	13
3.3 Вопросы к защите лабораторной работы №2………………………………	14
4 Лабораторная работа №3 Нахождение кратчайшего остова в графе алгоритмом Прима……………………………………………………………….	15
4.1 Теоретические сведения……………………………………………………	15
4.2 Задания к лабораторной работе №3……………………………………….	16
4.3 Вопросы к защите лабораторной работы №3………………………………	16
Список использованных источников…………………………………………...	17

1 Инструкционная карта

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

Задачи:

теоретический компонент:

- изучить основные понятия и принципы моделирования;

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

2) познавательный компонент:

- получить представление о роли и месте знаний по дисциплине «Математические методы» при освоении смежных дисциплин по выбранной специальности и в сфере профессиональной деятельности;

- овладеть навыками самостоятельного изучения учебной литературы по математическим методам;

3) практический компонент:

- уметь составлять простейшие математические модели задачи, возникающие в практической деятельности человека;

- решать задачи, соответствующие изучаемым разделам;

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

1.1 Оборудование (приборы, материалы, дидактическое  обеспечение)

методические рекомендации к выполнению лабораторной работы; задание и инструкционная карта; компьютер; компьютерные программы: Microsoft Office, среда программирования Delphi

1.2 Порядок выполнения лабораторной работы

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

1.3 Содержание  отчета 

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

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

2 Лабораторная работа №1 Матричное представление графа с информационной поддержкой

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

2.1 Теоретические сведения

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

Определение.  Графом G=G(V, U) называется совокупность двух множеств – непустого множества V (множества вершин) и множества U отрезков, соединяющих соответствующие вершины. Множество U  называется множеством ребер.

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

Число вершин графа G обозначим v, а число ребер - u:

.

Определение.  Ориентированный граф или орграф G=G(V, U) – это такой граф, который состоит из множества V вершин и множества U  упорядоченных пар элементов из V (рис. 2).

Элемент множества U называется дугой.

Если (vi, vj)∈ U, то vi называется начальной вершиной дуги (vi, vj), а vj называется конечной вершиной.

Определение. Неориентированный граф или н-граф G = G(V, U) состоит из конечного множества вершин V и множества ребер U (рис. 1).

В отличие от ориентированного графа, здесь каждое ребро (vi, vj) соответствует неупорядоченной паре вершин: если (vi, vj) – неориентированное ребро, то (vi, vj) = (vj, vi).

Определение. Ребро, которое соединяет вершину саму с собой, называется петлей.

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

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

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

Если V′=V, то G′ называется остовным подграфом G (остовом).

Определение. Граф называется полным, если любые две его вершины соединены ребром. Полный граф с n вершинами обозначается через Gn.

Определение. Степенью вершины v для неориентированного графа, обозначается d(v), называется количество ребер, инцидентных этой вершине.

Вершина степени 0 называется изолированной.

Вершина степени 1 называется висячей.

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

Теорема. (Теорема Эйлера)  Сумма степеней вершин графа равна удвоенному количеству ребер:

.

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

Определение. Матрицей смежности графа G называется квадратная матрица A(G)=[aij] порядка n, где n – число вершин графа, у которой

Определение. Матрицей инцидентности орграфа G называется (n×m) –матрица B(G)=[bij], у которой

Определение. Матрицей инцидентности н-графа G называется (n×m) –матрица B(G)=[bij], у которой

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

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

Число n называется длиной пути.

Определение. Путь без повторяющихся ребер называется цепью, без повторяющихся вершин - простой цепью.

Путь может быть замкнутым (v0=vn).

Определение. Замкнутый путь без повторяющихся ребер называется циклом (или контуром в орграфе); без повторяющихся вершин (кроме первой и последней) - простым циклом.

Определение. Вершина vj орграфа G достижима из вершины vi, если либо vi=vj, либо существует путь из vi в vj (маршрут, соединяющий vi и vj).

Определение. Матрица достижимостей R = [rij] называется квадратная матрица порядка n, где n – число вершин графа и определяется следующим образом:

  1, если есть путь из vi в vj, 

  Rnxn=[rij] =

  0, если нет пути из vi в vj.

Контрдостижимым множеством Q(xi) графа G является множество таких вершин, что из любой вершины этого множества можно достигнуть вершины vi.

Определение. Матрица контрдостижимостей Q = [qij] называется квадратная матрица порядка n, где n – число вершин графа и определяется следующим образом:

  1, если есть путь из vj в vi, 

  Qnxn=[qij] =

  0, если нет пути из vj в vi.

Следует заметить, что столбец vi матрицы Q совпадет со строкой vi матрицы R, т. е. Q = RT, где RT – матрица, транспонированная к матрице достижимостей R.

2.2 Задания к лабораторной работе №1

Задание 1. Дан граф. Определить число рёбер и дуг, число вершин, степень всех вершин. Задать данный граф матрицами смежности, инциденции и достижимости  .

Вариант	Граф	Вариант	Граф
1		6
2		7
3		8
4		9
5		10

Задание 2. Граф задан матрицей смежности. Перевести матрицу смежности в матрицы инциденции, достижимости и контрдостижимости. Изобразить граф. Составить программу решения задачи в среде программирования Delphi.

Вариант	Матрица смежности	Вариант	Матрица смежности
1	А=	6	А=
2	А=	7	А=
3	А=	8	А=
4	А=	9	А=
5	А=	10	А=

2.3 Вопросы к защите лабораторной работы № 1

1. Что называется графом?

2. Какой граф называется орграфом?

3. Какой граф называется н-графом?

4. Что такое петля?

5. Какая вершина называется изолированной?

6. Что называется степенью вершины?

7. Какие вершины называются смежными?

8. Какие ребра называются инцидентными?

9. Что называется матрицей смежности графа?

10. Что называется матрицей инциденции графа?

11. Что называется маршрутом (путем) в графе?

12. Что такое цепь графа?

13. Какая цепь называется замкнутой?

14.  Что называется матрицей достижимости?

15. Что называется матрицей контрдостижимости?

3 Лабораторная работа №2 Нахождение кратчайшего остова в графе алгоритмом Краскала

Цель работы: Изучить алгоритмы Краскала для нахождения кратчайшего остова графа. Программно реализовать алгоритм Краскала.

3.1 Теоретические сведения

Определение. Деревом называется граф T(V, U) без циклов.

Лес – это граф, компоненты которого являются деревьями.

Ориентированное дерево T′ представляет собой свободный от петель ориентированный граф, соотнесенный граф которого является деревом.

Если дерево имеет хотя бы одно ребро, оно имеет хотя бы две вершины со степенью 1. Вершины степени 1 называются листьями. Другие вершины называются внутренними вершинами.

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

Если корень выбран, уровень вершины v определяется длиной единственной цепи из корня в вершину v.

Определение. Высотой дерева называется длина самой длинной цепи от корня до листа. Высоту дерева будем обозначать h(T).

Пример.

Теорема. Если в связном графе G, содержащем u ребер и v вершин и имеем v=u+1, то G является деревом.

Определение. Остовным деревом (остовом) графа называется дерево T, содержащее все вершины искомого графа.

Теорема. У каждого связного графа существует подграф, который является остовом.

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

Определение. Вес остова взвешенного графа G равен сумме весов, приписанных ребрам остова. Будем обозначать ω(T).

Определение. Минимальным остовом называется такой остов графа G, что вес T меньше или равен весу любого другого остова графа G.

Вес минимального остова будем обозначать ωmin(T).

Если граф G несвязный, он не может иметь остовного дерева, но у него есть остовный лес.

Алгоритм Краскала — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые описан Джозефом Крускалом в 1956 году.

Алгоритм Краскала может строить дерево одновременно для нескольких компонент связности, которые в процессе решения объединяются в одно связанное дерево.

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

Алгоритм состоит из следующей последовательности действий:

Создается список ребер R, содержащий вес ребра, номер исходной вершины ребра (i), номер конечной вершины ребра (j), признак включения данного ребра в дерево. Данный список упорядочивается в порядке не убывания весов ребер. Просматривается список R и выбирается из него n-1 ребро с минимальным весом, еще не включенное в результирующее дерево и не образующее цикла с уже построенными ребрами. Если все вершины включены в дерево и количество ребер на единицу меньше количества вершин, то алгоритм свою работу закончил. В противном случае осуществляется возврат к пункту 3.

Для реализации алгоритма Краскала на ПК необходимо:

Построить матрицу смежности исходного графа; Составить список ребер с их весами и отсортировать их одним из способов сортировки. Для того чтобы уменьшить время сортировки можно сортировать не весь список, а n-1 ребро, с минимальным весом; Для проверки на цикл можно использовать построение матрицы достижимости после каждого добавления ребра. Добавляем ребро vivj, смотрим есть ли единица в матрице достижимости на месте vivj, если есть, то ребро vivj не перебрасываем в матрицу смежности исходного остова, так как получаем цикл, если единицы нет, то ребро vivj заносим в матрицу смежности остова.

Пример. 

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

Решение. 

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

Начало	Конец	Вес
v4	v6	4
v2	v4	5
v3	v5	6
v1	v2	7
v1	v3	7
v3	v6	9
v5	v6	10
v1	v4	11
v2	v3	12

Используем для построения остова алгоритм Краскала. В графе выбираем ребро с минимальным весом. В нашем случае это ребро, соединяющее вершины и с весом, равным 4. Пусть, например, вершина будет корнем дерева. Далее выбираем ребра, инцидентные вершинам , и имеющие минимальный вес. Таким является ребро с весом 5, соединяющее вершины и . Включаем его в строящееся дерево. Затем к вершине присоединяем ребро с весом 7, соединяющее вершины и . К вершине присоединяем ребро с весом 7, соединяющее вершины и . И в заключение, к вершине присоединяем ребро с весом 6, соединяющее вершины и . Таким образом, получаем кратчайший остов. Минимальный вес построенного дерева равен: ωmin(T)=4+5+7+7+6=29.

Так как мы в качестве корня дерева выбрали вершину , то высота дерева будет равна h(T)=4.

Замечание. Если бы в качестве корня выбрали вершину , то высота дерева была бы равна h(T)=5.

3.2 Задание к лабораторной работе№2

Граф задан матрицей весов ребер. Построить кратчайший остов графа алгоритмом Краскала. Определить вес и высоту построенного дерева. Составить программу решения задачи в среде программирования Delphi.

Вариант	Матрица весов	Вариант	Матрица весов
1		6
2		7
3		8
4		9
5		10

3.3 Вопросы к защите лабораторной работы №2

Что называется деревом? Что называется высотой дерева? Какое дерево называется остовом? Какое количество остовов в полном графе? Что называется кратчайшим остовом? Какой граф называется взвешенным? Сформулируйте алгоритм Краскала.

4 Лабораторная работа №3 Нахождение кратчайшего остова в графе алгоритмом Прима

Цель работы: Изучить алгоритмы Прима для нахождения кратчайшего остова графа. Программно реализовать алгоритм Прима.

4.1 Теоретические сведения

Алгоритм Прима — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые был открыт в 1930 году чешским математиком Войцехом Ярником, позже переоткрыт Робертом Примом в 1957 году, и, независимо от них, Э. Дейкстрой в 1959 году.

Принципиальное отличие алгоритма состоит в том, что всегда имеется дерево, к которому ребра добавляют до тех пор, пока не получится остов.

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

Алгоритм Прима:

1)  Выбрать вершину v0 графа G и ребро с наименьшим весом u1, для которого v0 – одна из вершин, и сформировать дерево T1.

2)  Для заданного дерева Tk с ребрами u1, u2, u3, …, uk, если имеется вершина, не принадлежащая Tk, выбрать ребро с наименьшим весом, смежное с ребром дерева Tk и имеющее вершину вне дерева Tk. Добавить в дерево Tk, формируя дерево Tk+1.

3)  Продолжить, пока имеются вершины графа G, не принадлежащие дереву.

Пример. 

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

Решение. 

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

Построим кратчайший остов данного взвешенного графа с помощью алгоритма Прима. Выбираем вершину , которая будет корнем дерева. Из трех ребер, которые инцидентны вершине , выбираем те, что имеют наименьший вес. Два ребра с весом, равным 7, инцидентны вершине . Присоединяем эти ребра к выбранной вершине. К вершине присоединяем ребро с весом 5, соединяющее вершины и . К вершине присоединяем ребро с весом 4, соединяющее вершины и . К вершине присоединяем ребро с весом 6, соединяющее вершины и .Таким образом, получаем следующий кратчайший остов с весом, равным ωmin(T)=7+7+6+5+4=29. Высота построенного дерева равна h(T)=3.

4.2 Задания к лабораторной работе №3

Решить задачу алгоритмом Прима аналитически в соответствии со своим вариантом из Лабораторной работы №2. Составить программу решения задачи в среде программирования Delphi.

4.3 Вопросы к защите лабораторной работы №3

Что называется деревом? Что называется высотой дерева? Какое дерево называется остовом? Какое количество остовов в полном графе? Что называется кратчайшим остовом? Какой граф называется взвешенным? Сформулируйте алгоритм Прима.

Список использованных источников

1 Бережная методы моделирования экономических систем [Текст] / ,  . –М.: Финансы и статистика, 2002. –368 c.

2 Агальцов методы в программировании [Текст] /., .  –М.: Форум - Инфра-М, 2006. -224 c.

3   Сборник задач и упражнений по высшей математике: Математическое программирование [Текст]  /,   –Мн.: Вышэйшая школа, 2002. -447 с.

4 Москинова математика. Математика для менеджеров в примерах и упражнениях  [Текст] /. –М.: Логос, 2002.-240 с.

5   Математические методы [Текст] /, . –М.: Форум - Инфра-М, 2005. -464 с.

6 Струченков оптимизациии [Текст] /. –М.: Экзамен, 2005. – 256 с.

7 Черноруцкий оптимизации в теории управлении [Текст]  / –СПб: Питер, 2004. –256с.

8 Рыжиков моделирование. Теория и технология [Текст] /  –СПб.: Корона принт,  2004. –384 с.

9  Акулич программирование в примерах и задачах [Текст] /. –М.: Высшая школа, 1993. –336 с.

10.   Математические методы и модели в экономике  [Текст] /. –М.: Экзамен, 2004. –212 с.