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

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ

РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное автономное 

образовательное учреждение высшего образования
«ЮЖНЫЙ  ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»

Инженерно-технологическая академия

В. М. КУРЕЙЧИК
В. В. КУРЕЙЧИК

Е. Р. МУНТЯН

Учебное пособие

по курсу

ДИСКРЕТНАЯ МАТЕРМАТИКА

Раздел 

ТЕОРИЯ ГРАФОВ 

Ростов-на-Дону – Таганрог 

Издательство Южного федерального университета

2022

Содержание

2

УДК 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

Содержание

3

СОДЕРЖАНИЕ

ВВЕДЕНИЕ …………………………………………………………...
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

Содержание

4

2.3. Цикломатические и хроматические числа графа …………….
85

Примеры решения задач для самостоятельной работы ………...
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 рассматриваются вопросы решения задачи коммивояжера, 

а также организация специальных циклов в графах на примере эйлеровых
и гамильтоновых графов.

Все подразделы пособия организационно структурированы и вклю
чают в себя:


теоретический материал курса лекций;


примеры выполнения практических заданий;


рекомендации для проведения практических занятий.

Введение

6

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

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

1.1. Графы, способы их задания. Виды графов 

7

1. ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ

1.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. Заметим, что для реальных задач необходима 

1. Введение в теорию графов

8

нумерация элементов. Поэтому в дальнейшем будем рассматривать помеченные графы. Аналогичным образом помечаются ребра.

Тогда графом можно считать математический объект, который обо
значается 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
U

o
U

1.1. Графы, способы их задания. Виды графов 

9

Например, на рис. 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
U

o
U

1. Введение в теорию графов

10

«Заметим, что подмножество петель можно рассматривать как дуги, 

так и ребра. Обычно всегда оговаривают, когда рассматривается граф с пет
лями. Граф 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. 

U