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

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

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

3.1. Найти все минимальные пути из v1 в v10 .v1v2v3v4v5v6v7v8v9v10v10001101000v21010101101v30101110011v41000010100v51000010100v60101100110v71000100010v80111011000v91010101100v100110011010Табл.3.1Решение. Действуя согласно алгоритму 3.2, последовательно определяем:FW0 (v1 )  {v1}, FW1 (v1 )  D(v1 )  {v4 , v5 , v7 },FW2 (v1 )  D( FW1 (v1 )) \ ( FW0 (v1 )  FW1 (v1 ))  D({v4 , v5 , v7 }) \ {v1 , v4 , v5 , v7 }  {v1 , v5 , v6 , v8 , v9 }) \ {v1 , v4 , v5 , v7 }  {v6 , v8 , v9 },FW3 (v1 )  D( FW2 (v1 )) \ ( FW0 (v1 )  FW1 (v1 )  FW2 (v1 ))  D({v6 , v8 , v9 }) \\ {v1 , v4 , v5 , v6 , v7 , v8 , v9 }  {v1 , v2 , v3 , v4 , v5 , v6 , v7 , v8 , v9 } \ {v1 , v4 , v5 , v6 , v7 , v8 , v9 }  {v2 , v3 },20FW4 (v1 )  D( FW3 (v1 )) \ ( FW0 (v1 )  FW1 (v1 )  FW2 (v1 )  FW3 (v1 ))  D({v2 , v3}) \ {v1, v2 , v3 , v4 , v5 , v6 , v7 , v8 , v9}  {v1 , v2 , v3 , v4 , v5 , v6 , v7 , v8 , v9 , v10} \\ {v1 , v2 , v3 , v4 , v5 , v6 , v7 , v8 , v9 }  {v10}.Таким образом, v10  FW4 (v1 ), а следовательно, согласно алгоритму 3.2 существуетминимальный путь в орграфе D из v1 в v10 длины 4.

Найдем все эти пути. На рис. 3.2изображен подграф D орграфа D, на котором последовательно изображены множестваFWk (v1 ), k  0, 1, 2, 3, 4, а также дуги вида (v, v), где для некоторого k {0, 1, 2, 3}v  FWk (v1 ), v  FWk 1 (v1 ), т.е. исходящие из вершин некоторого k -го фронта волны и за-ходящие в вершины следующего (k  1) -го фронта волны.Рис. 3.2Используя изображение D, нетрудно выделить все минимальные пути из v1 в v10в орграфе D. При этом, следуя (3.1), находим эти минимальные пути, используя орграфD, но двигаясь в D в обратной последовательности (т.е. не из v1 в v10 , а наоборот, из v10в v1 ). Используя рис. 3.2, получаем, что в любом минимальном пути из v1 в v10 соблюдается следующая последовательность вершин.

Вершиной, предшествующей вершине v10 ,может быть любая из вершин v2 , v3 . Вершиной, предшествующей вершине v2 , может бытьлюбая из вершин v6 , v8 , а вершиной, предшествующей вершине v3 , – любая из вершинv8 ,v9 и т.д. Этими условиями однозначно определяется множество минимальных путей изv1 в v10 , которое компактно изображено на рис. 3.3. На этом рисунке изображены всевершины, входящие в минимальные пути из v1 в v10 . Для каждой из промежуточных вершин v показано множество вершин, которые могут ей предшествовать, а также соответствующие дуги (исходящие из вершин, предшествующих v, и заходящие в v ).

Из рис. 3.3видно, что всего существует семь минимальных путей из v1 в v10 одним из которых является v1v4 v6 v2 v10.21Рис. 3.3Поиск минимальных путей (маршрутов) в нагруженных орграфах (графах).Назовем орграф D  (V , X ) нагруженным, если на множестве дуг X определена некоторая функция l : X  R. Тем самым в нагруженном орграфе D каждой дуге x  X поставлено в соответствие некоторое действительное число l (x ) – длина дуги x. Для любого пути  нагруженного орграфа D обозначим через l ( ) сумму длин входящих в  дуг; приэтом каждая дуга учитывается столько раз, сколько она входит в этот путь. Будем называть l ( ) длиной пути  .

