WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 || 3 | 4 |   ...   | 6 |

называется его связный подграф, не являющийся собственПуть называется контуром, если его начальная вершиным подграфом никакого другого связного подграфа даннона совпадает с конечной вершиной.

Путь (контур), в котором все дуги различны, называет- го графа.

ся простым. Неориентированным деревом (или просто деревом) наПуть (контур), в котором все вершины, кроме первой и зывается связный граф без циклов.

последней, различны, называется элементарным.

15 Остовным деревом (деревом-остовом, покрывающим Шаг 1. В матрице расстояний просматриваем элементы деревом, скелетным деревом) связного графа G называется первой строки и выбираем минимальный элемент (например, любой его подграф, содержащий все вершины графа G и явэлемент i-го столбца). Строится ребро, соединяющее 1-ю и iляющийся деревом.

ю вершины (i1).

Шаг 2. Исключаются из рассмотрения 1-й и i-й столбцы.

2.2. Задача построения минимального Шаг 3. Найти минимальный элемент в 1-й и i-й стропокрывающего дерева ках (если минимальных элементов несколько, то выбирается Задачу построения минимального дерева-остова можно любой из них).

решить с помощью алгоритмов Краскала и Прима. Приведем Шаг 4. Шаги 2 и 3 повторяются до тех пор, пока либо в описание алгоритма Краскала по шагам [7].

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

невозможен. В первом случае минимальное покрывающее Шаг 2. Положить, что каждая вершина относится к дерево построено. Во втором случае для исходного графа несвоей компоненте связности.

возможно построить покрывающее дерево.

Шаг 3. Просмотреть ребра в «отсортированном» порядке. Для каждого ребра выполнить следующую проверку:

2.3. Задача построения кратчайшего пути а) если вершины, соединяемые данным ребром, лежат Пусть G = (Х, А) — связный граф, каждой дуге которов разных компонентах связности, то объединить эти компого приписано некоторое число а(x, y) 0. Задача построения ненты в одну, а рассматриваемое ребро добавить к минимальному дереву-остову;

кратчайшего пути между заданной парой вершин sХ и tХ б) если вершины, соединяемые данным ребром, лежат заключается в том, чтобы из множества путей, соединяющих в одной компоненте связности, то исключить ребро из расуказанные вершины, найти такой, суммарная длина дуг космотрения, так как при включении данного ребра образуется торого минимальна.

цикл.

Для решения задачи можно воспользоваться алгоритШаг 4. Если есть еще нерассмотренные ребра и не все мом Дейкстры [7]. Приведем его описание по шагам.

компоненты связности объединены в одну, то перейти к шагу Шаг 1. Перед началом выполнения алгоритма все вер3, иначе алгоритм завершает работу:

шины графа не окрашены. Каждой вершине хХ в ходе выа) если при этом просмотрены все ребра, но не все компоненты связности объединены в одну, то для исходного полнения алгоритма присваивается число d(x), равное длине графа невозможно построить покрывающее дерево;

кратчайшего пути из s в х, включающего только окрашенные б) если просмотрены все ребра, и все компоненты вершины.

связности объединены в одну, то для исходного графа поПоложить d(s)=0, d(x)= для всех х, отличных от s. Окстроено минимальное покрывающее дерево.

расить вершину s и положить y=s (y – последняя из окрашенАлгоритм Прима последовательно наращивает дерево, ных вершин).

состоящее из одной компоненты связности, по матрице расШаг 2. Для каждой неокрашенной вершины х следуюстояний. Алгоритм состоит из следующей последовательнощим образом пересчитать величину d(x):

сти действий.

d(x)=min {d(x), d(y)+a(y, x)}.

17 мый поток максимален. Все узлы сети находятся в одном из Если d(x)= для всех неокрашенных вершин х, законследующих состояний: не помечен, помечен и не просмотчить процедуру алгоритма: в заданном графе отсутствуют рен, помечен и просмотрен. Вначале все узлы не помечены.

