Файл: Волков Д. В. 2023 г. Руководитель Кандидат технических наук, доцент каф. Ксуп жигалова Е. Ф.pdf

Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ Кафедра компьютерных систем в управлении и проектировании Способы задания графа Отчет по лабораторной работе №1 Дисциплина Дискретная математика Студент гр.
з-512П12-6
Волков Д.В.
« » 2023 г. Руководитель Кандидат технических наук, доцент каф. КСУП
Жигалова Е.Ф.
« »
2023 г.
Серов 2023 подпись) подпись) оценка)

Содержание Введение ......................................................................................................................................... 3 Выполнение работы ...................................................................................................................... 4 Задание №1 ................................................................................................................................. 4 Задание №2 ................................................................................................................................. 5 Задание №3 ................................................................................................................................. 9 Задание №4 ............................................................................................................................... 10 Задание №5 ............................................................................................................................... 11 Задание №6 ............................................................................................................................... 13 Задание №7 ............................................................................................................................... 13 Задание №8 ............................................................................................................................... 14 Заключение ................................................................................................................................... 15 Список использованной литературы ......................................................................................... 16

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

Выполнение работы Задание №1 ВАРИАНТ По матрицам (рис. 2 и 3) построить диаграммы графов, определив предварительно вид данных матриц.

Задание Методами поискав глубину ив ширину найти наибольший минимальный маршрут между вершинами графа (рис. 1). Поиск в ширину Для начала составим пустую матрицу смежности с нулями на главной диагонали. Затем осуществляем итеративный алгоритм произвольно выбираем вершину, обозначаем расстояния от неѐ до смежных с ней, для данной вершины выбираем меньшее из следующих значений для всяких уже рассмотренных вершин вычисляем сумму кратчайших путей отданной вершины до смежных с рассматриваемой вершиной узлов, которые были обработаны в предыдущих итерациях алгоритма, с расстоянием от рассматриваемой вершины до этого узла, смежного ей и рассмотренного в алгоритме ранее. Если, при переходе к следующему шагу алгоритма, есть выбор между несколькими вершинами, то выбирается ближайшая к данной, при равенстве расстояний (например, не взвешенный граф – наш случай, порядок вершин можно задать произвольно.
(
)
(
)

(
)
(
)
(
)
(
)
(
)
(
)
(
)
4. Наибольший элемент таблицы 3. Поиск в глубину Для начала, при поиске в глубину, нужно составить иерархическое дерево графа, для этого произведѐм выбор произвольной вершины и будем производить рекурсивный выбор смежной с текущей выбранной вершины с пометкой шага, на котором выбор вершины произведѐн, при невозможности выбрать новую не выбранную ранее вершину, откатываемся назад, производя отметку шага, на котором выбор вершины был отменѐн:

Составим дерево и отметим обратные рѐбра: Были рассмотрены разделѐнные обратными рѐбрами связные поддеревья и заданы в них кратчайшие расстояния
(
Вычислим расстояния с учѐтом расстояний до связующих вершин между соседними поддеревьями:
(
)

Для прочих вершин
(
Наибольший элемент таблицы 3.

Задание №3 Для каждой пары вершин графа (рис. 1) аналитическим способом вычислить количество маршрутов длины, равной 4, и выделить те пары вершин, для которых их количество ≥ 3, ноне более 10. Выписать эти маршруты для какой-либо из выделенных пар. В описании маршрутов указывать вершины и ребра, входящие в него. Составим матрицу смежности изначального графа
(
Анализируя граф, можем сказать, что для вычисления числа маршрутов фиксированной длины между всеми его вершинами, нам нужно возвести его матрицу смежности в степень числа нужной длины
(
Искомые пары вершин (
) ( ) ( ) ( ) ( ) ( ) ( ). Опишем маршруты между вершинами 1 и 8:
( l6h8);(1a2l6i8);(1a2l6j8);

Задание №4 Построить матрицу метрики графа (рис. 1). Для этого для матрицы связности найдѐм
, затем каждый шаг будем получать
, для всех ячеек, которые являются нулевыми в и ненулевыми в зададим значение , прочие скопируем изв Если
, то завершаем алгоритм, находя матрицу метрики
, копируя туда все ненулевые ячейки из
, а вместо нулевых задавая
,
(
)
;
(
)
;
(
)
;
(
)
;
(
)

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

Задание №6 Определить число вершинного покрытия графа (рис. 1). На основании из предыдущего задания, имеем число вершинного покрытия равным 4. Задание №7 Определить, содержит ли граф (рис. 1) эйлерову цепь или эйлеров цикл. Ответ обосновать. Имеем более двух вершин, имеющих нечѐтную степень узлы
. Так что в нѐм эйлерова цикла и эйлеровой цепи быть не может.

Задание №8 Аналитическим способом определить число компонент связности графа. Будем обходить граф в ширину (имеем очередь и множество, в очередь добавляем вконец все новые вершины, смежные стой, что вначале очереди в эту итерацию алгоритма, эти же вершины добавляем в множество, в конце итерации убираем первый элемент из очереди. Повторяем, пока очередь не окажется пуста, узлы в множестве – компонента связности графа, выбираем вершину произвольно
{1}, Q (1)
{1, 2, 6}, Q (2)
{1, 2, 6}, Q (6)
{1, 2, 6,}, Q ()
{3}, Q (3)
{3, 4, 5, 7}, Q (4, 5, 7)
{3, 4, 5, 7}, Q (5, 7)
{3, 4, 5, 7, 8}, Q (7)
{3, 4, 5, 7, 8}, Q (8)
{3, 4, 5, 7, 8}, Q () Компоненты связности *
+ * +

Заключение Были изучены
- Основные понятия графов
- Определения и терминология графов
- Классы графов
- Способы задания графа
- Простейшие операции на графах
- Числовые характеристики графа и способы их вычислений

Список использованной литературы
1.Хаггарти Род. Дискретная математика для программистов : учеб. пособие для вузов : перс англ. / Род. Хаггарти. — е изд, доп. — М. : Техносфера,
2005. — 393 с.
2.Макоха АН. Дискретная математика : учеб. пособие для вузов / АН.
Макоха. — М. : Физматлит, 2005. — 368 с.
3.Шапорев С. Д. Математическая логика. Курс лекций и практических занятий : учеб. пособие для вузов / С. Д.Шапорев. — БХВ-Петербург, 2005.
4.Новиков ФА. Дискретная математика для программистов : учеб. пособие для вузов / ФА. Новиков. — е изд. — СПб. ; М. ; Нижний Новгород.