Разновидности орграфов

Разделение орграфа на его части (суграф, подграф, частичный подграф) аналогично разделению неориентированного графа (см. задание №2), при том, что ребра заменены дугами. На рис. 3.2,а представлен подграф орграфа (рис. 3.1) без вершины v₅.

Симметрическим называется орграф G=(V,U), в котором ( v_iV, v_jV) (v_i, v_j)  U  (v_j, v_i)  U, т.е. любые две смежные вершины v_i и v_j соединены двумя встречными дугами, при этом возможны петли при некоторых вершинах (рис. 3.2,б).

Антисимметрическим называется орграф G=(V,U), в котором ( v_iV, v_jV) (v_i, v_j)  U  (v_j, v_i)  U, т.е. пара смежных вершин может иметь только одну дугу, а петли отсутствуют (рис. 3.2,в).

Полным называется орграф G=(V,U), в котором ( v_iV, v_jV) (v_i, v_j)  U  (v_j, v_i)  U, т.е. любые две вершины соединены по крайней мере одной дугой, петли могут присутствовать (рис. 3.2,г).

Полным графом с петлями называется орграф G=(V,U), если (v_iV) Гv_i=V, т.е. полный симметрический орграф с петлями при всех вершинах.

- 9 -

Обыкновенным называется орграф G=(V,U), если он не имеет параллельных дуг и петель (рис. 3.2,д).

а) u₁ б) в)

v ₁ v₂ v₁ v₂ v₁ v₂

u₂

u₇ u₄ u₃

u₆ v₃

v ₄ v₃ v₄ v₄ v₃

u₅­

г) v₁ v₂ д) v₁ v₂

v₄ v₃ v₄ v₃

Рис. 3.2. Орграф и его разновидности:

а) подграф ; б) симметрический; в) антисимметрический; г) полный; д) обыкновенный

Перемещения в орграфе

Перемещения по дугам графа обусловлено их ориентацией.

Путем длины n является последовательность дуг (u₁,u₂,...,u_n) через вершины (v₀,v₁,...,v_n) таких, что u_i=(v_i-1, v­_i) для i=1,2,...,n , т.е. конец предыдущей дуги является началом следующей, при чем дуги могут повторяться . Например, для графа на рис. 3.2,а путь (u₇,u₁,u₂,u₁) проходит через вершины (v₄,v₁,v₂,v₁,v₂).

Простой путь – это путь без повторяющихся дуг, например, простой путь (u₇,u₁,u₂) через вершины (v₄,v₁,v₂,v₁) (рис. 3.2,а).

Элементарный путь – это путь, если все его вершины различны, например, элементарный путь (u₇,u₁,u₃) через вершины (v₄,v₁,v₂,v₃) (рис. 3.2,а).

Контуром называется замкнутый путь, когда v₀=v_n , например, контур через (u₂,u₁,u₃,u₆, u₇,u₁) через вершины (v₂,v₁,v₂,v₃, v₄,v₁,v₂) (рис. 3.2,а).

Простой контур – это контур с различными дугами, например, (u₁,u₃,u₅,u₆, u₇) через вершины (v₁,v₂,v₃,v₃, v₄,v₁) (рис. 3.2а).

Элементарный контур – это контур с различными вершинами (кроме начальной и конечной), например, (u₁,u₃,u₆,u_7­) через вершины (v₁,v₂,v₃,v₄,v₁) (рис. 3.2,а).

Длиной пути =(u₁,u₂,...,u_n) называют число его дуг l(), например, на рис. 3.2,а ₁=(u₁,u₂,u₁,u₃), l(₁)=4; ₂=(u₁,u₃,u₅), l(₂)=3. Для изолированной вершины длина пути равна нулю.

-10 -

Орграф называется циклическим (контурным), если он содержит, по крайней мере, один контур, и ациклическим (бесконтурным) в противном случае. Петля является специальным видом контура.

Ориентированные деревья

Ориентированным деревом (прадеревом), растущим из корня v₀ , называется граф G=(V,Г), если:

1) ( !v₀  V) Г^-1{v₀}= , т.е. существует единственная вершина v₀ (корень дерева), в которую не заходит ни одна дуга (нет предшествующих вершин);

