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

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

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

Для решения этойзадачи рассматриваем орграф конденсации D0  (V0 , X 0 ) и выделяем множество W0  {v0 V0 | D01 (v0 )  } (множество вершин с нулевыми столбцами в A( D0 ) ). Тогда искомым множеством U  V является множество вершин таких, что каждая вершина u Uявляется вершиной («представителем») одной и только одной компоненты сильной связности орграфа D, принадлежащей множеству W0 .

Заметим, что W0  {D1 , D2 } (см. рис.2.2), v1  D1 , v2  D2 (см. рис. 2.1), поэтому полагаем U  {v1 , v2 }. Следуя алгоритму 2.3,далее полагаем U1  U  {v1 , v2 }. Используя матрицу A(D), находим множествоF (U1 )  D(U1 ) \ U1  D({v1 , v2 }) \ {v1 , v2 }  {v4 , v5 } \ {v1 , v2 }  {v4 , v5 }и выбираем из него произвольную вершину, например, v4 , т.е. полагаем u1  v4 . Далее находим множество U1  D 1 (u1 )  U  D 1 (v4 )  {v1 , v2 } {v2 }  {v2 }. Единственная вершинаэтого множества v2 оповещает v4 (кратко пишем: v2  v4 ).

Далее полагаем U 2  U1  {u1}  {v1 , v2 , v4 }, находим множествоF (U 2 )  D(U 2 ) \ U 2  D({v1 , v2 , v4 }) \ {v1 , v2 , v4 }  {v2 , v4 , v5 } \ {v1 , v2 , v4 }  {v5 },содержащее единственную вершину v5 и полагаем u2  v5 . Находим множество1U 2  D 1 (u2 )  U 2  D (v5 )  {v1 , v2 , v4 }  {v1 , v2 }  {v1 , v2 }, выбираем из него произвольнуювершину, например, v1 . Тогда v1  v5 .

Далее полагаем U 3  U 2  {u2 }  {v1 , v2 , v4 , v5 }, находим множествоF (U 3 )  D(U 3 ) \ U 3  D({v1 , v2 , v4 , v5 }) \ {v1 , v2 , v4 , v5 }  {v2 , v3 , v4 , v5 , v6 } \ {v1 , v2 , v4 , v5 }  {v3 , v6 },и выбираем из него произвольную вершину, например, v3 , т.е. полагаем u3  v3 . Находиммножество U 3  D 1 (u3 )  U 3  D 1 (v3 )  {v1 , v2 , v4 , v5 } {v5 , v6 }  {v5 }, содержащее единст16венную вершину v5 . Тогда v5  v3 .

Далее полагаем U 4  U 3  {u3}  {v1 , v2 , v3 , v4 , v5 }, находим множествоF (U 4 )  D(U 4 ) \ U 4  D({v1 , v2 , v3 , v4 , v5 }) \ {v1 , v2 , v3 , v4 , v5 }  {v2 , v3 , v4 , v5 , v6 } \ {v1 , v2 , v3 , v4 , v5 }  {v6 },и полагаем u4  v6 . Находим множество U 4  D 1 (u4 )  U 4  D 1 (v6 )  {v1 , v2 , v3 , v4 , v5 } {v3 , v5 }  {v3 , v5 }, выбираем из него произвольную вершину, например, v3 .

Тогда v3  v6 .Далее полагаем U 5  U 4  {u4 }  {v1 , v2 , v3 , v4 , v5 , v6 }, находим множество F (U 5 )  D(U 5 ) \ U 5  , а это согласно алгоритму 2.3 (см. шаг 2), означает, что схема оповеще-ния построена. А именно, вначале оповещаются v1 , v2 , а затем v2  v4 , v1  v5  v3  v6 .Замечание 2.2.

При решении задачи из типового варианта нахождение T (D), S (D)производилось по формулам из утверждения 2.4. Найдем также эти матрицы методомУоршелла (см. утверждение 2.5). Введем в рассмотрение вспомогательную квадратную(l )(l )матрицу Bˆ  [bˆ ] порядка n с элементами bˆ (l )  b(l 1) & b(l 1) , где l  1,2,..., n.

