Основные положения. Ориентированные графы

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

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

Основные положения

Ориентированный граф или орграф представляет собой пару G = (V, Е), где V — конечное множество вершин, а Е — отношение на V. Графическое изображение графа состоит из множества по­меченных вершин с ориентированными ребрами (называемых дуга­ми), соединяющими пары вершин. Совокупность всех дуг образует множество Е.

Дугу, соединяющую пару (и, v) вершин и и v орграфа G, бу­дем обозначать через uv. В простом орграфе отсутствуют петли и кратные дуги. Следовательно, для любой пары вершин и и v в ор­графе найдется не более одной дуги uv из вершины u и v, и не более одной дуги vu из v в и. Если uv — дуга орграфа, то и называют антецедентом v.

На рис. 8.1 приведен пример простого орграфа с множеством вершин V = {а, b, с, d} и множеством дуг Е = {ab, bd, cb, db, dc}.

c

Рисунок 8.1. Пример орграфа

Матрицей смежности данного графа служит (несимметричная) матрица

	а	b	с	d
a	Л	и	л	Л
b	Л	л	л	и
с	Л	и	л	л
d	л	и	и	л

(вершины а, с и d здесь — антецеденты 6).

Путем длины к в орграфе называют последовательность раз­личных вершин v_о, v₁,…, v _k, каждая пара v_i-₁v_i которой образует дугу(i = 1,...,k ).

Контуром в орграфе G принято называть последовательность вершин v_o, v ₁,.... v _k, образующую путь, в которой первая верши­на v_о совпадает с последней v _k, а других повторяющихся вершин в ней нет. Орграф G называют бесконтурным, если в нем нет конту­ров.

Бесконтурные орграфы полезны в качестве моделей ситуаций, задачи в которых должны выполняться в определенном порядке (кон­тур в такой интерпретации означает, что та или иная задача вы­полняется с некоторой периодичностью и предшествует сама себе). В задаче о планировании заданий соответствующий бесконтурный орграф имеет кодовое название «система ПЕРТ».

Пример 8.1. Для получения степени магистра биологии студенту университета, в частности, необходимо прослушать восемь курсов, которые некоторым образом зависят друг от друга. Эта зависи­мость представлена в табл. 8.1. Изобразите систему ПЕРТ, иллю­стрирующую приоритетную структуру курсов.

Таблица 8.1

		Предварительные курсы
(А)	Биотехнология	В
(В)	Начальный курс биотехнологии	С
(С)	Цитология	н
(D)	Структура ДНК	с
(Е)	Этимология	D, G
(F)	Диетология	Е
(G)	Генная инженерия	С
(Н)	Биология человека	Никаких требований

Решение. Система ПЕРТ (см. рис. 8.2) — это просто орграф, пред­ставляющий данную приоритетную структуру. Вершины орграфа в данном случае — восемь курсов. Для краткости ссылок мы обозна­чим курсы буквами латинского алфавита от А до Н. Дуги орграфа отражают представленные в таблице требования, необходимые для усвоения данного курса.

Рисунок 8.2. Система ПЕРТ: приоритетная структура курсов

Предположим, что студент из примера 8.1 намерен определить порядок, в котором ему следует изучать предметы, учитывая их, зависимость друг от друга. Он может сделать это с помощью ал­горитма топологической сортировки. Алгоритм создает последо­вательность согласованных меток для вершин бесконтурного ор­графа таким образом, что если 1, 2, 3,..., п — метки вершин и uv — дуга орграфа, идущая от вершины и с меткой iк вершине v с меткой j, то i < j.

Итак, граф, содержащий направленные дуги с нача­лом v' и концом v", является ориентированным (оргра­фом).

Для орграфа число дуг, исходящих из вершины v называется полустепенью исхода, а входящих – полустепенью захода. Обозначаются соответственно – d^-(v) и d⁺(v)

Пример: b

c

a d

d⁺(a)=1, d⁺(b)=0, d⁺(c)=1, d⁺(d)=2.

d^-(a)=1, d^-(b)=2, d^-(c)=1, d^-(d)=0.

Теорема(лемма о рукопожатиях): Сумма степеней всех вершин обыкновенного графа равна удвоенному количеству ребер, Сумма полустепеней исхода и захода орграфа равна удвоенному количеству ребер.