2) (v_i  V) | Г^-1{v_i} | =1 (v_i  v₀), т.е. в каждую вершину (кроме v₀ ) заходит только одна дуга (только одна вершина предшествует данной v_i);

3. граф не содержит контуров.

Вершина v_i называется висячей, если Гv_i=, т.е. из v_i не исходит дуга (нет следующей вершины).

Двоичным деревом называется прадерево, если (v_i  V) | Г{v_i} | =0 или 2, т.е. из каждой вершины исходят только две дуги, если это не висячая вершина.

V₂

v₁ v₃

v₄

Рис. 3.3. Прадерево

Можно сказать, что прадеревом является орграф без контуров и петель, в котором из корня дерева в любую другую вершину можно придти только по одному элементарному пути. На рис. 3.3 представлен суграф в виде прадерева для графа рис. 3.2,а от вершины v₂ в качестве корня.

ОБЩИЕ МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ

ЗАДАНИЙ 4 – 8

Цель работы: а) освоение математических описаний и методов решения поставленной задачи; б) освоение способов алгоритмизации и использования ЭВМ для решения подобных задач.

Содержание работы: а) представить математическое описание задачи; б) составить блок-схему машинного алгоритма задачи; в) написать и отладить программу на языке высокого уровня; г) представить отчет по решению задачи с результатами решения для тестового примера и исходного графа.

- 11 -

Задание 4. ОПРЕДЕЛЕНИЕ СУЩЕСТВОВАНИЯ ПУТЕЙ В ГРАФЕ

Методические указания к выполнению задания

Постановка задачи

Пусть N₀={1,2,...} – множество натуральных чисел без нуля. Для графа G=(V,Г) путь положительной длины из вершины v_i в v_j существует, если

( p  N₀) v_j  Г ^p v_i. (4.1)

Если рассматривать пути длины ноль, то (4.1) можно записать так: v_j  v_i , т.е. v_j входит в множество транзитивного замыкания вершины v_i .

Метод решения задачи

Булева матрица смежности || S || орграфа G без параллельных дуг показывает, какие существуют пути длины 1 (рис. 4.1), при этом |V|=n.

||S||:
	A	B	C	D	E	F
A	0	1	1	0	0	1
B	1	1	1	1	0	1
C	0	0	0	1	0	1
D	0	0	0	0	1	0
E	0	0	0	1	1	1
F	0	0	0	0	0	0

A

F

B

E C

D

Рис. 4.1. Орграф и булева матрица смежности

Применим к матрице смежности ||S|| операции булева умножения и сложения. Пусть ||S||² = ||S||  ||S|| , ||S||⁴ = ||S||²  ||S||² , ... , , тогда

где i,j=1(1)n (изменение от 1 с шагом 1 до n);  – булево умножение;  – булево сложение.

Если , то ненулевые элементы матрицы показывают, какие вершины в графе связаны путями.

Пример.

На рис. 4.1 приведена матрица ||S|| , а на рис. 4.2 показаны матрицы ||S||², ||S||⁴, ||S||⁸. Матрица ||S||² показывает, какие существуют пути длиной не более 2 дуг. Поскольку ||S||⁴ = ||S||⁸ , постольку ||S||⁴ показывает, какие вершины в графе связаны путями.

- 12 -

||S||²: ||S||⁴: ||S||⁸:

	A	B	C	D	E	F			A	B	C	D	E	F			A	B	C	D	E	F
A	1	1	1	1	0	1		A	1	1	1	1	1	1		A	1	1	1	1	1	1
B	1	1	1	1	1	1		B	1	1	1	1	1	1		B	1	1	1	1	1	1
C	0	0	0	0	1	0		C	0	0	0	1	1	1		C	0	0	0	1	1	1
D	0	0	0	1	1	1		D	0	0	0	1	1	1		D	0	0	0	1	1	1
E	0	0	0	1	1	1		E	0	0	0	1	1	1		E	0	0	0	1	1	1
F	0	0	0	0	0	0		F	0	0	0	0	0	0		F	0	0	0	0	0	0

Рис. 4.2. Булевы матрицы существования путей между вершинами графа

Описание машинного алгоритма задачи

Возможный вариант алгоритма задачи определения существования путей в графе может включать следующие шаги:

1. Ввести булеву матрицу смежности (S) и ее размер (n).

2.Скопировать матрицу S в рабочую матрицу R (R=S), сбросить счетчик длин путей (L=0).

3. С помощью процедуры булевого умножения матриц вычислить матрицу R1=R  R.

4. В циклах по строкам (i) и столбцам (j) матрицы поэлементно сравнивать R1_ij и R_ij. Если R1_ij  R_ij , то скопировать R=R1, увеличить L и перейти к шагу 3, иначе вывести R и L как результат решения задачи.

Задание № 5. ПЕРЕСЧЕТ ДЛИН ПУТЕЙ

Методические указания к выполнению работы

Постановка задачи

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

Метод решения задачи

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

||S|| – дает число путей длины 1 между каждой парой вершин (v_i,v_j);

||S||² = ||S||||S|| – дает число путей длины 2 между каждой парой вершин (v_i,v_j);

||S||^r = ||S||^r-1||S|| – дает число путей длины r между каждой парой вершин (v_i,v_j), где

- 13 -

Пример.

Для графа на рис. 4.1 матрицы на рис. 5.1 дают число путей длины соответственно 1,2,3,4.

||S||: ||S||²:

			A	B	C	D	E	F				A	B	C	D	E	F
		A	0	1	1	0	0	1			A	1	1	1	2	0	2
		B	1	1	1	1	0	1			B	1	2	2	2	1	3
		C	0	0	0	1	0	1			C	0	0	0	0	1	0
		D	0	0	0	0	1	0			D	0	0	0	1	1	1
		E	0	0	0	1	1	1			E	0	0	0	1	2	1
		F	0	0	0	0	0	0			F	0	0	0	0	0	0

||S||³: ||S||⁴:

			A	B	C	D	E	F				A	B	C	D	E	F
		A	1	2	2	2	2	3			A	2	3	3	6	4	7
		B	2	3	3	5	3	6			B	3	5	5	9	8	11
		C	0	0	0	1	1	1			C	0	0	0	1	2	1
		D	0	0	0	1	2	1			D	0	0	0	2	3	2
		E	0	0	0	2	3	2			E	0	0	0	3	5	3
		F	0	0	0	0	0	0			F	0	0	0	0	0	0

Рис. 5.1. Матрицы пересчета длин путей между вершинами графа

Описание машинного алгоритма

Алгоритм пересчета длин путей можно описать следующим образом:

1. Ввести матрицу смежности (S), ее размер (n) и счетчик длин путей (L), полученный в задании 4.

2. В цикле k=2(1)L копировать S в рабочую матрицу R, использовать процедуру умножения двух матриц и выводить матрицы S^k путей длины k.

Задание № 6. ПОИСК ТРАНЗИТИВНОГО ЗАМЫКАНИЯ

Методические указания к выполнению задания

Постановка задачи

Пусть задан произвольный граф G=(V,U). Требуется построить такой путь, соединяющий две заданные вершины v и w, который содержит наименьшее число дуг (это путь минимальной длины, если считать длины путей одинаковыми, т.е. элементарный путь в графе).

Метод решения задачи

Рассмотрим шаги алгоритма решения этой задачи, который проиллюстрирован на рис. 6.1.

- 14 -

Прямой ход.

1. Присвоить вершине v метку 0.

2. Если x  v и x  Гv, то присвоить каждой такой вершине метку 1 (это вершины-концы дуг, исходящих от вершины v, при этом исключаются петли).

3. Пусть X(m) (m=0,1,2,...) – множество вершин, имеющих метку m. Вершинам X(m+1)={ x  ГX(m), x  X(k) при k  m } присвоить метки m+1 (это вершины-концы дуг, исходящих из вершин множества X(m), при этом исключаются контуры).

4. Процесс присвоения вершинам меток прекратить, как только вершина w получит некоторую метку n (w  X(n)).

Обратный ход.

5. Рассмотреть вершины , , ... , такие, что

 X(n-1) , w  Г ,

 X(n-2) ,  Г ,

...

 X(0) ,  Г .

Путь  = ( v= , , ... , , , w ) дает решение задачи.

X(0) X(1) X(m) X(m+1) X(n-2) X(n-1) X(n)

x₂(1)

... ...

v(0) x₁(1) w(n)

Рис. 6.1. Процесс поиска пути между вершинами v и w

Замечание. Если на некотором шаге невозможно присвоение метки m+1 вершинам, поскольку множество ГX(m) пусто и вершина w не получила метки, то это означает, что в графе G не существует никакого пути, соединяющего вершину v с вершиной w.

Рассмотренный алгоритм описывает процесс нахождения транзитивного замыкания , отображающего дерево поиска кратчайших простых (т.е. элементарных) путей, исходящих от любой вершины v как от корня дерева.

Аналогично, может быть описан процесс нахождения обратного транзитивного замыкания , т.е. множества вершин, из которых можно попасть в вершину v по кратчайшему пути.

Пример.

Для графа G на рис. 6.2,а показаны метки вершин, начиная с вершины B,

- 15 -

– положительные для транзитивного замыкания и отрицательные для обратного транзитивного замыкания .

|| S ||:

	0	0	0	1	0	A	3
	0	0	0	1	0	B	0
	1	1	0	0	1	C	2
	0	1	1	1	1	D	1
	0	0	0	0	1	E	2
	A	B	C	D	E
	2	0	1	1

а) C(2,-1) б)

B(0) D(1,-1)

A(3,-2) E(2)

Рис. 6.2. Пути в графе с наименьшим числом дуг для вершины В:

а) граф с метками и ; б) матрица смежности графа замыкания и

Принципы построения машинного алгоритма поиска транзитивного и обратного транзитивного замыканий рассмотрим на примере получения и на основе анализа матрицы смежности графа (рис. 6.2,б).

Справа от матрицы смежности ||S|| находится вектор-столбец для , а внизу – вектор-строка для . Рассмотрим порядок заполнения столбца .

1. В позицию В вектора-столбца помещаем 0 (начальная вершина).

2. В строке В матрицы S единица находится в позициях, соответствующих вершинам, в которые есть путь длины 1, поэтому в позицию D вектора-столбца записываем 1.

3. Строка D матрицы содержит 1 в позициях вершин, которые отстоят от D на одну дугу, а значит удалены от вершины В на 2 дуги.

Если в позициях столбца , соответствующих единичным позициям в строке D матрицы, уже есть числа, то они не изменяются (например, в позициях B и D), а в пустые позиции C и Е помещаем число 2. Тем самым исключаются петли (например, в вершине D) и контуры (например, встречная дуга (D,B)).

4. Повторяем пункт 3 для вершин С, Е и других, увеличивая длину пути на 1, до тех пор пока это возможно.

Аналогично действуем при заполнении вектора , но при этом необходимо транспонировать матрицу смежности. Числа, получаемые в векторе , дают минимальные длины путей (числа дуг) для тех вершин, из которых можно попасть в вершину В. Например, из вершины Е нельзя попасть в вершину В никаким путем.

Описание машинного алгоритма

Машинный алгоритм должен обеспечивать поиск транзитивного замыкания (вектор Z) для любой начальной вершины (К) графа. Возможный вариант

- 16 -

алгоритма может включать следующие основные шаги:

1. Ввод матрицы смежности (S), ее размера (n) и номера начальной вер-

шины (К).

2. Установка начального значения вектора Z (i=1(1)n, Z_i = –1).

3. Установка Z_K=0 (начальная вершина), L=0 (счетчик длины пути).

4. Начало цикла анализа необработанных вершин:

5. Установка C=n-1 (счетчик необработанных вершин).

6. Цикл i=0(1)n-1 (заполнение вектора Z):

{ если Z_i  L (вершина не удалена на длину L), то учет такой вершины (С=С-1) и продолжение цикла i,

иначе:

7. Цикл j=0(1)n-1 (по позициям строки i матрицы S ):

{если S_ij = 1 и Z_j  0 (вершина j входит в замыкание и еще не включена) , то Z_j =L+1 (занесение длины пути до вершины j в Z_j ).

8. } (конец цикла j )

9. } (конец цикла i )

