Дискретная математика. В 2 ч. Ч. 2

Министерство науки и высшего образования Российской Федерации 
Департамент координации деятельности организаций  
в сфере сельскохозяйственных наук 
Федеральное государственное бюджетное образовательное  
учреждение высшего образования 
«Волгоградский государственный аграрный университет» 
 
Электроэнергетический факультет 
 
Кафедра «Высшая математика» 
 
 
 
Т. Р. Ищанов 
 
 
 
ДИСКРЕТНАЯ МАТЕМАТИКА 
 
Учебное пособие 
 
Часть 2 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Волгоград 
Волгоградский ГАУ 
2024 
 
1 

УДК 517 
ББК 22.1 
И-98 
 
Рецензенты: 
кандидат педагогических наук, доцент кафедры «Высшая математика» 
ФГБОУ ВО Волгоградский ГАУ Е. А. Комарова; кандидат технических наук, доцент кафедры «Математических, естественнонаучных и 
общепрофессиональных дисциплин» ФГКВОУ ВО «Михайловская 
военная артиллерийская академия» Министерства обороны Российской Федерации П. П. Белоцерковский  
 
Ищанов, Тлек Рахметолович 
И-98  Дискретная математика: учебное пособие / Т. Р. Ищанов. – Волгоград: ФГБОУ ВО Волгоградский ГАУ, 2024. – Часть 2. – 100 с. 
 
ISBN 978-5-4479-0460-9 
 
Учебное пособие по дискретной математике предназначено для 
студентов математических и инженерных специальностей. Оно состоит из двух разделов: теория графов и теория алгоритмов. В разделе 
теории графов рассматриваются основные понятия и методы, такие 
как матрицы смежности, инцидентности, степени вершин графа, а 
также алгоритмы поиска кратчайшего пути в графе. Особое внимание 
уделено практическому применению теории графов посредством примеров и задач. 
В разделе теории алгоритмов описываются основные принципы 
и методы анализа проектирования алгоритмов. Каждая глава снабжена 
примерами и задачами для самостоятельного решения. Пособие предназначено для использования как в учебных заведениях, так и для самостоятельного изучения, помогая студентам овладеть фундаментальными знаниями и навыками в области дискретной математики. 
Предназначено для обучающихся по направлению подготовки 
09.03.03 Прикладная информатика всех форм обучения. 
 
УДК 517 
ББК 22.1 
 
Рекомендовано методической комиссией Электроэнергетического факультета ФГБОУ ВО Волгоградский ГАУ (протокол № 9 от 
21 мая 2024 г.). 
 
ISBN 978-5-4479-0460-9 
© ФГБОУ ВО Волгоградский 
ГАУ, 2024  
© Ищанов Т. Р., 2024 
2 

ВВЕДЕНИЕ 
 
Учебное пособие по дискретной математике предназначено для 
студентов математических и инженерных специальностей, а также для 
всех, кто интересуется данной областью. Пособие состоит из двух основных разделов: теория графов и теория алгоритмов, каждый из которых охватывает ключевые концепции и методы, необходимые для 
глубокого понимания дисциплины. 
Первый раздел посвящен теории графов, которая является важным инструментом в моделировании и решении множества практических задач. Здесь рассматриваются основные понятия графов, которые 
имеют широкое применение в различных областях науки и техники. 
Особое внимание уделено алгоритмам поиска в графах. Раздел завершается обсуждением применений теории графов в реальных задачах, 
что помогает студентам понять практическую ценность изучаемых 
концепций. 
Второй раздел охватывает теорию алгоритмов, фундаментальную область компьютерных наук. В нем рассматриваются основные 
методы анализа и проектирования алгоритмов, которые являются 
ключевыми для эффективного решения вычислительных задач. Этот 
раздел помогает студентам развить навыки формального анализа алгоритмов и понимать ограничения вычислительных методов. 
Каждая глава пособия снабжена подробными примерами и задачами для самостоятельного решения, что способствует закреплению 
материала и развитию практических навыков. Учебное пособие предназначено для использования как в рамках учебных курсов, так и для 
самостоятельного изучения. Оно помогает студентам овладеть фундаментальными знаниями и навыками, необходимыми для успешной 
карьеры в области математики, информатики и инженерии. 
Аннотация подчеркивает значимость изучения дискретной математики как основы для дальнейшего изучения других разделов математики и компьютерных наук, а также ее практическую применимость в решении реальных задач. 
 
 
 
 
 
