Отношения и графы

 

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

ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ 

БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ  

УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ 

 

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

(МИИТ)» 

 

ИНСТИТУТ ЭКОНОМИКИ И ФИНАНСОВ 

 
 
 

КАФЕДРА «МАТЕМАТИКА» 

 

 

З.С. Липкина, М.В. Тюленева 

 

ОТНОШЕНИЯ И ГРАФЫ 

 

 

 

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

 

МОСКВА – 2018 

 

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

ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ 

БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ  

УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ 

 

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

(МИИТ)» 

 

ИНСТИТУТ ЭКОНОМИКИ И ФИНАНСОВ 

 
 
 

КАФЕДРА «МАТЕМАТИКА» 

 

 

З.С. Липкина, М.В. Тюленева  

 

ОТНОШЕНИЯ И ГРАФЫ 

 

Учебное пособие для студентов направления «Бизнес-

информатика » и специальности «Компьютерная 

безопасность» 

 

 

Москва – 2018 

 

 

УДК 517 
Л 61 

Липкина З.С., Тюленева М.В. Отношения и графы: 

Учебное пособие для студентов направления «Бизнес-
информатика» и специальности «Компьютерная 
безопасность». –М.: РУТ (МИИТ), 2018. – 93с. 

 

Данное 
учебное 
пособие 
адресовано 
студентам 

направления «Бизнес-информатика » и специальности 
«Компьютерная безопасность». В первой главе даются 
основные определения и простейшие теоремы теории 
графов, во второй главе разбираются некоторые 
алгоритмы оптимальных задач на графах, имеющие 
разнообразные практические приложения. 

Для 
лучшего 
усвоения 
материала 
предлагаются 

тестовые задачи с ответами и примеры оптимальных 
задач. 

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

 

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

Теория 
графов 
занимает 
особое 
место 
в 
дисциплине 

«Дискретная математика», поскольку позволяет наглядно 
описывать сложные и тонкие вещи. С помощью картинки, 
геометрической интерпретации, можно увидеть суть дела на 
интуитивном уровне. Мы уже отмечали глубокую связь между 
бинарными 
отношениями 
и 
графами. 
В 
частности, 

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

максимальным, наименьшим и минимальным элементами. 
Широкое применение теории графов в программировании 
связано с алгоритмами решения различных оптимальных задач 
на графах. 

Начало теории графов положено знаменитой задачей о 
Кёнигсбергских мостах. Она была решена Леонардом Эйлером 
в 1736г., получившим необходимые и достаточные условия 
существования решения для всех подобных задач. Другая 
знаменитая задача о трех домах и трех колодцах была решена 
Казимиром Куратовским в 1930г. также сформулировавшим 
необходимые и достаточные условия решения для всех задач 
этого типа. Наконец в 1976г. Аппель и Хейкен опубликовали 
решение задачи о четырех красках, которое представляло 
собой перебор всех вариантов с помощью компьютера. 

 
 

§ 1. Основные определения графов 

Для понятия «граф» нет общепринятого единого определения. 
Разные авторы в разных приложениях пользуются похожими, 
но 
все-таки 
различными 
определениями. 
Мы 
будем 

придерживаться терминологии, связанной с книгой Харари Ф. 
«Теория графов» и чаще всего применяемой. 

Пусть 
V 
– 
непустое 
множество 
и 
E 
– 
множество 

неупорядоченных пар элементов из V. E={(u,w)|u,wV}. 
Элементы множества V будем называть вершинами, а 
элементы из Е – ребрами. 

Множество Е может содержать пары (u,u), называемые 
петлями, а также несколько одинаковых пар (u,w), которые 
называются кратными ребрами. Количество одинаковых пар  
(u,w) в Е назовем кратностью ребра (u,w). 

Пару (V, E) назовем графом с кратными ребрами и петлями 
(или псевдографом) и обозначать G = G (V, E). 

Если в псевдографе нет петель, то назовем его мультиграфом, а 
если нет и кратных ребер, то просто графом (или 
неориентированным графом). 

Если пары в наборе E являются упорядоченными, то граф 
называется ориентированным (орграфом), (соответственно 
мультиорграф, псевдоорграф). 

При этом элементы множества V называются часто «узлами», а 
множества E – «дугами». Будем, чтобы различать, обозначать 
орграфы D = D(V, E). 

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

 

Пример 1.Орграф (псевдоорграф)D = D(V, E) 

 






7
6
5
4
3
2
1

4
3
2
1

,
,
,
,
,
,

,
,
,

e
e
e
e
e
e
e
E

v
v
v
v
V




 

Рис. 1 

 

 

v1

v2

v3

v4

e1

e2

e3
e4

e5

e6

e7

u
w

Пример 2.Граф G = G(V, E) 

 






8
7
6
5
4
3
2
1

5
4
3
2
1

,
,
,
,
,
,
,

,
,
,
,

e
e
e
e
e
e
e
e
E

v
v
v
v
v
V




 

Рис. 2 

§2 Смежность, инцидентность, степени 

