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

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

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

Полагаем p  1, S1  S ( D).Шаг 2. Включаем в множество вершин V p очередной компоненты сильной связности D pорграфа D вершины, соответствующие единицам первой строки матрицы S p . В качествеA( D p ) берем подматрицу матрицы A(D), находящуюся на пересечении строк и столбцов,соответствующих вершинам из V p .Шаг 3. Вычеркиваем из S p строки и столбцы, соответствующие вершинам из V p . Если врезультате такого вычеркивания не остается ни одной строки (и соответственно ни одногостолбца), то p – количество компонент сильной связности орграфа D и A( D1 ) ,…, A( D p ) –матрицы смежности компонент сильной связности D1 ,…, D p орграфа D.

В противномслучае, обозначаем оставшуюся после вычеркивания из S p соответствующих строк истолбцов матрицу через S p 1 , увеличиваем p на 1 и переходим к шагу 2.При решении ряда задач нередко необходимо выяснить, есть ли контуры в заданном орграфе. Заметим, что если в орграфе D присутствует некоторый контур, то всевершины, входящие в этот контур, взаимно достижимы и поэтому принадлежат однойкомпоненте сильной связности орграфа D, а следовательно, эта компонента будет содержать более одной вершины. Заметим также, что если некоторая компонента сильной связности орграфа D содержит более одной вершины, то в этой компоненте, а следовательно,и в самом орграфе D обязательно присутствует контур. Таким образом, справедливоУтверждение 2.6. Для того чтобы орграф D имел хотя бы один контур, необходимо и достаточно, чтобы он имел хотя бы одну компоненту сильной связности, содержащую более одной вершины или (что то же самое), чтобы матрица S (D) была отлична отединичной матрицы E.Иногда вопрос стоит так.

В случае, когда орграф D имеет контуры, определить,какую минимальную длину имеют эти контуры. Для решения этой задачи снова воспользуемся утверждением 2.2, следствием которого являетсяУтверждение 2.7. Для того, чтобы орграф D с матрицей смежности A  A(D)имел контур минимальной длины k {2,..., n( D)}, необходимо и достаточно, чтобы матри11цы A2 ,..., Ak 1 имели только нулевые диагональные элементы, а матрица Ak имела ненулевые диагональные элементы.Пусть D  (V , X ) – орграф.

Обозначим V1  V F (V1 )  D(V1 ) \ V1. ПустьD1  (V1 , X 1 ), … , Dp  (Vp , X p ) – компоненты сильной связности орграфа D, D0  (V0 , X 0 ) –орграф конденсации орграфа D. Приведем алгоритм нахождения матрицы смежностиA0  A( D0 )  [aij(0) ], i, j {1,2,..., p}.Алгоритм 2.2Для нахождения элементов строки матрицы A0 с номером i {1,2,..., p} действуемследующим образом. Находим F (Vi )  D(Vi ) \ Vi .

Тогда aij( 0)  1  F (Vi )  V j  ,j  1,2,..., p. Множества F (Vi ) легко определяются, исходя из матрицы A(D).Пусть D  (V , X ) – орграф. Приведем также алгоритм решения задачи об оптимальном оповещении членов организации (см. тему 1) для случая, когда V – множество членоворганизации и x  (v, w)  X тогда и только тогда, когда v может передать информациюw. Этот алгоритм, в отличие от метода, приведенного в теме 1 и использующего изображение орграфа D, основан на использовании матрицы смежности A(D). В соответствии спостановкой задачи, приведенной в теме 1, требуется выделить подмножество U множества V с минимальным количеством элементов такое, что через оповещение некоторойинформацией членов из U можно добиться оповещения этой информацией всех членовиз V .

Кроме того, следует указать схему такого оповещения.Алгоритм 2.3Шаг 1. Следуя методу, приведенному в теме 1, определяем орграф конденсации1D0  (V0 , X 0 ) и выделяем множество W0  {v0 V0 | D0 (v0 )  }. Тогда искомым множест-вом U  V является множество вершин таких, что каждая вершина u U является вершиной («представителем») одной и только одной компоненты сильной связности орграфа D,принадлежащей множеству W0 . Оповещаем (требуемой информацией) всех членов из U .Полагаем U1  U , i  1.Шаг 2. Если F (U i )  , то задача решена (т.е. все члены организации оповещены). В противном случае выбираем произвольную вершину ui  F (U i ).

Ее оповещает любая вершинаиз U i  D 1 (ui ).Шаг 3. Полагаем U i 1  U  {ui }, увеличиваем i на 1 и переходим к шагу 2.Разбор типового варианта. Орграф D  (V , X ), где V  {v1 ,..., vn }, задан матрицей 0 0 0 0 1 0 0 0 0 1 1 00 0 0 0 0 1 смежности A  A(D )  . Определить: (а) матрицы T (D), S (D); (б) нали0 1 0 0 0 00 0 1 0 0 1  0 0 1 0 0 0чие контуров в D (имеются или не имеются); (в) в случае наличия контуров в D определить минимальную длину контуров; (г) количество p компонент сильной связности орг-12рафа D, матрицы смежности этих компонент, а также их изображения; (д) матрицу смежности орграфа конденсации D0 орграфа D ; (е) изображение орграфа D0 ; (ж) решить задачу об оптимальном оповещении членов организации (см. тему 1), если V – множествочленов организации и x  (v, w)  X тогда и только тогда, когда v может передать информацию w.Решение.

(а) Будем определять матрицу T (D) по формуле из утверждения 2.4 (см.также замечание 2.2, в котором T (D) определяется методом Уоршелла, т.е. по формуламиз утверждения 2.5). В соответствии с этим последовательно определяем:0 0 0 0 1 0 0 0 0 0 1 0  0 0 1 0 0 10 0 0 1 1 0 0 0 0 1 1 0  0 1 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1  0 0 1 0 0 02,A 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0  0 0 1 0 0 1  0 0 1 0 0 1   0 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 00032A  AA  00000043A  AA  000000A5  AA4  0000 0 0 1 0  00 0 1 1 0  00 0 0 0 1  01 0 0 0 0 00 1 0 0 1  00 1 0 0 0 00 0 0 1 0 00 0 1 1 0 00 0 0 0 1  01 0 0 0 0  00 1 0 0 1  00 1 0 0 0  00 0 0 1 0  00 0 1 1 0  00 0 0 0 1  01 0 0 0 0 00 1 0 0 1  00 1 0 0 0 00 1 0 0 1  01 1 0 0 1  0 0 1 0 0 0 00 0 1 1 0  0 0 1 0 0 1  00 0 0 0 1  00 1 0 0 1  00 1 1 1 1  0 0 0 0 0 1  01 1 0 0 1  0 0 1 0 0 1  00 1 0 0 0 00 1 0 0 1  01 1 0 0 1  0 0 1 0 0 0 00 1 1 1 1  0 0 1 0 0 1  00 0 0 0 1  00 1 0 0 10 1 1 1 10 0 0 0 1,1 1 0 0 10 1 0 0 10 1 0 0 00 1 0 0 11 1 0 0 10 1 0 0 0,0 1 1 1 10 1 0 0 10 0 0 0 10 1 0 0 10 1 1 1 10 0 0 0 1.1 1 0 0 10 1 0 0 10 1 0 0 0Замечание 2.1.

Из определения логического умножения матриц и вида матрицы Aследует, что первая строка матрицы A2 совпадает с пятой строкой матрицы A (совершенно аналогично, первая строка матрицы Ak 1 совпадает с пятой строкой матрицы Ak ,k  1,2,... ). Заметим далее, что вторая строка матрицы Ak 1 совпадает с дизъюнкцией четвертой и пятой строк матрицы Ak , а третья строка матрицы Ak 1 совпадает с шестой строкой матрицы Ak , k  1,2,... , и т.д.В силу утверждения 2.4,1310000010025T ( D)  E  A  A  ...  A  0001 00 10 0TS (D)  T (D) & [T ( D)]  0 10 00 00 0 0 0 01 0 1 0 00 1 0 0 1.