пути между указанной парой вершин. В противном случае Операция А (процесс расстановки пометок). Источник окрасить ту из вершин x, для которой величина d(x) является s получает пометку (-, (s)=) (источник теперь помечен и наименьшей. Положить y=x.

не просмотрен, остальные узлы не помечены). Выбираем Шаг 3. Если y=t, закончить процедуру: кратчайший любой помеченный и не просмотренный узел х. Пусть он путь из вершины s в вершину t найден. В противном случае ± имеет пометку (z, (x)). Всем узлам y, которые не помечеперейти к шагу 2.

ны и для которых f(x, y) < c(x, y) приписываем пометку + 2.4. Задача построения максимального (x, (y)), где потока и минимального разреза ( y) = min[ (x), c(x, y)-f(x, y)] Для любой сети максимальная величина потока из ис(такие узлы y теперь помечены и не просмотрены). Всем узточника s в сток t равна минимальной пропускной способнолам y, которые после этого не помечены и для которых f(y, x) сти разреза, отделяющего s и t. Разрезом (X, X) в сети > 0 приписываем пометку (x, (y)), где G = (N, A), отделяющим узлы s и t, называется множество ( y) = min[ (x), f(y, x)] дуг, где s X, t X. При этом X X =, X X = N.

(такие узлы y теперь помечены и не просмотрены, а узел х Задача построения максимального потока между запосле этого помечен и просмотрен).

данной парой вершин sN и tN заключается в том, чтобы Этот общий шаг повторяем до тех пор, пока из множества путей, соединяющих указанные вершины, 1) не окажется помеченным и не просмотренным сток t, найти такие, по которым можно пропустить максимальное 2) или же до тех пор, пока нельзя будет пометить ни один количество единиц потока в единицу времени. При этом узел, а сток t не будет помечен.



должны соблюдаться следующие ограничения:

В первом случае переходим к операции В, а во втором — ал поток по каждой дуге не должен превышать ее горитм закончил работу, так как максимальный поток в сети пропускную способность;

получен.

поток из источника s равен потоку, приходящему в Операция В (изменение потока). Пусть сток t имеет сток t;

± + пометку (y, (t)). Если он имеет пометку (y, (t)), то для промежуточных вершин количество единиц потока, попавшего в этот узел, должно в точности f(y, t) заменяем на f(y, t)+(t); если он имеет пометку равняться количеству единиц потока, вышедшего (y, (t)), то f(y, t) заменяем на f(y, t)-(t). В любом из этих из этого узла.

случаев переходим к узлу y. Вообще, если узел y имеет поДля решения задачи можно воспользоваться алгорит+ метку (x, ( y)), то f(x, y) заменяем на f(x, y)+(t), а если он мом расстановки пометок Форда-Фалкерсона [12].

Алгоритм может начинать работу с нулевого потока.

имеет пометку (x, (y)), то f(x, y) заменяем на f(x, y)-(t) и Затем вычисления развиваются в виде последовательности переходим к узлу х. Когда мы достигнем источника s, изме«расстановки пометок» (операция А), каждая из которых линение потока прекращается. Нужно стереть все старые побо приводит к потоку с большей величиной (операция В), метки и вновь перейти к операции А.

либо заканчивается заключением о том, что рассматривае 19 Примечание. Пропускные способности дуг должны Пример 3. Граф G содержит 10 вершин. Расстояния между вершинами указаны на рисунке 18. Найти его минибыть целыми неотрицательными числами. В [12] приведен мальное дерево-остов, используя алгоритм Краскала.

пример с иррациональными пропускными способностями дуг. Для этого примера алгоритм не приводит к правильному решению.

2.5. Примеры решения задач Пример 2. Построить матрицы смежности и инцидентности для графа, приведенного на рисунке 15.

Решение. В соответствии с определениями матриц смежности и инцидентности матрица смежности для данного графа имеет вид как на рисунке 16, а матрица инцидентности — на рисунке 17.

Рисунок Решение. Отсортированный список ребер графа приведен в таблице 1.

Таблица Номер Номер Рисунок 15 Рисунок Ребро Вес Ребро Вес ребра ребра 1 (3, 7) 2 10 (4, 5) 2 (8, 9) 4 11 (1, 2) 3 (2, 3) 4 12 (3, 4) 4 (5, 6) 4 13 (5, 7) 5 (6, 10) 4 14 (1, 4) 6 (6, 7) 4 15 (6, 9) 7 (5, 10) 4 16 (4, 7) 8 (2, 4) 6 17 (9, 10) 9 (3, 8) 6 18 (1,5) Рисунок 21 Включаем в строящееся дерево ребро (3, 7). Обозначим множество вершин, включенных в дерево, через V1 = {3,7}.

4. Для ребра (6, 10) 10 (V1 V2 V3), 6V3. Следова1. Для ребра (8, 9) 8V1, 9V1. Следовательно, образутельно, полагаем V3 = {5,6,10}. Включаем это ребро в ем новое множество V2 = {8,9}и включаем это ребро в строящееся дерево.

строящееся дерево.

2. Для ребра (2, 3) 2 (V1 V2), 3V1. Следовательно, 5. Для ребра (6, 7) 6V3, 7 V1. Следовательно, объедиможно положить V1 = {2,3,7}. Включаем это ребро в строяняем множества V1 и V3 во множество V13 = {2,3,5,6,7,10}.

щееся дерево.

3. Для ребра (5, 6) 5,6(V1 V2). Следовательно, образуем новое множество V3 = {5,6}. Включаем это ребро в 6. Для ребра (5, 10) 5,10 V13. Поэтому ребро не вклюстроящееся дерево.

чается в строящееся дерево.

23 7. Для ребра (2, 4) 4 (V13 V2), 2V13. Поэтому полагаем V13 = {2,3,4,5,6,7,10} и включаем это ребро в строящееся дерево.

11. Так как все вершины графа вошли в дерево, то получено покрывающее дерево (дерево-остов) с минимальным весом, равным 41 (рис. 19).

8. Для ребра (3, 8) 3V13, 8V2. Поэтому объединяем множества V13 и V2 во множество V123 = {2,3,4,5,6,7,8,9,10}и включаем ребро (3, 8) в строящееся дерево.

Рисунок Пример 4. Найти минимальное дерево-остов для графа, 9. Для ребра (4, 5) 4,5 V123. Ребро не включается в приведенного на рисунке 18, с использованием алгоритма строящееся дерево.

Прима.

10. Для ребра (1, 2) 2V123, 1V123. Поэтому включаем это ребро в строящееся дерево и полагаем Решение. Для решения задачи воспользуемся элекV123 = {1,2,3,4,5,6,7,8,9,10}.

тронными таблицами MS EXCEL. Вес отсутствующих ребер будем обозначать числом 1000. Разместим данные на рабочем листе так, как на рисунке 20.

25 В ячейку Р3 (рис. 20) вводим формулу (2.1) из таблицы В столбце А, начиная с ячейки А3 (рис. 22), распо2. Для определения номера столбца, содержащего минимальлагаются номера вершин, включенных в дерево-остов. В ный элемент, вводим формулу (2.2) в диапазон Т2:АС2. Застолбец С помещаются веса ребер, добавленных в деревотем определяем номер столбца и минимальное значение по остов.

формуле (2.3), введенной в ячейку Q3. На этом этапе алгоВ таблице 3 приводятся формулы для заполнения ритма ячейка R3 заполняется вручную значением 1 – номеячеек диапазона А15:AM24. Это одна итерация алгоритма.

ром первой вершины.

Каждая итерация занимает 12 строк.

Рисунок Таблица Ячейка Формула (диапазон) Р3 =МИН(F3:O3) (2.1) Т2:АС2 {=ЕСЛИ(F3:O3=$P3;F$2:O2;100)} (2.2) Q3 =МИН(T3:AC3) (2.3) Рисунок R3, А3, D3 1 (2.4) Таблица A4 =Q3 (2.5) Ячейка Формула C3 =P3 (2.6) (диапазон) F15:O24 =ЕСЛИ((ЕОШИБКА(ВПР($E15:$E24; (2.7) СМЕЩ($A$3;0;0;(D151)*12;1);1;ЛОЖЬ)))+ (ЕОШИБКА(ВПР(F14:O14;СМЕЩ($A$ Рисунок 3;0;0;(D15-1)*12;1);1;ЛОЖЬ))=2);1000;





27 ЕСЛИ(ЕОШИБКА(ВПР($E15:$E24; (2.15) в таблице 3). Просматривая столбцы Q и R, выписыСМЕЩ($A$3;0;0;(D15-1)*12;1); ваем ребра, входящие в состав дерева-остова. Результат 1;ЛОЖЬ));1000;ЕСЛИ(ЕОШИБКА работы приведен на рисунке 24. Полностью решение зада(ВПР(F14:O14;СМЕЩ($A$3;0;0;(D15чи приведено в [21].

1)*12;1);1;ЛОЖЬ)); $F$3:$O$12; 1000))) S15:AB24 {=ЕСЛИ(F15:O24=$P15;F14:O14;1000)} (2.8) Q15 =МИН(S15:AB24) (2.9) AD15: {=ЕСЛИ($Q15=S15:AB24;$E15:$E24; (2.10) AM24 1000)} R15 {=МИН(AD15:AM24)} (2.11) D15 =D3+1 (2.12) A15 =ЕСЛИ(ЕОШИБКА(ВПР(Q15;СМЕЩ($ (2.13) A$3;0;0;(D15-1)*10;1);1;ЛОЖЬ));

Q15;R15) C15 =ВПР(Q15;$E$3:$O$12;R15+1) (2.14) С1 =ЕСЛИ(СУММ(C3:C99)>=1000; "граф (2.15) Рисунок несвязный";СУММ(C3:C99)) Пример 5. В заданном на рисунке 25 графе найти кратчайший путь между вершинами s и t.

Решение. Для решения задачи воспользуемся алгоритмом Дейкстры.

Перед началом выполнения алгоритма полагаем d(s) = 0, d(x) = для всех хs; вершина s – последняя из окрашенных вершин.

Рисунок Далее выделяем и копируем диапазон А14:АM24.

Устанавливаем курсор в ячейку А26 и вставляем фрагмент. Последовательно производим такую же вставку в ячейки А38, А50, А62, А74, А86 и А98.

