автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Оценки структурной надежности сети передачи информации

Введение

1. Предмет и цели исследования, актуальность темы

2. Семейства конечных множеств

3. Независимое случайное множество

4. Случайная бинарная структура и ее надежность

5. Случайный матроид и его надежность

6. Бинарная структура со слоистым комплексом и ее надежность

7. Вычислительная сложность проблем структурной надежности

8. Обзор литературы

8.1. Оценки надежности общей случайной бинарной структуры

8.2. Оценки надежности однородной случайной бинарной структуры

8.3. Оценки надежности случайного матроида

8.4. Оценки ненадежности однородной случайной бинарной структуры со слоистым семейством независимости

8.5. Оценки к-терминальной надежности сети

8.6. Оценки вероятности связности случайного графа

8.7. Оценки двухполюсной надежности

9. Краткое описание результатов диссертации

10. Теоретическая и практическая ценность работы, ее апробация, благодарности

Глава 1. Оценки надежности случайной бинарной структуры

1. Развязывание клаттера

1.1. Развязывание клаттера раздвоением элемента

1.2. Развязывание клаттера по элементу

2. Развязывание клаттера и теорема о клаттерной перколяции

2.1. Развязывание клаттера раздвоением элемента и надежность

2.2. Факторные преобразования клаттеров и теорема Мак-Диармида о клаттерной перколяции

2.3. Теорема о клаттерной перколяции

3. Развязывание клаттера и корреляционные неравенства

4. Развязывание клаттера и статистическая независимость монотонных событий в НСМ

4.1. Клаттерная характеризация существенных элементов бинарной структуры

4.2. Статистическая независимость монотонно неубывающих событий в НСМ

4.3. Статистическая независимость других монотонных событий в НСМ

5. Развязочные оценки надежности СБС

5.1. Доказательство оценок Эзари-Прошана посредством развязывания клаттера

5.2. Развязочные оценки надежности СБС в терминах клаттеров и антиблокирующих множеств

5.3. Другие развязочные оценки СБС

Глава 2. Сумма матроидов и ациклический спектр матроида

1. Матроид: определения и сведения

2. Задачи упаковки, покрытия и пересечения для матроидов

3. Техника вспомогательных орграфов: увеличивающий путь и конструктивное описание цикла матроида-суммы

4. Решетка экстремальных множеств матроида-суммы

5. Базовый ряд последовательности матроидов

6. Алгоритм построения базового ряда последовательности матроидов

7. Ациклический спектр матроида и алгоритм его построения

8. Качественное сравнение алгоритмов упаковки, покрытия и пересечения для матроидов

Глава 3. Оценки надежности случайного матроида

1. Некоторые свойства надежности СМ

2. Специфика оценок надежности СБС для СМ

3. Надежность СМ, порожденных суммами однородных матроидов ранга

4. Нижние оценки надежности СМ

5. Обобщение одного асимптотического результата Эрдеша-Реньи о СГ на СМ

6. Сравнение нижних оценок надежности СМ

Глава 4. Оценки терминальной надежности случайного графа

1. Параллельные базисы 2-разбиения и деревья

2. Параллельные базисы Т-разрезов графа

3. Связка и ее матроид

4. Спектр взвешенной связки

5. Параллельные базисы Т-разрезов и спектр Т-связности

6. Параллельные базисы Т-разрезов и верхние оценки терминальной надежности СГ

7. Нижние оценки терминальной надежности СГ

8. Роль двусвязных и 2-лесистых графов

Глава 5. Оценки вероятности связности случайного графа

1. Специфика оценок надежности СБС и СМ для вероятности связности СГ

1.1. Упаковочные нижние оценки

1.2. Специфика верхних оценок надежности СМ в терминах семейств коциклов для вероятности связности СГ

1.3. Нижние оценки вероятности связности однородного СГ в терминах его АС

2. Верхняя оценка вероятности связности однородного СГ в терминах числа вершин и ребер

3. Верхняя оценка вероятности связности СГ в терминах вероятности связности однородного СГ. порожденного полным графом

4. Двусвязные мультиграфы

4.1. Предварительные сведения

4.2. Простейшие миноры двусвязных графов