3 

ТЕОРИЯ ГРАФОВ 
 
Теория графов – это раздел математики, изучающий структуры, 
называемые графами. Граф представляет собой абстрактный математический объект, состоящий из вершин (узлов) и рѐбер (связей) между 
этими вершинами. Графы широко используются для моделирования 
различных ситуаций из реального мира, а также в компьютерных 
науках, транспортных сетях, социологии, биоинформатике и других 
областях. 
Теория графов также содержит множество алгоритмов для работы с графами, таких как поиск кратчайшего пути, поиск минимального остовного дерева, топологическая сортировка и многое другое. Она 
имеет широкое практическое применение в различных областях науки 
и техники. 
 
1.1 Основные определения теории графов 
 
Термин «граф» впервые появился в книге выдающегося венгерского математика Д. Кѐнига в 1936 г, хотя начальные задачи теории 
графов восходят еще к Эйлеру (XVIII в.). 
Л. Эйлер в 1736 году опубликовал решение задачи о Кенигсбергских мостах. 
Граф 𝐺= (𝑉, 𝐸) состоит из двух множеств: конечного множества элементов 𝑉, называемых вершинами, и конечного множества 
элементов 𝐸, называемых ребрами. 
На рисунке 1.1.1 задан граф 𝐺= (𝑉, 𝐸), где множество вершин 
 𝑉= *𝑉
1, 𝑉
2, 𝑉
3, 𝑉
4, 𝑉
5, 𝑉
6, 𝑉
7, 𝑉
8, 𝑉
9, 𝑉
10+ ;  
множество ребер 𝐸= *𝑒1, 𝑒2, 𝑒3, 𝑒4, 𝑒5, 𝑒6, 𝑒7, 𝑒8, 𝑒9, 𝑒10, 𝑒11, 𝑒12, 𝑒13, 𝑒14+. 
 
 
 
Рисунок 1.1.1 – Граф 𝐺= (𝑉, 𝐸) 
4 

Вершины 𝑣𝑖 и 𝑣𝑗, определяющие ребро 𝑒𝑘, называются концевыми вершинами ребра 𝑒𝑘. 
Ребра с одинаковыми концевыми вершинами называются параллельными (𝑒12, 𝑒13). 
Петля – замкнутое ребро (𝑒10). 
Ребро, принадлежащее вершине, называется инцидентным (ребро 𝑒2 инцидентно вершинам 𝑉
2 и 𝑉
3). 
Изолированная вершина не инцидентна ни одному ребру (𝑉
10). 
Две вершины смежны, если они являются концевыми вершинами некоторого ребра (𝑉
3, 𝑉
9).  
Если два ребра имеют общую концевую вершину, они называются смежными (𝑒1, 𝑒2). 
Подграф – любая часть графа, сама являющаяся графом. 
 
 
Рисунок 1.1.2 – Подграф K графа G 
 
 
1.2 Виды графов 
 
Граф G = (V, E) называется простым, если он не содержит петель и параллельных ребер. 
 
 
Рисунок 1.2.1 – Простой граф 
5 

Граф 𝐺= (𝑉, 𝐸) называется полным, если он простой и каждая 
пара вершин смежна.  
 
 
 
Рисунок 1.2.2 – Полный граф 
 
Дополнением графа 𝐺′ называется граф 𝐺̅′, имеющий те же вершины, что и граф 𝐺′, и содержащий только те ребра, которые нужно 
добавить к графу 𝐺′, чтобы он стал полным. 
На рисунке 1.2.3 для получения полного графа 𝐺 необходимо 
дополнить граф 𝐺̅′ графом 𝐺̅′. 
 
 
 
Рисунок 1.2.3 – Дополнение графа 𝐺′ 
 
Пустой граф (ноль-граф) – граф, множество ребер которого пусто.  
6 

 
Рисунок 1.2.4 – Пустой граф 
 
Граф 𝐺 с кратными (параллельными) ребрами называется мультиграфом. 
 
 
Рисунок 1.2.5 – Мультиграф 
 
 
 
Граф 𝐺 с петлями и кратными ребрами называется псевдографом. 
 
 
Рисунок 1.2.6 – Псевдограф 
 
 
7 

