Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

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

Покупка
Основная коллекция
Артикул: 806351.01.99
Доступ онлайн
350 ₽
В корзину
Учебное пособие содержит материал по разделу «Теория графов» в рамках курса «Дискретная математика» и включает разделы: «Введение в теорию графов», «Метрики и числа графов», «Специальные циклы графов». Каждый раздел пособия содержит теоретический материал курса лекций, примеры выполнения практических заданий и рекомендации для проведения практических занятий. С целью повышения эффективности самостоятельной работы студентов каждый раздел пособия завершается списком вопросов для самоконтроля, перечнем практических заданий для самостоятельной работы и рекомендациями для выполнения домашних заданий. Организационные особенности предложенного материала делают данное пособие полезным как преподавателям, так и студентам вузов. Пособие предназначено для студентов всех форм обучения по всем направлениям подготовки бакалавров и специальностям Института компьютерных технологий и информационной безопасности.
56
Курейчик, В. М. Учебное пособие по курсу «Дискретная математика». Раздел «Теория графов» : учебное пособие / В. М. Курейчик, В. В. Курейчик, Е. Р. Мунтян ; Южный федеральный университет. - Ростов-на-Дону ; Таганрог : Издательство Южного федерального университета, 2022. - 164 с. - ISBN 978-5-9275-4257-4. - Текст : электронный. - URL: https://znanium.ru/catalog/product/2039100 (дата обращения: 19.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
МИНИСТЕРСТВО  НАУКИ  И  ВЫСШЕГО  ОБРАЗОВАНИЯ 
РОССИЙСКОЙ  ФЕДЕРАЦИИ 
Федеральное государственное автономное  
образовательное учреждение высшего образования 
«ЮЖНЫЙ  ФЕДЕРАЛЬНЫЙ  УНИВЕРСИТЕТ» 
Инженерно-технологическая академия 
 
 
В. М. КУРЕЙЧИК 
В. В. КУРЕЙЧИК 
Е. Р. МУНТЯН 
 
 
Учебное пособие 
по курсу 
ДИСКРЕТНАЯ  МАТЕРМАТИКА 
Раздел  
ТЕОРИЯ  ГРАФОВ  
 
 
 
 
 
 
 
 
 
 
 
Ростов-на-Дону – Таганрог  
Издательство Южного федерального университета 
2022 
 
 


Содержание 
УДК 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 
 


Содержание 
СОДЕРЖАНИЕ 
ВВЕДЕНИЕ …………………………………………………………... 
5 
1. ВВЕДЕНИЕ  В  ТЕОРИЮ  ГРАФОВ …………………………….. 
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 
Примеры решения задач для самостоятельной работы ………... 
41 
Задания для самостоятельной работы …………………………... 
46 
Вопросы для самоконтроля ……………………………………... 
46 
Рекомендации для проведения практического занятия № 1 …….. 
47 
Рекомендации для выполнения домашнего задания № 1 ………... 
54 
2. МЕТРИКИ  И  ЧИСЛА  ГРАФОВ ………………………………… 
56 
2.1. Нахождение кратчайших маршрутов (цепей) ……………….. 
56 
2.1.1. Алгоритм Форда ………………………………………………... 
56 
2.1.2. Алгоритм Дейкстры …………………………………………… 
59 
Примеры решения задач для самостоятельной работы ………... 
64 
Задания для самостоятельной работы …………………………... 
68 
Вопросы для самоконтроля ……………………………………... 
69 
2.2. Метрические характеристики графа …………………………. 
69 
Примеры решения задач для самостоятельной работы ………... 
71 
Задания для самостоятельной работы …………………………... 
80 
Вопросы для самоконтроля ……………………………………... 
81 
Рекомендации для проведения практического занятия № 2 …….. 
81 
Рекомендации для выполнения домашнего задания № 2 ……….. 
84 
 


