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

 

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

ФЕДЕРАЦИИ 

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

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

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

_________________________ 

 

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

 

Д.Д. Захаров  

  
 
 

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

 

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

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

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

 

 

 

 

 

 

Москва – 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. 

 
-6-

Для любых  булевых величин 1r  и 
2r  определим следующие 

«логические» операции 

1) дизъюнкция 
2
1
r
r 
  (логическое «сложение»), 

2) конъюнкция 
2
1
r
r 
  (логическое «умножение»), 

3) отрицание 1r  или 2r  (логическое «дополнение»), 

представляя результат операции в виде таблицы: 

1r
2r
2
1
r
r 
2
1
r
r 
1r
2r

0
0
0
0
1
1

0
1
1
0
1
0

1
0
1
0
0
1

1
1
1
1
0
0

 

 Пусть 
X  есть некоторое множество с бинарными 

отношениями  
2

1
X
 
, 
2

2
X
 
, 
2

3
X
 
. Если любая 

пара 

3
,
i
j
x x
  тогда и только тогда, когда существует 

хотя бы один элемент 
kx  , такой, что 

1
,
i
k
x x
  и 



2
,
k
j
x x
 , то отношение 
3
  называется композицией 

отношений 
1
  и 
2
 : 
3
1
2
  
 . 

Очевидно, что порядок компонент в композиции важен, т.е., 

вообще говоря, 
1
2
2
1

  
 . 

 Пусть 
теперь бинарные 
отношения 
1
 , 
2
 , 
3
  

представлены своими матрицами смежности  
1
Γ , 
2
Γ , 
3
Γ . 

Теорема о композиции. Если 
3
1
2
  
 , то элементы 

матрицы смежности 
 
3

3
ij


Γ
 могут быть получены 

 
-7-

следующими 
операциями 
над 
элементами 
матриц 

 1

1
ij


Γ
 и 
 
2

2
ij


Γ
: 

 
 
 



 
 



 
 



 
 



3
1
2

1

1
2
1
2
1
2

1
1
2
2
     
.

n

ij
i
j

i
j
i
j
in
nj



























    (1.1) 

Действительно, справа мы получим единичное значение 
только тогда, когда хотя бы одна скобка обращается в 1, но 

если  
 
 
1
2
1
i
j



 , то элемент x
X

  удовлетворяет 

определению композиции. Разумеется, такой элемент не 
обязательно единственен. 
Отметим также, что операция (1.1) аналогична правилу 
умножения числовых матриц, только в данном случае 
сложение и умножение «логическое».  

 Назовем простым ориентированным конечным графом  

(оргафом) любую пару 
,
G
X

 , где X – конечное 

множество и  – бинарное отношение  над X . В теории 
графов множество  X  называют множеством  вершин, а   

множеством дуг (или ребер). Для ребра 


,
ij
i
j
x x
 
 

вершину 
ix  будем называть начальной, а вершину 
jx  – 

конечной вершиной ребра 
ij
 ; сами вершины, связанные  

ребром 
ij
 , будем называть смежными между собой и 

инцидентными ребру 
ij
 . Ребро вида 


,
ii
i
i
x x
 
 назовем 

петлей. 

Для каждой вершины 
ix , число ребер 
 
i
d
x

, для которых 

вершина 
ix  конечная, назовем верхней полустепенью 

 
-8-

вершины; число ребер 
 
i
d
x

, для которых вершина 
ix  

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

 
 
 
deg
i
i
i
x
d
x
d
x




. 

Очевидно, 
степень 
вершины 
совпадает 
с 
числом 

инцидентных данной вершине ребер. 

При 
 
deg
0
ix

 вершину назовем изолированной, при 

 
deg
1
ix
  – висячей вершиной. 

Для 
графической 
иллюстрации 
вершины 
удобно 

изображать 
маркированными 
кружками, 
а 
ребра 
– 

направленными непрерывными кривыми любой формы. 
Если в графе имеется симметрия ребер, такая, что для 

каждой 
существующей 
дуги 


,
ij
i
j
x x
 
 
найдется 

«обратная» дуга 


,
ji
j
i
x x


, такой граф часто называют 

неориентированным (неографом) и обе направленные дуги 

ij
 , 
ji

 изображают одной ненаправленной дугой. 

Очевидно, петли всегда можно изображать именно так. 

Теорема о степенях. Для каждой вершины 
ix  графа 

,
G
X

  
с 
матрицей 
смежности 
ij


Γ
 
для 

полустепеней и степени выполнены равенства: 

 

1

n

i
ik

k

d
x






, 
 

1

n

i
si

s

d
x






, 
 

1
1

deg

n
n

i
ik
si

k
s

x










, 

т.е. верхняя полустепень равна сумме элементов матрицы в 
столбце i , а нижняя – сумме элементов строки i . 
Утверждение прямо следует из способа задания матрицы 
смежности. 
Следствие 1:  

 
-9-

 
 

1
1

n
n

i
i

i
i

d
x
d
x
m










, 
 

1

deg
2

n

i

i

x
m





, 

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

теоремы о степенях примет вид 

 
 













m
m
x
d
x
d

n

i

i

n

i

i
0

1
1

2
, 

где 
0
m  есть количество неориентированных ребер, а 

m  – 

количество петель в графе. 

 

Граф без петель также удобно характеризовать матрицей 

инцидентности 
i
 
, где строки соответствуют вершинам, а 

столбцы – ребрам, и 
1
i  , когда вершина 
ix  инцидентна ребру 

  и является начальной,  
1
i    для конечной вершины 
ix  

ребра  , и 
0
i 
 в остальных ситуациях. Для неографа 

используются 
неориентированные 
ребра 
и 
в 
случае 

инцидентности ребра и вершины 
1
i  . 

 

Примеры отношений, матриц смежности и графов: 

 

1) Пусть 
,
G
X

 , где число элементов X : 
4
X 
 и  

 
-10-

1
0
1
0

1
1
0
0

0
1
1
1

1
0
1
0









 








Γ
.  Граф изобразим так:

 
Вершины 
графа 
моделируют 
элементы 
 
множества 



1
2
3
4
,
,
,
X
x x x x

, каждая пара 

,
i
j
x x
   изображена 

направленной дугой из вершины 
ix  в вершину 
jx .  

2) Пусть теперь матрица смежности имеет вид 

1

2

3

1

2

3

4

0
0
0
0
1
1
1

0
0
0
1
1
0
0

0
0
0
0
1
0
1

   
0
0
0
0
0
0
0

0
0
0
0
0
0
0

0
0
0
0
0
0
0

0
0
0
0
0
0
0

a
a

a
b
b
b
b















 


















Γ

, тогдаG :

(A)          (B)

Матрица инцидентности графа имеет размер 
7
7
 (7 вершин на 7 

ребер). Ребра маркированы парой номеров вершин: 


j
i b,
a
ij 
. 

4

3

2

1

1

1

1

   

0
0
0
0
1
0
0

0
0
0
0
0
1
0

0
1
1
0
0
0
1

0
0
0
1
0
0
0

1
1
0
0
0
0
0

0
0
1
1
0
0
0

0
0
0
0
1
1
1

34
32
22
 
21
14
 
13
12
         

b
b
b
b
a
a
a







































Ι

 

 
В данном случае любая дуга соединяет вершину из множества 

A
X

 с вершиной множества B
X

 и 


 B
A
.