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

 

МИНИСТЕРСТВО ТРАНСПОРТА РОССИЙСКОЙ 

ФЕДЕРАЦИИ 

Федеральное государственное бюджетное образовательное 

учреждение высшего образования 

«РОССИЙСКИЙ УНИВЕРСИТЕТ ТРАНСПОРТА (МИИТ)»  

_________________________ 

 

Кафедра «Математический анализ» 

 

Д.Д. Захаров  

  
 
 

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

 

Учебно-методическое пособие к практическим занятиям  

по дисциплине  

«ВЫСШАЯ МАТЕМАТИКА» 

 

 

 

 

 

 

Москва – 2018 

 

 
-1
 

 

МИНИСТЕРСТВО ТРАНСПОРТА РОССИЙСКОЙ ФЕДЕРАЦИИ 

Федеральное государственное бюджетное образовательное 

учреждение высшего образования 

«РОССИЙСКИЙ УНИВЕРСИТЕТ ТРАНСПОРТА (МИИТ)»  

_________________________ 

 

Кафедра «Математический анализ» 

 

Д.Д. Захаров  

  
 
 

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

 
 

 

 

  Учебно-методическое пособие для студентов 

 всех строительных специальностей 

 

 

 

Москва – 2018 

 

 

 
-2
УДК 517 
З-38 

 
Захаров 
Д.Д. 
Введение 
в 
теорию 
графов: 
Учебно
методическое пособие к практическим занятиям по математике. – 
М.: РУТ (МИИТ), 2018. –49 с. 

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

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

Предполагается предварительное знакомство студента с 
началами математического анализа и алгебры. Пособие 
нацелено на прививание учащимся навыков самостоятельного решения прикладных задач инженерной практики.  

 

Рецензент: зав. кафедрой «Высшая и вычислительная математи
ка» РУТ (МИИТ)     к.ф.-м.н. Платонова О.А. 

 

 

                                              ©РУТ (МИИТ), 2018 

 

 

 

 

 

 

 
-3
 

 

ОГЛАВЛЕНИЕ 

 

Оглавление.................................................................................
3

Введение.....................................................................................
4

1.
Орграфы и бинарные отношения: основные понятия и 
определения...............................................................................
5

2.
Применение матриц к анализу простейших свойств 
графов.........................................................................................
15

3.
Неографы. Полные,
двудольные
и эйлеровы графы. 

Изоморфизм...............................................................................
22

4.
Деревья и леса...........................................................................
27

5.
Задачи оптимизации: алгоритм ближайшего соседа и 
алгоритм Дейкстры...................................................................
31

6.
Плоские и планарные графы....................................................
39

7.
Раскраски графов.......................................................................
43

Заключение……….....................................................................
48

Список литературы....................................................................
49

 
 
 
 
 
 
 
 
 
 
 

 
-4
Введение 

 

Начало теории графов как самостоятельного раздела 

математики обычно относят к 18-веку и связывают с именами 
таких классиков математического знания как Л. Эйлер, Г. Монж, 
Д. Кениг, Д. Сильвестр, А. Кэли, У. Гамильтон, Г. Кирхгоф и 
многих  других. К настоящему времени теория графов стала 
развитой 
и 
востребованной 
дисциплиной 
дискретной 

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

Теория 
графов 
широко 
использует 
матричные 
и 

комбинаторные методы, но в то же время имеет собственную 
специфику, 
конструктивно 
дополняющую 
родственные 

математические дисциплины.  

Ниже приводятся базовые сведения из теории графов, 

позволяющие сначала моделировать (и программировать) графы 
общего вида с помощью двоичных матриц и анализировать их 
фундаментальные свойства. Затем рассматриваются некоторые 
основные виды неориентированных графов, методы их изучения 
и типичные задачи. В каждом параграфе сначала приводятся 
основные теоремы и свойства графов, а потом рассматривается 
ряд примеров для развития навыков самостоятельного решения 
прикладных задач инженерной практики. 

 
 
 
 
 

 
-5
1. Орграфы и бинарные отношения: основные понятия 

и определения 

 

Пусть X  есть некоторое конечное множество, состоящее 

из n  различных элементов:  


1
2
,
,
,
n
X
x x
x

. Любое 

множество  , такое, что  
2
X
X
X
 


назовем бинарным 

отношением на множестве X .  

Таким образом,   есть любое множество упорядоченных 

пар вида 

                




,
  
,
ij
i
j
i
j
x x
x
X x
X

 



,   

для каких-то возможных номеров i  и j  элементов на первых и 

вторых местах в паре. Характеризовать его можно следующей 
квадратной матрицей бинарного отношения или матрицей 
смежности 

 






если

если

0,  
  
,

1,   
  
,

i
j

ij

i
j

x x

x x






 



,      

1
2

1
11
12
1

2
21
22
2

1
2

        
  
    
      

0,1

n

n

n

ij

n
n
n
nn

x
x
x

x
x

x



































. 

На пересечении строки i  и столбца j  ставим символ 

принадлежности пары 

,
i
j
x x
 отношению  .  

Сохраним обозначение матрицы той же буквой 
ij


Γ
, 

что и для отношения  . 

 Назовем величину r  булевой, если она может принимать 

только значения 0 и 1.