Содержание 
2.3. Цикломатические и хроматические числа графа ……………. 
Примеры решения задач для самостоятельной работы ………... 
89 
Задания для самостоятельной работы …………………………... 
99 
Вопросы для самоконтроля ……………………………………... 
101 
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 


 
ВВЕДЕНИЕ 
Настоящее пособие отражает содержание теоретического, практического и методического обеспечения раздела «Теория графов» дисциплины 
«Дискретная математика». Кроме того, в пособии рассмотрены формы текущего контроля, предусмотренные в рамках данного модуля.
Дисциплина «Дискретная математика» изучается студентами первого курса Института компьютерных технологий и информационной безопасности (ИКТИБ) в 1 семестре. Пособие предназначено для студентов 
всех форм обучения по всем направлениям подготовки бакалавров и специальностям Института компьютерных технологий и информационной 
безопасности. В соответствии с учебными планами образовательных программ подготовки бакалавров и специалистов ИКТИБ по дисциплине 
«Дискретная математика» предусмотрено проведение лекционных и практических занятий. Конкретно в рамках раздела «Теория графов» предусмотрено чтение лекций в объеме 8 часов и проведение практических занятий в объеме 8 часов. 
Структурно настоящее пособие организовано в виде трех разделов.  
Разд. 1 посвящен аспектам введения в теорию графов и содержит материал, включающий в себя следующие темы: определение и виды графов, 
матричные и списковые способы задания графов, маршруты (пути), циклы 
и цепи в графах.  
В разд. 2 рассматриваются алгоритмические основы теории графов. 
Здесь рассматриваются алгоритмы определения кратчайших путей в графах, вычисления метрик и других чисел графов, а также эвристики планарности графов. 
В разд. 3 рассматриваются вопросы решения задачи коммивояжера, 
а также организация специальных циклов в графах на примере эйлеровых 
и гамильтоновых графов. 
Все подразделы пособия организационно структурированы и включают в себя: 
 
теоретический материал курса лекций; 
 
примеры выполнения практических заданий; 
 
рекомендации для проведения практических занятий. 


Введение 
С целью повышения эффективности самостоятельной работы студентов каждый подраздел пособия завершается списком вопросов для самоконтроля, перечнем практических заданий для самостоятельной работы 
и рекомендациями для выполнения домашних заданий. Организационные 
особенности предложенного материала делают данное пособие полезным 
как преподавателям, так и студентам вузов.
Теоретическая часть данного учебного пособия основана на материалах учебника авторского коллектива ЮФУ Гладкова Л. А., Курейчика В. В., 
Курейчика В. М. «Дискретная математика» [1].  
 
 
 
 


Для исследования взаимодействия объектов или субъектов их 
удобно представлять в виде точек, а отношения между ними можно представлять соединяющими линиями. Необходимость анализа таких взаимодействий возникает при решении ряда практических задач, например: для 
исследования взаимоотношений субъектов или объектов (ботов, роботов 
и т.д.) в организационных системах, в том числе в различного рода сетях 
(социальных и/или профессиональных сетях); при определении зон влияния технических объектов на систему и т.п. 
«Такое изображение ввиду наглядности позволяет определять наиболее существенные связи, находить оптимальное решение задачи, определять 
ошибки в рассуждениях и т.д. 
Описание, состоящее из точек и соединяющих их линий, оказывается удобной моделью любого объекта, и в этой связи представляет интерес 
исследование самого этого объекта. Теория графов оперирует формальными моделями объектов, имеет дело со свойствами самих графов независимо от того, какова природа объектов, описываемых графами. Использование аппарата теории графов для разработки алгоритмов в науке и технике 
приводит к повышению эффективности и качества создаваемых объектов. 
Понятие графа опирается на понятие множества. Графом можно 
назвать объект, состоящий из двух множеств: точек и линий, которые находятся между собой в некотором отношении. Множество точек графа обозначается X = {x1, x2, …, xn}, |X| = n и называется множеством вершин. Множество линий, соединяющих любые пары вершин, (xi, xj)  X называется 
множеством ребер или дуг и обозначается U = {u1, u2, …, um}, |U| = m. 
Граф, у которого все вершины “помечены” целыми числами от 1 
до n, называется помеченным. Известна формула Пойа, утверждающая, что 
число непомеченных графов с увеличением числа вершин приближается к 
значению 
2𝑘
𝑛!, где 𝑘= 
𝑛(𝑛−1)
2
. 
Числа 1, 2, …, n называют метками графа и обозначают вершины 
графа G как x1, x2, …, xi, …, xn. Заметим, что для реальных задач необходима 
 


нумерация элементов. Поэтому в дальнейшем будем рассматривать помеченные графы. Аналогичным образом помечаются ребра. 
Тогда графом можно считать математический объект, который обозначается G = (X, U) и состоит из множества вершин и множества ребер или 
дуг, находящихся между собой в некотором отношении.
В общем случае множество линий U, соединяющих любые пары вершин, можно представить в виде U = 
  
  
, где 
  подмножество 
неориентированных линий, для которых несуществен порядок соединения 
вершин. Подмножество 
 называется подмножеством ребер. Причем 
