Примеры решения задач

Пример 1. Пусть задан орграф D, изображенный на рис. 17.21, а. Построить основание, матрицу смежности и матрицу инцидентности заданного графа.

Рис. 17.21, а. Ориентированный граф D

Решение: основание исходного графа D, полученное путем замены дуг соответствующими им ребрами, показано на рис. 17.21, б.

Рис. 17.21, б. Основание графа D

Матрица смежности исходного графа D будет иметь следующий вид:

								r ^+(xj)	.
R(D) =
	r ^–(xj)

Таким образом, для вершины x ₁, например, полустепень исхода r ⁺(x ₁) равна единице, а полустепень захода r ^–(x ₁) равна трем.

Матрица инцидентности для того же графа запишется следующим образом:

u 1

u 2

u 3

u 4

u 5

u 6

u 7

u 8

u 9

u 10

I(D) =

х 1

– 1

– 1

+ 1

– 1

.

x 2

+ 1

+ 1

+ 1

х 3

– 1

+ 1

x 4

+ 1

+ 1

– 1

x 5

+ 1

– 1

+ 1

x 6

– 1

+ 1

– 1

– 1

Пример 2. Пусть задан ориентированный граф D = (X, U) (рис. 17.22). Построить дерево, используя вышеописанный алгоритм.

Рис. 17.22. Орграф D

Решение: 1. Выбираем вершину x ₁. Находим смежные ей вершины и получаем подмножество X’ = { x ₁, x ₂, x ₄, x ₆}. Поскольку êX’ï ¹ X, переходим к пункту 2.

2. Из подмножества X’ выбираем произвольную вершину, например x ₂. Находим смежные ей вершины. Это вершины x ₃, x ₅, x ₆. Добавляем в подмножество X’ вершины x ₃, x ₅. Вершина х ₆ уже входит в подмножество X’, поэтому дугу < x ₂, x ₆> мы игнорируем.

3. После выполнения пункта 2 настоящего алгоритма получим подмножество X’ = { x ₁, x ₂, x ₃, x ₄, x ₅, x ₆}, таким образом, условие êX’ï = êХï, выполнено, переходим к пункту 4.

4. Построено дерево Т = {< x ₁, x ₂>, < x ₁, x ₄>, < x ₁, x ₆>, < x ₂, x ₃>, < x ₂, x ₅>}. Алгоритм окончен.

Ответ: Построено дерево Т (рис. 17.23.).

Рис. 17.23. Дерево T

Пример 3. Разбить граф G = (X,U), изображенный на рис. 17.24, на максимально связные подграфы и построить его конденсацию.

Рис. 17.24. Граф G

Решение: Используем алгоритм Мальгранжа.

Выбираем произвольную вершину. Пусть это будет вершина х ₁. Строим матрицу смежности заданного графа.

R =

По матрице смежности определяем вершины, достижимые из вершины х ₁:

Г⁺(x ₁) = { х ₁} È { х ₂}.

Теперь определяем вершины, достижимые из х₂:

Г⁺(x ₁) = { х ₁} È { х ₂} È { х ₁, х ₇, х ₈}.

Определяем вершины, достижимые из х₇ и х₈:

Г⁺(x ₁) = { х ₁} È { х ₂} È { х ₁, х ₇, х ₈} È { х ₁, х ₉, х ₅, х ₇, х ₁₀}.

Определяем вершины, достижимые из вершин х ₅, х ₉, х ₁₀:

Г⁺(x ₁) = { x ₁} È { x ₂} È { x ₁, х ₇, х ₈} È { х ₁, х ₅, х ₇, х ₉, х ₁₀} È { х ₃, х ₅, х ₉, х ₁₀}.

Определяем вершины, достижимые из вершины х ₃:

Г⁺(x ₁) = { х ₁} È { х ₂} È { х ₁, х ₇, х ₈} È { х ₂, х ₅, х ₇, х ₉, х ₁₀} È { х ₃, х ₅, х ₉, х ₁₀} È { х ₄}.

Поскольку из вершины х ₄ достижима только вершина х ₉, а она уже включена в список рассмотренных вершин, то в итоге, после выполнения операции объединения данных подмножеств вершин, получим Г⁺(x ₁) = { х ₁, х ₂, х ₃, х ₄, х ₅, х ₇, х ₈, х ₉, х ₁₀}.

Теперь нам необходимо найти вершины, из которых достижима вершина х ₁:

Г ^-(x ₁) = { х ₁} È { х ₂, х ₆, х ₇} È { х ₁} È { х ₂, х ₆, х ₈} È { х ₂} = { х ₁, х ₂, х ₆, х ₇, х ₈}.