10. Изменение счетчика длины пути (L=L+1).

11. Пока С  0 (не все вершины обработаны), перейти на пункт 5.

12. Вывод результата: Z.

Задание № 7. ПОИСК КРАТЧАЙШИХ ПУТЕЙ В ГРАФЕ

Методические указания к выполнению задания

В задании № 6 мы считали, что длины всех дуг графа были равны, например, L(u)=1. Рассмотрим теперь случай, когда каждой дуге u поставлено в соответствие число L(u)  0, называемое длиной дуги. В зависимости от конкретного приложения это число может быть мерой физического расстояния, времени, стоимости или другого важного параметра. Длиной пути  называется сумма длин дуг, входящих в  :

.

Отметим две важнейшие характеристики длины, существенные для дальнейшего рассмотрения.

1. Длина должна быть аддитивна (длина совокупности дуг равна сумме длин отдельных дуг).

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

- 17 -

Для графов с контурами можно говорить только о задаче отыскания минимальных путей графа, а в ациклическом графе можно искать как минимальный, так и максимальный путь между вершинами графа.

Постановка задачи поиска минимальных путей в орграфе

Для произвольного орграфа G(V,U), где для u  U сопоставлено число L(u)  0 (длина дуги), необходимо найти путь  минимальной длины, соединяющий вершину v₀ с вершиной v_n.

Метод решения задачи

Существует несколько методов решения этой задачи, среди которых рассмотрим алгоритм Форда, описываемый следующими правилами.

Прямой ход.

1.Переименовать, если это необходимо, вершины графа G так, чтобы исходная вершина получила номер 0.

2. Присвоить каждой вершине v_i метку _i так, чтобы ₀=0 , _i =  при i0 (под символом  здесь следует понимать достаточно большое положительное число).

3. Найти такую дугу (v_i , v_j), для которой _j – _i  L(v_i , v_j). У вершины v_j заменить метку _j на новую метку

^_j = _i + L(v_i , v_j) , если ^_j  _j .

4. Применять правило 3 до тех пор, пока для каждой дуги (v_i , v_j) не станет справедливым неравенство _j – _i  L(v_i , v_j).

Обратный ход.

5. В множестве Г^-1v_n найти такую вершину , что

_n = + L( , v_n) или _n – = L( , v_n) .

Аналогично, в множестве Г^-1 найти такую вершину , чтобы было

справедливо равенство

= + L( , ) или - = L( , ) и т.д.

После некоторого числа шагов вершина совпадет с вершиной v₀.

По условию задачи L(v_i , v_j)  0 , поэтому метки , , , ... образуют строго убывающую последовательность неотрицательных чисел, отличающихся друг от друга на величину, большую или равную длине кратчайшей дуги графа. Следовательно, при некотором k получим = 0, = v₀ . Вершина v₀ выделена тем, что ей в силу правила 2 с самого начала присвоена метка = 0 и в формировании этой метки не участвуют дуги графа.

Путь  = ( v₀= , ,..., , , v_n ) – минимальный и его длина L() = _n .

Пример.

На рис.7.1 представлен орграф с разными длинами дуг и проиллюстрирован (в квадратных скобках) процесс изменения меток при вершинах графа. Вы-

- 18 -

делены 3 кратчайших пути между вершинами v₀ и v₆ : ₁ = (v₀ , v₁ , v₄ , v₆) , ₂ = (v₀ , v₃ , v₄ , v₆) , ₃ = (v₀ , v₃ , v₅ , v₆) . Минимальная длина пути L_min= 19, что равно последней метке ₆ .

v₁[ , 7] 4 v₄[ , 15,11]

7 15 2 8

v₀[0] 9 v₃[ , 9] 16 v₆[ , 25,19]

7 8 5 3 4 2 6 4

v₂[ , 8] 6 v₅[ , 14,13]

Рис. 7.1. Орграф с длинами дуг и метками вершин

На рис. 7.2 представлены матрицы смежности и длин дуг этого орграфа.

	0	1	2	3	4	5	6						0	1	2	3	4	5	6
