Лабораторная работа по «Дискретной математике»

Министерство науки и высшего образования РФ

Федеральное государственное бюджетное образовательное

учреждение высшего образования

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

Кафедра компьютерных систем в управлении

и проектировании (КСУП)

ОТЧЕТ

Лабораторная работа № 1

по дисциплине

«Дискретная математика»

Выполнил студент:

группы з-581П12-4 

направления подготовки 09.03.01

Страхова О.В.

     (ФИО)

Проверил:

к.т.н., доцент каф. КСУП ТУСУР, (ученая степень, звание)

Жигалова Е. Ф.

      (ФИО)

Томск 2022

[pic 1]

Цель лабораторной работы

Изучить основные понятия, определения и терминологию теории графов, классы графов, способы задания графа, простейшие операции на графах, числовые характеристики графа и способы их вычисления.

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

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

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

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

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

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

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

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

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

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

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

Дана матрица смежности R = (ri,j) графа G

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

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

На рисунке 2 представлена матрица смежности графа. Граф содержит 7 вершин. Т.к. матрица смежности симметрична относительно главной диагонали, граф является неориентированным.

[pic 2]

 На рисунке 3 представлена матрица инцидентности графа. Т.к. все значения в матрице положительные, то граф неориентированный. Граф содержит 6 вершин и 9 ребер.

[pic 3]

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

[pic 4]

Поиск в «глубину»

Начинаем с вершины 1.

Из вершины 1 можем перейти в вершину 2 по ребру x1

Из вершины 2 можем перейти в вершину 3 по ребру x2

Из вершины 3 можем перейти в вершину 4 по ребру x4

Из вершины 4 можем перейти в вершину 9 по ребру x6

Из вершины 9 можем перейти в вершину 8 по ребру x13

Из вершины 8 можем перейти в вершину 7 по ребру x12

Из вершины 7 можем перейти в вершину 6 по ребру x11

Из вершины 6 можем перейти в вершину 5 по ребру x10

У вершины 5 нет смежных не посещённых вершин.

Алгоритм закончен.

Максимальный путь: 1→2→3→4→9→8→7→6→5