4.3. Разделяющие ребра в двусвязном графе

4.4. Простейшие миноры двусвязных 2-лесистых графов

4.5. Взаимосвязь двусвязности и 2-лесистости графов

5. Оценки вероятности связности СГ, порожденных двусвязными мультыграфами

6. Аппроксимация вероятности связности однородного СГ на основе гриди-алгоритма вычисления двусторонних оценок

Глава 6. Оценки двухполюсной надежности случайного графа

1. Точно 2-остовные графы

2. Верхняя оценка двухполюсной надежности СГ, порожденного двусвязным графом

1. Предмет и цели исследования, актуальность темы

Теория структурной надежности сетей - один из разделов теории сетей передачи информации; число работ, посвященных проблемам структурной надежности сетей превышает сотни (см., например, обзоры [51, 55]). Пионерской работой в области структурной надежности сетей была работа Ф.Мура и К.Шеннона [110] (русский перевод [23]). Из монографий общего плана, посвященных математическим аспектам теории надежности, в том числе и аспектам структурной надежности сетей, отметим иностранную монографию [57] (первое издание [56] и ее русский перевод [4]) и отечественные монографии [3, 7, 8], включая монографию [6], посвященную вычислению структурной надежности сетей специального вида.

Что касается более узкого направления теории оценок структурной надежности сетей, то проблема построения, например, оценок вероятности связности впервые была сформулирована, по-видимому, в [12, 84]. Направление теории оценок характеристик структурной надежности сложилась лишь с течением времени (см. [51]).

Интерес к оценкам характеристик структурной надежности сетей обусловлен несколькими причинами. С одной стороны - практической проблемой синтеза надежной структуры (топологии) сетей [70, 123], алгоритмы решения которой принципиально связаны с вычислением характеристик структурной надежности для огромного количества потенциально возможных структур сети - графов. Сложность точного вычисления этих характеристик (а точное вычисление каждой такой характеристики Ц-полная проблема) драматически усиливает потребность в их эффективной аппроксимации и оценках. При этом полиномиально вычислимые оценки характеристик структурной надежности используются и в статистических методах аппроксимации этих характеристик. Например, доказательство полиномиальности статистической аппроксимации вероятности связности (этот результат [94] получен сравнительно недавно) использует некоторые полиномиально вычислимые оценки вероятности связности.

