Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 32
Текст из файла (страница 32)
Процедура трассировки пути из узла 2 в узел 13 посредственно за узлом 1, либо непосредственно предшествует узлу й, а также другие узлы оптимального пути между 1' и й. Например, при трассировке пути из источника 2 в сток 13 с помощью матрицы узлов мы получаем информацию, содержащуюся в табл.
2.40. Отметим, что данный путь определяется однозначно. Перейдем теперь к трассировке пути нз источника 3 в сток 13. С помощью матрицы узлов мы получаем информацию, содержащуюся в табл. 2.41. После небольшой тренировки читатель без труда справится с построением оптимального решения. В данном примере описана основная процедура поиска всех видов решений. Таблица 2.41. Процедура трассировки пути из узла 3 в узел 13 2.17.
ПОВРЕЖДЕНИЯ УЗЛОВ И ДУГ В СЕТЯХ Очевидно, что с помощью сетей может быть описан широкий круг физических, экономических и управляющих систем. Большинство систем, рассмотренных выше, было связано с решением физических или экономических задач. Однако сетевой анализ может также играть большую роль при изучении управляю1цнх систем и описании их характеристик. Ниже мы рассмотрим задачи, связанные с управляющими системами. В этих задачах изучается возможность систем эффективно ра- Детерминированнме нагони в сетях 201 ботать, или функционировать, после того, как одна или несколько компонент сети (узлы и дуги) будут «повреждены».
Напомним, что сеть называется связной, если для каждой пары узлов существует по крайней мере один путь, соединяющий их. В противном случае сеть называется несвязной. Для того чтобы определить характер задач, которые мы хотим рассмотреть, необходимо точно указать, как оеарактернстики оперирующих систем связаны с процессом построения сетей.
Сеть является несвязной, когда не для каждой пары узлов существует путь, соединяющий их. Отметим, что удаление одной илн нескольких дуг может не привести к разрыву сети. Однако при последовательном удалении дуг, выбираемых произвольным образом, в конце концов сеть будет разорвана. Часто интерес представляет только вопрос о том, можно ли конечное множество узлов разъединить путем удаления дуг. Такой разрыв будем называть частичным разрывом и будем определять его только для двух или более узлов.
Другой важной задачей, связанной с определением условий возникновения частичного разрыва, является задача нахождения числа узлов, удаление которых из сети приведет к тому, что не для каждой пары узлов будет существовать соединяющий нх путь. Детальное изучение этой задачи было проведено Фрэнком и Фришем ,'18, 36], а также Клейтманом 136]. Последующий материал основан на их работах. Первая задача, которую мы рассмотрим, состоит в нахождении минимального числа ветвей, удаление которых приводит к разрыву сети. Мы воспользуемся следующей теоремой, доказанной Фрэнком и Фрншем [36]. Теорема. Если каждой ветви связной сети приписать пропускную способность, равную 1, то максимальный поток между каждой парой узлов сети равен минимальному числу ветвей, удаление которых приводит к разрыву всех путей нз одного узла к другому.
Иными словами, данная теорема утверждает, что если пропускные способности всех дуг полагаются равными 1, то максимальный поток между каждой парой узлов равен числу путей между этими узлами, не содержащих общих дуг. Следовательно, если для каждой пары узлов найдена величина максимального потока между этими узлами, то число ветвей, удаление которых приводит к разрыву сети, равно минимуму среди всех величин максимальных потоков. Отметим, что если при выполнении вычислений будет использоваться алгоритм, описанный в равд. 2.15, то расчеты упростятся в результате полу' чения всех частичных разрывов между всеми парами узлов. Вторая задача, которую мы рассмотрим в данном разделе, состоит в нахождении минимального числа узлов, удаление ко.
202 Глава 2 торых из сети приведет к разъединению всех пар ее узлов. Данная задача может быть решена с помощью алгоритма, ана; логичного тому, который описан в равд. 2.5. Выберем в качестве источника произвольный узел 1, а в качестве стока — произвольный узел 1. Предположим, что пропускная способность каждого узла равна 1. Эта величина соответствует штрафу за выполнение поворота, определенному для каждого узла в алгоритме из равд.
2.5. В рассматриваемом нами случае метка, приписанная каждой дуге фиктивной сети, равна 1. Будем рассматривать величину этой метки как пропускную способность. Далее, определим максимальный поток из фиктивного источника в фиктивный сток. Величина данного потока равна максимальному числу путей в исходной сети, не имеющих общих узлов, за исключением источника и стока. Эти пути будем называть путями, не пересекающимися по узлам. Данная процедура выполняется для всех пар узлов сети. Число узлов, удаление которых приведет к разрыву сети, равно минимуму среди всех величин максимальных потоков.
Хотя приведенная выше процедура позволяет находить точное решение, при большом числе узлов она является очень громоздкой. Например, для того чтобы определить, приведет ли удаление не более четырех узлов сети, содержащей 1000 узлов, к полному ее разрыву, необходимо решить свыше 500000 задач о максимальном потоке. Такие вычисления встречаются при решении задач небольшой размерности, связанных с распределением электроэнергии, в которых узлы представляют места соединений линий электропередач. Очевидно, что для решения практических задач нужен эффективный алгоритм. Клейтман [361 показал, что для решения описанной выше задачи достаточно решить не более 4000 задач о максимальном потоке с использованием следующей процедуры.
Выберем произвольный узел сети и убедимся, что максимальный поток из этого узла в любой другой узел сети составляет не менее 4 единиц. Если это так, то удалим нз сети данный узел и все соединенные с ним ветви. Выберем одни из узлов в полученной редуцированной сети и убедимся, что между этим узлом и всеми другими узлами редуцированной сети существует поток величиной не менее 3 единиц.
Удалим из сети этот узел и соединенные с ним дуги и проверим, что между произвольно выбранным узлом полученной сети и каждым из оставшихся узлов существует поток величиной не менее 2 единиц. Выбирая четвертый узел (предварительно исключив соответствующий узел и соединенные с ним дуги), проверим, существует ли между этим узлом и всеми остальными узлами поток величиной в 1 единицу. Отметим, что при выполнении данной процедуры на каждом ее шаге между (произвольным) детерминированные потоки е сетях источником и всеми остальными узлами строится некоторое количество путей, не пересекающихся по узлам.
Если данную последовательность операций выполнить нельзя, то сеть будет разорвана в результате удаления из нее менее четырех узлов. Рпс. 2.61а. Пример сети я задаче о разрыве сетей. Рпе. 2.616, Сеть после удалеяяя узла тт. Ряс. 2.61в. Сеть после удалеяяя узлов 6 а А. Например, если было найдено только два не пересекающихь. по узлам пути, то на предпоследнем шаге процедуры не существовало бы требуемого потока. Обычно данная процедура является очень аффективной, поскольку на каждом ее шаге из исходной сети удаляется один узел и, возможно, большое число дуг.
Работа данной процедуры показана на следующем примере. Рассмотрим сеть, состоящую из 8 узлов и 16 дуг (рис. 2.61а). Определим, будет ли сеть разорвана в результате удаления пяти или менее дуг. Глава 2 Шаг 1. Выбрать произвольный узел, например узел б. Можно показать, что между узлом 6 и любым другим узлом расположено не менее пяти путей, не пересекающихся по узлам. Шаг 2.
Исключить узел б и все соединенные с ним дуги. Редуцированная сеть изображена на рис. 2.616. Выбрать произвольный узел, например узел А. Можно показать, что между Рис. 2.6!г. Сеть после удалеиия узлов б, А и В. Рис. 2.61д. Сеть после удалеиия узлов О, А, В и С. узлом А и каждым из остальных узлов существует по крайней мере четыре пути, не пересекающихся по узлам.
Шаг 3. Удалить узел А и все соединенные с ним дуги. Образованная в результате такой редукции сеть изображена на рис. 2.61в. Выбрать произвольный узел, например узел В. Можно показать, что между узлом В и каждым из остальных узлов существует по крайней мере три пути, не пересекающихся по узлам. Шаг 4. Удалить узел В и все соединенные с ним дуги. Образованная в результате такой редукции сеть изображена на рис. 2.61г. Выбрать произвольный узел, например узел С. Можно показать, что между узлом С и каждым из остальных узлов существует не менее двух путей, не пересекающихся по узлам. Шаг 5.
Удалить увел С и все соединенные с ннм дуги. В результате итого образуется сеть, изображенная на рис. 2.61д. Отметим, что в сети, изображенной на рнс. 2.61д, число путей, не пересекающихся по узлам, равно единице. Поскольку на шаге 5 процедура завершается, принятая гипотеза верна. Дегвриинировиннив патоки в сетях УПРАЖНЕНИЯ 1. Показать, как метод Дейкстры может быть использован для построения древовндяостн с заданным корнем. 2. Следует лн заново начать решение задачи, если на одной нз промежуточных нтерацнй прн определенна постоянной пометки была допущена ошибка, которая не была обнаружена до завершения решения задачи? 3.
В изображенной ниже сети найти кратчайший путь нз узла 1 в узел 4: (а) простым перебором; (б) с помощью метода Дейкстры. Почему втн два решения разлнчаются? 4. Привести несколько примеров практического использования задач о путн максимальной дликы. Указать условия, прн выполнения которых задача о пути максимальной длины может быть сведена к эквивалентной задаче о кратчайшем путн. 3. Прн работе каких алгоритмов о кратчайшем пути нз числа описанных в кастоящей главе вначале определяются длины путей, а затем используются процедуры трасснровкн для нахождения самих путей? В чем пренмущество таких алгоритмов по сравнению с алгорнтмамн, в которых длины путей н сами пути определяются одновременно? 6.
В настоящей главе был описан вариант метода Дейкстры, в котором предполагается, что все параметры дуг неотрицательные. Моднфнцнровать данный алгоритм таким образом, чтобы он был применим к сетям, содержазцим дуги с отрицательными .параметрами. Какое условие в данном случае имеет решающее значенне? 7. Обьяснить, почему чнсло итераций в алгоритме Флойда равно числу узлов сети.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
