Введение в схемы, автоматы и алгоритмы

Графы


Мы часто сталкиваемся с задачами, в условиях которых заданы некоторые объекты и между некоторыми их парами имеются определенные связи. Если объекты изобразить точками (вершинами), а связи - линиями (ребрами), соединяющими соответствующие пары точек, то получится рисунок, называемый графом. Приведем основные определения.

Граф (ориентированный) - это пара

(V, E)
, где
V
- конечное множество вершин (узлов, точек) графа, а
E
- некоторое множество пар вершин, т.е. подмножество множества
V \times V
или бинарное отношение на
V
. Элементы
E
называют ребрами (дугами, стрелками, связями). Для ребра
e= (u,v) \in E
вершина
u
называется началом
e
, а вершина
v
- концом
e
, говорят, что ребро
e
ведет из
u
в
v
.

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

Заметим, что в графе может быть ребро вида

(u,u)
, называемое петлей.

Пример 1.3. На рис. 1.1 приведен пример графа

G_1=(V_1, E_1)
. Здесь
V_1=\{ a,b,c,d\}, E_1=\{ (a,b), (a,c), (b,b), (b,d), (d,a)\}
, В графе
G_1
ребро
(b,b)
является петлей, полустепень исхода вершины
a
равна 2, а полустепень захода для нее равна 1.

Граф G1

Рис. 1.1.  Граф G1

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

Определение 1.6.

Размеченный граф - это граф

G= (V, E)
, снабженный одной или двумя функциями разметки вида:
l: V \rightarrow M
и
c: E \rightarrow L
, где
M
и
L
- множества меток вершин и ребер, соответственно.

Упорядоченный граф - это размеченный граф

G= (V, E)
, в котором ребра, выходящие из каждой вершины
v \in V
, упорядочены, т.е. помечены номерами
0, \ldots, k_v-1
, где
k_v
- полустепень исхода
v
, т.е.
k_v =|\{ w\ |\ (v,w) \in E\}|
.

Упорядоченный граф с полустепенью исхода вершин

\leq 2
называется бинарным.

В качестве множества меток ребер

L
часто выступают числа, задающие "веса", "длины", "стоимости" ребер. Графы с такой разметкой часто называют взвешенными.

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

Определение 1.7. Мультиграф

G= (V, E)
состоит из конечного множества вершин
V
и мультимножества ребер
E,
состоящего из пар вершин
(u,v) \in V \times V,
в которое эти пары могут входить по нескольку раз.




Начало  Назад  Вперед