С другой стороны теория структурной надежности сетей тесно связана с математической теорией случайных графов (СГ) и теорией надежности случайных дискретных структур, более общих чем СГ. Поэтому оценки структурной надежности сетей используются также и для решения проблем теории СГ, ибо проблемы связности СГ пересекаются с проблемами структурной надежности (например, в монографии [60] по СГ есть специальный раздел (Reliable Networks), посвященный структурной надежности сетей (см. также обзоры [100, 101] по СГ).

В самых общих терминах СГ есть пара (©, Р), где 0 - семейство графов и Р -вероятностное распределение на Простейшая математическая модель структуры сети передачи информации есть неориентированный (ориентированный) граф G с множеством вершин VG и множеством ребер (дуг) EG, вершины которого соответствуют узлам сети, а ребра (дуги) - линиям связи. Простейшая вероятностная модель надежности структуры сети - Бернуллевская модель случайного графа (СГ) (G;p) (где Р = {Р(е) '■ е £ EG}) характеризуется независимым удалением из графа G его ребер (дуг) е £ EG с вероятностью q(e) = 1 — р(е); определенные характеристики связности этого СГ и есть характеристики структурной надежности сети.

Это значит, что в теории структурной надежности сетей <5 - семейство всех подграфов графа G и каждому графу Н G © приписана вероятностная мера

Р(Н) = П Р{е) П «(/)• ееЕН feEG-EH

СГ (G~,p) называют также биномиальным СГ, ибо эту модель можно описывается в терминах \EG\ независимых Бернуллевских экспериментов на ребрах EG графа G: удалим ребро е из EG с вероятностью q(e) независимо от всех других ребер или, эквивалентно, начнем с пустого графа на множестве вершин VG графа G и выберем ребро е из EG независимо с вероятностью р(е).

Понятие СГ ввел П.Эрдеш в 1947 г., но его понятие СГ отличалось от понятия СГ, указанного выше. Первые статьи [78, 79] по 'Эрдешевским' СГ были опубликованы П.Эрдешем и А.Реньи в 1959 и I960 годах. Одновременно и независимо появились статьи [49, 84], исследующие биномиальную модель СГ. Модель, введенная П.Эрдешем, имела перечислительную окраску и получалась взятием © семейства всех графов с п помеченными вершинами и N ребрами, 0 < N < Каждому (? £ 0 приписана вероятностная мера

Укажем и динамическую модель СГ. часто используемую в теории СГ. Пусть {Те}, е £ EG - независимые случайные величины (с.в.) с общим непрерывным распределением на [0, оо); каждая такая с.в. рассматривается как время, необходимое для появления ребра е. Пусть Gn(t) - граф с множеством вершин VG и теми ребрами е, для которых Те < t, iE [0,оо). СГ Gn(t) может быть идентифицирован со СГ (G;p), с р = Рг{Те < ¿}, т.е. рассматривается как состояние процесса Gn(t) во время t.

Хотя имеются разные модели СГ, но между ними существует определенная взаимосвязь (см. [100, 101]) и результаты, полученные для одной модели, вообще говоря, применимы и для другой модели. По теории СГ опубликовано сотни статей, обзоров и монографий (см., например, [44, 60, 86, 100, 101, 114, 124]). В этой теории исследуется вероятность того, что СГ обладает некоторым данным свойством, то есть принадлежит к классу графов, обладающим им. Рассматриваются разные свойства - связность, гамильтоновость, наличие совершенного паросочетания, и т.д. В теории СГ в основном интересуются случаем, когда вероятность интересующего события стремится к единице, если число вершин СГ стремится к бесконечности. Числовые параметры графа, например, степени вершин, реберная и вершинная связность, диаметр, хроматическое число, размер наименьшего цикла, и т.д., являются в СГ случайными величинами. В теории СГ интересуются их распределениями, в основном асимптотическими.

В теории структурной надежности сетей используется [51, 66, 119] несколько характеристик; наиболее общая - вероятность Rs(G;T;p) того, что из выделенного источника s в указанном множестве Т,Т С VG выделенных вершин (терминалов, полюсов) существует путь ко всем остальным терминалам из Т — s\ ее называют ^-терминальной надежностью, где к — \Т\. Ее важные частные случаи - вероятность RS(G; VG]р) того, что существует путь из s ко всем остальным вершинам сети, и двухполюсная надежность RS(G; (случай к = 2), то есть вероятность существования 5,^-пути (пути из ä в i). В диссертации в основном рассматривается неориентированный граф G. В этом случае вместо обозначений Г;р), УО]р), Ия(0] {з, используются обозначения Д(С?;р), соответственно; называется вероятностью связности СГ

В теории структурной надежности сетей сложились два направления: 1) аппроксимация характеристик структурной надежности, 2) построение двусторонних оценок характеристик структурной надежности.

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

В диссертации статистические подходы к аппроксимации характеристик структурной надежности не рассматриваются; исследования в ней ограничены исследованием вклада комбинаторных структур в теорию структурной надежности сетей. Поясним о каких комбинаторных структурах идет речь. Ч.Калберн пишет в [66]: "Понимание проблемы подразумевает извлечение комбинаторики из сердца этой проблемы. Ключевой момент в понимании надежности сети - извлечение комбинаторики надежности сети . Поверхностное исследование обнаруживает классические теоремы о связности и разрезах, простые факты из перечислительной комбинаторики. Более тщательное исследование открывает, однако, тесные связи с экстремальной теорией множеств, теорией матроидов, и т.д.". Д.Шир также отмечает в [119], что "интерес в предмете (то есть в структурной надежности) увеличивается из-за наличия разнообразной дискретной, комбинаторной и алгебраической математики, которая 'таится' под покровом практики . в основе проблем надежности сети лежат различные комбинаторные структуры . они то и играют основную роль в понимании проблем надежности сети". Среди этих структур - бинарная структура, матроид и граф, поэтому в диссертации исследуется последовательно случайная бинарная структура (СБС), случайный матроид (СМ) и СГ.

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

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

