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

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

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

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

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

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

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

Е. Р. МУНТЯН

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

по курсу

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

Раздел 

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

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

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

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

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

11

К. Берж [6] предлагает задавать граф как соответствие Г между подмножествами 
множества вершин. При этом граф можно задать в виде 
G = (X, Г), где Г  X  X, Г = {Гx1, Гx2, …, Гxn}. Здесь Г – это отображение 
множества Х в множество Х. 

Например, пусть задан граф G5 = (X5, Г5), как показано на рис. 1.5. 

Тогда |X5| = 6, X5 = {x1, x2, …, x6}, Г3 = {Гx1, Гx2, …, Гx6}, Гx1 = {x2, x5, x6}, Гx2 = 
= {x1, x3, x5, x6}, Гx3 = {x2, x4}, Гx4 = {x5, x6}, Гx5 = {x1, x2, x4}, Гx6 = {x1, x2, x4}.

x1
x2

x3
x4

u1

u3
u2

u6

u4

u5

u7 u8

u9

x6

x5

Рис. 1.5. Граф G5

Учитывая вышесказанное, граф часто рассматривают как пару G = 

= (X, Г), образованную множеством X и отображением Г множества X в себя.

Отметим, что для однозначного задания графов достаточно использовать 
Гx1, Гx2, …, Гxn-1 отображений. В этом случае элементы xi, определяющие 
Гxi, не включают в отображение Гxi+1; в отображение Гxi+2 не включают 
элементы xi, xi+1 и т.д. Соответственно в последнее отображение Гxn-1 не 
включают элементы x1, x2, …, xn-2. Тогда рассматриваемый граф G3 (рис. 1.5) 
может быть задан следующим образом: Гx1 = {x2, x5, x6}, Гx2 = {x3, x5, x6}, 
Гx3 = {x4}, Гx4 = {x5, x6}, Гx5 = .

Такое представление графа позволяет экономить память ЭВМ и исключать 
избыточную информацию при представлении графа аналитическим 
способом.

Большинство задач информатики удобно решать при использовании 

матричного задания графов. Квадратная таблица R = ||ri,j||nxn называется 
матрицей смежности неориентированного графа, если ее элементы образуются 
по правилу:

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

12

Заметим, что для мультиграфа

Очевидно, что для рассматриваемых неорграфов ri,j = rj,i и для зада-

ния графа можно использовать треугольную матрицу R. Для графа без пе-
тель ri,i = 0, для графа с петлями ri,i  0. Для графа G5 (см. рис. 1.5) 
треугольная матрица смежности имеет вид:

x1
x2
x3
x4
x5
x6

x1
0
1
0
0
1
1

.

x2
0
1
0
1
1

R5 = x3
0
1
0
0

x4
0
1
1

x5
0
0

x6
0

Строки и столбцы матрицы R соответствуют вершинам графа G. На 

пересечении xi строки и xj столбца ставится элемент ri,j, соответствующий 
числу ребер, соединяющих вершины xi и xj. Заметим, что строки и столбцы 
матрицы R также можно нумеровать числами натурального ряда, соответ-
ствующими индексам помеченных вершин графа. Петли в графе изобража-
ются элементами ri,j, расположенными по главной диагонали матрицы R.

Орграф G может быть однозначно задан матрицей смежности R(G) =

= ||rij||nn, причем

𝑟𝑖𝑗 = {1, если < 𝑥𝑖, 𝑥𝑗 > – дуга орграфа,

0, в противном случае.

Так как rij  rji, то матрица не симметрична относительно главной 

диагонали. То есть в общем случае матрица смежности орграфа не будет 
симметрична относительно главной диагонали.

Преимущество использования матриц смежности – это простота и 

формальность преобразований над графами.

Основной недостаток применения матрицы смежности заключается 

в том, что она занимает в ЭВМ память объемом |X|2 даже тогда, когда граф 

,

1, есливершина
смежна свершиной
;

0, впротивномслучае.


 



i
j

i j

x
x

r

,

, есливершина
соединена
ребрами свершиной
;

0, впротивномслучае.



 



i
j

i j

q
x
q
x

r