Задания для самостоятельной работы

1. Для произвольного ориентированного графа D = (X, U) запишите его матрицу смежности, матрицу инцидентности и постройте его основание.

2. Для произвольного ориентированного графа D = (X, U) постройте дерево.

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

4. Для произвольного ориентированного графа запишите алгоритм определения прямого транзитивного замыкания.

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

6. Постройте алгоритм определения конденсации ориентированного графа.

7. Определите способы задания нечетких орграфов.

8. Постройте нечеткие орграфы первого и второго рода.

9. Запишите алгоритм определения прямого транзитивного замыкания в нечетком орграфе.

10. Запишите алгоритм определения обратного транзитивного замыкания в нечетком орграфе.

 

Г иперграфы

В описанных выше графах использовались бинарные отношения на множестве вершин. Однако необходимо отметить, что в общем случае на множестве вершин X графа G = (X, U) можно задать k -арные отношения с помощью гиперграфов. Такое обобщение понятия графа позволяет строить объекты, в которых каждое ребро может соединять не только две вершины, но и любое подмножество множества вершин, что является важным при решении многих технических задач. Это обстоятельство позволяет также при построении математических моделей более точно отражать некоторые свойства реальных объектов.

Дадим определение гиперграфа. Пусть X = { х ₁, х ₂, …, х _n } – конечное множество и Е= { l ₁, 1 ₂, …, 1 _m } – семейство подмножеств X такое, что(" l_i) l_i ¹ 0 и , I = {1, 2, …, m }. Говорят, что объект Н = (Х, Е) – гиперграф на множестве Х, если он состоит из множества вершин X и множества ребер E, причем каждое ребро l_i Î E представляет собой некоторое подмножество множества вершин, т.е. l_i Í X. Если " l_i Î E (| l_i | = 2), то гиперграф H является графом G без изолированных вершин. На рис. 17.30, а показан пример гиперграфа H = (X, Е), |Х| = 7, |E| = 5. Заметим, что ребро l ₅ с | l ₅| = 1 есть петля. Ребрами гиперграфа являются: l ₁ = { х ₁, х ₂, х ₃, х ₄}; l ₂ = { х ₂, х ₃, х ₆, х ₇}; l ₃ = { х ₅, х ₄}; l ₄ = { х ₅, х ₇}; l ₅ = { х ₁}.

Рис. 17.30, a. Гиперграф H = (X, Е)

В гиперграфе H = (X, E) две вершины называются смежными в том случае, если существует ребро e_i, содержащее эти вершины. Ребра гиперграфа называются смежными в случае, если выполняется следующее условие: e_i Ç e_j ¹ 0, то есть если их пересечение представляет собой непустое подмножество.

Матрицей инцидентности гиперграфа H называется матрица I(H) = || h_ij || _{m ´ n}, причем

Для гиперграфа Н на рис. 17.30, а матрица инцидентности примет вид

 

		х 1	x 2	х 3	х 4	х 5	х 6	х 7
I(H) =	l 1	1	1	1	1	0	0	0	.
	l 2	0	1	1	0	0	1	1
	l 3	0	0	0	1	1	0	0
	l 4	0	0	0	0	1	0	1
	l 5	1	0	0	0	0	0	0

Любому гиперграфу H = (X, E) соответствует гиперграф H* = (E, X), вершинами которого являются ребра Е = { l ₁, 1 ₂, …, 1 _m }, а ребрами – вершины х ₁, х ₂, …, х _n. Гиперграф H* называется двойственным H. Матрица инцидентности гиперграфа H* есть транспонированная матрица гиперграфа H. Если два ребра l_i, l_j Î E в H смежны, то соответствующие вершины l_i, l_j Î E в H* также смежны, тоже выполняется и для вершин х _i, х _j Î X в H, когда они становятся ребрами H*. Гиперграф H*, двойственный Н, показан на рис. 17.30, б.

Рис. 17.30, б. Двойственный гиперграф H*

А его матрица инцидентности запишется в виде:

		l 1	l 2	l 3	l 4	l 5
I(H)* =	x 1	1	0	0	0	1	.
	x 2	1	1	0	0	0
	x 3	1	1	0	0	0
	x 4	1	0	1	0	0
	x 5	0	0	1	1	0
	x 6	0	1	0	0	0
	x 7	0	1	0	1	0

 

В гиперграфе Н = (Х, Е) цепь длины q определяется как последовательность вида s(H) = x ₁, l ₁, х ₂, 1 ₂, …, l_q, x_{q +1}. Если q > 1 и x_{q +1} = x ₁, то цепь с такими параметрами называется циклом длины q.

Гиперграф H с n вершинами, m ребрами и k связными компонентами считается деревом в случае, когда его ребра имеют не более одной общей вершины, то есть тогда, когда

.

При решении задач автоматизации конструирования возникает необходимость сопоставлять гиперграфу граф.

Гиперграф Н= (X, Е) можно представить в виде двудольного графа Кёнига К(Н) = (X È E, V), где X – первое подмножество вершин двудольного графа, соответствующее множеству вершин гиперграфа H; Е – второе подмножество вершин двудольного графа, соответствующее множеству ребер гиперграфа H; V – множество ребер двудольного графа, устанавливающее смежность между двумя множествами вершин X и Е в графе К(Н) в соответствии с инцидентностью вершин и ребер гиперграфа H.

Заметим, что в двудольном графе К(H) вершины внутри подмножеств X и Е не смежны, причем вершины x_i Î Х и l_j Î E в К(Н) смежны тогда и только тогда, когда в гиперграфе H вершина x_i принадлежит ребру l_j. На рис. 17.30, в приведен граф Кёнига для гиперграфа H.

Рис. 17.30, в. Граф Кёнига K(H)

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

Под раскраской вершин гиперграфа Н = (Х, Е) понимается некоторое разбиение множества его вершин на классы, не содержащие пустого подмножества, когда инцидентные вершины должны быть окрашены в разные цвета, причем каждому классу X _i (X₁ È X₂ È … X _q = X; X₁ Ç X₂ Ç … X _q = Æ) отвечает определенный цвет, в который окрашены вершины, а q соответствует количеству различных цветов, которые можно использовать для раскраски.

 

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Пример 1. Построить матрицу инцидентности гиперграфа Н = (Х, Е), изображенного на рис. 17.31.

Рис. 17.31. Гиперграф H

Граф, изображенный на рис. 17.31. можно задать следующей матрицей инцидентности.

 

ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ

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

2. Какие две вершины, либо два ребра гиперграфа считают смежными?

3. Как составляется матрица инцидентности гиперграфа?

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

5. Как составляется матрица смежности гиперграфа?

6. Каким образом для гиперграфа можно построить двойственный граф?

7. Какой гиперграф считается деревом?

8. Что такое раскраска гиперграфа?

9. Дайте определение двудольного графа Кенига.

10. Как строится двудольный граф Кенига?