Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

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

Покупка
Основная коллекция
Артикул: 788099.01.99
Доступ онлайн
186 ₽
В корзину
Данное учебное пособие адресовано студентам направления «Бизнес-информатика » и специальности «Компьютерная безопасность». В первой главе даются основные определения и простейшие теоремы теории графов, во второй главе разбираются некоторые алгоритмы оптимальных задач на графах, имеющие разнообразные практические приложения. Для лучшего усвоения материала предлагаются тестовые задачи с ответами и примеры оптимальных задач.
Липкина, З. С. Отношения и графы : учебное пособие для студентов направления «Бизнес-информатика» и специальности «Компьютерная безопасность» / З. С. Липкина, М. В. Тюленева. - Москва : РУТ (МИИТ), 2018. - 93 с. - Текст : электронный. - URL: https://znanium.ru/catalog/product/1896906 (дата обращения: 19.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
 
МИНИСТЕРСТВО ТРАНСПОРТА РОССИЙСКОЙ 
ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ 
БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ  
УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ 
 
«РОССИЙСКИЙ УНИВЕРСИТЕТ ТРАНСПОРТА 
(МИИТ)» 
 
 
ИНСТИТУТ ЭКОНОМИКИ И ФИНАНСОВ 
 
 
 
КАФЕДРА «МАТЕМАТИКА» 
 
 
З.С. Липкина, М.В. Тюленева 
 
ОТНОШЕНИЯ И ГРАФЫ 
 
 
 
Учебное пособие 
 
МОСКВА – 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 
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 


 
В ориентированном графе ребро е=(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 маршрут
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 – связный. 


Доступ онлайн
186 ₽
В корзину