Требование эффективной вычислимости оценок резко уменьшает как многообразие привлекаемых параметров (вычисление многих параметров трудно), так и многообразие исследуемых конструкций (надежность экстремальной конструкции должна вычисляться эффективно). Это означает исследование лишь простых, регулярных конструкций - упаковок для СБС, прямых сумм однородных матроидов для СМ, полных графов и ряда других, симметричных графов для СГ. Такие конструкции, вообще говоря, взаимосвязаны с монотонными преобразованиями надежности исследуемой СБС (преобразованиями СБС, уменьшающими/увеличивающими надежность СБС), ибо последовательность таких преобразований может приводить к экстремальной конструкции.

Наконец, в случае однородной СБС существует дополнительная возможность для отыскания таких оценок: тот факт, что функция надежности однородной СБС - полином от р (и существует несколько таких полиномов) подразумевает построение оценок этого полинома (например, одновременная оценка всех его коэффициентов снизу и сверху дает соответственно нижнюю и верхнюю оценку надежности однородной СБС).

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

Методы исследования, используемые в диссертации, - это методы дискретной теории вероятности, теории мажоризации, теории гиперграфов (семейств конечных множеств), теории матроидов и теории графов.

Чтобы дать представление о современном состоянии теории структурной надежности сетей необходимо ввести ряд понятий из теории систем конечных множеств (гиперграфов), определить понятие Бернуллевского или независимого случайного множества (НСМ), и рассмотреть некоторые их свойства. Без этого экскурса невозможен обзор литературы по теме диссертации; кроме того, вводимые обозначения и сведения используются при описании результатов диссертации во введении и далее в основном тексте диссертации.

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

2. Айгнер М. Комбинаторная теория. М.: Мир, 1982.

3. Барзилович Е.Ю., Беляев Ю.К., Каштанов В.А., Коваленко И.Н., Соловьев А.Д., Ушаков И.А. Вопросы математической теории надежности. М.: Радио и связь, 1983.

4. Барлоу Р., Прошан Ф. Математическая теория надежности. М.: Сов. Радио, 1969.

5. Буртин Ю.Д. О вероятности связности случайного подграфа n-размерного куба // Проблемы передачи информации. 1977. Т. 13. N.2. С.90-95.

6. Гадасин В.А., Ушаков И.А. Надежность сложных информационно- управляющих систем. М.: Сов.Радио, 1975.

7. Гнеденко Б.В., Беляев Ю.К., Соловьев А.Д. Математические методы в теории надежности. М.: Наука, 1965.

8. Гнеденко Б.В., Козлов Б.А., Ушаков H.A. О роли и месте теории надежности в процессе создания сложных систем. В кн.: Теория надежности и массовое обслуживание. М.: Наука, 1969.

9. Кельманс А.К. Некоторые проблемы анализа надежности сетей // Автоматика и Телемеханика. 1965. Т.26. N.3. С.567-574,

10. Кельманс А.К. О связности вероятностных сетей // Автоматика и Телемеханика. 1967. Т.28. N.3. С.98-116.

11. Кельманс А.К. О свойствах характеристического многочлена графа // Кибернетика на службу коммунизму. 1967. М.-Л.,: Энергия.

12. Кельманс А.К. Об оценке вероятностных характеристик случайных графов // Автоматика и Телемеханика. 1970. Т.11. N.4. С.130-137.

13. Кельманс А.К. Асимптотические формулы для вероятности к-связности случайных графов // Теория вероятн. и ее прим. 1972. N.2. С.243-254.

14. Кельманс А.К., Ломоносов М.В., Полесский В.П. О минимальных покрытиях вматроиде // Проблемы передачи информации. 1976. Т.12. N.3. С.94-107.

15. Кельманс А.К., Полесский В.П. Экстремальные множества и задачи покрытия и упаковки в матроидах // Исследования по прикладной теории графов. Новосибирск: Наука. Сиб. отд., 1986. С.140-168.

16. Коваленко И.Н. К теории случайных графов // Кибернетика. 1971. Т.16. N.4. С.1-4.