Граф 𝐺, рѐбра которого не имеют определѐнного направления, 
называется неориентированным (неорграф). 
 
 
 
Рисунок 1.2.7 – Неориентированный граф 
 
Граф 𝐺, имеющий определѐнное направление, называется ориентированным графом или орграфом. 
Ребра, имеющие направление, называются дугами. 
 
 
 
Рисунок 1.2.8 – Ориентированный граф 
 
1.3 Способы задания графов 
 
1) Явное задание графа как алгебраической системы (список 
ребер). 
Чтобы задать граф, достаточно для каждого ребра указать 
двухэлементное множество вершин – его мы и будем отождествлять 
с ребром.  
 
𝐺= {*𝑉
1, 𝑉
2+, *𝑉
1, 𝑉
3+, *𝑉
3, 𝑉
5+, *𝑉
2, 𝑉
4+, *𝑉
4, 𝑉
5+}. 
 
2) Геометрический. 
8 

 
 
Рисунок 1.3.1 – Неориентированный граф 
 
3) Матрица смежности. 
Элементы 𝐴𝑖𝑗 матрицы смежности 𝐴 для неориентированного 
графа равны количеству ребер между рассматриваемыми вершинами; 
для ориентированного графа – числу ребер с началом в i-ой вершине и 
концом в j-ой.  
 
4) Матрица инцидентности.  
Матрица инцидентности 𝐵 – это таблица, строки которой соответствуют вершинам графа, а столбцы – ребрам.  
Элементы матрицы определяются следующим образом: 
1) для неориентированного графа 
 
𝑏𝑖𝑗= {1, если вершина 𝑣𝑖 инцидентна ребру 𝑒
𝑗;
0, в противном случае.
 
 
2) для ориентированного графа 
 
 
 
 
 
1, если ребро 𝑒
𝑗  входит в вершину 𝑣𝑖;
−1, если ребро 𝑒
𝑗  выходит из вершины 𝑣𝑖;
 
𝑏𝑖𝑗=
2, если ребро 𝑒
𝑗 −петля из вершины 𝑣𝑖;
0, если ребро 𝑒
𝑗  и вершина 𝑣𝑖 не инцидентны.
{
 
 
 
Задача 1.3.1. Для неориентированного графа 𝐺, представленного на рисунке 1.3.2, записать матрицы смежности, инцидентности и 
список ребер. 
9 

 
Рисунок 1.3.2 – Неориентированный граф 
 
Решение. 
 
Таблица 1.3.1 – Матрица смежности 
 
𝑉
1 
𝑉
2 
𝑉
3 
𝑉
4 
𝑉
5 
𝑉
6 
𝑉
1 
0 
2 
1 
0 
0 
0 
𝑉
2 
2 
0 
0 
1 
0 
0 
𝑉
3 
1 
0 
0 
1 
0 
0 
𝑉
4 
0 
1 
1 
0 
1 
1 
𝑉
5 
0 
0 
0 
1 
1 
0 
𝑉
6 
0 
0 
0 
1 
0 
0 
 
Таблица 1.3.2 – Матрица инцидентности 
 
𝑒1 
𝑒2 
𝑒3 
𝑒4 
𝑒5 
𝑒6 
𝑒7 
𝑒8 
𝑉
1 
1 
1 
1 
0 
0 
0 
0 
0 
𝑉
2 
1 
1 
0 
1 
0 
0 
0 
0 
𝑉
3 
0 
0 
1 
0 
1 
0 
0 
0 
𝑉
4 
0 
0 
0 
1 
1 
1 
1 
0 
𝑉
5 
0 
0 
0 
0 
0 
1 
0 
1 
𝑉
6 
0 
0 
0 
0 
0 
0 
1 
0 
 
Таблица 1.3.3 – Список ребер 
Ребра 
Вершины 
𝑒1 
(𝑉
1, 𝑉
2) 
𝑒2 
(𝑉
1, 𝑉
2) 
𝑒3 
(𝑉
1, 𝑉
3) 
𝑒4 
(𝑉
2, 𝑉
4) 
𝑒5 
(𝑉
3, 𝑉
4) 
𝑒6 
(𝑉
4, 𝑉
5) 
𝑒7 
(𝑉
4, 𝑉
6) 
𝑒8 
(𝑉
5, 𝑉
5) 
10