0	0	1	1	1	1	0	0					0	0	7	8	9	15	0	0
1	0	0	0	0	1	0	0					1	0	0	0	0	4	0	0
2	1	0	0	1	0	1	0					2	7	0	0	3	0	6	0
3	1	0	0	0	1	1	1					3	5	0	0	0	2	4	16
4	0	0	0	0	0	0	1					4	0	0	0	0	0	0	8
5	0	0	0	1	0	0	1					5	0	0	0	2	0	0	6
6	0	0	0	0	0	1	0					6	0	0	0	0	0	4	0

|| S ||: || L ||:

Рис. 7.2. Матрицы смежности и длин дуг графа

Матрица длин дуг графа по сути включает всю информацию о графе, делая матрицу смежности излишней для данной задачи.

Описание машинного алгоритма

Построение машинного алгоритма основано на анализе матрицы длин дуг графа ( L_nn , n – число вершин графа), постепенном заполнении вектора меток вершин (М) новыми метками и получении матрицы кратчайших путей (K _nn).

В результате вектор меток (М) отражает минимальные расстояния между начальной вершиной v₀ и остальными вершинами. Матрица кратчайших путей (K) отражает информацию о подграфе минимальных путей исходного графа между начальной вершиной v₀ и конечной вершиной v_n. Поскольку задача может иметь несколько вариантов решения, то возможный алгоритм может включать следующие основные шаги.

- 19 -

Прямой ход.

1. Ввод матрицы L и ее размера n.

2. Установка начальных значений: 1) вектора меток: M₀=0; i=1(1)n–1, M_i=max, где max – максимально допустимое число данного типа; 2) вспомогательного вектора вершин, входящих в критические пути: V₀=V_n-1=1; i=1(1)n–2, V_i=0.

3. Реализация правил 3 и 4 алгоритма Форда:

циклы i=0(1)n–1, j=0(1)n–1 (поиск смежных вершин графа по строкам i и столбцам j и обновление меток вершин): если L_{i j}  0 и M_j – M_i  L_{i j} , то вычисление новой метки (MN) вершины j и, если необходимо, замена старой метки (M_j = MN).

4. Вывод вектора меток М.

Обратный ход.

5. Реализация правила 5 алгоритма Форда: цикл j=n–1(–1)1 (по столбцам матрицы L – по вершинам, начиная с последней), цикл i=0(1)n–1 (по строкам – для поиска предшествующих вершин i , смежных с вершиной j ): если L_{i j}  0 и M_j – M_i = L_{i j} , то заполнение K_{i j} = L_{i j} и включение вершины i в вектор V_i = 1, иначе K_{i j} = 0.

6. Исключение из матрицы K (подграфа кратчайших путей) "висячих" вершин, не вошедших в вектор V: цикл по вершинам j=1(1)n–2: если V_j = 0 , то в цикле i=0(1)n–1 установить K_{i j} = 0 ( т.е. подавить связи вершины j с предшествующими вершинами). 7. Вывод матрицы K.

По матрице K необходимо построить для исходного орграфа подграф кратчайших путей от вершины v₀ к v_n .

Задание № 8. ПОИСК КОНТУРОВ В ГРАФЕ

Методические указания к выполнению задания

Постановка задачи

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

Орграфы и бинарные отношения

Пусть V – множество объектов, подлежащих исследованию путем их по парного (бинарного) сравнения. Множество всех упорядоченных пар v, v^  V есть декартово произведение VV. Подмножество B  VV называется бинарным отношением, т.е. (v, v^ ) B.

- 20 -

Существует соответствие между бинарным отношением и орграфом, при этом вершины графа соответствуют объектам сравнения v_i  V , а дуги отображают бинарное отношение между объектами.

Бинарное отношение называется : рефлексивным, если (v, v ) B (граф с петлями); симметричным, если (v, v^ ) B  (v^, v ) B (встречные дуги между вершинами); транзитивным, если (v, v^ ) B и (v^, v^ ) B  (v, v^ ) B (если три вершины последовательно связаны дугами, то имеется дуга между 1 и 3-й вершинами).

Транзитивное, рефлексивное и симметричное отношение, называемое эквивалентностью, отражается на графе G контурами и порождает классы (подмножества) эквивалентных объектов K_i  V.