ТУСУР, дискретная математика (лабораторные работы) - Высшая математика - ВЫСШАЯ МАТЕМАТИКА - Работы, которые мы выполняем (есть много готовых работ): - std72.ru

Общая информация » Каталог студенческих работ » ВЫСШАЯ МАТЕМАТИКА » Высшая математика

ТУСУР, дискретная математика (лабораторные работы)

Узнать стоимость этой работы

09.01.2026, 21:20

Выбор варианта лабораторной работы осуществляется по общим правилам с использованием следующей формулы:

V = (N × K) div 100,

где V – искомый номер варианта,

N – общее количество вариантов, div – целочисленное деление,

при V = 0 выбирается максимальный вариант,

K – код варианта.

Отчет к лабораторной работе должен содержать:

1. Титульный лист. Пример оформления титульного листа представлен в приложении А.

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

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

4. Основная часть отчета включает: математическую постановку задачи; описание алгоритма решения задачи; результат решения каждого шага применяемого алгоритма или итерации (если применялся итерационный алгоритм).

5. Заключение. В данном разделе приводятся основные выводы по результатам выполненных расчетов (сопоставление прогнозируемых и полученных результатов, эффективность алгоритма решения поставленной задачи и др.).

6. Список литературы – список источников, используемых для выполнения работы.

ЛАБОРАТОРНАЯ РАБОТА № 1

Задание 1. По матрицам (рис. 2 и 3) построить диаграммы графов, определив предварительно вид данных матриц.

Задание 2. Методами поиска «в глубину» и «в ширину» найти наибольший минимальный маршрут между вершинами графа (рис. 1).

Задание 3. Для каждой пары вершин графа (рис. 1) аналитическим способом вычислить количество маршрутов длины, равной 4, и выделить те пары вершин, для которых их количество ≥ 3, но не более 10. Выписать эти маршруты для какой-либо из выделенных пар. В описании маршрутов указывать вершины и ребра, входящие в него.

Задание 4. Построить матрицу метрики графа (рис. 1).

Задание 5. С помощью алгоритма Магу – Вейсмана выполнить правильную раскраску вершин графа с минимальным количеством цветов.

Задание 6. Определить число вершинного покрытия графа (рис. 1).

Задание 7. Определить, содержит ли граф (рис. 1) эйлерову цепь или эйлеров цикл. Ответ обосновать.

Варианты исходных данных для выполнения заданий 1–7 лабораторной работы № 1 представлены в приложении Б.

Задание 8. Аналитическим способом определить число компонент связности графа.

Исходные данные:

Дан неорграф G(X,U).

Дана матрица смежности R = (ri,j) графа G (значения элементов матрицы смежности R(r[i,j]) представлены в приложении В).

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

Примечания

Значения элементов матрицы R, симметричных указанным, получить самостоятельно.

Значения неуказанных элементов приравнять нулю.

По результатам выполнения лабораторной работы оформляется отчет.

ЛАБОРАТОРНАЯ РАБОТА № 2

Задание 1. Решить задачу нахождения кратчайшего маршрута на взвешенном графе с помощью алгоритма Дейкстры.

Исходные данные: вершина х₀ – начальная; вершина х₇ – конечная.

Примечания

r[i,j] – элементы матрицы R длин ребер (или дуг) данного графа G = (X, U). Значение r[i,j] равно длине ребра (дуги), соединяющего i-ю и j-ю вершины графа.

Значения симметричных элементов получить самостоятельно. Варианты графов представлены в приложении Г.

Задание 2. Решить задачу о коммивояжере.

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

Задание 3. Решить задачу нахождения максимального потока в транспортной сети с помощью алгоритма Форда – Фалкерсона.

Исходные данные:

Дана сеть S(X,U)

x₀ – исток сети; x₇ – сток сети, где x₀ Î X; x₇ Î X.

Значения пропускной r_i_,j способности дуг сети представлены в приложении Е.

Задание:

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

2. Построить разрез сети S. Примечание

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

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

Варианты булевой функции представлены в приложении Ж.

По результатам выполнения лабораторной работы оформляется отчет.

ПРИЛОЖЕНИЕ Б

Варианты исходных данных для выполнения заданий 1–7 лабораторной работы № 1

.....

ПРИЛОЖЕНИЕ В

Значения элементов матрицы смежности R(r[i,j])

*ВАРИАНТ 1*
r_1,2 = 2	r_3,5 = 2	r_8,9 = 2
r_1,6 = 1	r_3,7 = 3	r9,10 = 2
r_2,4 = 2 r_2,6 = 1	r_8,8 = 1 r_7,5 = 2	r10,8 = 2
*ВАРИАНТ 2* r[1,2] = 2	r[3,7] = 4
r[2,6] = 1	r[4,5] = 3
r[1,6] = 2	r[3,5] = 2
r[3,4] = 2	r[7,8] = 3
*ВАРИАНТ 3*
r_1,2 = 2 r₂₃ = 1 r_4,6 = 3 r_5,6 = 2	r_7,6 = 2 r_8,9 = 1 r8,10 = 1 r9,10 = 2
*ВАРИАНТ 4*
r_1,2 = 2 r_2,6 = 1 r_1,6 = 2 r_3,7 = 1	r_3,4 = 1 r_4,5 = 1 r_3,5 = 2 r_7,8 = 2	r_9,9 = 2
*ВАРИАНТ 5*
r_1,2 = 3 r_1,3 = 1 r_2,3 = 2 r_3,4 = 1	r_4,5 = 3 r_6,5 = 4 r_6,6 = 1

.....

ПРИЛОЖЕНИЕ Г

Задача нахождения кратчайших маршрутах в графе.

Алгоритм Дейкстры

ВАРИАНТ 1

r[0,1] = 38	r[4,7] = 34	r[6,3] = 13	r[5,7] = 25
r[0,2] = 10	r[4,2] = 18	r[6,7] = 24	r[5,4] = 46
r[0,3] = 29	r[2,5] = 21	r[2,1] = 37	r[6,5] = 11
r[1,4] = 25	r[2,6] = 15	r[3,2] = 12

ВАРИАНТ 2

r[0,1] = 19	r[4,7] = 34	r[6,3] = 13	r[5,7] = 43
r[0,2] = 10	r[4,2] = 18	r[6,7] = 39	r[5,4] = 26
r[0,3] = 96	r[2,5] = 21	r[2,1] = 11	r[6,5] = 41
r[1,4] = 35	r[2,6] = 45	r[3,2] = 52

ВАРИАНТ 3

r[0,1] = 19	r[4,7] = 34	r[6,3] = 13	r[5,7] = 43
r[0,2] = 10	r[4,2] = 18	r[6,7] = 35	r[5,4] = 26
r[0,3] = 9	r[2,5] = 21	r[2,1] = 11	r[6,5] = 41
r[1,4] = 25	r[2,6] = 15	r[3,2] = 32

ВАРИАНТ 4

r[0,1] = 12	r[4,7] = 4	r[6,3] = 13	r[5,7] = 43
r[0,2] = 13	r[4,2] = 18	r[6,7] = 30	r[5,4] = 26
r[0,3] = 9	r[2,5] = 21	r[2,1] = 23	r[6,5] = 11
r[1,4] = 25	r[2,6] = 15	r[3,2] = 32

ВАРИАНТ 5

r[0,1] = 12	r[4,7] = 4	r[6,3] = 13	r[5,7] = 43
r[0,2] = 10	r[4,2] = 18	r[6,7] = 35	r[5,4] = 26
r[0,3] = 9	r[2,5] = 21	r[2,1] = 3	r[6,5] = 11
r[1,4] = 25	r[2,6] = 15	r[3,2] = 32

.....

ПРИЛОЖЕНИЕ Д

Исходные данные к задаче нахождения гамильтонова цикла в графе (задача коммивояжера)

ВАРИАНТ 1

Значения элементов матрицы расстояний:

a(1.1) = ¥

a(1.2) = 125

a(1.3) = 15

a(1.4) = 13

a(1.5) = 46

a(2.1) = 53

a(2.2) = ¥

a(2.3) = 24

a(2.4) = 36

a(2.5) = 75

a(3.1) = 32

a(3.2) = 23

a(3.3) = ¥

a(3.4) = 18

a(3.5) = 24

a(4.1) = 11

a(4.2) = 35

a(4.3) = 29

a(4.4) = ¥

a(4.5) = 38

a(5.1) = 22

a(5.2) = 63

a(5.3) = 34

a(5.4) = 162

a(5.5) = ¥

ВАРИАНТ 2

Значения элементов матрицы расстояний:

a(1.1) = ¥	a(2.1) = 53	a(3.1) = 32	a(4.1) = 11	a(5.1) = 22
a(1.2) = 25	a(2.2) = ¥	a(3.2) = 72	a(4.2) = 35	a(5.2) = 63
a(1.3) = 15	a(2.3) = 24	a(3.3) = ¥	a(4.3) = 29	a(5.3) = 34
a(1.4) = 13	a(2.4) = 36	a(3.4) = 18	a(4.4) = ¥	a(5.4) = 16
a(1.5) = 46	a(2.5) = 75	a(3.5) = 24	a(4.5) = 38	a(5.5) = ¥

ВАРИАНТ 3

Значения элементов матрицы расстояний:

a(1.1) = ¥	a(2.1) = 53	a(3.1) = 32	a(4.1) = 11	a(5.1) = 222
a(1.2) = 25	a(2.2) = ¥	a(3.2) = 72	a(4.2) = 35	a(5.2) = 63
a(1.3) = 15	a(2.3) = 124	a(3.3) = ¥	a(4.3) = 29	a(5.3) = 34
a(1.4) = 13	a(2.4) = 36	a(3.4) = 98	a(4.4) = ¥	a(5.4) = 16
a(1.5) = 46	a(2.5) = 75	a(3.5) = 24	a(4.5) = 38	a(5.5) = ¥

ВАРИАНТ 4

Значения элементов матрицы расстояний:

a(1.1) = ¥	a(2.1) = 53	a(3.1) = 32	a(4.1) = 211	a(5.1) = 22
a(1.2) = 25	a(2.2) = ¥	a(3.2) = 72	a(4.2) = 35	a(5.2) = 63
a(1.3) = 15	a(2.3) = 24	a(3.3) = ¥	a(4.3) = 29	a(5.3) = 34
a(1.4) = 13	a(2.4) = 36	a(3.4) = 18	a(4.4) = ¥	a(5.4) = 16
a(1.5) = 46	a(2.5) = 75	a(3.5) = 124	a(4.5) = 38	a(5.5) = ¥

ВАРИАНТ 5

Значения элементов матрицы расстояний:

a(1.1) = ¥	a(2.1) = 53	a(3.1) = 32	a(4.1) = 11	a(5.1) = 22
a(1.2) = 25	a(2.2) = ¥	a(3.2) = 32	a(4.2) = 35	a(5.2) = 63
a(1.3) = 15	a(2.3) = 24	a(3.3) = ¥	a(4.3) = 29	a(5.3) = 234
a(1.4) = 13	a(2.4) = 36	a(3.4) = 18	a(4.4) = ¥	a(5.4) = 16
a(1.5) = 46	a(2.5) = 75	a(3.5) = 24	a(4.5) = 38	a(5.5) = ¥

.....

ПРИЛОЖЕНИЕ Е

Задача о максимальном потоке на сети.

Алгоритм Форда – Фалкерсона

ВАРИАНТ 1

r[0,1] = 19	r[4,7] = 14	r[6,3] = 13	r[5,7] = 43
r[0,2] = 10	r[4,2] = 18	r[6,7] = 35	r[5,4] = 26
r[0,3] = 9	r[2,5] = 21	r[2,1] = 61	r[6,5] = 41
r[1,4] = 15	r[2,6] = 35	r[3,2] = 32

ВАРИАНТ 2

r[0,1] = 19	r[4,7] = 34	r[6,3] = 13	r[5,7] = 43
r[0,2] = 10	r[4,2] = 18	r[6,7] = 35	r[5,4] = 26
r[0,3] = 9	r[2,5] = 21	r[2,1] = 11	r[6,5] = 41
r[1,4] = 25	r[2,6] = 15	r[3,2] = 32

ВАРИАНТ 3

r[0,1] = 12	r[4,7] = 4	r[6,3] = 13	r[5,7] = 43
r[0,2] = 10	r[4,2] = 18	r[6,7] = 35	r[5,4] = 26
r[0,3] = 9	r[2,5] = 21	r[2,1] = 3	r[6,5] = 11
r[1,4] = 25	r[2,6] = 15	r[3,2] = 32

ВАРИАНТ 4

r[0,1] = 29	r[4,7] = 64	r[6,3] = 13	r[5,7] = 43
r[0,2] = 32	r[4,2] = 58	r[6,7] = 35	r[5,4] = 36
r[0,3] = 102	r[2,5] = 21	r[2,1] = 81	r[6,5] = 41
r[1,4] = 25	r[2,6] = 15	r[3,2] = 32

ВАРИАНТ 5

r[0,1] = 12	r[4,7] = 4	r[6,3] = 13	r[5,7] = 33
r[0,2] = 10	r[4,2] = 18	r[6,7] = 32	r[5,4] = 26
r[0,3] = 9	r[2,5] = 21	r[2,1] = 3	r[6,5] = 11
r[1,4] = 25	r[2,6] = 15	r[3,2] = 32

.....

ПРИЛОЖЕНИЕ Ж

Варианты булевой функции

ВАРИАНТ 1

f(a,b,c) = abc Ú a¬bc Ú ¬(abc) Ú ¬(ab)c Ú ¬abc Ú ¬b¬c.

ВАРИАНТ 2

f(a,b,c) = abc Ú a¬bc Ú ¬(abc) Ú ¬(ab)c Ú ¬abc.

ВАРИАНТ 3

f(a,b,c) = abc Ú a¬bc Ú ¬(abc) Ú ¬(ab)c.

ВАРИАНТ 4

f(x,y,z) = y × zÚx × y Ú x × z Ú x ×`y ×`z.

ВАРИАНТ 5

f(x,y,z) = x × y Ú y × z Ú`x × z Ú`x × y ×`z.

.....

Узнать стоимость этой работы

АЛФАВИТНЫЙ УКАЗАТЕЛЬ ПО ВУЗАМ Найти свою работу на сайте	АНАЛИЗ ХОЗЯЙСТВЕННОЙ ДЕЯТЕЛЬНОСТИ Контрольные, курсовые, дипломы из разных ВУЗов
БУХГАЛТЕРСКИЙ УЧЕТ, АНАЛИЗ И АУДИТ Контрольные, курсовые, дипломы из разных ВУЗов	ВЫСШАЯ МАТЕМАТИКА Контрольные работы из разных ВУЗов
МЕНЕДЖМЕНТ И МАРКЕТИНГ Контрольные, курсовые, дипломы из разных ВУЗов	МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ, ТЕОРИЯ ИГР Контрольные, курсовые, рефераты, тесты из разных ВУЗов
ПЛАНИРОВАНИЕ И ПРОГНОЗИРОВАНИЕ Контрольные, курсовые, рефераты, тесты из разных ВУЗов	СТАТИСТИКА Контрольные, курсовые, рефераты, тесты из разных ВУЗов
ТЕОРИЯ ВЕРОЯТНОСТЕЙ И МАТ. СТАТИСТИКА Контрольные работы из разных ВУЗов	ФИНАНСЫ, ДЕНЕЖНОЕ ОБРАЩЕНИЕ И КРЕДИТ Контрольные, курсовые, дипломы из разных ВУЗов
ЭКОНОМЕТРИКА Контрольные, курсовые, рефераты, тесты из разных ВУЗов	ЭКОНОМИКА Контрольные, курсовые, дипломы из разных ВУЗов
ЭКОНОМИКА ПРЕДПРИЯТИЯ, ОТРАСЛИ Контрольные, курсовые, дипломы из разных ВУЗов	ГУМАНИТАРНЫЕ ДИСЦИПЛИНЫ Контрольные, курсовые, дипломы из разных ВУЗов
ДРУГИЕ ЭКОНОМИЧЕСКИЕ ДИСЦИПЛИНЫ Контрольные, курсовые, дипломы из разных ВУЗов	ЕСТЕСТВЕННЫЕ ДИСЦИПЛИНЫ Контрольные, курсовые, дипломы из разных ВУЗов
ПРАВОВЫЕ ДИСЦИПЛИНЫ Контрольные, курсовые, дипломы из разных ВУЗов	ТЕХНИЧЕСКИЕ ДИСЦИПЛИНЫ Контрольные, курсовые, дипломы из разных ВУЗов
РАБОТЫ, ВЫПОЛНЕННЫЕ НАШИМИ АВТОРАМИ Контрольные, курсовые работы	ОНЛАЙН ТЕСТЫ ВМ, ТВ и МС, статистика, мат. методы, эконометрика

Ваше имя *

Ваш e-mail *

Контактный телефон

Город *

Учебное заведение *

Предмет *

Тип работы *

Тема работы/вариант *

Кол-во страниц

Срок выполнения *

Прикрепить файл

Дополнительные условия

Ваше имя:
Ваш электронный адрес *:
Дополнительные условия:
Код безопасности *:

	500