Путь в нагруженном орграфе D из вершины v в вершину w,где v, w V , называется минимальным, если он имеет минимальную длину среди всех путей орграфа D из v в w.Пусть D  (V , X ) – нагруженный орграф, V  {v1 ,..., vn }, n  2. Опишем метод Форда – Беллмана поиска минимальных путей из начальной вершины v1 в вершиныvi , i  2,..., n (если таковые пути существуют). Если в орграфе существует хотя бы одинконтур отрицательной длины, то в нем может не существовать путь минимальной длиныиз некоторой вершины в некоторую другую вершину.Пример 3.1. Рассмотрим нагруженный орграф D, изображенный на рис.

3.4 (околокаждой дуги указана ее длина). В этом орграфе не существует минимального пути из v1 вv4 , поскольку в нем существует контур   v2 v3v2 длины –1. Действительно,l (v1v2 v4 )  3, l (v1v4 )  2, l (v1 v4 )  1, ... , l (v1... v4 )  3  k , k  0,1,... .kРис. 3.422Будем для простоты считать, что все дуги в орграфе D неотрицательны. В этом)случае в D отсутствуют контуры отрицательной длины. Введем величины (ki , где(k )i  1,2,..., n, k  1,2,... .

Для каждых фиксированных i и k величина i равна длине ми-нимального пути среди всех путей орграфа D из v1 в vi , содержащих не более k дуг; ес)  (здесь и далее под  понимается   ). Кроме того, если же таких путей нет, то (kiли произвольную вершину v V считать путем из v в v нулевой длины, то величины(ki ) можно ввести также и для k  0, и при этом1( 0)  0, (i 0)  , i  2,..., n.(3.2)Поскольку по предположению в D отсутствуют контуры отрицательной длины, то(3.3)1( k )  0, k  0,1,...

.Введем также в рассмотрение квадратную матрицу C ( D)  [cij ] порядка n с элементамиcij  l (vi , v j ), если (vi , v j )  X , и cij   – в противном случае, которую будем называтьматрицей длин дуг нагруженного орграфа D .Справедливы следующие утверждения.Утверждение 3.1. При j  2,..., n, k  0,1,... выполняется равенство(jk 1)  min{(i k )  cij }.(3.4)1i  nУтверждение 3.2. Если i {2,..., n}, (i n1)   , то вершина vi не достижима из v1 .

Впротивном случае vi достижима из v1 и (i n 1) – длина минимального пути из v1 в vi .Таким образом, по величинам (2n 1) ,…, (nn 1) можно судить о достижимости вершин v2 ,..., vn из v1 , а также определять длины минимальных путей из v1 во все достижимые вершины. Кроме того, по таблице (i j ) , i  1,2,..., n, j  0,1,..., n  1, можно определятьминимальные пути из v1 во все достижимые вершины.

При этом, как и в алгоритме«фронта волны», двигаемся в обратной последовательности, т.е. из некоторой заданнойвершины vi с (i n1)  , где i {2,..., n}, в исходную вершину v1 , после чего восстанавливаем истинную последовательность вершин. Сначала определяем минимальный номер k 0 ,(k )при котором i 0  (i n1) .

Величина k 0 соответствует числу дуг в минимальном пути изv1 в vi . Предшествующей вершиной для vi (в минимальном пути из v1 в vi ) являетсявершина vi , для которой выполняется равенство (i k0 )  min{(ik0 1)  cii }  (i1k0 1)  ci1i . Вер1i n1шиной, предшествующей вершине vi (в минимальном пути из v1 в vi ), является вершина1vi2 , для которой выполняется равенство (i1k0 1)  min{(ik0 2)  cii1 }  (i2k0 2 )  ci2i1 и т.д. (это1i  nрассуждение основано на равенстве (3.4)).Разбор типового варианта.

Нагруженный орграф D задан матрицей длин дугC (D) (см. табл. 3.2). Найти минимальные пути из v1 во все достижимые вершины.Решение. Сначала определим таблицу величин (i j ) , i  1,2,..., n, j  0,1,..., n  1 (см.табл. 3.3), где n  7. Обозначим ( k )  (1( k ) ,..., (7k ) ) T , где k  0,1,...,6. Это столбцы в табл.233.3. Элементы (i 0) , где i  1,2,...,7, столбца ( 0) определяются согласно (3.2).

Из (3.3) следует, что первая строка таблицы 3.3 состоит из нулевых элементов.v1v2v3v4v5v6v7( 0)(1)( 2)(3)( 4)(5)( 6)v192120000000v21124105555v32112999666v41115555v512233333v618222222v72112121010988Табл. 3.2Табл. 3.3Далее, используя утверждение 3.1, последовательно определяем (согласно формуле(3.4)) элементы столбца (1) , используя элементы столбца ( 0) (а также элементы матрицыC (D) ), затем находим элементы столбца ( 2) , используя элементы столбца (1) и т.д.

Например, (23)  min{(i 2)  ci 2 }  5, поскольку при сложении соответствующих столбцов1i  7имеем (см. табл. 3.4):( 2)v211220= 10= 9= 10= 3=52= 10= 12Табл. 3.4и число 5 является минимальным элементом в последнем столбце этой таблицы (выделеножирным шрифтом).Длина минимального пути из v1 в v 7 равна 8 (см. утверждение 3.2). В таблице 3.3+++++++жирным шрифтом указаны величины, по которым последовательно находятся вершины в(k )минимальном пути из v1 в v7 . Минимальное число k 0 , при котором 7 0  8, равно 5, по-этому выделена величина (75)  8 . Вершиной, предшествующей v7 (в минимальном путииз v1 в v 7 ) является вершина v3 , поскольку (75)  8  min{(i 4)  ci 7 }  (34)  c37  6  21i 7(вершина v 3 находится в первом столбце табл.

3.2, в котором перечисляются вершиныорграфа D, напротив выделенного числа 6  (34 ) ). Вершиной, предшествующей v3 , является v 4 (вершина v 4 находится в первом столбце табл. 3.2 напротив выделенного числа5  (43) ) и т.д. Таким образом, минимальным путем из v1 в v 7 является v1v6 v5v4 v3v7 (см.24последовательность выделенных элементов в табл. 3.3).

Соответственно v1v6 v5v4 v3 ,v1v6 v5 v4 , v1v6 v5 , v1v6 – минимальные пути из v1 в соответствующие вершины. Минималь-ный путь из v1 в v 2 находится аналогично. Его длина равна 5. Минимальное число k 0 ,при котором (2k0 )  5, равно 3. Вершиной, предшествующей v2 , является вершина v5 ,поскольку (23)  5 min{(i 2)  ci 2 }  (52)  c52  2  3. Далее, как было показано ранее, вер1i 7шиной, предшествующей v5 , является вершина v6 , а вершиной, предшествующей вершине v6 , является вершина v1 .

Таким образом, минимальным путем из v1 в v 2 являетсяv1v6 v5v2 .Тема 4. Деревья и циклыГраф G называется деревом, если он связен и не имеет циклов.Пример 4.1. Граф G , изображенный на рис. 4.1, является деревом.Рис. 4.1Свойства деревьев. Следующие утверждения эквивалентны:(1) Граф G есть дерево.(2) Граф G является связным и не имеет простых циклов.(3) Граф G является связным и число его ребер ровно на 1 меньше числа вершин.(4) Любые две различные вершины графа G можно соединить единственной (ипритом простой) цепью.(5) Граф G не содержит циклов, но, добавляя к нему любое новое ребро, получимровно один (с точностью до направления обхода и выбора начальной вершины обхода) ипритом простой цикл (проходящий через добавляемое ребро).Остовное дерево связного графа.

Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.Пусть G – связный граф. Тогда, в силу свойства (3), остовное дерево графа G (еслионо существует) должно содержать n(G)  1 ребер. Таким образом, любое остовное дерево связного графа G есть результат удаления из G ровно m(G)  (n(G)  1)  m(G)  n(G)  1 ребер. Это число называется цикломатическим числом связного графаG и обозначается через  (G). Покажем существование остовного дерева для произвольного связного графа G , описав алгоритм его выделения.Алгоритм 4.1Шаг 1.

Выбираем в G произвольную вершину u1 , которая образует подграф G1 графаG , являющийся деревом. Полагаем i  1.25Шаг 2. Если i  n  n(G), то задача решена и Gi – искомое остовное дерево графа G. Впротивном случае переходим к шагу 3.Шаг 3. Пусть уже построено дерево Gi , являющееся подграфом графа G и содержащеевершины u1 ,..., ui , где 1  i  n 1. Строим граф Gi 1 , добавляя к графу Gi новую вершинуui 1 V , смежную в G с некоторой вершиной u j графа Gi и новое ребро {u j , ui 1} (в силусвязности G и того, что i  n, указанная вершина ui 1 обязательно найдется).

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

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