Пусть e = (u, v). Тогда говорят, что вершины u, vинцидентны 
ребру е, а ребро е инцидентно вершинам u,v.Вершины u,v 
называются смежными. Аналогично, ребра е1= (u,v) и е2= (u, w) 
называются смежными. 

В неориентированном графе (псевдографе) степенью вершины 
называют число ребер, инцидентных данной вершине, при 
этом вклад каждой петли считают равным 2. Обозначают (v). 
Так, в примере 2 (v1) = 3, (v4) = 4. 

v1

v2

v3

v4

e1

e2

e3

e4

e5

e6

e7
e8

v5

В ориентированном графе ребро е=(u,v) называют исходящим 
для вершины u и входящим для вершины v. Также определяют 
полустепени+ (u)–число исходящих их вершины u ребер, и - 
(u)–число входящих ребер. При этом для петли += 1 и - = 1. В 
примере 1 +(v1) = 3, -(v1) = 0; +(v4) = 2, -(v4) = 2. 

В 
неориентированном 
графе 
вершина 
называется 

изолированной, если ее степень равна 0, и «висячей», если 
степень равна 1. 

Теорема 
1. 
Для 
любого 
псевдографа
)
,
(
E
V
G
G 
сумма 

степеней всех вершин равна удвоенному числу ребер

 
N
v

i

i
2

 
, N–число ребер. 

Следствие. Число вершин нечетной степени четно. 

Теорема 2. Для орграфа
)
,
(
E
V
D
D 
 
 
N
v
v

i

i

i

i

 






. 

Так в примере 2 3+3+4+4+2=16=2·8, а в примере 1 

 
 
7
2
2
3
0
2
1
1
3
















i

i

i

i
v
v


 

§3 Маршруты, цепи, циклы 

Введем 
понятие 
маршрута 
для 
неориентированного 

псевдографа 
)
,
(
E
V
G
G 
 и пути для орграфа
)
,
(
E
V
D
D 
. 

Чередующаяся 
последовательность 
вершин 
и 
ребер

1
1
2
1
1
...
...


k
k
i
i
i
v
e
v
e
v
v
e
v
,где
,1

k
,
V
vi 
;1
,...,
1


k
i
,
E
e j 

k
j
,...,
1

, такая, что 
)
,
(
1


i
i
i
v
v
e
называется 
маршрутом 

(путем) из v1 в vk+1. Точка v1называется начальной, а vk+1– 
конечной, а остальные – внутренними вершинами, причем 
одна и та же вершина может быть начальной, конечной и 
внутренней. 

Маршрут называется замкнутым, если его начальная вершина 
совпадает с конечной. 

Незамкнутый маршрут (путь), в котором все ребра различные, 
называется цепью. Цепь, в которой все вершины различные, 
называется простой. Замкнутая цепь называется циклом 
(контуром). Цикл (контур) называется простым, если в нем все 
вершины попарно различны. 

Пример 3. Последовательность
2
1
1
7
3
2
2
1
1
v
e
v
e
v
e
v
e
v
 – маршрут 

(пример 2),
4
6
1
7
3
2
2
1
1
v
e
v
e
v
e
v
e
v
– 
цепь,
4
5
3
2
2
1
1
v
e
v
e
v
e
v
– 
простая 

цепь,
1
7
3
2
2
1
1
v
e
v
e
v
e
v
– простой цикл. 

Пример 4. Для примера 1, последовательность 
2
7
3
6
2
1
1
v
e
v
e
v
e
v
– 

цепь, 
3
6
2
2
1
v
e
v
e
v
– простая цепь. 

Замечание. При отсутствии кратных ребер для маршрута 
(пути) достаточно указать последовательность вершин. 

Число ребер (дуг) в маршруте (пути) называется длиной 
маршрута (пути). 

Так, в примере 3 маршрут
2
1
1
7
3
2
2
1
1
v
e
v
e
v
e
v
e
v
 имеет длину 4, в 

примере 4 цепь
3
6
2
2
1
v
e
v
e
v
 длины 2. Цикл
1
7
3
2
2
1
1
v
e
v
e
v
e
v
 примера 

3 имеет длину 3. 

§4 Подграф. Связный граф. Связная компонента 

Граф 
)
,
(
1
E
V
G
G



называется частью графа
)
,
(
E
V
G
G 
, если

E
E
V
V




,
. 

Часть графа называется подграфом, если из того, что вершины 
a и
V
b


, и в графе G существует ребро (a, b), то

E
b
a


,
. 

Аналогично определяется часть графа и подграф в случае 
ориентированных графов. 

В примере 1, если положить




6
1
3
2
1
,
,
,
,
e
e
E
v
v
v
V




, то 



E
V
D
D




,
– часть графа


E
V
D
D
,

, но не подграф. Если 

же добавить ребра 
2e и 
7e – то получим подграф.  

Аналогично в примере 2 


2
1
3
2
1
,
;
,
,
e
e
v
v
v
G 
– часть графа, но 

не подграф. Добавить ребро
7e , получим подграф. 

Неориентированный граф 
)
,
(
E
V
G
G 
называется связным, 

если существует маршрут, соединяющий любые две вершины 
графа. В противном случае граф называется несвязным. 

Граф примера 2 – связный.