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

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

Основные понятия и свойства

Орграф и его элементы

Абстрактное определение ориентированного графа (орграфа) формулируется аналогично определению обычного графа, данному в пункте 1.1.

Ориентированным графом или орграфом G(V, Е, f) называется совокупность непустого , множества V, изолированного от него произвольного множества Е и отображения f:E—> VxV множества Е в VxV, которое каждому элементу из Е ставит в соответствие некоторый элемент из VxV, т.е. упорядоченную пару элементов из V. При этом множества V и Е называются соответственно множеством вершин и множеством дуг орграфа G(V, Е, f), а отображение / называется отображением инциденции этого орграфа.

Пусть ееЕ. Если f(e)=(A, В), то вершина А называется началом дуги е, а вершина В называется концом этой дуги. Также говорят, что дуга е идет от вершины А к вершине В.

Отличие орграфа от неориентированного графа состоит в том, что для каждого ееЕ если f(e)=(A, В), то отображение инциденции / указывает не просто пару вершин А и В, соединенных е (как это было в случае неориентированного графа), а еще к тому же сохраняет различие между А и В, так как пары (А, В) и (В, А) являются различными элементами множества VxV.

Элементами орграфа являются вершины и дуги. Орграф называется конечным, если множества вершин V и ребер Е содержат конечное число элементов.

Чтобы обеспечить наглядность графического изображения орграфа, его дуги (т.е. кривые, соединяющие соответственные вершины) снабжаются стрелками. На рис. 178 приведен пример орграфа G(V, E.f). Этот граф имеет 5 вершин и 12 ребер: V=(A,B,C,D,P}, E=(a),a2,---,ai2l- Отображение инциденции / определяется следующим образом:

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >