Графы

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

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

$(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.

Рис. 1.1. Граф G1

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

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

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

$G= (V, E)$