Ориентированные графы

Граф называется ориентированным если для любого его ребра про пару ее инцидентных вершин известно какая из вершин является началом ребра, а какая ее концом. На ребрах ориентированных графов таким образом появляется направление – от начальной вершины к конечной, которое принято в графических изображениях обозначать стрелкой (Рисунок 2.1‑3). Примером ориентированного графа может служить схема бассейна рек ибо (известно в каком направлении течет каждая из рек его составляющих) или схема электрического сигала (ток течет от источников к приемникам). Немного позднее будет показано, что и графы моделирующие управление проектом являются ориентированными.

Рисунок 2.1‑3. Пример ориентированного графа.

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

Для ориентированного графа принято различать корневые вершины и терминальные вершины. Корневой вершиной называется вершина графа, все инцидентные ребра которой являются исходящими. Терминальной вершиной называется вершина графа, все инцидентные ребра которой являются входящими. На приведенном выше графе вершины v1 и v6 являются корневыми, а v2 и v5 – терминальными.

Граф называется неориентированным если ни для одного его ребра направление не задано. Схема метрополитена – это пример неориентированного графа.

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

Дата добавления: 2014-11-15; просмотров: 278; Нарушение авторских прав

Мы поможем в написании ваших работ!