Ориентированные графы. 
Геометрическая теория графов

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

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

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

Абстрактное определение ориентированного графа (орграфа) формулируется аналогично определению обычного графа, данному в пункте 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- Отображение инциденции / определяется следующим образом: