Методы анализа и синтеза некоторых сетей с заданной структурой тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ВВЕ ДЕНЙЕ.

ГЛАВА I. ЭФФЕКТИВНО РАЗРЕШИМЫЕ КЛАССЫ ЗАДАЧ О МАКСИМАЛЬНЫХ

ПОТОКАХ В МНОГОПОЛЮСНЫХ СЕТЯХ. II

§ 1.1. Параметрические задачи о максимальном потоке. II

§ 1.2. Максимальные потоки в однородных неориентированных сетях.

§ 1.3. Максимальные потоки в полных псевдосимметрических сетях.

ГЛАВА 2. СВОЙСТВА МАТРИЦЫ МАКСИМАЛЬНЫХ ПОТОКОВ В ПОЛНОЙ

ШОРИЕНТИРОВАЩОЙ. СЕТИ '.

§ 2.1. Характеристическая пропускная способность вершин неориентированной сети.

§ 2.2. Оптимальное распределение пропускных способностей по ребрам полной сети.

§ 2.3. Определение матрицы максимальных потоков полной сети при ограничениях на пропускные способности ребер

ГЛАВА 3. СИНТЕЗ СЕТЕЙ С ЗАДАННОЙ СТРШУРОЙ.

§ 3.1. Синтез полной сети по заданной матрице требований.

§ 3.2. Синтез двухполюсной сети с заданным уровнем функциональной надежности

§ 3.3. Приближенный метод решения задачи синтеза двухполюсной сети (ЗСДС)

§ 3.4. Вопросы практического использования ЗСДС

В настоящее время исследование задач теории сетей, моделирующих многочисленные практические проблемы построения связывающих сетей самого разнообразного назначения (сетей связи, электрических сетей, сетей вычислительных центров и т. д.) относится к одному из актуальных разделов математической кибернетики.

Основными математическими задачами, возникающими при проектировании оптимальных по различным критериям связывающих сетей являются [14, 27, 32] :

- структурный анализ проектируемой сети;

- аналитическое описание системы относительно выбранного критерия эффективности;

- синтез топологической структуры с заданными стоимостными и надежностными ограничениями;

- определение оптимальных по заданному критерию пропускных способностей линий связи.

Для анализа и решения этих задач широко используются [36, 40, 44] комбинаторные и теоретико-графовые подходы.

Особый как теоретический, так и практический интерес представляют задачи синтеза оптимальных по каким-либо критериям сетей. Изучению таких задач последние десять-пятнадцать лет уделяется большое внимание, о чем свидетельствует рост публикаций, посвященных как теоретическим (например, работы [13, 40, 43, 53, 76, ), так и прикладным аспектам [2, 21, 35, 36, 44, 50, 87, 10?] исследования задач синтеза оптимальных сетей.

Анализ этих работ позволяет выделить два основных подхода к решению задач синтеза сетей. При первом подходе (например, в работах [7, 19, 37, 38, 58, 60, 69, 93, 94, 100, 104] ) сразу определяются структура сети и пропускные способности, обеспечивающие требуемые потоки. При этом, многие методы [71, 78, 83, 91] строят сеть древовидной структуры (возможно [91] с дополнительным ограничением на структуру дерева). Основным критерием оптимальности при первом подходе является [7,19, 37, 38, 60, 100, 107] стоимость синтезируемой сети. Отметим, что при этом подходе обычно не учитываются надежностные характеристики сети. Практические проблемы построения надежных сетей обуславливают необходимость развития методов анализа и синтеза сетей с заданным уровнем надежности. При разработке математических методов решения этих задач надежность трактуется как устойчивость функционирования сети при изменении ее параметров. Второй подход к исследованию задач синтеза сетей состоит [8,36,82] в решении задачи в два этапа: сначала находится структура, отвечающая заданным надежностным и стоимостным характеристикам, и затем определяются оптимальные по выбранному критерию пропускные способности. На первом этапе широко используются строгие математические методы (см., например, [б, 40, 53, 55, 56, 74] ). Задачи нахождения пропускных способностей в основном [10, 29, 32, 35, Зб] решаются на содержательном уровне. Вместе с тем разработка математически обоснованных методов выбора оптимальных пропускных способностей сетей с заданной структурой представляет [77] значительный как теоретический, так и практический интерес. Построение таких методов во многом обосновывается результатами исследования параметрических потоковых задач, связанных с понятием устойчивости сети. Также как и в других разделах дискретной математики [23, 24] , в теории сетей исследование устойчивости является одной из важнейших задач анализа. В работе [24] подчеркивается, что в настоящее время существует достаточно много различных понятий устойчивости, выбор каждого из которых обуславливается характером решаемой задачи. Для решения задач выбора оптимальных пропускных способностей представляют интерес параметрические потоковые задачи, заключающиеся в изучении поведения величины максимального потока как функции пропускных способностей дуг (или ребер), а также задачи нахождения множеств дуг (или вершин) наибольшим образом "влияющих" на величину потока в сети. Отметим, что в основном исследование перечисленных задач проводилось [5, II, 57, 61, 92, 95, 98] для двухполюсных сетей (то есть сетей с вьщеленными источником и стоком). Для многополюсных сетей параметрические задачи о максимальном потоке еще сравнительно мало исследованы, хотя именно такие сети чаще всего являются моделями реальных связывающих сетей.

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

Работа состоит из введения, трех глав, приложения и списка цитированной литературы.

В первой главе для неориентированных однородных (в частности, полных) сетей и полных псевдосимметрических сетей определены свойства функции пропускных способностей, при которой матрица максимальных потоков находится с помощью простых вычислительных операций.

В § 1.1 проведен обзор постановок параметрических задач о максимальном потоке, в которых исследуется зависимость величины

- б максимального потока от изменения пропускных способностей дуг (или ребер) сети.

В § 1.2 для полных неориентированных, а в § 1.3 для полных псевдосимметрических сетей определены замкнутые интервалы значений пропускных способностей, при которых любая функция пропускных способностей на ребрах (или дугах) приводит к матрице пхп максимальных потоков, которая является так называемой матрицей максимальной пропускной способности (ММПС), то есть матрицей, в которой для любого ее значения ( максимального потока из XI в Х^ справедливо равенство

Щ - тс/г (сгх1) , С(х^)] , где С (Х1) - пропускная способность вершины Х-ь , равная суммарной пропускной способности инцидентных ей ребер (или суммарной пропускной способности входящих в нее дуг, если сеть псевдосимметрическая) . Псевдосимметрической называется ориентированная сеть, для любой вершины которой сумма пропускных способностей входящих в нее дуг равна сумме пропускных способностей выходящих из нее дуг. В результате исследования выделены классы эффективно разрешимых задач о максимальных потоках в многополюсных сетях.

В главе 2 исследуются свойства матрицы максимальных потоков в полных неориентированных сетях в зависимости от характеристик функции пропускных способностей, принимающей значения из заданного замкнутого интервала. Целью исследования является определение характеристик функции пропускных способностей, при которых матрица V" является ММПС.

В § 2.1 вводится понятие характеристической пропускной способности Х.(Хй вершины, значение которой позволяет оценить величины возможных максимальных потоков из заданной вершины в любую другую вершину сети. Для значения Х(*С) показана справедливость формулы

12 с+ 12 /¿г, РФЛ1 гефиХ? г* Л? где Я^ - {г I СцЬ (е + 1)С*, г =/,., Л- 3 - специальные множества, связанные с каждой вершиной ^ , и , Ж^ ,

1 - подмножества множества , построенные по определенным правилам. Значение ^ находится по формуле - * - м", где с** - УПО,Х [Сс]} , с* = ггьСп, { ] ? 2 и /2. - число вершин сети. Величины ¿-¿^ ^¿¿г для 2 ^ определяются с помощью разработанного алгоритма вычисления характеристической пропускной способности (МВХВ) с оценкой трудоемкости

Показано, что величина ¡^ максимального потока из Х^ в х^ зависит от типа отношений (в теоретико-множественном смысле) между множествами Х^ и Ж} . В частности, доказано, что в полной неориентированной сети при ~ £ для любого значения Х^л матрицы V справедливо равенство

Г *шъ {¿(Х^ , Х(х>)} при ¿Ф Л] , </ = I гШп [, Х'(х^) ] при ^ ^ ^ . Для нахождения значений X ^Х^) также используется МВХВ. В § 2.2 определяются типы отношений между множествами Ж^ , при которых соответствующая матрица V" является ММПС. В частности, доказано, что если для любой вершины Л^ сети с заданным ограничением на функцию пропускных способностей справедливо условие

I ¿; \ Lj.fl V и 4 ' ^ символ наименьшее целое, не меньшее а- . то матрица V является ММПС. Здесь Lj - подмножества множеств Жj , построенные с помощью специальной процедуры и

Gtj = { L I j Ф L[ 7 ¿*J, - На основе проведенных в главе исследований построен (§ 2.3) метод определения матрицы V (МОУ) полной сети с заданным ограничением на пропускные способности. Эффективность метода обеспечивается тем, что для многих классов задач все значения матрицы V находятся путем построения множеств Lj и анализа отношений между ними, что требует не более 0(г£) действий. При необходимости дополнительного нахождения значений Xfxfl и (или) х'(х^) общее число действий МОV" не превосходит 0(п к).

В главе 3 исследуются задачи синтеза оптимальных сетей с заданной структурой при условии минимизации суммарной пропускной способности ребер (или дуг) сети, а также при дополнительном требовании обеспечения заданного уровня надежности.

В § 3.1 исследуется задача синтеза полной неориентированной сети (ЗСПС) в следующей постановке. Пусть заданы положительные целые значения С* и С** и симметричная матрица V Для полной неориентированной сети требуется найти целочисленную функцию пропускных способностей, значения которой на ребрах удовлетворяют условию с* ±CLj±C** v (xL) Xj) , и при которой матрица V является ММПС построенной сети.

Отметим, что требование нахождения функции пропускных способностей, при которой матрица V является ММПС, равносильно требованию минимизации суммы пропускных способностей ребер. Задачи синтеза по симметричной матрице требований при условии минимизации суммарной пропускной способности ребер сети рассмотрены в работах [?8, 88, 104 J . Основные отличия ЗСПС от указанных задач состоят в том, что, во-первых, в ЗСПС определено требование на структуру синтезируемой сети, во-вторых, в отличие от предложенных в работах [78, 104] решений, допускающих полуцелые значения пропускных способностей, требуется найти только целочисленные значения пропускных способностей из заданного замкнутого интервала значений.

Определены необходимые и достаточные условия реализуемости заданной матрицы как ММПС при ограничениях ЗСПС. Построен метод синтеза сети, который состоит в последовательном нахождении для каждой вершины сети пропускных способностей инцидентных ей ребер, трудоемкость метода оценивается величиной 0(пг),

В § 3.2 исследуется задача синтеза двухполюсной сети (ЗСДС), которая заключается в нахождении минимально возможных значений пропускных способностей, обеспечивающих передачу потока заданной величины из источника в сток при дополнительном требовании обеспечения заданного уровня надежности.

Пусть в двухполюсной сети передается максимальный поток величины Ü с дуговыми потоками J-ij >0 . Обозначим через

Л = mirt [Лц], где , и через f = та.* {($;], x^tyeß 0 6 СЧ (xLy хреЛ * где (flj - значение, на которое уменьшается величина Ü при удалении дуги (Х^ Xj) . Назовем сР уровнем Функциональной надежности сети. ЗСДС состоит в следующем.

На графе & с реберной связностью 9 требуется ввести ориентацию ребер и определить на них такие положительные значения пропускных способностей, при которых максимизируется Л при заданных значениях величины IT требуемого потока из S в t и уровня (Г функциональной надежности.

Указан способ нахождения общего для всех дуг сети значения Л* и определены условия, при которых А* достигает максимально возможного значения при заданных и (Г

В § 3.3 излагается приближенный метод решения ЗСДС. Показано, что определенные с его помощью значения пропускных способностей являются минимально возможными при найденном распределении потока заданной величины по дугам сети. В случае определения значения Л* меньшего, чем оптимальное, улучшение решения возможно за счет перераспределения заданного потока по сети с целью приближения к оптимальному потоку.

В § 3.4 обсуждаются вопросы практического использования результатов решения ЗСДС при выборе оптимальных пропускных способностей реальных связывающих сетей. В приложении приводится документ, подтверждающий внедрение результатов работы.

Основные результаты диссертационной работы изложены в работах [108 - 1183 » а также докладывались и обсуждались на 1У Всесоюзной научно-технической конференции по повышению качества функционирования и надежности информационных сетей и их элементов (Новосибирск, 1981), первой Крымской весенней школе по дискретной оптимизации (Судак, 1982), втором Всесоюзном совещании "Методы и программы решения оптимизационных задач на графах и сетях" (Улан-Удэ, 1982), на семинаре лаборатории исследования операций Института математики АН БССР (Минск, 1983), на Республиканском семинаре научного совета по кибернетике АН УССР "Теория оптимальных решений" (Киев, 1983), на Минском городском семинаре по математической кибернетике ( 1983 ).

Разработанные в диссертационной работе методы синтеза сетей с заданной структурой включены в математическое обеспечение создаваемой в Институте математики АН БССР системы проектирования и управления Белорусской зоны Региональной вычислительной подсети "Прибалтика", а также положены в основу пакета прикладных программ, разрабатываемого на кафедре математического обеспечения АСУ факультета прикладной математики Белгосуниверситета имени В. И. Ленина.

1. Адельсон-Вельский Г.М., Дгаиц Е.А., Карзанов А. В. Потоковые алгоритмы. - М.: Наука, 1975. - 119 с.

2. Анализ и синтез сетей связи с использованием ЭВМ (Алгоритмыи программы)/Под общ. ред. В. Г. Лазарева. М.: Наука, 1974. -209 с.

3. Апраксин Ю.К. 0 перечислении элементарных сечений в сети связи ЭВМ. Автоматика и вычислительная техника, 1981, Р 4,с. 62-66.

4. Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1974. -368 с.

5. Беленова Н.К. Задача о выборе параметров ориентированной сети. Матем. методы решения экономич. задач, М., 1980, № 9, с. 49-55.

6. Берж К. Теория графов и ее применение. М.: Иностр. л-ра, 1962. - 319 с.

7. Вычислительные методы выбора оптимальных проектных решений /B.C. Михалевич, Н.З. Шор и др. Киев: Наукова думка, 1977.178 с.

8. Давыдов Г.Б., Рогинский В.И., Толчан А.Я. Сети электросвязи.-М.: Связь, 1977. 360 с.

9. Дшиц Е.А. Алгоритм решения задачи, о максимальном потоке в сети со степенной оценкой. Докл. АН СССР, 1970, т. 194, Р 4, с. 754-757.

10. Дэвис Д., Барбер Д. Сети связи для вычислительных машин. -М.: Мир,, 1976.- 680 с.

11. Евстигнеев В.А. Об оптимальном весе элементов сети. В сб.: Проблемы кибернетики. М.: Наука, 1966, с. 219-223.

12. Замбицкий Д.К., Солтан П.С. Нахождение класса £ -связности графа. В сб.: Прикладная математика и прогр. Выл Л, Кишинев, Штиинца, 1969, с. 61-67.

13. Замбицкий Д.К., Лозовану Д.Д. Алгоритмы решения оптимизационных задач на сетях. Кишинев, Штиинца, 1983. - 116 с.

14. Информационно-вычислительные сети ЭВМ (Обзор по зарубежным источникам). М.: ВИМИ, 1976. - 144 с.

15. Карзанов A.B. Нахождение максимального потока в сети методом предпотоков. Докл. АН СССР, 1974, т. 215, № I,с. 49-53.

16. Карзанов A.B. Экономный алгоритм нахождения максимального потока в сети. Экономика и матем. методы, 1975, т. II, Р 4, с. 723-729.

17. Корниенко A.A., Погребной В.К., Щэрбанов В.А. О минимальных разрезах графа. В сб.: Кибернетика и вуз. Вып. 4, Томск, изд. Томского ун-та, 1971, с. 141-147.

18. Корнилова А.Е. Минимальный поток и максимальный фронт в сети. В сб.: Применение матем. методов в экономич. исслед. и планир. Вып. I, Киев, 1967, с. 35-45.

19. Красиловец Л. В., Никитин А. И. К решению задачи синтеза од-нопродуктовой сети. Кибернетика, 1982, № 4, с. 74-79.

20. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. - 432 с.

21. Лазарев В.Г., Саввин Г.Г. Сети связи, управление и коммутация. М.: Связь, 1973. - 264 с.

22. Лазарев Ю.В. Влияние обходных путей на качество обслуживания вызовов и надежность связи. В сб.: Надежность и качество функционирования информационных сетей и их элементов. Тез. докл. 1У Всесоюзн. конф. Новосибирск, 1981, с. 51-52.

23. Леонтьев B.K. Устойчивость в комбинаторных задачах выбора. -Докл. АН СССР, 1976, т. 228, II? I, с. 23-25.

24. Леонтьев В.К. Дискретные экстремальные задачи. В сб.: Итоги науки и техники. Сер. Теор. вероят. Матем. статистика. Теоретич. кибернетика. М., ВИНИТИ, 1979, с. 31-102.

25. Лепешинский H.A., Малышко В.В. Об одной оценке вершин орграфа. Рук. деп. в ВИНИТИ, 10.03.1976, per. Р 657.

26. Лепешинский H.A., Малышко В.В. Дуговые графы и определение элементарных путей между парами вершин графа. Весц1АН БССР, сер. физ.-мат. навук, 1976, № I, с. 5-8.

27. Летунов Ю.П. Методы проектирования и концепции построения сетей передачи данных. В сб.: Сети ЭВМ и системы передачи: данных. Материалы семинара. М., 1977, с. 25-32.

28. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981. - 323 с.

29. Малиновский С.Т. Сети и системы передачи дискретной информации и АСУ. М.: Связь, 1979. - 384 с.

30. Малышко В.В., Харари Ф. Задача о минимальном блокирующем потоке в сети. В сб.: Методы и программы решения оптимизационных задач на графах и сетях. Тез. докл. Второго Всесоюзн. совещ. Улан-Удэ, 1982, ч.2, с. 99-100.

31. Нечепуренко М.И. Формализация понятия живучести систем. -Веб.: Имитационное моделирование систем. Новосибирск, 1979, с. 3-16.

32. Основы построения больших информационно-вычислительных сетей /Под общ. ред. Д. Г. Жимерина, В.В. Максименко. М.: Статистика, 1976. - 296 с.

33. Попков В.К. Некоторые структурные характеристики сетей связи. В сб.: Системный анализ и исследование операций. Новосибирск, 1979, с. 84-93.

34. Попков B.K. Классификации показателей структурной надежности и живучести информационных сетей. В сб.: Надежность и качество функционирования информационных сетей и их элементов. Тез. докл. 1У Всесоюзн, конф. Новосибирск, 1981, с,12-14.

35. Сети ЭВМ / Под ред. В.М. Глушкова. М.: Связь, 1977.- 280 с.

36. Теория сетей связи /Под ред. В.Н. Рогинского. М.: Радио и связь, 1981. - 192 с.

37. Трубин В.А., Шдоян А.К. Алгоритмы и свойства задачи синтеза сетей с одним источником. В сб.: Теория оптимальных решений. Киев, 1980, с. 81-88.

38. Трубин В. А. Метод и программы решения некоторых задач синтеза оптимальных сетей. В сб.: Методы и программы решения оптимизационных задач на графах и сетях. Тез. докл. Второго Всесоюзн. совещ. Улан-Удэ, 1982, ч.1, с. 213-214.

39. Форд JI., Фалкерсон Д. Потоки в сетях. М.: Мир, 1966. -276 с.

40. Фрэнк Г., Фриш И. Сети, связь и потоки. М.: Связь, 1978. -447 с.

41. Харари Ф. Теория графов. М.: Мир, 1973. - 300 с.

42. Храмшин С.К., Ченцов В.М. 2Нивучесть сетей передачи информации. Изв. АН СССР, Техн. киберн. 1976, № 4, с. 91-92.

43. Ху Т. Целочисленное программирование и потоки в сетях. -М.: Мир, 1974. 519 с.

44. Ченцов В.М. Системы распределения информации. Синтез структуры и управление. М.: Связь, 1980. - 143 с.

45. Черкасский Б.В. Алгоритм построения максимального потока в сетях со сложностью 0 (пг\р) действий. Матем. методы решения экономич. задач, 1977, № 2, с. 117-125.

46. Черкасский Б.В. Быстрый алгоритм построения максимального потока в сети. Сб. тр. ВНИИ системных исследований, 1979, W 3, с. 90-96.

47. Якубайтис Э.А. Архитектура вычислительных сетей. М.: Статистика, 1980. - 279 с.

48. Якубайтис Э.А. Архитектура региональных и локальных вычислительных сетей. Автоматика и вычисл. техника, 1982, № I,с. 3-И.

49. Янбых Г.Ф., Эттингер Б.Я. Методы анализа и синтеза сетей ЭБМ.-Л.: Энергия, 1980. 96 с.

50. Abel ü.,Bicker R. Determination of all minimal cut sets between a vertex pair in an undirected graph* - IEEE Trans. Reliab., 1982, v. 31, K2f p. 167-171.

51. Ahuja R.K., Batra J.L., Gupta S.K. The constrained maximum flow problem.- Scientific management of transport system, 1981, p. 304-316.

52. Ayoub J.N., Prisch J.T. Optimally invulnerable directed communication netwoks.- IEEE Trans. Commun. Techol., 1970, v. com 18, p. 484-489.

53. Bellman R. On a Routing problems.- Qurt a applied Mathematics, 1958, v. 16, p. 87-90.

54. Boorstun R.R.f Frank H. Largescale network topological optimization. IEEE Trans. Communs., 1977, v. 25, N1, p. 29-47.

55. Chare P.M., Motgomery D.C., Turner W.C. Optimal interdiction policy for a flow network. Nav. Ees. Log. Qurt., 1971»v. 18, N1, p. 37-45.

56. Chartrand G. A Graph Theoretic Approach to the Communication Problem. SIAM J. Appl. Math., 1966, v.14, p. 778-781.

57. Chien E.T. Synthesis of Communication Net, * IBM J. Ees. Dev. 1960, N4, p. 311-320.

58. Cor ley H.W., Chang H. Finding the n most vital nodes in a flow network.- Manag. Sci., 1974, v. 21, N3, p. 362-364.

59. Doulliez P.J., Eao M.E. Network problem with parametric demands and ars feulures. A labeling algorithm. Cah. Cent, etud. rech. oper., 1976, v. 18, N4, p. 419-438.

60. Durbin E.P. An Interdiction Model of Highway Transportation.--EM- 4945 PE. The Eand Corporation. Santa Monica. California, 1966.

61. Edmonds J. Existence of k-Edge Connected Ordinary Graphs with Eescribed Degrees. J. Ees. Natl. Bur. Std. B., 1964,p. 73-74.

62. Edmonds J., Karp E.M. Theoretical impruvements in algorithmic eflicieney for network flow problems.- Jornal ACM, 1972, v.1, N19, p. 248-264.

63. Frank H., Frisch J., Chou W. Topological considerations in the design of the AEPA Computer network.- In Conf. Ees., 1970. Spring Joint Comput Conf. 1970, v. 36, p. 581-587.

64. Friseh J.T. An Algorithm for Vertex Pair Connectivity.- Intern. J. Control, 1967, v. 6, p. 579-593.

65. Frisch J.T. Analysis of the Vulnerability of Communication Nets.

66. Hammer P. Inereasing the capacity of a network.- CORS Jornal, 1969, N2, p. 83-91.

67. Henschel D. Probleme der DurchlarfS- higkeit von Nachrictenverkehrsystemen unter Berücksicttigung der zuverlässig -keitsteorie. Fernmeldetechnik, 1971, v. 11, N1, s. 19-24.

68. Hy T.C. Optimum Communication Spanning trees. SIAM J. Computing, 1974, v. 3, N3, p. 188-195.

69. Malhutra V.M., Kumar M.P., Maheshwari S.N. An 0 (|v|3) Algorithms for Maximum Flow in Networks. Jnformation Processing Letters, 1978, v. 7, N6, p. 277-278.

70. Mandl Ch. Applied Network optimizationrLondon, Academic Press, 1979.

71. Mayeda W. Terminal and Branch Capacity Matrices of a Communication Net. IRE Trans. Circuit Theory, 1960, v. ct-8, p. 261-269.

72. Memasters A.W., Mustin T.M. Optimal inderdiction of a sypply Network. Nav. Res. Log. Qurt, 1970, v. 17, N3, p. 261-268.

73. Moss F.H., Merlin P.M. Some Theoretical Results in Multiple Path Definition in Networks. Networks, 1981, N11, p. 401-411.

74. Ozawa T. Realization of a symmetric terminal capacity matrix by a tree with the minimum diameter. Networks, 1980, v. 10, N2, p. 129-142.

75. Ratliff H.D., Sicilia G.T., Lubore S.H. Finding the n mostlinks in flow network. Manag. Sei., 1975, v. 21, N5, p.531-539.93* Resh J. A. On the Synthesis of Oriented Communication Nets.- ieee Trans. Circuit Theory, 1965, v. ct-12, p. 540-546.

76. Sen D.K., Frisch J.T. Synthesis of Oriented Communication Nets. In Proceedings of the IEEE Symposium of Signal Transmission and Processing. New York. Columbua University, 1965, p. 90-91.

77. Shapley L.S. On network flow functions. RAND Corporation Research Memorandum. RM-23338. March, 1959, v. 16.

78. Shier D. Iterative Methods for Determining the k Shortest Paths in a Network. Networks, 1976, N6, p. 205-230.

79. Shiloach Y. Multiterminal 0-1 flow. SIAM J. Comput., 1979, v.8, N3, p. 422-430.

80. Somers F., Jlan A. The max flow problem with parametric capacities. - Discrete Appl. Math., 1979, v.1, N4, p. 287-300.

81. Syslo M.M. Optimal constructions of event-node networks. -- RAIRO Rech. oper., 1981, v. 15, N3, p. 241-260.

82. Tang D.T., Chein R.T. Analysis and Synthesis Techniques of Oriented Communication Nets. IRE Trans. Circuit Theory, 1961, v. ct-8, p. 39-44.

83. Tarjan R.E. Resent Developments in the complexity of Combinatorial Algorithms. The Fifth IBM Sump, on Mathematical Foon-dations of Computer Science. Hokole, Japan, 1980, p. 12-28.

84. Tetsuo J., Hiroaki J., Toshio N. A minimum flow problem.- Math. Fap., 1979, v.24, N1, p. 65-71.

85. Vlastimal K. Maximeilni tok parametricky ohodnocenou siti. --Ekon mat. obz., 1982, v.18, N3, p. 266-284.

86. Wing 0., Chien R.T. Optimal Synthesis of a Communication Net.- IRE Trans. Circuit Theory, 1961, v. ct-8, p. 44-49.

87. Wollmer R.D. Some methods for Determinig the most vital link in a railway network. RAND Memorandum RM - 3321 - ISA. April,1963, p. 93-98.

88. Yen J.Y. Pinding the к shortest, loopless paths in a network.- Manag. Sei., 1971, N17, p. 712- 720.

89. Zaden N. On bilding minimum cost communication Network -over times. Networks, 1974, N4, p. 19-34.

90. Батурина JI.H. Алгоритм определения максимального потока при изменениях пропускных способностей дуг. В сб.: У Республиканская конференция математиков Белоруссии. Тез. докл. Гродно, ч. I, с. 50-51.

91. Батурина Л.Н. Определение мак с гадальных потоков при изменении параметров сети. Минск, 1982. - 8 с. - рук. представлена редколлегией журн. Вестн. Белорусского ун-та, сер. I, физ., мат. и мех., деп. в ВИНИТИ 24.03.1982, per. Р 1327.

92. Батурина Л.Н., Лепешинский H.A. Эффективный метод определения потоковой функции. В сб.: Методы и программы решения оптимизационных задач на графах и сетях. Тез. докл. Второго Всесоюзн. совещ. Улан-Удэ, 1982, ч. 2, с. 7-9.

93. Батурина Л.Н., Лепешинский H.A. Имитация работы сетей ЭВМ. -МТА Szamitastechn es automatiz. Kut. Inter, Tanul, 1982,131, сб. н.-и. работ РГ-II/KH ВВТ, № I, с. 25-30.

94. Батурина Л.Н. Синтез сетей по симметричной положительной матрице требований. Минск, 1983. - 14 с. - Ь^ук. представлена редколлегией журн. Вестн. Белорусского ун-та, сер. I, физ., мат. и мех., деп. в ВИНИТИ 17.01.1983, per. Ш 281.

95. Батурина Л.Н., Лепешинский H.A. Алгоритмы оптимизации параметров, обеспечивающих заданный уровень живучести сети. -Весц1 АН БССР, сер. ф1з.-мат. навук, 1983, № 4, с. 26-29.

96. Лепешинский H.A., Батурина Л.Н. Синтез надежных сетей. -27 Intern. Wiss. Ко11. ТН Ilmenau, 1982, h. 6, s. 53-55.