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

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

Текст из файла (страница 2)

Подграф называется собственным, если он отличен от самого графа. Подграфом графа G  (V , X ), порожденным множеством вершин V1  V , называется граф G1  (V1 , X 1 ), где X 1  X  V12 (т.е. содержащий множество вершин V1 имножество всех ребер графа G, соединяющих вершины из V1 ). Приведенные определенияраспространяются и на орграфы. Граф называется связным, если для любых двух его различных вершин существует маршрут, соединяющий их. Орграф называется сильно связным, если для любых двух его различных вершин v, w существует путь из v в w.

Компонентной связности графа G называется его связный подграф, не являющийся собственным подграфом никакого другого связного подграфа графа G. Компонентной сильнойсвязности орграфа D называется его сильно связный подграф, не являющийся собственным подграфом никакого другого сильно связного подграфа орграфа D. У графа, изображенного на рис. 1.3, три компоненты связности. У орграфа, изображенного на рис. 1.4, трикомпоненты сильной связности: D1 , D2 , D3 , изображенные на рис. 1.5 и выделенные пунктирными линиями на рис. 1.4.6Рис.

1.3Рис. 1.4Рис. 1.5Орграф конденсации. Орграфом конденсации орграфа D  (V , X ) называетсяорграф D0  (V0 , X 0 ), множеством вершин которого является совокупность компонентсильной связности орграфа D с множеством дуг X 0 таких, что x0  (v0 , w0 )  X 0  вкомпонентах сильной связности v0 , w0 существуют вершины v  v0 , w w0 такие, что(v, w)  X .Пример 1.2.

Орграфом конденсации орграфа, изображенного на рис. 1.4, являетсяорграф, изображенный на рис. 1.6.Рис. 1.6Образ, прообраз вершины, множества вершин. Пусть D  (V , X ) – орграф,v V , V1  V . Обозначим D(v)  {w V | (v, w)  X } – образ вершины v, D 1 (v )  {w V | ( w, v)  X } – прообраз вершины v (см. рис. 1.7), D(V1 )   D(v) – образ множеvV1ства вершин V1 , D 1 (V1 )   D 1 (v) – прообраз множества вершин V1 .vV1Рис.

1.77Задача об оптимальном оповещении членов организации. Пусть в орграфеD  (V , X ), V – множество членов организации, X – множество дуг таких, что x  (v, w)  X тогда и только тогда, когда v может передать информацию w. Рассмотрим следующую задачу. Требуется выделить подмножество U множества V с минимальным количеством элементов такое, что через оповещение некоторой информацией членов из U можно добиться оповещения этой информацией всех членов из V . Для решения этой задачидостаточно перейти от орграфа D к орграфу конденсации D0  (V0 , X 0 ) и выделить множество W0  {v0 V0 | D01 (v0 )  }.

Тогда искомым множеством U  V является множествовершин таких, что каждая вершина u U является вершиной («представителем») одной итолько одной компоненты сильной связности орграфа D, принадлежащей множеству W0 .Пример 1.3. Решением указанной задачи для орграфа D, изображенного на рис.1.4, является множество U  {v1} (или U  {v2 } или U  {v3} ). Действительно, v1 передаетинформацию v2 (кратко, v1  v2 ), а затем v2  v3 , v2  v4 , v2  v5 .Разбор типового варианта. Пусть схема взаимного оповещения членов организации задана орграфом D, изображенным на рис. 1.8 (см.

замечание 1.1). Выделить подмножество U множества V с минимальным количеством элементов такое, что через оповещение некоторой информацией членов из U можно добиться оповещения этой информацией всех членов из V . Указать общую схему такого оповещения.Рис. 1.8Решение. Выделим компоненты сильной связности орграфа D : D1 ,…, D7 , (на рис.1.8 они обведены замкнутыми пунктирными линиями). Построим по орграфу D его орграф конденсации D0 (см. изображение D0 на рис. 1.9). Условию D01 (.)   удовлетворяют D1 , D2 , D3 . Возможными представителями этих орграфов являются вершины v1 , v2 , v4 .Тогда можно положить U  {v1 , v2 , v4 } и согласно рис.

1.8, одной из возможных схем оповещения является: первоначально оповещаем v1 , v2 , v4 ; далее: v1  v9  v10  v11 ;v9  v12 ; v2  v3 ; v4  v5  v6  v8  v7 .8Рис. 1.9Тема 2. Матрицы достижимости, связности. Определение наличия контуровв орграфахВ этом разделе рассматривается матричное задание графов (орграфов). С помощьюэтих матриц удобно задавать графы (орграфы) для обработки на ЭВМ. В рассмотренной втеме 1 задаче (см.

разбор типового варианта) компоненты сильной связности орграфаD  (V , X ) легко определяются «визуально», т.е. исходя из изображения этого орграфа.Однако при большом количестве дуг такой подход затруднителен. В этом случае даже построение изображения орграфа является весьма трудоемким, а выделение компонентсильной связности становится практически невозможным. Поэтому представляют интересалгоритмы выделения компонент сильной связности орграфа, основанные на использовании не изображения орграфа, а некоторых других способов задания орграфа, в частности,матричного. Такие матрицы должны легко строиться, исходя из множеств V , X , а сам алгоритм должен быть легко программируемым и практически реализуемым даже прибольших n  n(D), m  m(D).

Именно такой подход и рассматривается в настоящем разделе. В дальнейшем, если об этом не оговорено особо, предполагается, что в рассматриваемых графах (орграфах) отсутствуют петли и кратные ребра (дуги).Матрицы смежности. Пусть D  (V , X ) – орграф, где V  {v1 ,..., vn }. Матрицейсмежности орграфа D называется квадратная матрица A( D)  [aij ] порядка n, у которойaij  1 , если (vi , v j )  X , и aij  0 – в противном случае.