каждое ребро ui  
 определяется неупорядоченной парой вершин xk, yl, 
которые оно соединяет. Записывается ui = (xk, yl) или ui = (yl, xk). 
 – подмножество ориентированных линий, для которых существен порядок соединения вершин. Подмножество 
 называется подмножеством дуг. Причем каждая дуга ui  
 определяется упорядоченной парой (кортежем длины два) вершин xk, yl, которые ui соединяет. Записывается ui = <xk, yl>. Заметим, что ui = <xk, yl> и uj = <yl, xk> – это различные дуги в графе G. 
 – подмножество линий, каждая из которых выходит и входит в 
одну и ту же соответствующую этой линии вершину. Называется 
 подмножеством петель. Каждая петля ui  
 может определяться упорядоченной 
или неупорядоченной парой, например вида ui = <xk, xk>, ui = (xk, xk)» [1]. 
1.1.1. Способы задания графов 
Существует несколько способов задания графов, в том числе [2–6]: 
 
аналитический способ; 
 
графический способ; 
 
в виде матриц; 
 
в виде списков. 
Аналитический или теоретико-множественный способ задания 
графа позволяет представить граф в виде множеств, например, вершин, ребер, соответствий. Графический способ позволяет наглядно представить 
граф на плоскости в виде рисунка.  
U
U
o
U
U
U
U
U
U
U
o
U
o
o


Например, на рис. 1.1 изображен неориентированный граф G1 = 
= (X1, U1), который задан множеством вершин X1 = {x1, x2, x3, x4, x5} и множеством ребер U1 = {u1, u2, u3, u4, u5, u6}. 
x1
x2
x3
x4
x5
u1
u3
u2
u6
u4
u5
 
Рис. 1.1. Неориентированный граф G1 
«Граф G = (X, U), у которого U = 
, а 
 = , называется ориентированным, или орграфом. Орграф будем обозначать D = (X, U) или                  
G = {X, 
}» [1]. 
Пример орграфа приведен на рис. 1.2. Граф G2 задан множествами 
вершин X2 = {x1, x2, x3, x4, x5} и дуг U2 = {u1, u2, u3, u4, u5, u6}. 
x1
x2
x3
x4
x5
u1
u3
u2
u6
u4
u5
 
Рис. 1.2. Ориентированный граф G2 
«Граф G = (X, U), у которого 
, 
, 
  , называется смешанным» [1].  
На рис. 1.3 показан смешанный граф G3, для которого |X| = 6, |U| = 13; 
U = 
  
  
; 
 = {u3, u4, u7, u9, u10, u11}; 
 = {u1, u2, u8, u12, u13}; 
 = {u5, u6}. 
U
U
U
U U
o
U
U
U
o
U
U
o


«Заметим, что подмножество петель можно рассматривать как дуги, 
так и ребра. Обычно всегда оговаривают, когда рассматривается граф с петлями. Граф G, у которого U = 
, называется неориентированным графом, 
или неорграфом. Графы, не содержащие петель и кратных ребер, называются простыми графами. 
Рассмотрим сначала неорграфы с петлями и без петель, которые будем называть графами. Граф G, у которого существует хотя бы одна пара 
вершин, соединяемых k ребрами ui  U, называется мультиграфом, а максимальное mk – мультичислом графа G (mk  {2, 3, …}). Ребра, соединяющие одну и ту же пару вершин, называются кратными. На рис. 1.4 показан 
пример мультиграфа G4, где mk = 4. 
x1
x2
x5
x6
x4
x3
u1
u2
u3
u4
u7
u8
u12
u13
u11
u10
u9
u5
u6
 
x1
x2
x4
x3
u1
u2
u3
u4
u7 u8
u10
u9
u5
u6
 
 
Рис. 1.3. Смешанный граф G3 
Рис. 1.4. Мультиграф G4 
Если ребро uk  U графа G = (X, U) соединяет вершины xi, xj  X, т.е. 
uk = (xi, xj), то говорят, что ребро uk – инцидентно вершинам xi, xj. Верно и 
обратное, вершины xi, xj инцидентны ребру uk. Любые две вершины xi, xj  X 
графа G называются смежными, если существует соединяющее эти вершины ребро uk  U, т.е. uk = (xi, xj). Если два ребра uk, ui  U инцидентны 
одной и той же вершине, то они также называются смежными. 
Рассмотрим подробнее аналитический способ задания графа G = 
= (X, U). Согласно Н. Бурбаки, граф записывается как G  B = X × X.  


Доступ онлайн
350 ₽
В корзину