17. Ломоносов М.В. Схема Бернулли с замыканием // Проблемы Передачи Информации. 1974. Т.10. N.1. С.91-101.

18. Ломоносов М.В, Полесский В.П. Верхняя граница надежности информационных сетей // Проблемы передачи информации. 1971. Т.7. N.4. С.78-81.

19. Ломоносов М.В., Полесский В.П. Нижняя оценка надежности сетей // Проблемы Передачи Информации. 1972. Т.8. N.2. С.47-53.

20. Ломоносов М.В., Полесский В.П. О максимуме вероятности связности // Проблемы передачи информации. 1972. Т.8. N.4. С.68-73.

21. Маргулис Г.А. Вероятностные характеристики графов с большой связностью // Проблемы Передачи Информации. 1974. Т.10. N.2. С.101-108.

22. Маршалл А., Олкин И. Неравенства. Теория мажоризации и ее приложения. М.: Мир, 1983.

23. Мур Ф., Шеннон К.Е. Надежные схемы из ненадежных реле // Киб. сб. 1960. N 1. Изд-во Иностр Лит-ры. Москва. С. 109-148.

24. Нечепуренко М.И., Попков В.К. и др. Алгоритмы и программы решения задач на графах и сетях. Новосибирск: Наука. Сиб. отд-ние, 1990.

25. Полесский В.П. Структурная надежность однородных вероятностных сетей // Управление сетями связи и синтез управляющих устройств. 1969. М.: Наука. С.16-21.

26. Полесский В.П. Об одном способе построения структурно-надежной сети // Дискретные автоматы и сети связи. 1970. М.: Наука. С.13-19.

27. Полесский В.П. Об одной нижней границе надежности информационных сетей //Тезисы докладов I Всесоюзного Симпозиума "Оценка надежности сетей связи и их элементов". 1970. Новосибирск. С.64-65.

28. Полесский В.П. Об одной нижней границе надежности информационных сетей // Проблемы передачи информации. 1971. Т.7. N.2. С.88-96.

29. Полесский В.П. Покрытие конечного графа минимальным числом лесов // Проблемы передачи информации. 1976. Т. 12. N.2. С.76-82.

30. Полесский В.П. Структура перешейков суммарного матроида // Проблемы передачи информации. 1976. Т.12. N.4. С.95-104.

31. Полесский В.П. Схемы вычисления приближенного значения характеристик связности в вероятностной модели устойчивости системы связи // Техника средств связи, серия "Системы связи". 1986. Вып.6. С.34-41.

32. Полесский В.П. Эффективные оценки характеристик связности систем со сложной структурой // Техника средств связи, серия "Системы связи". 1988. Вып.6. С.23-30.

33. Полесский В.П. Оценки вероятности связности случайного графа // Проблемы передачи информации. 1990. Т.26. N.1. С.90-98.

34. Полесский В.П. Оценки вероятности групповой связности случайного графа // Проблемы передачи информации. 1990. Т.26. N.2. С.87-97.

35. Полесский В.П. Нижние оценки вероятности связности в классах случайных графов, порожденных двусвязными графами с заданным базовым спектром // Проблемы передачи информации. 1992. Т.28. N.2. С.86-95.

36. Полесский В.П. Нижние оценки вероятности связности для некоторых классов случайных графов // Проблемы передачи информации. 1993. Т.29. N.2. С.85-95.

37. Полесский В.П. Границы двухполосной надежности и базовый спектр ее графа // Проблемы передачи информации. 1993. Т.29. N.3. С.86-100.

38. Полесский В.П. Нижние оценки вероятности полного ранга в случайном матроиде // Проблемы передачи информации. 1993. Т.29. N.4. С.58-66.

39. Полесский В.П. Достижимые границы вероятности полного ранга случайного подматроида // Проблемы передачи информации. 1995. Т.31. N.4. С.81-99.

40. Полесский В.П. Развязывания клаттеров, корреляционные неравенства и границы комбинаторной надежности//Проблемы передачи информации. 1997. Т.31. N.4. С.81-99.

41. Ревякин A.M. Теоретико-структурные свойства некоторых комбинаторных схем // Труды семинара по дискретной математике и ее приложениям. 1989. Издательство Московского Университета. С.44-49.

