Учебное пособие по курсу «Дискретная математика». Раздел «Теория графов» (246,00 руб.)

Стр.3

Стр.4

Стр.5

Содержание УДК 004(075.8) ББК 73я73 К20 Печатается по решению кафедры вычислительной техники Института компьютерных технологий и информационной безопасности Южного федерального университета (протокол № 7 от 8 апреля 2022 г.) Рецензенты: доктор технических наук, профессор, профессор кафедры прикладной математики и искусственного интеллекта ФГБОУ ВО «Национальный исследовательский университет «МЭИ», г. Москва, А. П. Еремеев доктор технических наук, заведующая кафедрой информационных технологий Самарского государственного технического университета (СамГТУ) А. Е. Колоденкова Курейчик, В. М. К20 Учебное пособие по курсу «Дискретная математика». Раздел «Теория графов» : учебное пособие / В. М. Курейчик, В. В. Курейчик, Е. Р. Мунтян ; Южный федеральный университет. – Ростов-на-Дону ; Таганрог : Издательство Южного федерального университета, 2022. – 164 с. ISBN 978-5-9275-4257-4 Учебное пособие содержит материал по разделу «Теория графов» в рамках курса «Дискретная математика» и включает разделы: «Введение в теорию графов», «Метрики и числа графов», «Специальные циклы графов». Каждый раздел пособия содержит теоретический материал курса лекций, примеры выполнения практических заданий и рекомендации для проведения практических занятий. С целью повышения эффективности самостоятельной работы студентов каждый раздел пособия завершается списком вопросов для самоконтроля, перечнем практических заданий для самостоятельной работы и рекомендациями для выполнения домашних заданий. Организационные особенности предложенного материала делают данное пособие полезным как преподавателям, так и студентам вузов. Пособие предназначено для студентов всех форм обучения по всем направлениям подготовки бакалавров и специальностям Института компьютерных технологий и информационной безопасности. УДК 004(075.8) ББК 73я73 ISBN 978-5-9275-4257-4 © Южный федеральный университет, 2022 © Курейчик В. М., Курейчик В. В., Мунтян Е. Р., 2022 © Оформление. Макет. Издательство Южного федерального университета, 2022 2

Стр.3

Содержание СОДЕРЖАНИЕ ВВЕДЕНИЕ …………………………………………………………... 1. ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ …………………………….. 5 7 1.1. Графы, способы их задания. Виды графов …………………… 7 1.1.1. Способы задания графов ………………………………………. 8 1.1.2. Виды графов. Операции над графами ………………………. 15 1.1.3. Нечеткие неориентированные графы ……………………… 23 1.1.4. Нечеткие ориентированные графы ………………………… 25 Примеры решения задач для самостоятельной работы ………... Задания для самостоятельной работы …………………………... Вопросы для самоконтроля ……………………………………... 28 33 34 1.2. Маршруты, цепи, циклы, шарниры в графах ………………… 35 1.2.1. Маршруты в неориентированных графах …………………. 35 1.2.2. Маршруты в орграфах ………………………………………… 41 Примеры решения задач для самостоятельной работы ………... Задания для самостоятельной работы …………………………... Вопросы для самоконтроля ……………………………………... Рекомендации для проведения практического занятия № 1 …….. Рекомендации для выполнения домашнего задания № 1 ………... 41 46 46 47 54 2. МЕТРИКИ И ЧИСЛА ГРАФОВ ………………………………… 56 2.1. Нахождение кратчайших маршрутов (цепей) ……………….. 2.1.1. Алгоритм Форда ………………………………………………... 56 56 2.1.2. Алгоритм Дейкстры …………………………………………… 59 Примеры решения задач для самостоятельной работы ………... Задания для самостоятельной работы …………………………... Вопросы для самоконтроля ……………………………………... 64 68 69 2.2. Метрические характеристики графа …………………………. 69 Примеры решения задач для самостоятельной работы ………... Задания для самостоятельной работы …………………………... Вопросы для самоконтроля ……………………………………... Рекомендации для проведения практического занятия № 2 …….. Рекомендации для выполнения домашнего задания № 2 ……….. 71 80 81 81 84 3

Стр.4

Содержание 2.3. Цикломатические и хроматические числа графа ……………. 85 Примеры решения задач для самостоятельной работы ………... Задания для самостоятельной работы …………………………... Вопросы для самоконтроля ……………………………………... 101 89 99 2.4. Числа внутренней и внешней устойчивости графа …………. 101 Примеры решения задач для самостоятельной работы ………... 109 Задания для самостоятельной работы …………………………... 114 Вопросы для самоконтроля ……………………………………... 115 2.5. Планарность графов …………………………………………... 116 Задания для самостоятельной работы ………………………….. 118 Вопросы для самоконтроля ……………………………………... 118 Рекомендации для проведения практического занятия № 3 …….. 119 Рекомендации для выполнения домашнего задания № 3 ……….. 128 3. СПЕЦИАЛЬНЫЕ ЦИКЛЫ ГРАФА …………………………….. 130 3.1. Эйлеровы и Гамильтоновы цепи ……………………………... 130 3.2. Связь между эйлеровыми и гамильтоновыми графами …….. 134 Примеры решения задач для самостоятельной работы ………... 137 Задания для самостоятельной работы …………………………... 146 Вопросы для самоконтроля ……………………………………... 146 3.3. Алгоритмы решения задача о коммивояжере ……………….. 146 3.3.1. Алгоритм Хелда и Карпа ……………………………………… 146 3.3.2. Геометрический метод решения ……………………………. 147 Примеры решения задач для самостоятельной работы ………... 151 Задания для самостоятельной работы …………………………... 156 Вопросы для самоконтроля ……………………………………... 156 Рекомендации для проведения практического занятия № 4 …….. 157 4. ОРГАНИЗАЦИЯ ТЕКУЩЕГО И РУБЕЖНОГО КОНТРОЛЯ ПО РАЗДЕЛУ «ТЕОРИЯ ГРАФОВ» ……………... 159 ЗАКЛЮЧЕНИЕ ……………………………………………………… 161 СПИСОК СОКРАЩЕНИЙ …………………………………………. 162 СПИСОК ЛИТЕРАТУРЫ …………………………………………... 163 4

Стр.5