Мы часто сталкиваемся с задачами, в условиях которых заданы некоторые объекты и между некоторыми их парами имеются определенные связи. Если объекты изобразить точками (вершинами), а связи - линиями (ребрами), соединяющими соответствующие пары точек, то получится рисунок, называемый графом. Приведем основные определения.
Граф (ориентированный) - это пара
В графе полустепень исхода вершины - это число исходящих из нее ребер, а полустепень захода - это число входящих в данную вершину ребер.
Заметим, что в графе может быть ребро вида
Пример 1.3. На рис. 1.1 приведен пример графа
Во многих приложениях с вершинами и ребрами графов связывается некоторая дополнительная информация. Обычно она представляется с помощью функций разметки вершин и ребер.
Определение 1.6.
Размеченный граф - это граф
Упорядоченный граф - это размеченный граф
Упорядоченный граф с полустепенью исхода вершин
В качестве множества меток ребер
Часто на одном множестве объектов определено несколько различных бинарных отношений. Для представления такой ситуации служат мультиграфы.
Определение 1.7. Мультиграф