Примеры.

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

Вводя понятие графа, мы интерпретировали ребро u как символ связи между двумя объектами. Но часто такая связь бывает неравнозначной. Например: 1. Два человека могут быть не просто знакомыми, а, допустим, один из них по службе подчиняется другому, или один из них является родителем другого. 2. Схема города – граф с вершинами на перекрестках и поворотах, а если ввести одностороннее движение транспорта, то на ребрах необходимо ставить указатели направления движения.

Чтобы отразить подчинение одной вершины другой, рассматривают упорядоченные пары вершин, а соответствующий граф называют ориентированным графом или орграфом.

Определение 33. Ориентированным графом называется упорядоченная пара , где – множество вершин, – множество упорядоченных пар различных вершин из V.

На диаграммах ориентированных графов и мультиграфов ребра снабжают стрелкой, указывающей, в какую вершину идет данное ребро.

Определение 34. Упорядоченная пара (a, b)называется ориентированным ребром или дугой, идущим из вершины а к вершине b.

Иногда ориентированное ребро (или дугу) от А к В обозначают: , А – начальная вершина, В – конечная вершина. В отличие от ребер (в простых графах), дуги соединяют две неравноправные вершины: одна из них – начало дуги, другая – конец.

Замечание. Ориентированный граф определяется как кортеж , где V – набор вершин, а W – подмножество прямого произведения , обозначающее ребра.

Примеры. 1)Пусть Х – множество лиц некоторой военной организации. Бинарное отношение R на множестве Х введем следующим образом: xRy, если лицо у подчинено лицу х. Итак, (X, G) – граф. Связь любого начальника с подчиненным изобразиться в виде дуги графа (X, G). 2) Орграф – стройка, вершины – работы, дуги – необходимое предшествование работы.

Определение 33 можно переписать: Граф, все ребра которого ориентированы, называется ориентированным графом.

Соответствующим образом можно определить и ориентированные мультиграфы.

1. Изобразить орграф , где , .