Лабораторная работа по "Дискретной математике"
Автор: moncro • Май 16, 2024 • Лабораторная работа • 1,495 Слов (6 Страниц) • 115 Просмотры
Министерство науки и высшего образования РФ
Федеральное государственное бюджетное образовательное
учреждение высшего образования
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
Кафедра компьютерных систем в управлении
и проектировании (КСУП)
ОТЧЕТ
Лабораторная работа № 1
(вариант № 7)
по дисциплине
«Дискретная математика»
Выполнил студент:
группы _______
направления подготовки________
Иванов И. И.
(ФИО)
Проверил:
к.т.н., доцент каф. КСУП ТУСУР,
(ученая степень, звание)
Жигалова Е. Ф.
(ФИО)
Томск 2022
Задание
Задание 1. По матрицам (рис. 2 и 3) построить диаграммы графов,
определив предварительно вид данных матриц.
1 | 2 | 3 | 4 | 5 | 6 | 7 | |
1 | 0 | 2 | 0 | 0 | 0 | 3 | 0 |
2 | 2 | 0 | 0 | 0 | 0 | 0 | 0 |
3 | 0 | 0 | 0 | 2 | 0 | 0 | 0 |
4 | 0 | 0 | 2 | 0 | 1 | 1 | 0 |
5 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
6 | 3 | 0 | 0 | 1 | 0 | 0 | 1 |
7 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
Рисунок 2 - Исходные данные для лабораторной работы №1
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 |
2 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
3 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
4 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
5 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 |
6 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
Рисунок 3 - Исходные данные для лабораторной работы №1
Задание 2. Методами поиска «в глубину» и «в ширину» найти
наибольший минимальный маршрут между вершинами графа
(рис. 1).
[pic 1]
Рисунок 1 - Исходный граф для лабораторной работы №1
Задание 3. Для каждой пары вершин графа (рис. 1) аналитическим
способом вычислить количество маршрутов длины, равной 4, и выделить те пары вершин, для которых их количество ≥ 3, но не более 10. Выписать эти маршруты для какой-либо из выделенных пар. В описании маршрутов указывать вершины и ребра, входящие в него.
Задание 4. Построить матрицу метрики графа (рис. 1).
Задание 5. С помощью алгоритма Магу – Вейсмана выполнить правильную раскраску вершин графа с минимальным количеством цветов.
Задание 6. Определить число вершинного покрытия графа (рис. 1).
...