Компоненты сильной связности графа

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

ФГБОУ ВО

«Воронежский государственный университет
инженерных технологий»

КАФЕДРА ИНФОРМАЦИОННЫХ ТЕХНоЛОГИЙ МОДЕЛИРОВАНИЯ И

УПРАВЛЕНИЯ

 

Методические указания и задания

К контрольной работе № 2

по дисциплине “Теоретические основы информационных технологий ”

 

для студентов 1-го курса ФБО

направления 09.03.02

 

 

Воронеж 2016

Контрольная работа состоит из четырех заданий. К каждому заданию приведены необходимые для их выполнения теоретические сведения и примеры выполнения заданий. Ход выполнения и результаты решения заданий студентом оформляются средствами MS WORD. Номер варианта каждого задания выбирается по последней цифре шифра логина студента.

Маршруты в орграфе

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

З а д а ч а. Дан орграф порядка 6 Сколько в нем маршрутов длины 3? Записать их.

 

Пример. Дан орграф. Сколько в нем маршрутов длиной 3?

Решение. Используем алгебраический метод решения задачи. Запишем матрицу смежности. Матрица смежности орграфа — несимметричная:

Возведем эту матрицу в степень 3:

.

Суммируя все элементы полученной матрицы, находим, что число маршрутов длиной 3 равно восьми. Три единицы, стоящие по диагонали, показывают, что сюда входит 3 помеченных контура. Очевидно, это контуры 1–4–3, 4–3–1 и 3–1–4.

Проверить наличие контура в орграфе можно также методом топологической сортировки. Если граф не может быть отсортирован топологически, то в нем есть контуры.

 

 

Компоненты сильной связности графа

Понятие сильной связности относится только к орграфам. Основание орграфа — неограф с теми же вершинами, но ребрами вместо соответствующих дуг. Орграф называется связным, если связно его основание. Вершина u достижима из вершины v, если существует маршрут из v в u.

Орграф называется сильно связным (или орсвязным), если любаяего вершина достижима из любой вершины. Граф называется ориентируемым, если он является основанием сильно связного графа.

З а д а ч а. Найти компоненты сильной связности орграфа.

Пример. Найти сильные компоненты связности орграфа G.

Решение. Найдем матрицу смежности вершин орграфа G:

Найдем матрицу достижимости вершин орграфа:

 

 

Построим матрицу контрдостижимости

 

Отсюда получаем матрицу сильных компонент связности орграфа:

 

Таким образом, данный орграф содержит сильные компоненты связности G 1 = (1,2,3,7).