Лабораторная работа №1 по Дискретной математике 24 вариант. Дискретная математика №1. Волков Д. В. 2023 г. Руководитель Кандидат технических наук, доцент каф. Ксуп жигалова Е. Ф
 Скачать 0.72 Mb.
|
|
Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ Кафедра компьютерных систем в управлении и проектировании Способы задания графа Отчет по лабораторной работе №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.Новиков ФА. Дискретная математика для программистов : учеб. пособие для вузов / ФА. Новиков. — е изд. — СПб. ; М. ; Нижний Новгород. |