Готовые работы → Дискретная математика
лабораторная работа: 1. Решить задачу нахождения кратчайшего маршрута на взвешенном графе с помощью алгоритма Дейкстры. Задание 2. Решить задачу о коммивояжёре. Задание 3. Решить задачу нахождения максимального потока в транспортной сети с помощью алгоритма Форда—Фалкерсона. Задание 4. Выполнить минимизацию булевой функции с помощью карты Карно.
2015
Важно! При покупке готовой работы
241-12-15
сообщайте Администратору код работы:
Содержание
лабораторная работа №2 вариант 6
Задание 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.
Значения пропускной способности дуг сети r[i,j] представлены в Приложении Е.
Задание:
1). Вычислить значение максимального потока на сети S, применяя алгоритм Форда—Фалкерсона.
2). Построить разрез сети S.
Примечание:
* Значения пропускных способностей дуг r[i,j] заданы по направлению ориентации дуг:
от индекса i к индексу j.
Задание 4. Выполнить минимизацию булевой функции с помощью карты Карно.
ВАРИАНТ 6
Составляем таблицу истинности.
|
№ набора |
|
|
|
|
0 |
000 |
0+0+0+0=0 |
0+0+0=0 |
|
1 |
001 |
0+0+0+1=1 |
1+0+0=1 |
|
2 |
010 |
0+0+1+0=1 |
0+1+0=1 |
|
3 |
011 |
1+1+1+0=1 |
1+1+1=1 |
|
4 |
100 |
0+0+0+0=0 |
0+0+0=0 |
|
5 |
101 |
1+0+0+0=0 |
0+0+0=0 |
|
6 |
110 |
0+0+0+0=0 |
0+0+0=0 |
|
7 |
111 |
1+1+0+0=1 |
0+0+1=1 |
Заполняем карту Карно.
