Графы

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

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

, где - конечное множество вершин (узлов, точек) графа, а - некоторое множество пар вершин, т.е. подмножество множества или бинарное отношение на . Элементы называют ребрами (дугами, стрелками, связями). Для ребра вершина называется началом , а вершина - концом , говорят, что ребро ведет из в .

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

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

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

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

. Здесь , В графе ребро является петлей, полустепень исхода вершины равна 2, а полустепень захода для нее равна 1.

Рис. 1.1.  Граф G1

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

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

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

, снабженный одной или двумя функциями разметки вида: и , где и - множества меток вершин и ребер, соответственно.

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

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

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

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

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

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

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

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

состоит из конечного множества вершин и мультимножества ребер состоящего из пар вершин в которое эти пары могут входить по нескольку раз.

Содержание  Назад  Вперед

---

---

---

---