42. Степанов В.Е. Комбинаторная алгебра и случайные графы // Теория вероятн. и ее прим. 1970. Т.14. N.3. С.393-420.

43. Степанов В.Е. О вероятности связности случайного графа £m(t) // Теория вероятн. и ее прим. 1970. Т.15. N.l. С.56-68.

44. Степанов В.Е. Случайные графы// Вопросы кибернетики. 1973. Наука. Москва. С.164-185.

45. Форд JI., Фалкерсон Д. Потоки в сетях. М.: Иностр. Лит., 1966.

46. AboELFotoh H.F.M., Colbourn C.J. Series-parallel bounds for the two-terminal reliability problem // ORSA J.Comput. 1989. N.l. P.205-222.

47. Aho A.V., Hopcroft J.E, Ulam J.D. The Design and Analysis of Computer Algorithms. New York: Addison-Wesley, 1974.

48. Alon N., Spencer J.H., Erdos P. The Probabilistic Method. New York, etc: Jonh Wiley and Sons, INC., 1992.

49. Austin T.L., Eagen R.E., Penney W.F., Riordan J. The number of components in random linear graphs // Annals of Math. Stat. 1959. V.30. P.747-754.

50. Ball M.O. Complexity of network reliability computatuions // Networks. 1980. V.10. P.153-165.

51. Ball M.O., Coulborn C.J., Provan J.S. Network Reliability. In: Handbooks in OR and MS, Chapter 11. New York, etc: Elsevier Science B.V. 1995.

52. Ball M.O., Nemhauser G.L. Matroids and reliability analysis // Math. Operations Res.1979. V.4. N 2. P. 132-143.

53. Ball M.O., Provan J.S. Bounds on the reliability polynomial for shellable independence systems // SIAM J. on Algebraic and Discrete Methods. 1982. V.3. P.166-181.

54. Ball M.O., Provan J.S. Calculating bounds on reachability and connectedness in stochastic networks // Networks. 1983. V.13. P.253-278.

55. Barlow R.E. Mathematical theory of reliability: a historical perspective // IEEE Transactions on Reliability. 1984. R-33. P. 16-20.

56. Barlow R.E., Proschan F. Mathematical Theory of Reliability // New York London -Sydney: John Wiley and Sons Inc. 1965.

57. Barlow R.E., Proschan F. Statistical Theory of Reliability and Life Testing, to Begin With. Md: Silver Spring. 1981.

58. Birnbaum Z.W., Esary J.D., Saunders S.C. Multicomponent systems and structures and their reliability // Technometrics. 1961. N.l. P.55-77.

59. Bixby R. The minimum number of edges and vertecies in a graph with edge-connectivity N and MN-bonds // Networks. 1975. V.5. P.259-298.

60. Bollobas B. Random Graphs. London.: Academic Press, etc., 1985.

61. Brecht T.B., Colbourn C.J. Improving reliability bounds in computer networks // Networks. 1986. V.16. P.369-380.

62. Brecht T.K., Colbourn C.J. Lower bounds for two-terminal network reliability // Discr.Appl.Math. 1988. V.21. P.185-198.

63. Brooks R.L., Smith C.A.B., Stone A.H., Tutte W.T. The dissection of rectangles into squares // Duke Math.J. 1940. V.7. P.312-340.

64. Brown J.I., Colbourn C.J. A set system polynomial with colouring and reliability applications // SIAM J.Discr.Math. 1988. V.l. N.2. P.151-157.

65. Brown J.T., Colbourn C.J., Devit J.S. Transformations and Bounding Network Reliability // School of Math, and Statistics. Curtin Univ. of Technology, Technical Report 8/90. 1990.

66. Colbourn C.J. The Combinatorics of Network Reliability. Oxford New York: Oxford Univ.Press, 1987.

67. Colbourn C.J. Edge-packings of graphs and network reliability // Discrete Mathematics. 1988. V.72. P.49-61.

68. Colbourn C.J. A note on bounding k-terminal reliability // Algorithmica. 1992. V.7. P.303-310.

69. Colbourn C.J., Elmallah E.S. Reliable assignments of processors to tasks and factoring on matroids // Discr.Math. 1993. V.114, P.115-129.