(б) В орграфе1 0 1 0 00 0 0 1 00 1 0 0 10 1 0 1 11 1 1 1 10 1 0 0 1,1 1 1 1 10 1 0 1 10 1 0 0 11 0 1 1 11 1 1 1 01 0 0 1 11 1 1 1  01 0 1 1  11 0 0 1  10 0 0 0 01 0 1 0 01 1 1 1 11 0 1 0 01 0 1 1 01 1 1 1 1 D имеются контуры, так как S ( D)  E. (в) Посколь-ку уже в матрице A 2 имеются ненулевые диагональные элементы, то в орграфе D имеется контур минимальной длины 2. (г) Используя алгоритм 2.1, последовательно определяемматрицы смежности компонент сильной связности орграфа D. Согласно алгоритму 2.1, впервую компоненту сильной связности D1 орграфа D войдет единственная вершина v1 ,т.е.

D1  (V1 , X 1 ), где V1  {v1}, X 1  . Соответствующая этой компоненте сильной связности матрица смежности имеет вид (находится на пересечении первой строки и первогостолбца матрицы A(D) )A( D1 ) v1v10.Изображение орграфа D1 приведено на рис. 2.1.Рис. 2.1Вычеркнув из матрицы S1  S ( D) первую строку и первый столбец, получаем матрицуS2 v2v3v4v5v6v210100v301001v410100v500010v60100114.Согласно алгоритму 2.1 во вторую компоненту сильной связности D2 орграфа D войдутвершины v2 , v4 , т.е. D2  (V2 , X 2 ), где V2  {v2 , v4 }. Соответствующая этой компонентесильной связности матрица смежности имеет вид (находится на пересечении второй ичетвертой строк со вторым и четвертым столбцами матрицы A(D) )A( D2 ) v2v4v201v410.Изображение орграфа D2 приведено на рис.

2.1. Вычеркнув из матрицы S 2 строки истолбцы, соответствующие вершинам v2 , v4 , получаем матрицуS3 v3v5v6v3101v5010v6101.Согласно алгоритму 2.1 в третью компоненту сильной связности D3 орграфа D войдутвершины v3 , v6 , т.е. D3  (V3 , X 3 ), где V3  {v3 , v6 }.

Соответствующая этой компонентесильной связности матрица смежности имеет вид (находится на пересечении третьей ишестой строк с третьим и шестым столбцами матрицы A(D) )A( D3 ) v3v6v301v610.Изображение орграфа D3 приведено на рис. 2.1. Вычеркнув из матрицы S 3 строки истолбцы, соответствующие вершинам v3 , v6 , получаем матрицуS4 v5v5.1Согласно алгоритму 2.1, в четвертую компоненту сильной связности D4 орграфа D войдет единственная вершина v4 , т.е. D4  (V4 , X 4 ), где V4  {v5 }, X 1  . Соответствующаяэтой компоненте сильной связности матрица смежности имеет вид (находится на пересечении четвертой строки и четвертого столбца матрицы A(D) )A( D4 ) v5v50.Изображение орграфа D4 приведено на рис. 2.1. Очевидно, что p  4, так как после исключения из S 4 строки и столбца, соответствующих вершине v5 , получаем пустую матрицу.

(д) Для нахождения матрицы A( D0 ) воспользуемся алгоритмом 2.2. В нашем при( 0)мере V1  {v1}, F (V1 )  D(V1 ) \ V1  {v5 } \ {v1}  {v5 }, v5 V4  a14(0)  1, a1 j  0, j  1, 2, 3;( 0)( 0)V2  {v2 , v4 }, F (V2 )  D(V2 ) \ V2  {v2 , v4 , v5 } \ {v2 , v4 }  {v5 }, v5 V4  a24 1, a2 j  0, j  1, 2, 3;15V3  {v3 , v6 }, F (V3 )  D(V3 ) \ V3  {v3 , v6 } \ {v3 , v6 }    a3 j  0, j  1, 2, 3, 4; V4  {v5 }, F (V4 ) ( 0)( 0) D(V4 ) \ V4  {v3 , v6 } \ {v5 }  {v3 , v6 }, v3 , v6 V3  a43  1, a4 j  0, j  1, 2, 4.

Таким образом,A( D0 ) D1D2D3D4D10001D20001D30000D40010.Рис. 2.2(д) Изображение орграфа D0 строится по матрице A( D0 ) (приведено на рис. 2.2). (е) В соответствии с алгоритмом 2.3 выделяем подмножество U множества V с минимальнымколичеством элементов такое, что через оповещение некоторой информацией членов изU можно добиться оповещения этой информацией всех членов из V .

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

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