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

Задача 1. Задана матрица смежности орграфа:

.

Определить свойства отношения смежности вершин орграфа. Является ли орграф сильно связным? Если нет, то выделить компоненты сильной связности.

Решение. В орграфе отсутствуют все петли, следовательно, отношение смежности вершин не обладает свойством рефлексивности, более того, оно антирефлексивно. В орграфе для любой дуги прямого направления отсутствует дуга обратного направления, следовательно, смежность вершин орграфа в данном случае не обладает свойством симметрии, оно антисимметрично. Кроме того, отношение смежности вершин орграфа не транзитивно, так как при наличии дуг (v₁,v₃) и (v₃,v₂) отсутствует дуга (v₁,v₂).

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

; ;

;

.

Выполним поразрядную дизъюнкцию элементов матриц ,,,, получим матрицу достижимости орграфаG:

.

Теперь найдем элементы из соотношения, получим матрицу сильной связности данного графа:

.

Матрица сильной связности S(G) содержит нули, что указывает на то, что не все вершины орграфа достижимы одна из другой. Таким образом, орграф не является сильно связным.

Образуем первую компоненту сильной связности. Это орграф, вершины которого соответствуют единицам первой строки матрицы сильной связности. Множество вершин G₁– первой компоненты сильной связности:. В качестве матрицы смежностиG₁берем подматрицу матрицы А(G), находящуюся на пересечении первой, третьей, пятой строк с первым, третьим, пятым столбцом:

.

Вычеркиваем из матрицы первую, третью, пятую строки, а также первый, третий, пятый столбцы, переходим к матрице. С помощью нее определяем множество вершинG₂– второй компоненты сильной связности:. Матрица смежностиG₂имеет вид:.

Вычеркивая из матрицы S₂первые строку и столбец, получаем матрицу. Третья компонента сильной связностиG₃содержит одну вершину –v₄и характеризуется матрицей смежности.

В результате вычеркивания первых строки и столбца из матрицы S₃ничего не осталось. Работа алгоритма прекращена. Орграф имеет три компоненты сильной связности.

2.10.3 Задачи для самостоятельного решения

1. Найти матрицу смежности и инцидентности орграфов (а, б, в) и неориентированного графа (г), представленных на рисунке 9:

v1 x1 x3 v4 v2 x5 x4 x2 v3
а)	б)
v1 v4 x1 x2 x3 x7 x4 v3 v5 x6 x5 v2 v6 в)	x4 v2 x3 v3 x2 x1 x5 x6 x7 v1 x8 v4 г)
Рисунок 9 – К задаче 1 (2.10.3)

2. Построить диаграмму орграфа, заданного матрицей смежности .

3. Построить диаграмму неориентированного псевдографа, заданного матрицей смежности:

.

2. По условию задачи 2 указать свойства отношения смежности вершин орграфа.

3. Какими свойствами обладает отношение связности вершин графа (рисунок 10)? Чему равно число компонент связности данного графа?

v₃ v₁₀

v₅ v₈

v₁ v₄ v₉

v₂ v₇ v₆ v₁₁

Рисунок 10 – К задаче 5 (2.10.3)

2. Каким операциям над орграфами соответствуют основные операции над отношениями?

3. Какими особенностями отличается орграф G, взаимно однозначно соответствующий бинарному отношениюR, если это отношение:

а) симметрично;

б) антисимметрично;

в) рефлексивно;

г) антирефлексивно;

д) транзитивно?

2. Показать, что в любом графе количество вершин нечетной степени четно.

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

4. Показать, что ребро, входящее в цикл графа, входит в некоторый его простой цикл.

5. Показать, что любая вершина, входящая в цикл, не является висячей.

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

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

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

9. Определить, имеют ли контуры орграфы с матрицами смежности:

а) ; б);

в) ; г);

д) .

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

3. Орграф задан матрицей смежности. Определить матрицу сильной связности. Найти число компонент сильной связности и определить матрицы смежности этих компонент. Построить изображения орграфа и его компонент сильной связности. Рассмотреть случаи:

а) ; б);

в) ; г);

д) .

2. Какими свойствами обладает отношение достижимости вершин орграфа (рисунок 11а, 11б).

v1 v3 v5 v7 v2 v4 v6 а)

б)

Рисунок 11 – К задаче 18 (2.10.3)

2. Доказать, что отношение связности вершин орграфа является эквивалентностью на множестве вершин. Определить классы эквивалентности по отношению связности вершин орграфа.

3. Какими свойствами характеризуется отношение достижимости вершин орграфа, представленного на рисунке 12.

Рисунок 12 – К задаче 20 (2.10.3)

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