Если граф не имеет покрывающего дерева, то есть является несвязным, то в сумму будут включаться значения, равные 1000. Косвенно по этому признаку можно судить о том, имеет ли граф покрывающее дерево (формула Рисунок 29 d(1) = min{d(1), d(s) + a(s,1)} = min{,0 + 2} = 2;

d(x) = x s, 1.

Так как минимум выпал на вершину 1, то y=1 – последняя из окрашенных вершин (рис. 26). На рисунках будем отмечать окрашенные вершины знаком, а вершины с оценками, меньшими, но не окрашенными - знаком.

d(2) = min{d(2), d(1) + a(1,2)} = min{,2 + 3} = 5;

d(3) = min{d(3), d(1) + a(1,3)} = min{,5 + 4} = 9;

d(x) = x s,1,2,3.

Рисунок Так как минимум выпал на вершину 2, то y=2 – последняя из окрашенных вершин (рис. 27).

d(3) = min{d(3), d(2) + a(2,3)} = min{9,5 + 2} = 7;

d(6) = min{d(6), d(2) + a(2,6)} = min{,5 +1} = 6;

d(x) = x = 4,5, t.

Так как минимум выпал на вершину 6, то y=6 – последняя из окрашенных вершин (рис. 28).

d(3) = min{d(3), d(6) + a(6,3)} = min{7,6 + } = 7;

d(4) = min{d(4), d(6) + a(6,4)} = min{,6 + 2} = 8;

d(x) = x = 5, t.

Рисунок Так как минимум выпал на вершину 3, то y=3 – последняя из окрашенных вершин (рис. 29).

Рисунок Рисунок 31 d(5) = min{d(5), d(3) + a(3,5)} = min{,7 + 4} = 11;

d(4) = min{d(4), d(3) + a(3,4)} = min{8,7 + 2} = 8;

d(t) =.

Так как минимум выпал на вершину 4, то y=4 – последняя из окрашенных вершин (рис. 30).

d(5) = min{d(5), d(4) + a(4,5)} = min{11,8 +1} = 9;

d(t) =.

Так как минимум выпал на вершину 5, то y=5 – последняя из окрашенных вершин (рис. 31).

d(t) = min{d(t), d(5) + a(5, t)} = min{,9 + 3} = 12.

Рисунок Так как минимум выпал на вершину t (нет других неокрашенных вершин), то y=t – последняя из окрашенных вершин (рис. 32). В соответствии с алгоритмом Дейкстры, получен кратчайший путь из вершины s в вершину t.

Таким образом, кратчайший путь из вершины s в вершину t проходит через промежуточные вершины 1, 2, 6, 4 и 5.

Длина этого пути равна 12.

Пример 6. Найти кратчайший путь из вершины 1 в Рисунок вершину 10 для графа, представленного на рисунке 33, используя электронные таблицы MS EXCEL [19].

Решение. В [6] приведено решение этой задачи с использованием надстройки «Поиск решения». Однако для изучения самого алгоритма имеет смысл получить формулы, реализующие шаги алгоритма Дейкстры. Разместим исходные данные для длин дуг графа так, как на рисунке 34. В этой матрице отсутствующие дуги получили длину, равную 1000.

Рисунок 33 Рисунок В ячейку О26 вводим формулу (2.18) и распространяем ее на диапазон О26:X35 (правая матрица на рисунке 35).

=ЕСЛИ(B26=$L26;B$25;1000). (2.18) В ячейку В27 вводим формулу (2.19), которая реализует основное соотношение алгоритма Дейкстры, и распространяем Рисунок ее на диапазон В27:К35.

=ЕСЛИ($M26<>$Q$2;ЕСЛИ(ЕОШИБКА(ВПР($M(2.19) 6;$A$14:$K$23;B$13+1));"";МИН(B26;$L26+ ВПР($M26;$A$14:$K$23;B$13+1)));"") В столбец М, начиная с ячейки М26, вручную вводится минимальное из чисел, получающихся в этой же строке диапазона О:Х. На рисунке 36 показан первый такой шаг:

Рисунок введено число 1. После этого автоматически в строке 27 диапазонов В:К и О:Х производится пересчет значений. Выбирая В таблице, приведенной на рисунке 35 слева, произминимум (число 2) из диапазона О27:Х27, вводим его в ячейводим вычисление оценок d(x) для всех вершин. Начальная и ку М27 (рис. 37) и т.д.

конечная вершины пути расположены в ячейках О2 и Q2 соответственно. В ячейку В26 поместим формулу (2.16) и распространим ее далее на диапазон В27:К27. В ячейку L26 поместим формулу (2.17) и распространим ее на диапазон L27:L35.

(2.16) =ЕСЛИ(B25=$O$2;0;1000) Рисунок =ЕСЛИ(ЕОШИБКА(НАИМЕНЬШИЙ(B26:K26;A (2.17) 26));"";НАИМЕНЬШИЙ(B26:K26;A26)).

Рисунок 35 На рисунке 38 приведен шаг алгоритма, когда в диапазоне О32:Х32 оказались два числа, соответствующие 6 и вершинам (у них одинаковые оценки, равные 13). В соответствии с алгоритмом Дейкстры следует выбрать любую из них.

Рисунок Рисунок Выбираем, например, вершину 6. На следующей итерации следует выбрать вершину 8 (рисунок 39). Алгоритм Рисунок 41 Рисунок заканчивает работу, когда минимум выпадает на оценку для вершины 10. Длина полученного пути равна 19.

Pages:     | 1 || 3 | 4 |   ...   | 6 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.