70. Colbourn C.J., Nel L.D. Using and abusing for network reliability // Proc.IEEE Telecommunications Conference (Globecom90), IEEE Press. 1990. P.663-667.

71. Colbourn C.J, Provan J.S., Vertigan D. The complexity of computing the Tutte polynomial on transversal matroids // Technical Report UNC/OR/TR-91/2. 1991. University of North Carolina.

72. Colbourn C.J., Pulleybank. Matroid Steiner problems, the Tutte polynomial and network reliability // Journal of Combinatorial Theory, Series B. 1989. V.47. N1. P.20-31.

73. Daykin D.E. A simple proof of the Kruskal-Katona theorem // Jouranl of Combinatorial Theory. 1974. A 17. P.252-253.

74. Daykin D.E. A lattice is distributive iff \A\\B\ < \A V B\\A A B\ // Nanta Math. 1978. V.43. P.183-185.

75. Edmonds J. Minimum partition of a matroid into independent subsets // J.Res.Nat.Bur.Standards. 1965. Sect.69B. P.67-72.

76. Edmonds J. Edge-disjoint branching. In: Combinatorial Algorithms. Algorithmics Press. 1972.

77. Esary E.D., Proshan F. Coherent structures of non-identical components // Technometrics. 1963. V.5. P.191-209.

78. Erdos P., Renyi A. On random graphs I // Publ. Math. 1959. V.6. P.290-297.

79. Erdos P., Renyi A. On the evolution of random graphs // Publ. Math. Inst. Hung.Acad. Sci. 1960. V.5. P.17-61.

80. Erdos P., Spencer J. Evolution of the n-cube // Comput. Math. Appl. 1979. V.5. P.33-39.

81. Fortuin C.M., Kasteleyn P.W., Ginibre J. Correlation inequalities on some partially ordered sets // Comm. Math. Phys. 1971. V.22. P.89-103.

82. Frankl P. A new short proof for the Kruskal-Katona theorem // Discr.Math. 1984. V.48. P.327-329.

83. Garey M.R., Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. San-Francisco: W.H.Freeman, 1979.

84. Gilbert E.N. Random graphs // Annals Math. Stat. 30. 1959. P.1141-1144.

85. Gomory R.E., Hu T.C. Multiterminal network flows // SIAM J.Appl.Math. 1961. V.9. P.551-570.

86. Grimmet G.R. Random graphs. In: Selected Topics in Graph Theory 2. London: Academic Press, 1983.

87. Grimmet G. Percolation theory. Second edition. A series of Comprehensive Studies in Math. Berlin, etc.: Springer, 1999.

88. Guisfield D. Connectivity and edge-disjoint spanning trees // Information Processing Letters. 1983. V.16. P.87-89.

89. Holeyr I. The NP-completeness of some edge partition problems // SIAM J. on Computing. 1981. V.10. P.713-717.

90. Holyer I. The NP-completeness of edge-colouring // SIAM Journal on Computing. 1981. V.10. P.718-720.

91. Iri M. Application of Matroid Theory to Engineering Systems Problems. In: Proceedings of the Sixth Conference on Probability Theory, at Brasov, Roumania, Sept.10-15, 1979.

92. Iri M. A review of recent work in Japan on principal partitions of matroids and their applications // Annals of the New York Academy of Sciences. 1979. V.319. P.306-319.

93. Iri M., Tomizawa N. An algorithm for finding an optimal independent assignement //J. Oper. Res. Soc. Japan. 1976. V.19. P.32-57.

94. Karger D.R. A randomized fully polynomial time approximation scheme for the all terminal network reliability problem // Proceedings of the 37th Annual Symposium on the Foundations of Computer Science. 1996. P.l-13.

95. Karp R.M. Reducibility among combinatorial problems In: Complexity of Computer Computations, Plenum, 1972. P.85-103,

96. Katona G. A theorem of finite sets. In: Theory of Graphs, Akademia Kiado, Budapest, 1966. P.187-207.