Введем также матрицу смежности для неориентированного графа. Пусть G  (V , X ) – граф, где V  {v1 ,..., vn }. Матрицейсмежности графа G называется квадратная матрица A(G)  [aij ] порядка n, у которойaij  1 , если {vi , v j } X , и aij  0 – в противном случае.Нам понадобится следующее свойство матрицы смежности.

Обозначим черезA  [aij(k ) ] k  ю степень матрицы смежности A  A(D) орграфа D (аналогичное обознаkчение будем использовать и для графа G ), где k  N  {1,2,...}.Утверждение 2.1. Элемент aij(k ) матрицы Ak орграфа D  (V , X ) (графаG  (V , X )), где V  {v1 ,..., vn }, k  N, равен числу всех путей ( маршрутов) длины k из vi вv j (соединяющих vi , v j ).Булевы матрицы. Будем прямоугольную (m  n) – матрицу C  [cij ], у которойcij {0, 1} называть булевой. Заметим, что матрица смежности A(D) ( A(G ) ) для произ9вольного орграфа D (графа G ) является булевой. Над булевыми матрицами одинаковойразмерности можно производить любые двухместные операции, определенные в математической логике и теории булевых функций: &,  ,  , ∼ ,  и т.д. Например, если C  [cij ] ,D  [d ij ] – булевы (m  n) – матрицы, то F  [ f ij ]  C  D есть булева (m  n) – матрица сэлементами f ij  cij  d ij , i  1,2,..., m, j  1,2,..., n.

Кроме того, будем использовать логическое умножение матриц, отличающееся от алгебраического умножения матриц толькотем, что арифметическое сложение заменяется на  . Пусть C  [cij ] – булева (m  k ) – матрица, D  [d ij ] – булева (k  n) – матрица. Тогда F  [ f ij ]  CD есть булева (m  n) – матрицаkс элементами f ij   cir d rj , i  1,2,..., m, j  1,2,..., n. В дальнейшем из контекста будет ясно,r 1где используется алгебраическое умножение матриц, а где – логическое (всюду далее вэтом разделе используется только логическое умножение матриц).

Приведем утверждение, являющееся следствием утверждения 2.1, для случая, когда матрица Ak  [aij(k ) ] является k -й степенью матрицы смежности A  A(D) орграфа D в случае логического умножения (аналогичное обозначение будем использовать и для графа G ), где k  N  {1,2,...}.Утверждение 2.2. Элемент aij(k ) матрицы Ak орграфа D  (V , X ) (графаG  (V , X )), где V  {v1 ,..., vn }, k  N, равен 1, если существует путь (маршрут) длины k изvi в v j (соединяющий vi , v j ); в противном случае, он равен нулю.Матрицы связности. Определение наличия контуров. Говорят, что вершина wорграфа D (графа G ) достижима из вершины v, если либо v  w, либо существует путьиз v в w (маршрут, соединяющий v, w ).

Пусть D  (V , X ) – орграф, где V  {v1 ,..., vn }.Матрицей достижимости орграфа D называется квадратная матрица T ( D)  [tij ] порядка n, у которой tij  1, если вершина v j достижима из вершины vi , и tij  0 – в противном случае. Матрицей сильной связности орграфа D называется квадратная матрицаS ( D)  [ sij ] порядка n , у которой sij  1 тогда и только тогда, когда вершины vi , v j взаимно достижимы (т.е. принадлежат одной компоненте сильной связности).Пусть G  (V , X ) – граф, где V  {v1 ,..., vn }. Матрицей связности графа G называется квадратная матрица S (G)  [ sij ] порядка n, у которой sij  1 тогда и только тогда,когда вершины vi , v j взаимно достижимы (т.е. принадлежат одной компоненте связности).Справедливы следующие утверждения, являющиеся следствиями утверждения 2.2.Утверждение 2.3. Пусть G  (V , X ), где V  {v1 ,..., vn }, – граф с матрицей смежности A  A(G). Тогда S (G)  E  A  A2  ...

 An 1.Утверждение 2.4. Пусть D  (V , X ), где V  {v1 ,..., vn }, – орграф с матрицей смежности A  A(D). Тогда (1) T ( D)  E  A  A2  ...  An 1 ; (2) S (D)  T (D) & [T ( D)]T , где T –операция транспонирования матрицы.Утверждения 2.3, 2.4 дают простые, легко реализуемые на ЭВМ методы вычисления матриц S (G ) , T (D) , S (D). Существуют и более экономичные методы вычисления10этих матриц. Опишем, например, метод Уоршелла, основанный на следующем утверждении.Утверждение 2.5. Пусть А – матрица смежности графа G  (V , X ) (орграфаD  (V , X ) ), где V  {v1 ,..., vn }. Рассмотрим последовательность булевых квадратных мат(l )(l )риц B  [bij ] порядка n, где l  0,1,..., n, B ( 0)  A  E, элементы которых вычисляются последующей итерационной формуле bij(l )  bij(l 1)  (bil(l 1) & blj(l 1) ), где l  1,2,..., n.

ТогдаS (G)  B ( n ) (и соответственно T ( D)  B (n ) , S ( D)  T ( D) & [T ( D)]T ).Пусть орграф D задан матрицей смежности A(D) и уже найдена матрица связности S (D). Приведем алгоритм определения числа компонент сильной связности орграфаD, а также матриц смежности этих компонент.Алгоритм 2.1Шаг 1.

Характеристики

Список файлов книги