Тогда (см.ijijматрицы B (l 1)illj Bˆ . Из определения матрицы Bˆ (l ) следует, что l – ая строкаповторяется во всех строках матрицы Bˆ (l ) с номерами i {1,2,..., n}, для ко-утверждение 2.5) B  B(l )( l 1)(l )торых bil(l 1)  1, т.е., если матрицы B (l 1) , Bˆ (l ) стоят рядом, то l – ая строка матрицы B (l 1)находится в матрице Bˆ (l ) напротив всех единиц l – го столбца матрицы B (l 1) . Остальныестроки матрицы Bˆ (l ) являются нулевыми. Далее в соответствующих таблицах единицы l –ой строки, l – го столбца матрицы B (l 1) , а также единицы матрицы Bˆ (l ) будут выделеныжирным шрифтом, где l  1,2,...,6. Действуя таким образом, получаем:100(0)B  A E  000100(1)( 0)(1)B  B  Bˆ  000100B ( 2)  B (1)  Bˆ ( 2 )  0000 0 0 1 01 0 1 1 00 1 0 0 1,1 0 1 0 00 1 0 1 10 1 0 0 10 0 0 1 0 11 0 1 1 0 00 1 0 0 1  01 0 1 0 0  0 0 1 0 1 1  00 1 0 0 1 00 0 0 1 0  01 0 1 1 0 00 1 0 0 1  01 0 1 0 0  0 0 1 0 1 1  00 1 0 0 1 0170 0 0 1 00 0 0 0 00 0 0 0 0 B ( 0) ,0 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 0 11 0 1 1 0 00 0 0 0 0  01 0 1 1 0  0 0 0 0 0 0  00 0 0 0 0 00 0 0 1 01 0 1 1 00 1 0 0 1,1 0 1 1 00 1 0 1 10 1 0 0 1100( 3)( 2)(3)B  B  Bˆ  000100( 4)( 3)(4)B  B  Bˆ  0000 0 0 1 0  01 0 1 1 0 00 1 0 0 1  01 0 1 1 0  0 0 1 0 1 1  00 1 0 0 1 00 0 0 1 0 01 0 1 1 0 00 1 0 0 1 01 0 1 1 0 0 0 1 0 1 1 00 1 0 0 1 00 0 0 0 00 0 0 0 00 1 0 0 1 B ( 2) ,0 0 0 0 00 1 0 0 10 1 0 0 1B (5)  B ( 4)  Bˆ (5)1000000 0 0 1 0  01 0 1 1 0 00 1 0 0 1  01 0 1 1 0  0 0 1 0 1 1  00 1 0 0 1 00 1 0 1 1 10 1 0 1 1 00 0 0 0 0  00 1 0 1 1  0 0 1 0 1 1  00 0 0 0 0 0B ( 6)  B (5)  Bˆ ( 6 )1000000 1 0 1 1 01 1 1 1 1 00 1 0 0 1 01 1 1 1 1 0 0 1 0 1 1 00 1 0 0 1 00 1 0 0 10 1 0 0 10 1 0 0 1 B ( 5) .0 1 0 0 10 1 0 0 10 1 0 0 10 0 0 0 01 0 1 1 00 0 0 0 0 B ( 3) ,1 0 1 1 00 0 0 0 00 0 0 0 0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В силу утверждения 2.5 T ( D)  B (6) , S (D) находится из T (D) аналогично предыдущему.Тема 3.

Поиск маршрутов (путей) в графах (орграфах)Задача о лабиринте. Опишем метод поиска маршрута в связном графе G  (V , X ),соединяющим заданные вершины v, w V , v  w.Алгоритм 3.1 (Тэрри) поиска маршрута в связном графеЕсли, исходя из вершины v и осуществляя последовательный переход от каждойдостигнутой вершины к смежной ей вершине, руководствоваться следующими правилами: (1) идя по произвольному ребру, всякий раз отмечать направление, по которому онопройдено; (2) исходя из некоторой вершины v, всегда следовать по тому ребру, котороене было пройдено или было пройдено в противоположном направлении; (3) для всякойвершины v, отличной от v, отмечать первое заходящее в v  ребро, если вершина v встречается в первый раз; (4) исходя из некоторой вершины v, отличной от v, по первомузаходящему в v  ребру идти лишь тогда, когда нет других возможностей, то всегда можнонайти маршрут в связном графе G , соединяющий v, w.18Замечание 3.1.