97. Kelmans A.K., Polesskii V.P. Extremal sets and covering and packing problems in matroids. In: Selected Topics in Discrete Mathematics, Proceeding of the Moscow Discrete mathematics Seminar. AMS Translation Series 2, V. 158, 1994. P.149-174.

98. Knuth D.E. Matroid partitioning // Preprint. STAN-CS-73-342. Stanford University.1973.

99. Kordecki W. Probability of the connectedness of random graphs // Prace Naukowe Inst.Mat.Fiz. Teor.Pol. 1973. P.55-65.

100. Koronski M. A review on random graphs // Journal of Graph Theory. 1982. V.6. P.349-389.

101. Koronski M. Random Graphs // Handbook of Combinatairics. 1991.

102. Kruskal J.B. The number of simplices in a complex. In: Mathematical Optimization Techniques. University of California Press. 1963.

103. Kundu S. Bounds on the number of disjoint trees // Journal of Combinatorial Theory.1974. V.B17. P.199-203.

104. Lawler E. Combinatorial Optimization: Networks and Matroids. New York: Holt, Rinehart, and Winston, 1976.

105. Lawler E.L. Matroid intersection algorithms // Math. Programminig. 1976. V.9. P.31-56.

106. Lovasz L., Recski A. On she sum of matroids // Acta Math. Acad. Sci. Hungar. 1973.N 24. P.329-333.

107. McDiarmid C. Some inequalities for random graphs and percolation // Nyas Gtd Notes XIII. 1987. P.9-13.

108. McDiarmid C. Clutter percolation and random graphs // Mathematical Programming Study. 1980. V.13. P.17-25.

109. McDiarmid C. General percolation and random graphs // Adv.Appl.Prob. 1981. V.13. P.40-60.

110. Moore E.F., Shannon C.E. Reliable circuits using less reliable relays // J.Franklin Inst., 262, N.3, 1956, 191-208; N.4, 281-297.

111. Nakamura N., Iri M. A Structural Theory for Submodular Functions, Polymatroids and Polymatroid Intersections // Research Memorandum RMI, 1981. P.66-81.

112. Nash-Williams C.St.J.A. An application of matroids to graph theory // Theorie des Graphes. Congr.Internat.d'Etudes (Rome, 1966), Dunod, Paris. 1967. P.263-265.

113. Oxley J.G., Welsh D.J.A. On some percolation results of J.M.Hammersley // Journal of Applied Prob. 1979. V.16. P.526-540.

114. Palmer E.M. Graphical Evolution: An Introduction to the Theory of Random Graphs. New York: John Wiley and Sons, 1985.

115. Provan J.S. The complexity of reliability computations in planar and acyclic graphs // SIAM J.Comput. 1986. V.15. N.3. P.694-702.

116. Provan J.S., Ball M.O. The complexity of counting cuts and of computing the probability that a graph is connected // SIAM J.Computing. 1983. V.12. P.777-788.

117. Ramanathan A., Colbourn C.J. Bounds of all-terminal reliability via arc-packing // Ars Combinatorica. 1987. V.23A. P.91-94.

118. Seymour P.D. Matroids, Hypergraphs and the Max-Flow Min-Cut Theorem. D.Phil.Thesis, University of Oxford, 1975.

119. Shier D.R. Network Reliabilty and Algebraic Structures. Oxford: Claredon Press, 1991.

120. Valiant L.G. The comlexity of enumeration and reliability problems // SIAMJ.Computing. 1979. V.8. P.410-421.

121. Van Slyke R.M., Frank H. Network reliability analysis: part I // Networks. 1972. V.l. P.279-290.

122. Vertigan D. The computational complexity of Tutte invariants for planar graphs // Preprint, Mathematical Institute, Oxford University, 1994.

123. Weber K. Random graphs. Rostock, Math.Kolloq.21. 1982. P.83-98.

124. Welsh D.J. Matroid theory. Academic Press, 1976.

125. Wilkov R.S. Analysis and design of reliable computer networks // IEEE Trans. Comm. COM-20. 1972. P.660-678.

126. Wood R.K. Factoring algorithms for computing K-terminal network reliability // IEEE Transactions on Reliability, R-35. 1986. P.269-178.fite. 0.1.1(3УзРле. а1y¡ X -TT4 зк ilt