Теперь для того, чтобы выделить максимально связную компоненту, нам необходимо найти пересечение данных множеств:

Г⁺(х ₁) Ç Г^-(х ₁) = { х ₁, х ₂, х ₇, х ₈}; Х₁^* = { х ₁, х ₂, х ₇, х ₈}.

Исключаем эти вершины из рассмотрения и продолжаем процесс выделения максимально связных компонент. Берем вершину х ₃ и определяем для нее прямое и обратное транзитивное замыкание:

Г⁺(x ₃) = { x ₃} È { x ₄} È { x ₉} È { x ₃} = { x ₃, x ₄, x ₉};

Г ^-(x ₃) = { x ₃} È { x ₆, x ₉} È { x ₄, x ₁₀} È { x ₃, x ₅} È { x ₁₀} = { x ₃, x ₄, x ₅, x ₆, x ₉, x ₁₀}.

Тогда сильная компонента:

Х₂^* = Г⁺(x ₃) Ç Г ^-(x ₃) = { x ₃, x ₄, x ₉}.

Продолжаем процесс. Выбираем из оставшихся вершин х ₅, х ₆, х ₁₀ вершину х ₅:

Г⁺(x ₅) = { x ₅} È { x ₁₀} È { x ₅} = { x ₅, x ₁₀};

Г ^-(x ₅) = { x ₅} È { x ₁₀} È { x ₅} = { x ₅, x ₁₀}.

Таким образом, получена сильная компонента:

Х₃^* = { x ₅, x ₁₀}.

У нас осталась всего одна невыделенная вершина - это вершина х ₆. Следовательно, вершина х ₆ образует последнюю сильную компоненту в графе G: X₄^* = { x ₆}.

Итак, мы выделили в заданном графе все возможные сильные компоненты.

Теперь строим конденсацию графа G. В качестве вершин графа конденсации выступают сильные компоненты, при этом вершины, составляющие каждую сильную компоненту, стягиваются в одну. Все ребра, соединяющие стягиваемые вершины с вершинами, принадлежащими другим сильным компонентам, сохраняются. Таким образом, мы построили конденсацию D^* (рис. 17.25) исходного графа G.

Рис. 17.25. Конденсация D*

Пример 4. Для графа D = (X, U) на рис. 17.26 определить прямое и обратное транзитивные замыкания для вершины х ₇.

Решение:

Г⁺ х ₇ = { х ₇} È Г⁺ х ₇ È Г⁺² х ₇ È Г⁺³ х ₇;

Г⁺ х ₇ = { х ₇, х ₄, х ₆};

Г⁺² х ₇ = Г⁺{Г⁺ х ₇} = Г⁺{ х ₇, х ₄, х ₆} = { х ₇, х ₄, х ₆, х ₂, х ₅};

Г⁺³ х ₇ = Г⁺{Г⁺² х ₇} =Г⁺{ х ₇, х ₄, х ₆, х ₂, х ₅} = { х ₇, х ₆, х ₄, х ₅, х ₁, х ₂, х ₃};

Г^– х ₇ = { х ₇} È Г^–1 х ₇ È Г^–2 х ₇;

Г^– х ₇ = { х ₇, х ₂};

Г^–2 х ₇ = Г^–{Г^– х ₇} = { х ₇, х ₂, х ₄};

тогда Г^– х ₇ = { х ₂, х ₄, х ₇};

а Г х ₇ = { х ₁, х ₂, х ₃, х ₄, х ₅, х ₆, х ₇} = Х.

Пример 5. Построить разбиение на основе метода Мальгранжа ориентированного графа D = (X, U), заданного матрицей смежности R.

		х 1	х 2	х 3	х 4	х 5	х 6	х 7		Г^+ х 1	.
R =	х 1
х 2									–
х 3
х 4									–
х 5									–
х 6									–
х 7									–
	Г^– х 1

Решение: Столбец Г⁺ х ₁ строится следующим образом. В клетке столбца против стрелки х ₁ ставится 0. В клетку столбца против строки х ₃ ставится 1, так как строка х ₁ содержит 1 на месте х ₃. Строка х ₃ содержит 1 только на уже отмеченном месте х ₁. Тогда в оставшиеся клетки столбца Г⁺ х ₁ проставляются знаки «–». Числа в клетках Г⁺ х ₁ — это количество путей из вершины х ₁ в другие вершины графа D. Тогда Г⁺ х ₁ = { х ₁, х ₃}.