Задача, которую решает алгоритм Тэрри, нередко называют задачей о лабиринте. Здесь v – начальная точка поиска, w – выход из лабиринта.Замечание 3.2. Алгоритм Тэрри позволяет избежать повторного прохождения ребер в одном направлении. Если конец маршрута не задан, то, проводя поиск согласно алгоритму Тэрри, пока это возможно, мы найдем замкнутый маршрут, проходящий ровно подва раза (по разу в каждом направлении) по каждому ребру связного графа G.Задача о поливочной машине. Пусть граф G соответствует схеме дорог некоторого района, которые нужно полить летом водой (соответственно посыпать песком зимой)с двух сторон (дорожки с двухсторонним движением).

Вершина v1 соответствует базе, гдемашина заправляется водой и бензином и куда она возвращается после полива дорожек. Всилу замечания 3.2, алгоритм Тэрри дает оптимальное решение этой задачи (минимальный расход бензина и воды), поскольку каждая дорожка поливается ровно по разу в каждом направлении.Разбор типового варианта. Решить задачу о поливочной машине, если схема дорог описывается графом G  (V , X ), V  {v1 ,..., v7 }, изображенным на рис.

3.1 (см. замечание 1.1), т.е. требуется указать маршрут, обеспечивающий полный обход всех вершин иребер графа G, начиная из вершины v1 и заканчивая в этой же вершине. При этом каждоеребро должно быть пройдено по разу в каждом направлении.Решение. Для решения этой задачи действуем в соответствии с алгоритмом Тэрри(см. замечание 3.2). Для реализации алгоритма помечаем первые заходящие в вершиныребра крестиками, которые наносим на ребрах ближе к той вершине в которую в первыйраз заходим, а также указываем направления прохождения ребер и последовательностьпрохождения ребер. Алгоритм 3.1 дает следующий возможный маршрут (см. рис.

3.1)v1v3v2 v1v2 v3v4 v5v7 v4 v6 v7 v6 v4 v7 v5v4 v3v1 (см. замечание 1.2).Рис 3.1Поиск минимальных путей в орграфах. Алгоритм «фронта волны». Путь ворграфе D из вершины v в вершину w, где w  v, называется минимальным, если он имеет минимальную длину среди всех путей орграфа D из v в w. Аналогично определяетсяминимальный маршрут в графе G. Пусть D  (V , X ) – орграф с n  2 вершинами, v, w –заданные вершины из V , v  w. Опишем алгоритм фронта волны поиска минимальногопути из v в w в орграфе D.Алгоритм 3.2 (фронта волны)Шаг 1. Помечаем вершину v индексом 0, а все вершины, принадлежащие образу вершиныv, индексом 1.

Обозначим через FW0 (v), FW1 (v) – множества вершин, помеченных индексами 0 и 1, соответственно, т.е. FW0 (v)  {v}, FW1 (v)  D(v). Полагаем k  1.19Шаг 2. Если FWk (v)  , то вершина w не достижима из v и работа алгоритма на этомзаканчивается. В противном случае переходим к шагу 3.Шаг 3. Если w  FWk (v), то переходим к шагу 4. В противном случае существует минимальный путь из v в w, имеющий длину k . Последовательность его вершин vw1...wk 1w,гдеwk 1  FWk 1 (v)  D 1 ( w), wk 2  FWk 2 (v)  D 1 ( wk 1 ), … , w1  FW1 (v)  D 1 ( w2 ),(3.1)и есть искомый минимальный путь из v в w длины k . На этом работа алгоритма заканчивается.Шаг 4.

Помечаем индексом k  1 все непомеченные вершины, принадлежащие образумножества вершин, помеченных индексом k . Множество вершин, помеченных индексомkk  1, обозначаем FWk 1 (v), т.е. FWk 1 (v)  D( FWk (v)) \  FWi (v). Увеличиваем k на 1 и пеi 0реходим к шагу 2.Замечание 3.3. Множество FWk (v) будем называть фронтом волны k -го уровня сцентром в вершине v.Замечание 3.4.

Вершины w1 ,..., wk 1 из (3.1), вообще говоря, могут быть выделенынеоднозначно, что говорит о возможности существования нескольких различных минимальных путей из v в w.Замечание 3.5. Аналогично описывается алгоритм поиска минимальных маршрутов в неориентированном графе G.Разбор типового варианта. Орграф D  (V , X ), где V  {v1 ,..., v10}, задан матрицейсмежности A(D), приведенной в табл.

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

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