Элементы теории графов. Сюсюкалов А.И - 5 стр.

UptoLike

ВУЗ: 

РГРТУ | Рязань

Составители: 

Рубрика: 

1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ
1.1. Определения и свойства
Термин «граф» впервые появился в книге венгерского ма-
тематика Д. Кёнига в 1936 г., хотя начальные задачи теории
графов восходят ещё к Л. Эйлеру.
Первые задачи теории графов были связаны с решением
математических развлекательных задач и головоломок, напри-
мер:
– задача о кёнигсбергских мостах (задача Эйлера), развитие
которой привело к циклу задач об обходах графов;
– задачи о перевозках, решение которых привело к созданию
эффективных методов решения транспортных задач и др.
В настоящее время с помощью графов можно успешно мо-
делировать и решать разнообразные прикладные задачи.
Определение 1.1. Графом называется совокупность двух
конечных множеств:
V
– вершин,
E
– рёбер, оба конца которых
принадлежат множеству
V
.
Обозначение: EVEVGG ,, , где
V
,
VvvvE
iji
,, ,
ji
vve , – ребро, соединяющее
i
v и
j
v
nji ,1, .
Определение 1.2. Вершины, не принадлежащие ни одному
ребру, называются изолированными.
Определение 1.3. Ребро
ii
vve , называется петлей для
вершины
i
v .
Определение 1.4. Если пара
ji
vv , встречается в семействе
E
несколько раз, то ребро
ji
vve , называется кратным реб-
ром.
Определение 1.5. Вершины называются смежными, если
они соединены рёбрами.

Страницы