Лабораторная работа №2 "Дискретная математика" Вариант №15 ТУСУР

Лабораторная работа №2 "Дискретная математика" Вариант №15 ТУСУР

ЛАБОРАТОРНАЯ РАБОТА № 2 Цель лабораторной работы Изучить алгоритм Дейкстры нахождения кратчайшего маршрута на взвешенном (нагруженном) графе, алгоритм Форда – Фалкерсона нахождения максимального потока в транспортной сети, способ минимизации булевых функций с помощью карт Карно. 

Задания на лабораторную работу

Задание 1. Решить задачу нахождения кратчайшего маршрута на взвешенном графе с помощью алгоритма Дейкстры. Исходные данные: вершина х0 – начальная; вершина х7 – конечная. Примечания r[i,j] – элементы матрицы R длин ребер (или дуг) данного графа G = (X, U). Значение r[i,j] равно длине ребра (дуги), соединяющего i-ю и j-ю вершины графа. Значения симметричных элементов получить самостоятельно. Варианты графов представлены в приложении Г.

Задание 2. Решить задачу о коммивояжере. Исходные данные к задаче нахождения гамильтонова цикла в графе (задача о коммивояжере) представлены в приложении Д.

Задание 3. Решить задачу нахождения максимального потока в транспортной сети с помощью алгоритма Форда – Фалкерсона. Исходные данные: Дана сеть S(X,U) x0 – исток сети; x7 – сток сети, где x0 X; x7 X. Значения пропускной ri,j способности дуг сети представлены в приложении Е.

Задание:

1. Вычислить значение максимального потока на сети S, применяя алгоритм Форда – Фалкерсона.

2. Построить разрез сети S. Примечание Значения пропускных способностей дуг ri,j заданы по направлению ориентации дуг: от индекса i к индексу j.

Задание 4. Выполнить минимизацию булевой функции с помощью карты Карно. Варианты булевой функции представлены в приложении Ж. По результатам выполнения лабораторной работы оформляется отчет.