Дискретная математика. Никищенков С.А - 11 стр.

UptoLike

ВУЗ: 

СамГУПС | Самара

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

Рубрика: 

2. ТЕОРИЯ ГРАФОВ
2.1. Определение и способы представления графа
Графом G(V,E) называется совокупность двух множеств – непустого множества V
(множества вершин) и множества E неупорядоченных пар различных элементов
множества V (E – множество ребер). На исходном множестве Х элементов, называемых в
теории графов вершинами или узлами, задается множество пар вида (x
i
, x
j
), называемых
ребрами или дугами. Вершины изображаются кружками, а дуги – линиями
произвольной кривизны. Вершина x
i
, называется началом дуги, а x
j
– ее концом.
Направленность дуги от начала к концу помечается стрелкой. Мощности множества
вершин и дуг обозначаются соответственно через ⏐V⏐=n и ⏐E⏐=m.
Таким образом, граф G можно определить как совокупность множеств вершин V
и дуг Е, между которыми определено отношение инцидентности, причем каждый
элемент e
∈
E инцидентен ровно двум элементам v
i
, v
j
∈
V.
Граф является универсальным средством представления любых конечных
дискретных объектов. В частности, графы применимы для наглядного представления как
различного рода структур, так и операций.
Пример.
Построить схему Красноярской железной дороги
V1 – станция Красноярск;
V2 – станция Бугач;
V3 – станция Ачино;
V4 – станция Красная сопка;
V5 – станция Ташеба;
V6 – станция Черногорские копи;
V7 – станция Уяр;
V8 – станция Саянская;
V9 – станция Решоты;
V10 – станция Юрты;
V11 – станция Карабула;
V12 – станция Коркина;
V13 – станция Дивногорск.
2.2. Свойства элементов графа
К элементам графа относятся вершины и дуги,
поэтому наряду с выражениями
v
∈
V и e
∈
E допускаются выражения v
∈
G и e
∈
G.
Вершины и дуги в графе связаны отношением инцидентности R
И
⊂
E
×
V. Дуга (u, v)
инцидентна (adjacent) вершинам и и v. При этом она является выходящей (исходящей)
из вершины и и входящей (заходящей) в вершину v. Отношение инцидентности не
V12
V1
V7
V11
V9
V4
V2
V10 V8
V13
V6
V5
V4
Рис. 16

Страницы