Высшая математика

Петербургский государственный университет путей сообщения Императора Александра I

Федеральное образовательное учреждение высшего профессионального образования
«Санкт-Петербургский государственный университет путей сообщения»
Математические модели
Кафедра Высшая математика

Контрольная работа
Стоимость выполнения работы на заказ уточняйте при заказе

Контрольная работа должна содержать отчеты по практическим работам 1, 2, 3.
Практическая работа № 1
Построение кратчайших и максимальных путей в ориентированной сети
Цель работы 1:
Научиться применять алгоритмы нахождения кратчайших и наиболее длинных путей в графах.
Задание. Нарисовать диаграммы ориентированных сетей G1=(X1,A1), G2=(X2,A2) , заданных весовыми матрицами W1 и W2. Построить для сети G1 кратчайший путь от узла до узла с помощью алгоритма Дейкстры и максимальный путь. Построить для сети G2 кратчайший путь от узла x1 до узла x6 с помощью алгоритма Беллмана–Форда.
- постановку задачи;
- определения основных понятий, используемых в работе (путь, метка узла и др.);
- пошаговое применение алгоритмов Дейкстры, Беллмана-Форда и алгоритма нахождения максимального пути;
- графическое изображение полученных результатов.
Отчет должен содержать:
- постановку задачи;
- определения основных понятий, используемых в работе (путь, метка узла и др.);
- пошаговое применение алгоритмов Дейкстры, Беллмана-Форда и алгоритма нахождения максимального пути;
- графическое изображение полученных результатов.

Практическая работа № 2
Построение минимального остова для неориентированной сети
Цель работы 2:
Научиться применять алгоритмы построения остова минимального веса для неориентированной сети.
Задание. Нарисовать диаграмму неориентированной сети G3=(X3,A3), заданной весовой матрицей W3. Построить минимальный остов для сети G3 с помощью алгоритмов Краскала и Прима.
Отчет должен содержать:
- постановку задачи;
- определения основных понятий, используемых в работе (остов сети, разрез графа и др.);
- пошаговое применение алгоритмов Краскала и Прима;
- графическое изображение полученных результатов.

Практическая работа № 3
Построение потоков в сети
Цель работы 3:
Научиться применять алгоритмы Форда-Фалкерсона построения максимального потока и Басакера-Гоуэна построения потока минимальной стоимости.
Задание. Представить графически транспортную сеть G=(X,A), в которой X=..., заданную весовой матрицей W пропускных способностей дуг.
Построить максимальный поток от s к t и указать минимальный разрез, отделяющий s от t.
Построить поток величиной ..., имеющий минимальную стоимость. Стоимости транспортировки единичного потока вдоль дуг T-сети заданы матрицей С.
Отчет должен содержать:
- постановку задачи;
- определения основных понятий, используемых в работе (транспортная сеть, поток, разрез и др.);
- пошаговое применение алгоритмов Форда-Фалкерсона Басакера–Гоуэна;
- графическое изображение полученных результатов.