Содержание к диссертации
Введение
ГЛАВА I. Эффективно разрешимые классы задач о максимальных потоках в многополюсных сетях II
1.1. Параметрические задачи о максимальном потоке II
1.2. Максимальные потоки в однородных неориентированных сетях 17
1.3. Максимальные потоки в полных псевдосимметрических сетях 25
ГЛАВА 2. Свойства матрицы максимальных потоков в полной неориентированной. сети 30
2.1. Характеристическая пропускная способность вершин неориентированной сети 30
2.2. Оптимальное распределение пропускных способностей по ребрам полной сети 41
2.3. Определение матрицы максимальных потоков полной сети при ограничениях на пропуск
ные способности ребер 49
ГЛАВА 3. Синтез сетей с заданной структурой 55
3.1. Синтез полной сети по заданной матрице требований 55
3.2. Синтез двухполюсной сети с заданным уровнем функциональной надежности 71
3.3. Приближенный метод решения задачи синтеза двухполюсной сети (ЗСДС) 81
3.4. Вопросы практического использования ЗСДС 87
Приложение 92
Литература
- Максимальные потоки в однородных неориентированных сетях
- Оптимальное распределение пропускных способностей по ребрам полной сети
- Синтез двухполюсной сети с заданным уровнем функциональной надежности
- Вопросы практического использования ЗСДС
Введение к работе
В настоящее время исследование задач теории сетей, моделирующих многочисленные практические проблемы построения связывающих сетей самого разнообразного назначения (сетей связи, электрических сетей, сетей вычислительных центров и т. д.) относится к одному из актуальных разделов математической кибернетики.
Основными математическими задачами, возникающими при проектировании оптимальных по различным критериям связывающих сетей являются [14, 27, 32] :
структурный анализ проектируемой сети;
аналитическое описание системы относительно выбранного критерия эффективности;
синтез топологической структуры с заданными стоимостными и надежностными ограничениями;
определение оптимальных по заданному критерию пропускных способностей линий связи.
Для анализа и решения этих задач широко используются [36, 40, 44] комбинаторные и теоретико-графовые подходы.
Особый как теоретический, так и практический интерес представляют задачи синтеза оптимальных по каким-либо критериям сетей. Изучению таких задач последние десять-пятнадцать лет уделяется большое внимание, о чем свидетельствует рост публикаций, посвященных как теоретическим (например, работы [13, 40, 43, 53, 76, 99 J ), так и прикладным аспектам [2, 21, 35, 36, 44, 50, 87, I07J исследования задач синтеза оптимальных сетей.
Анализ этих работ позволяет выделить два основных подхода к решению задач синтеза сетей. При первом подходе (например, в работах [7, 19, 37, 38, 58, 60, 69, 93, 94, 100, 104] ) сразу определяются структура сети и пропускные способности, обеспечивающие требуемые потоки. При этом, многие методы [71, 78, 83, 9l] строят сеть древовидной структуры (возможно [91] с дополнительным ограничением на структуру дерева). Основным критерием оптимальности при первом подходе является [7,19, 37, 38, 60, 100, 107] стоимость синтезируемой сети. Отметим, что при этом подходе обычно не учитываются надежностные характеристики сети. Практические проблемы построения надежных сетей обуславливают необходимость развития методов анализа и синтеза сетей с заданным уровнем надежности. При разработке математических методов решения этих задач надежность тршстуется как устойчивость функционирования сети при изменении ее параметров. Второй подход к исследованию задач синтеза сетей состоит [8,36,82] в решении задачи в два этапа: сначала находится структура, отвечающая заданным надежностным и стоимостным характеристикам, и затем определяются оптимальные по выбранному критерию пропускные способности. На первом этапе широко используются строгие математические методы (см., например, [б, 40, 53, 55, 56, 74j ). Задачи нахождения пропускных способностей в основном [ТО, 29, 32, 35, Зб] решаются на содержательном уровне. Вместе с тем разработка математически обоснованных методов выбора оптимальных пропускных способностей сетей с заданной структурой представляет [77] значительный как теоретический, так и практический интерес. Построение таких методов во многом обосновывается результатами исследования параметрических потоковых задач, связанных с понятием устойчивости сети. Также как и в других разделах дискретной математики [23, 24] , в теории сетей исследование устойчивости является одной из важ-
нейших задач анализа. В работе [24] подчеркивается, что в настоящее время существует достаточно много различных понятий устойчивости, выбор каждого из которых обуславливается характером решаемой задачи. Для решения задач выбора оптимальных пропускных способностей представляют интерес параметрические потоковые задачи, заключающиеся в изучении поведения величины максимального потока как функции пропускных способностей дуг (или ребер), а также задачи нахождения множеств дуг (или вершин) наибольшим образом "влияющих" на величину потока в сети. Отметим, что в основном исследование перечисленных задач проводилось [5, II, 57, 61, 92, 95, 98J для двухполюсных сетей (то есть сетей с выделенными источником и стоком). Для многополюсных сетей параметрические задачи о максимальном потоке еще сравнительно мало исследованы, хотя именно такие сети чаще всего являются моделями реальных связывающих сетей.
Диссертационная работа посвящена исследованию свойств матрицы максимальных потоков многополюсной сети в зависимости от характеристик функции пропускных способностей и решению на этой основе задач анализа и синтеза многополюсных сетей с заданной структурой, а также исследованию задачи синтеза двухполюсной сети с заданным уровнем надежности.
Работа состоит из введения, трех глав, приложения и списка цитированной литературы.
В первой главе для неориентированных однородных (в частности, полных) сетей и полных псевдосимметрических сетей определены свойства функции пропускных способностей, при которой матрица максимальных потоков находится с помощью простых вычислительных операций.
В I.I проведен обзор постановок параметрических задач о максимальном потоке, в которых исследуется зависимость величины
максимального потока от изменения пропускных способностей дуг (или ребер) сети.
В 1.2 для полных неориентированных, а в 1.3 для полных псевдосимметрических сетей определены замкнутые интервалы значений пропускных способностей, при которых любая функция пропускных способностей на ребрах (или дугах) приводит к матрице пхп максимальных потоков, которая является так называемой матрицей максимальной пропускной способности (ММПС), то есть матрицей, в которой для любого ее значения ]Тп ( *J) максимального потока из Хі в X; справедливо равенство
Щ ^пгс/г [c(xL) , c(xj)] ,
где С(Х\) - пропускная способность вершины Х-ь , равная суммарной пропускной способности инцидентных ей ребер (или суммарной пропускной способности входящих в нее дуг, если сеть псевдосимметрическая) . Псевдосимметрической называется ориентированная сеть, для любой вершины которой сумма пропускных способностей входящих в нее дуг равна сумме пропускных способностей выходящих из нее дуг. В результате исследования выделены классы эффективно разрешимых задач о максимальных потоках в многополюсных сетях.
В главе 2 исследуются свойства матрицы максимальных потоков в полных неориентированных сетях в зависимости от характеристик функции пропускных способностей, принимающей значения из заданного замкнутого интервала. Целью исследования является определение характеристик функции пропускных способностей, при которых матрица V" является ММПС.
В 2.1 вводится понятие характеристической пропускной способности JC (Хі) вершины, значение которой позволяет оценить величины возможных максимальных потоков из заданной вершины в любую другую вершину сети. Для значения Х(хС) показана
справедливость формулы
где Д- = { Z I Ссг b(e + f)C*, l*Lj г=/,...,/г.j- специальные множества, связанные с каждой вершиной К і , и Уі>с , Ж і ,
jiL - подмножества множества 1 , построенные по определенным правилам. Значение ^ находится по формуле
- - ]Я ,
=
где С** = max [cCj] , С* = "^ 1сф ,
и /Z. - число вершин сети. Величины j-ii —Січ для Z^J^ определяются с помощью разработанного алгоритма вычисления характеристической пропускной способности (МВХВ) с оценкой трудоемкости 0(пь). Показано, что величина 1/п максимального потока из Х^ в X: зависит от типа отношений (в теоретико-множественном смысле) между множествами Л і и Ж\ . В частности, доказано, что в полной неориентированной сети при Z ~ С * jXL для любого значения У"и матрицы V справедливо равенство
Г ггъСп, IX(XL) , JCfXj)] при і Ф Xj , Щ = [ тйг [x'fxL) ? Jc'fxj)] при t*zXj .
Дяя нахождения значений Х'/Хі) >sX(Xj) также используется МЕКВ. В 2.2 определяются типы отношений между множествами Ji , при которых соответствующая матрица V является ММПС. В частности, доказано, что если для любой вершины X: сети с заданным ограничением на функцию пропускных способностей справедливо условие
\ L,\ Lj/lU Li I <*>
' символ ]aL- наименьшее целое, не меньшее CL .
то матрица V является ММПС. Здесь L: - подмножества множеств Ж і , построенные с помощью специальной процедуры и
Ш = / I IJ Ф Li 7 C*J, Is 4,..., л> j. На основе проведенных в главе исследований построен ( 2.3) метод определения матрицы V (MOV") полной сети с заданным ограничением на пропускные способности. Эффективность метода обеспечивается тем, что для многих классов задач все значения матрицы V находятся путем построения множеств Li и анализа отношений между ними, что требует не более 0(г) действий. При необходимости дополнительного нахождения значений Х(хЛ и (или) Л fXj) общее число действий МОV" не превосходит 0(пк).
В главе 3 исследуются задачи синтеза оптимальных сетей с заданной структурой при условии минимизации суммарной пропускной способности ребер (или дуг) сети, а также при дополнительном требовании обеспечения заданного уровня надежности.
В 3.1 исследуется задача синтеза полной неориентированной сети (ЗСПС) в следующей постановке. Пусть заданы положительные целые значения С* и С и симметричная матрица V Для полной неориентированной сети требуется найти целочисленную функцию пропускных способностей, значения которой на ребрах удовлетворяют условию
С* ± Cij ±С*« V (x^xjiefi *
и при которой матрица V является ММПС построенной сети.
Отметим, что требование нахождения функции пропускных способностей, при которой матрица V" является ММПС, равносильно требованию минимизации суммы пропускных способностей ребер. Задачи синтеза по симметричной матрице требований при условии минимизации суммарной пропускной способности ребер сети рассмотрены в работах [?8, 88, 104J . Основные отличия ЗСПС от указанных задач состоят в том, что, во-первых, в ЗСПС определено требование на структуру синтезируемой сети, во-вторых, в отличие
от предложенных в работах [78, 104J решений, допускающих полуцелые значения пропускных способностей, требуется найти только целочисленные значения пропускных способностей из заданного замкнутого интервала значений.
Определены необходимые и достаточные условия реализуемости заданной матрицы как ММПС при ограничениях ЗСПС. Построен метод синтеза сети, который состоит в последовательном нахождении для каждой вершины сети пропускных способностей инцидентных ей ребер, трудоемкость метода оценивается величиной 0(пг),
В 3.2 исследуется задача синтеза двухполюсной сети (ЗСДС), которая заключается в нахождении минимально возможных значений пропускных способностей, обеспечивающих передачу потока заданной величины из источника в сток при дополнительном требовании обеспечения заданного уровня надежности.
Пусть в двухполюсной сети передается максимальный поток величины и с дуговыми потоками J-n >0 . Обозначим через Л= min {Лц}, где Лц--^- , и через f = "^* {(fn] ,
где о и - значение, на которое уменьшается величина U при удалении дуги (х1л X?) . Назовем и уровнем Функциональной надежности сети. ЗСДС состоит в следующем.
На графе & с реберной связностью V требуется ввести ориентацию ребер и определить на них такие положительные значения пропускных способностей, при которых максимизируется Л при заданных значениях величины V требуемого потока из S в t и уровня О функциональной надежности.
Указан способ нахождения общего для всех дуг сети значения Л* и определены условия, при которых А достигает максимально возможного значения при заданных V и и
В 3.3 излагается приближенный метод решения ЗСДС. Пока-
зано, что определенные с его помощью значения пропускных способностей являются минимально возможными при найденном распределении потока заданной величины по дугам сети. В случае определения значения Л меньшего, чем оптимальное, улучшение решения возможно за счет перераспределения заданного потока по сети с целью приближения к оптимальному потоку.
В 3.4 обсуждаются вопросы практического использования результатов решения ЗСДС при выборе оптимальных пропускных способностей реальных связывающих сетей. В приложении приводится документ, подтверждающий внедрение результатов работы.
Основные результаты диссертационной работы изложены в работах l08 - 1183, а также докладывались и обсуждались на ІУ Всесоюзной научно-технической конференции по повышению качества функционирования и надежности информационных сетей и их элементов (Новосибирск, 1981), первой Крымской весенней школе по дискретной оптимизации (Судак, 1982), втором Всесоюзном совещании "Методы и программы решения оптимизационных задач на графах и сетях" (Улан-Удэ, 1982), на семинаре лаборатории исследования операций Института математики АН БССР (Минск, 1983), на Республиканском семинаре научного совета по кибернетике АН УССР "Теория оптимальных решений" (Киев, 1983), на Минском городском семинаре по математической кибернетике ( 1983 ).
Разработанные в диссертационной работе методы синтеза сетей с заданной структурой включены в математическое обеспечение создаваемой в Институте математики АН БССР системы проектирования и управления Белорусской зоны Региональной вычислительной подсети "Прибалтика", а также положены в основу пакета прикладных программ, разрабатываемого на кафедре математического обеспечения АСУ факультета прикладной математики Белгосуниверситета имени В. И. Ленина.
Максимальные потоки в однородных неориентированных сетях
В этом параграфе определяется класс эффективно разрешимых задач о максимальных потоках в неориентированных многополюсных сетях.
Пусть G- =(Х,Л}с) - неориентированная сеть с целочисленной неотрицательной функцией пропускных способностей. Обозначим через V IIVU llnxn симметричную матрицу максимальных потоков сети С- , где Vlj - величина максимального потока из вершины Xi в вершину X: . Будем считать, что Va =с для і =/, Z7..., і .
Как уже отмечалось, эффективным методом нахождения элементов матрицы V является метод Гомори-Ху. В основе этого метода [78J (см. также [20, 43 J ) лежит утверждение о том, что величины максимальных потоков в многополюсной сети удовлетворяют соотношению VLJ "Un [ViK, tAj) для всех (1.3) при этом матрица V реализуема в виде дерева / , потоково эквивалентного некоторой неориентированной сети с матрицей V .
Под потоковой эквивалентностью двух сетей понимается, что эти две сети неразличимы при характеризации их с помощью максимальных потоков между каждой парой вершин.
Метод Гомори-Ху состоит в нахождении пропускных способностей gti ребер дерева / , потоково эквивалентного заданной сети (г , путем решения Л -І задач о максимальном потоке. Каждая очередная задача решается на сети, полученной из исходной с помощью так называемой операции конденсации (см., например, [20J ). Значения матрицы V определяются по правилу где последовательность индексов (C} e±t Єх , - k,J) определяет единственную цепь из к і в Л; на построенном дереве Т .
Из определения потока (І.І) и (1.2) следует, что для любого значения 2 Zj ( L i ) матрицы V справедливо соот ношение где C(Xj) = у Ci - пропускная способность вершины Х
Покажем, что исследование зависимости свойств матрицы максимальных потоков от выбора интервала возможных значений функции; пропускных способностей позволяет найти классы эффективно разрешимых задач о максимальных потоках в многополюсных сетях.
Пусть = (X) Я, С) - полная неориентированная сеть с целочисленной положительной функцией пропускных способностей, то есть сеть, между каждой парой вершин которой существует ребро. Предположим, что в сети G- с помощью любого из известных методов найден максимальный поток величины UU из вершины X L в вершину X: и этим зафиксирована некоторая ориентация ребер.
Будем говорить, что вершина Хр достижима из вершины Ху, при найденном максимальном потоке из Х в Xj , если существует увеличивающий поток путь из Х . в Хр (то есть путь, для которого jrft i CP % на ДУгах» входящих в путь в направлении ориентации, и ffaft 0 на дугах, входящих в путь в направлении противоположном их ориентации).
На полной сети возникает задача определения свойств функции пропускных способностей, не удовлетворяющей условию /jz[ при которой соответствующая ей матрица I/ является ММПС. Исследованию этой задачи будет посвящена следующая глава.
Покажем,теперь, что существует более широкий класс неориентированных сетей, включающий полные сети, для которого также можно найти замкнутый интервал значений пропускных способностей, при котором любая функция пропускных способностей на ребрах сети приводит к матрице V , являющейся ММПС.
В дальнейшем изложении используются следующие понятия теории графов [41J . Неориентированный граф (г (Х}Д) называется однородным степени Ъ , если &( 1)-Ъ для любой вершины xL є л , где оі(Кі) - степень вершины, равная числу инцидентных ей ребер.
Реберной связность И графа называется наименьшее количество ребер, удаление которых приводит к несвязному графу.
Оптимальное распределение пропускных способностей по ребрам полной сети
К числу важнейших и интенсивно изучаемых задач теории сетей относятся задачи синтеза оптимальных по каким-либо критериям сетей. Они возникают при проектировании реальных сетей самого различного назначения. Этим объясняется многообразие исследуемых задач синтеза и используемых в них критериев оптимальности. В качестве критериев оптимальности обычно выбирают стоимостные или надежностные показатели. При этом надежностные критерии определяются [31, 33, 34, 40, 44] характеристиками связности.
В общем случае задачи синтеза оптимальных сетей относятся к NP - полным задачам математического программирования с несколькими критериями. В настоящее время не существует единых подходов, позволяющих решить задачу синтеза любого типа.
В самом общем виде задачи синтеза оптимальных сетей можно разделить на задачи нахождения топологической структуры с заданными стоимостными и надежностными характеристиками и задачи синтеза сетей, обеспечивающих передачу потоков не ниже заданной величины при некоторых дополнительных (например, стоимостных) ограничениях.
Ниже исследуется задача синтеза неориентированной сети, в которой обеспечивается передача потоков заданной величины между каждой парой вершин при условии минимизации суммы пропускных. способностей ребер.
Задачи такого типа известны в литературе [39, 40, 43, 60, 88, 94J как задачи синтеза многополюсных сетей. В общем виде задача синтеза многополюсной сети заключается в нахождении по заданной матрице требований Я Нгч11пхп » гДе / "" тРе буемая величина потока из XL в X; » топологии сети и значений а пропускных способностей, при которых обеспечивается выполнение условия V - - Я , где V - матрица максимальных потоков построенной сети.
Впервые такая задача была рассмотрена В. Майедой [88] и Р. Чином [60] , которые определили необходимые и достаточные условия реализуемости матрицы ft как матрицы максимальных потоков некоторой сети. Предложенные в работах [60, 88] методы решения задачи для случая симметричной матрицы Я , а в работах [94, 100] для случая несимметричной матрицы /t , позволяют найти сеть с заданной матрицей максимальных потоков без учета каких-либо стоимостных ограничений на единицу пропускной способности.
В общих случаях реализация матрицы R, при заданной функции стоимости является сложной задачей, решаемой [40, 44] с привлечением методов математического программирования. В работах Р. Гомори и Т. Ху [78] (см. также [43] ) и 0. Уинга и Р. Чайна [104] показано, что в случае симметричной матрицы и линейной функции стоимости можно построить простые комбинаторные методы решения этой задачи. Рассмотренные в работах [78, 104] задачи заключаются в нахождении допустимой сети с суммарной пропускной способностью ребер, равной нижней границе
В работе [19] рассмотренная постановка задачи изучается при дополнительном требовании различной стоимости единицы пропускной способности между каждой парой вершин сети.
Методы решения указанных задач заключаются в нахождении специальных равномерных поддеревьев (см., например, [43] ), каждое из которых затем синтезируется циклом, проходящим через вершины дерева. Затем, наложив построенные циклы друг на друга, определяют структуру сети и пропускные способности ребер. Отметим, что при реализации этих методов не учитываются какие-либо ограничения на структуру синтезируемой сети. При этом, в найденном оптимальном решении пропускные способности являются целыми или полуцелыми числами.
В отличие от перечисленных задач, нами изучается задача синтеза по симметричной матрице требований сети с наперед заданной структурой при условии минимизации суммарной пропускной способности ребер и дополнительном ограничении на значения пропускных способностей.
Синтез двухполюсной сети с заданным уровнем функциональной надежности
Нетрудно видеть, что требование выполнения равенства (1.5) для любого значения ЦІ синтезируемой сети равносильно требованию построения сети с минимальной суммарной пропускной способностью ребер, определяемой условиями (3.1) и (3.2). В самом деле, если для любой вершины X: выполняется требование С(Х:) = Uj , то сумма пропускных способностей построенной сети будет удовлетворять условиям (3.1) и (3.2).
Заметим, что поставленная задача синтеза является в определенном смысле обратной к задачам анализа, рассмотренным в первых двух главах. Если в изученных задачах анализа требовалось найти функцию пропускных способностей, при которой соответствующая ей матрица V является ММПС, то теперь по заданной ММПС необходимо найти соответствущую ей функцию пропускных способностей полной сети.
При ограничениях поставленной ЗСПС условие реализуемости (1.3) матрицы V как матрицы максимальных потоков некоторой сети является необходимым, но не достаточным. Поэтому для решения задачи нужно в первую очередь найти необходимые и достаточные условия реализуемости матрицы V при ограничениях задачи синтеза полной сети.
Говорят [40] , что матрица полуразделима, если после перестановки строк и соответствующих столбцов она удовлетворяет условиям: I) диагональные элементы I/ равны бесконечности; 2) может быть разделена, то есть представлена в виде квадратная матрица, а все элементы Vfz Равны минимальному элементу I/ ; 3) каждая подматрица, полученная в результате такого разделения и находящаяся на главной диагонали, может быть снова разделена и процесс разделения будет продолжаться до тех пор, пока полученные подматрицы не будут иметь порядок, равный единице.
Теорема 3.1 (.60 J . Если матрица V реализуема как матрица максимальных потоков некоторой сети, то I/ - полуразделима. Симметричная матрица ]/ называется [91J элементарной, если она имеет вид
Теорема 3.2. Матрица К реализуема как матрица максимальной пропускной способности некоторой неориентированной сети тогда и только тогда, когда она путем перестановки строк и столбцов приводится к элементарному виду.
Доказательство. Пусть матрица I/ реализуема, тогда из теоремы 3Л следует, что она полуразделима. Предположим, что она путем перестановки строк и столбцов приведена к полуразделенной форме. Тогда из определения полуразделимости матрицы следует, что для элементов первой строки матрицы V выполняется условие 2 / % -.- 1?/п-1 Ь %г. . Будем считать, что исходная нумерация вершин сети изменена в соответствии с произведенной перестановкой строк и столбцов. Тогда из равенств (1.5) и условия % Ї Аз Ї - - Ї V±n следует, что вершины сети теперь пронумерованы по невозрастанию величин C(xL) и t z-C(xz)
При этом для каждого из столбцов все элементы, расположенные над главной диагональю, равны между собой. Учитывая, что vu =VjC ,получаем, что матрица V приведена к элементарному виду.
Пусть теперь V имеет элементарный вид. Тогда, как показано в [91] , она может быть реализована линейным деревом (то есть деревом со степенями всех вершин не более двух) с пропускными способностями ребер, равными надциагональным элементам матрицы V . Ясно, что это дерево является деревом доминирующих требований (то есть его пропускные способности удовлетворяют условию (3.2)) полной сети требований, представленной матрицей V . Поэтому оно может быть реализовано с помощью метода синтеза, предложенного Р. Гомори и Т. Ху [78] , в виде некоторой сети, для всех значений Vcj которой справедливо равенство (1.5). Теорема доказана. Заметим, что из условия элементарности матрицы V некоторой сети не следует, что она является ММПС. Это показывает следующий пример.
Вопросы практического использования ЗСДС
Исследуем задачу синтеза двухполюсной сети при условии минимизации суммы пропускных способностей дуг, обеспечивающих передачу потока не ниже заданной величины в случае уменьшения пропускной способности любой дуги сети.
Одним из основных требований, предъявляемых к реальным связывающим сетям, является надежность. Поэтому задачи синтеза надежных по каким-либо критериям сетей относятся к числу актуальных задач теории сетей. Общие проблемы исследования надежности сетей можно разделить [44, 45] на задачи анализа для определения уровня надежности и задачи синтеза сетей с заданным уровнем надежности. При этом, постановки задач анализа и синтеза надежных сетей зависят от выбора в каждом конкретном случае критерия надежности. Одним из широко используемых критериев является связность. Показатели надежности по критерию связности обычно [34] делят на два основных класса: показатели структурной надежности и показатели функциональной надежности (или живучести). По - 72 казатели первого класса характеризуют [34] уровень надежности в условиях "пассивного" поведения сети при повреждении ее элементов. Показатели второго класса характеризуют [31, 34] качество функционирования сети в условиях "активного" противодействия преднамеренному повреждению элементов. Выбор показателя надежности зависит от определения понятия "разрушения" сети. Так, сеть считается разрушенной [40j , если при удалении некоторого подмножества вершин или ребер полученная сеть удовлетворяет одному или нескольким из следующих условий: (О сеть разбивается, по крайней мере, на две компоненты; (СІ) прерываются все пути между двумя выделенными множествами вершин; (СИ) число вершин в наибольшей компоненте меньше некоторого заданного числа; кратчайший путь между двумя выделенными вершинами длиннее некоторой заданной величины.
Основными детерминированными показателями, связанными с условиями U) и (и) являются: наименьшее число вершин, удаление которых приводит к несвязной сети, то есть связность сети; наименьшее количество ребер, удаление которых приводит к несвязной сети, то есть реберная связность; число независимых по вершинам (или ребрам) путей между выделенной парой вершин.
Для перечисленных показателей надежности задачи анализа заключаются в нахождении эффективных методов определения этих величин. Некоторые из таких методов представлены в работах [67,70] (для нахождения Л ), [з, 12, 17, 51, 68] (для нахождения tf ), [25, 26, 54, 84, 90, 96J (для определения К ). Задачи синтеза состоят в нахождении структуры с заданным числом вершин и ребер, которая обеспечивает необходимое количество независимых путей между каждой (или выделенными) парой вершин [40, 42, 44] , или структуры, для которой связность или реберная связность велика настолько, насколько это возможно при заданном числе вершин и ребер
Реальные связывающие сети обычно проектируются flOj в предположении возможного повреждения отдельных линий связи. Поэтому сеть с заданным уровнем надежности по критерию связности должна также удовлетворять некоторому показателю, учитывающему влияние изменения пропускных способностей отдельных ребер на функционирование сети в целом. Для потоковых сетей естественно потребовать, чтобы такой показатель характеризовал зависимость величины максимального (или заданного)потока от изменения пропускных способностей ребер. Исходя из сказанного, представляется целесообразным дополнить понятие "разрушения сети" условием: (ЇЇ) сеть считается разрушенной, если при удалении любого ребра (или дуги ) величина максимального (или заданного) потока между двумя выделенными вершинами меньше некоторого заданного значения.
Изучим связанную с введенным условием (V) задачу синтеза двухполюсной сети. Пусть с помощью любого из известных методов (например, [б, 64, 66, 80] ) по заданному числу П вершин и Р ребер найдена структура неориентированного графа &-(л} Л) с требуемым значением 9 реберной связности. Естественно считать, что Р і . Заметим, что для реальных задач синтеза [8, 29, 44] обычно V 3
Исследуем задачу преобразования графа G- в двухполюсную ориентированную сеть, удовлетворяющую некоторым ограничениям. Для уточнения постановки задачи введем следующие определе ния и обозначения.