Аналогично заполняются клетки строки Г^– х ₁. Против столбца х ₁ в клетке Г^– х ₁ ставится 0. В клетках строки Г^– х ₁ против х ₂ и х ₃ ставится 1, так как столбец имеет 1 против х ₂ и х ₃. В столбце х ₂ имеется 1 против строки х ₄, следовательно, в клетку Г^– х ₁ против х ₄ записывается 2. В столбце х ₃ имеем единицы против строк х ₁ и х ₅. Строка х ₁ уже рассмотрена, а в клетке Г^– х ₁, расположенной против х ₅, ставится 2. Далее аналогично заполняются оставшиеся клетки Г^– х ₁. Тогда Г^– х ₁ = { х ₁, х ₂, х ₃, х ₅, х ₆, х ₇}, С(х ₁) = Г⁺ х ₁ Ç Г^– х ₁ = { х ₁, х ₃}. Теперь удалим из графа D вершины х ₁ и х ₃. Получим матрицу R' оставшегося графа D'.

		х 2	х 4	х 5	х 6	х 7		Г^+ х 2	.
R' =	х 2
х 4
х 5
х 6
х 7
	Г^– х 2			–	–

Аналогично, заполняя клетки Г⁺ х ₂ и Г^– х ₂, определяем Г⁺ х ₂ = { х ₂, х ₄, х ₅, х ₆, х ₇}, Г^– х ₂ = { х ₂, х ₄, х ₇}. Тогда С(х ₂) = Г⁺ х ₂ Ç Г^– х ₂ = { х ₂, х ₄, х ₇}. Снова удалим из D' вершины х ₂, х ₄, х ₇, получим граф D". Запишем его матрицу смежности.

		х 5	х 6		Г^+ х 5	.
R'' =	х 5
х 6
	Г^– х 5

Получим Г⁺ х ₅ = { х ₅, х ₆}, Г^– х ₅ = { х ₅, х ₆}, C(х ₅) = { х ₅, х ₆}. Следовательно, в результате работы алгоритма получили разложение графа на три части, показанные на рис. 17.26 штриховыми линиями.

Рис. 17.26. Разложение графа на максимально связные подграфы

Пример 6. Зададим нечеткий ориентированный граф первого рода = (X, ), где X = { х ₁, х ₂, х ₃, х ₄, х ₅}, а = {<1/< х ₁, х ₄>>, <0,5/< х ₁, х ₅>>, <0,1/< х ₂, х ₂>>, <0,9/< х ₂, х ₃>>, <0,8/< х ₄, х ₂>>, <0,2/< х ₄, х ₁>>, <0,6/< х ₅, х ₅>>}.

Граф показан на рис. 17.28.

Рис. 17.28. Нечеткий ориентированный граф первого рода

Пример 7. Зададим нечеткий граф из примера 1 в виде = (Х, ).

Решение: Получим X = { х ₁, х ₂, х ₃, х ₄, х ₅}, (x ₁) = {<1/ х ₄>,<0,5/ х ₅>}, (x ₂) = {<0,1/ х ₂>,<0,9/ х ₃>}, (x ₃) = Æ, (x ₄) = {<0,2/ x ₁>, <0,8/ х ₂>}, (x ₅) = {<0,6/ х ₅>}.

Пример 8. Записать матрицу смежности R _x ² графа, рассмотренного в примере 1.

Решение: Матрица смежности запишется следующим образом:

		x 1	x 2	x 3	x 4	x 5
R x ^2 =	x 1					0,5	.
x 2		0,1	0,9
x 3
x 4	0,2	0,8
x 5					0,6

Пример 9. Задать нечеткий ориентированный граф второго вида = (, ), = {<0,9/ x ₁>, <0,8/ х ₂>, <0,7/ х ₃>, <0,6/ x ₄>, 0,4/ х ₅>}, = {<0,4/< x ₁, х ₂>>, <0,8/< x ₁, х ₃>>, <1/< x ₁, x ₄>>, <0,5/< х ₃, x ₄>>, <0,9/< х ₃, х ₅>>}.

Решение: Граф = (, ) приведен на рис.17.29.

Рис. 17.29. Нечеткий ориентированный граф второго вида = (, )

ВОПРОСЫ

1. Дайте определение ориентированного графа.

2. Что понимается под достижимостью?

3. Что такое основание орграфа?

4. Что называется сильной компонентой орграфа?

5. Поясните принцип формирования матриц достижимости и контрдостижимости.

6. В каком случае говорят, что вершины орграфа взаимнодостижимы?

7. Как определяется прямое и обратное транзитивное замыкания?

8. Что такое конденсация графа?

9. Опишите алгоритм разбиения графа на максимально связные подграфы.

10. Определите полустепени исхода и захода.

Дата добавления: 2015-10-26