Задачи теории экстремальных графов и их применение при разработке и исследовании алгоритмов синтеза топологической структуры сетей ЭВМ тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Белоцерковский, Дмитрий Леонидович

• Белоцерковский, Дмитрий Леонидович
• кандидат физико-математических наук
• 1998

Оглавление диссертации кандидат физико-математических наук Белоцерковский, Дмитрий Леонидович

ОГЛАВЛЕНИЕ

Стр.

Введение

Глава 1. ЗАДАЧИ ТЕОРИИ ЭКСТРЕМАЛЬНЫХ ГРАФОВ ДЛЯ РАЗРАБОТКИ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ ТОПОЛОГИЧЕСКОЙ ОПТИМИЗАЦИИ СЕТЕЙ ЭВМ

1.1. Теория экстремальных графов и ее применение для разработки алгоритмов синтеза топологии сетей ЭВМ и решения других

практических задач

1.2 Основные цели и задачи диссертационной работы

1.3. Алгоритм генерации двусвязных остовных подграфов для оптимизации топологии сети ЭВМ

1.3.1. Введение и постановка задачи

1.3.2. Необходимые и достаточные условия двусвязности для графов с диаметром не превосходящим 3

1.3.3. Описание алгоритма для графов с диаметром не превосходящим 2

1.3.4. Описание алгоритма для графов с диаметром не превосходящим 3

Выводы

Глава 2. ХАРАКТЕРИЗАЦИЯ ЭКСТРЕМАЛЬНЫХ ГРАФОВ С ДИАМЕТРОМ НЕ ПРЕВОСХОДЯЩИМ 3

2.1. Постановка задачи

2.2. Поиск экстремальных графов, в которых после удаления вершины или ребра диаметр не превосходит 3

2.2.1. Основные утверждения

2.2.2. Поиск п — вершинных экстремальных графов, если 4 < п < 7

2.2.3. Поиск п — вершинных экстремальных графов, если п > 8 и для которых минимальная степень вершины равна 2

2.2.4. Поиск п — вершинных экстремальных графов, если п > 8 и для которых минимальная степень вершины равна 3

2.3. Поиск экстремальных графов с диаметром не превосходящим 2, в которых после удаления вершины или ребра диаметр не превосходит 3

2.3.1. Основные утверждения

2.3.2. Поиск п — вершинных экстремальных графов, если п < 7 и п > 10

2.3.3. Поиск п — вершинных экстремальных графов, если 8 < п < 9

2.4. Сравнительный анализ нижней границы количества ребер для множеств графов с данными свойствами

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

2.5.1. Поиск экстремальных графов с диаметром не превосходящим 3, в которых после удаления вершины или ребра диаметр не превосходит 4

2.5.2. Определение нижней границы количества ребер для множеств графов с данными свойствами

Выводы

ГЛАВА 3. НАХОЖДЕНИЕ НИЖНЕЙ ГРАНИЦЫ КОЛИЧЕСТВА РЕБЕР ДЛЯ НЕКОТОРЫХ ГРАФОВ С ДИАМЕТРОМ ПРЕВОСХОДЯЩИМ 3

3.1. Постановка задачи

3.2. Поиск экстремальных графов с диаметром не превосходящим 4, в которых после удаления вершины или ребра диаметр не превосходит 6

3.3. Поиск экстремальных графов с диаметром не превосходящим 4, в которых после удаления вершины или ребра диаметр не превосходит 5

3.3.1. Нахождение нижней границы числа ребер в п — вершинных экстремальных графах при 7 < п < 12

3.3.2. Нахождение нижней границы числа ребер в п — вершинных экстремальных графах при п > 13 и в которых имеется V — нить при > 4

3.3.3. Нахождение нижней границы числа ребер в п — вершинных экстремальных графах при п > 13 и в которых имеется I' — нить при V = 3

3.3.4. Нахождение нижней границы числа ребер в п — вершинных экстремальных графах при п > 13 и в которых имеется /' — нить

при V = 2

3.4. Сравнительный анализ нижней границы количества ребер для

множеств графов с данными свойствами

Выводы

ГЛАВА 4. О ЗАДАЧЕ НАХОЖДЕНИЯ ЗНАЧЕНИЯ НИЖНЕЙ ГРАНИЦЫ ЧИСЛА РЕБЕР В ДВУСВЯЗНЫХ ГРАФАХ С ПРОИЗВОЛЬНЫМ ДИАМЕТРОМ

4.1. Постановка задачи и основной результат

4.2. Схема доказательства теоремы

4.2.1. Доказательство теоремы для случая нечетных значений диаметра с?

4.2.2. Доказательство теоремы для случая четных значений диаметра й

4.3. Следствия теоремы

4.4. Свойство операции удаления произвольного ребра в двусвязном графе с фиксированным диаметром

Выводы

ЗАКЛЮЧЕНИЕ

ЛИТЕРАТУРА

РИСУНКИ

-5-

Введение диссертации (часть автореферата) на тему «Задачи теории экстремальных графов и их применение при разработке и исследовании алгоритмов синтеза топологической структуры сетей ЭВМ»

ВВЕДЕНИЕ

Актуальность темы. В последнее время из-за непрерывного роста объема перерарабатываемой информации значение сетей ЭВМ чрезвычайно возросло. Поэтому использование сетей ЭВМ предъявляет к последним жесткие требования по времени доставки информации, надежности и экономичности. Весь комплекс требований к сетям ЭВМ решается в процессе их проектирования. Различным аспектам проектирования сетей ЭВМ посвящены работы [16,19].

Одной из важнейших задач, решаемых при проектирования сети ЭВМ, является задача топологической оптимизации сети. Задача выбора топологической структуры сети является основной подзадачей топологической оптимизации сети ЭВМ,, которую называют также задачей синтеза топологии сети.

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

Разработка алгоритмов синтеза топологии сети основывается на результатах из области теории экстремальных графов.- Под" экстремальными графами понимаются графы, на которых требуемые свойства достигаются при минимальном (максимальном) числе, ребер [27].

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

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

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

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

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

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

— решить задачу характеризации экстремальных двусвязных графов с диаметром не превосходящим 3;

— решить задачу нахождения нижней границы для двусвязных графов с диаметром не превосходящим 4;

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

— доказать теорему об изменении диаметра после удаления из графа произвольного ребра.

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

комбинаторного анализа, теории алгоритмов, оптимизации на графах и сетях.

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

Новыми научными результатами являются:

— разработка алгоритмов генерации двусвязных графов с диаметром не превосходящим 2 и 3;

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

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

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

Практическая ценность. Разработанные в диссертационной работе алгоритмы генерации двусвязных графов с диаметром, не превосходящим 3, а также полученные нижние оценки числа ребер в графах с ограничениями на диаметр и связность, предназначены для решения задачи синтеза топологии сети с ограничениями на надежность. Задача синтеза топологии сети является важной частью практической задачи общей топологической оптимизации сетей ЭВМ. Таким образом, полученные в диссертационной работе результаты могут быть использованы для задачи топологического проектирования сетей ЭВМ.

Апробация работы. Основные положения работы докладывались и обсуждались на 15-й и 16-й школах-семинарах по теории графов (Одесса, 1993 — 1994), на IX Всероссийской конференции по математическому программированию и приложениям (Екатеринбург, 1995), на Втором Сибирском Конгрессе по прикладной и индустриальной математике (Новосибирск, 1996), на IV международном форуме по информатизации (Санкт-Петербург, 1996), на Международной конференции "Distributed Computer Communication Networks. Theory and Applications." (Тель-Авив, 1996), на XIII Международной конференции "Массовое обслуживание. Потоки, системы, сети"(Минск, 1997), на совместном болгаро-российском семинаре "Methods and algorithms for distributed information systems design. Theory and Applications." (София, 1997), на международной конференции "Distributed Computer Communication Networks. Theory and Applications." (Тель-Авив, 1997).

Публикации. По теме диссертации опубликовано 13 печатных работ, из них 3 статьи в реферируемых научно — технических журналах.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, изложенных ца 251 страницах, содержит 61 рисунок, 1 таблицу и список цитируемой литературы из 108 наименований на 7 страницах. Структура и содержание глав отражены в оглавлении диссертации.

Заключение диссертации по теме «Теоретические основы информатики», Белоцерковский, Дмитрий Леонидович

-249-Выводы

1. Сформулированы несколько важных проблем из области теории экстремальных графов, часть из которых не решена до сих пор.

2. Сформулирована в качестве теоремы задача нахождения точной нижней границы числа ребер в двусвязных графах с произвольным диаметром.

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

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

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

6. Установлена зависимость между диаметром графа и диаметром графа после удаления произвольного ребра, которая сформулирована в качестве теоремы.

- 250 -ЗАКЛЮЧЕНИЕ

В диссертационной работе получены следующие основные результаты:

1. Сделан обзор литературы в области теории экстремальных графов. Сформулированы основные проблемы теории экстремальных графов и разработаны методы их решения.

2. Сформулирована задача из области теории экстремальных графов, связанная с задачей синтеза сети минимальной стоимости с ограничениями на надежность.

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

4. Разработаны алгоритмы генерации двусвязных графов с диаметром не превосходящим 2 и 3.

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

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

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

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

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

10. Установлена зависимость между диаметром графа и диаметром графа после удаления произвольного ребра.

Список литературы диссертационного исследования кандидат физико-математических наук Белоцерковский, Дмитрий Леонидович, 1998 год

-252-ЛИТЕРАТУРА

1. Белоцерковский Д.Л. Об одной задаче перечисления экстремальных графов // Дискрет, анализ и исслед. операций. Сер. 1. 1998. Т.5, N2. С. 3 — 27.

2. Белоцерковский Д.Л. Об одной задаче определения минимального числа ребер в экстремальных графах // Дискрет, анализ и исслед. операций. Сер. 1. 1997. Т.4, N4. С. 98 - 99.

3. Белоцерковский Д.Л., Вишневский В.М. Новый алгоритм генерации остовных двусвязных подграфов для оптимизации топологии сетей передачи данных //

Автоматика и телемеханика. 1997. N1. С. 108 — 120.

4. Белоцерковский Д.Л. Об одной задаче теории экстремальных графов // Сб. труд. 13 школы — семинара по теории массового обслуживания

(BWWQT-97). Минск. 1997. С. 11.

5. Белоцерковский Д.Л. Характеризация некоторых экстремальных графов с диаметром, не больше трех // Тез. докл. Второй Сиб. конгресс ИНПРИМ — 96. Новосибирск: Ин — т математики СО РАН. 1996. С. 113.

6. Белоцерковский Д.Л. О характеризации некоторых экстремальных графов с диаметром не превосходящим 3 // Проблемы теоретической кибернетики. Тез.

докл. XI Междунар.конф. Москва: ГК РФ по ВО. 1996. С.23 - 24.

7. Белоцерковский Д.Л. Модифицированный алгоритм генерации остовных двусвязных подграфов заданного графа // Информационный бюллетень... Ассоциация мат.прогр.: Тез. конф. "Математическое програмирование и приложения". Екатеринбург: Ин — т математики и механики УрОРАН. 1995. Вып.5. С.39-40.

8. Вишневский В.М., Белоцерковский Д.Л. Об одном алгоритме генерации остовных двусвязных подграфов для топологической оптимизации сетей передачи данных // Труды Второй междунар. конф. "Новые информационные

технологии в образовании". Минск. 1996. С. 341 — 348.

9. Вишневский В.М., Савинецкий А.Б., Федотов Е.В. Анализ и реализация одного метода повышения производительности сети пакетной коммутации // АиВТ. 1987. N 2. С. 24 - 30.

10. Вишневский В.М., Талалай А.И. Об одном методе топологического проектирования сети связи // Теория и техника автоматизированных систем массового ослуживания / МДНТП. М., 1982. С. 77 - 81.

11. Вишневский В.М., Федотов Е.В. Диалоговая система топологического проектирования сети связи ЭВМ // Вычислительные сети коммутации

пакетов, Рига: Ин — т электроники и вычисл. техники. 1983. С. 25 — 29.

-25312. Вишневский В.М., Федотов Е.В. Комбинаторный алгоритм синтеза топологической структуры сети пакетной коммутации // 12-й Всесоюзный семинар по вычислительным сетям. М., 1987. С. 48 — 53.

13. Вишневский В.М., Федотов Е.В. Оптимизация топологической структуры информационно — вычислительных сетей / / Распределенные автоматизированные системы массового обслуживания. Кишинев: Картя

молдавенянскэ. 1987. С. 91 — 93.

14. Вишневский В.М., Федотов Е.В. Топологическое проектирование сетей пакетной коммутации // ИППИ РАН. Москва. 1992.

15. Диниц Е.А., Зайцев М.А. О генерации помеченных деревьев и разделительных сетей // Алгоритмические исследования в комбинаторике.

М.: Наука. 1978. С. 100-107.

16. Жожикашвили В.А., Вишневский В.М. Сети массового обслуживания. Теория и применение к сетям ЭВМ. М.: Радио и связь. 1988.

17. Зайченко Ю.П. Задачи проектирования структуры распределенных вычислительных сетей // АиТ. 1981. N 4. С. 27 - 40.

18. Зыков А.А. Теория конечных графов. Т.1. — Новосибирск: Наука, 1969. — 543с.

19. Клейнрок Л. Вычислительные системы с очередями. М.: Мир, 1979.

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

- 321с.

21. Макаров А.В. Разработка методов и комплекса программ для проектирования топологии базовых вычислительных сетей с учетом структурной надежности в распределенных АСУ: Автореф. дисс. на соис. уч.ст.канд.техн.наук. М., 1986.

- 24с.

22. Ope О. Теория графов. - М.: Наука, 1968. - 352с.

23. Рейнгольд Э., Нивергельдт Ю., Део М. Комбинаторные алгоритмы. Теория и практика. - М.: Мир, 1980. - 476с.

24. Фараджев И.А. Генерирование неизоморфных графов с заданным распределением степеней вершин // Алгоритмические исследования в комбинаторике. М.: Наука. 1978. С. 11 — 19.

25. Федотов Е.В. Алгоритм генерации помеченных графов с заданными свойствами // II — я Всесоюзная школа — семинар по выислительным сетям. Научный совет по комплексной проблеме "Кибернетика" АН СССР. М., 1986. С. 52 - 54.

26. Федотов Е.В. Разработка и исследование алгоритмов синтеза топологической структуры сетей передачи данных автоматизированных систем массового

-254-

обслуживания // ИПУ РАН. Москва. 1988.

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

28. Харари Ф., Палмер Э. Перечисление графов. — М.: Мир, 1977.

29. Шувиков В.И. Минимальное число ребер в двусвязных графах с заданным диаметром // Принципы построения устройств распределения информации. М.: Наука. 1978. С. 87 - 90.

30. Agrawal D.P. Graph theoretical analysis and design of multistage interconnection networks // IEEE Trans. Comput. 1983. Vol.C-32. P. 637-648.

31. Ahlswede R., Gargano L. and others. Fault-tolerant minimum broadcast networks. Networks. 1996. Vol.27, No.4. P. 293 - 307.

32. Ball M.O. Complexity of network reliability computations // Networks. 1980. Vol.10. P. 153-165.

33. Ball M.O., Colbourn C.J., Provan J.S. Network reliability // M.O. et al., Eds., Handbooks in OR & MS. 1995. Vol.7, Chapter 11. P. 673-762.

34. Belozerkovskii D.L. About a problem of extremal graphical enumeration with diameter at most 3 // International Conference in Informational Networks and Systems ICINAS-96. St. Petersburg. 1996. P. 411-422.

35. Belotserkovskii D.L. Characterization of some extremal graphs with diameter no greater than three // Discrete Math. Appl. 1997. Vol.7, No.2. P. 163-176.

36. Bermond J.-C., Bollobas B. The diameter of graphs- a survey // Proc. 12-th Southeastern Conference. Congressus Num. 1981. Vol.32. P. 3-27.

37. Bermond J.-C., Bond J., Djelloub S. Dense bus networks of diameter 2 // Interconnect. Networks and Mapp. Schedul. Parall. Comput.: DIMACS Workshop.

1995. P. 9-18.

38. Bermond J.-C., Bond J., Paoli M., Peyrat C. Graphs and interconnection networks: diameter and vulnerability. In surveys in combinatorics: Proc. 9-th British Combinatorial Conference. London Math. Soc., Lec. Notes Ser .1983. Vol.82. P. 1- 30.

39. Bremond J.-C., Homobono N., Peyrat C. Large fault-tolerant interconnection networks // Graphs and Combinatorics. 1989. Vol.5. P. 107-123.

40. Boesch F.T. Graph theoretic models for network reliability studies // Technical Report 8010, Electrical Engineering and Computer Science Department, Stevens

Inst. Tech. Hoboken, New Jersey. 1983.

41. Boesch F.T. Large-scale networks: theory and design. - New York: IEEE Press. 1976. - 483 p.

42. Bollobas В. A problem in the theory of communications networks // Acta Mathematica Acad. Sci. Hung. 1968. Vol.19. P. 75-80.

43. Bollobas B. Extremal graph theory. - London: Acsd. Press, 1978. - 488p.

44. Bollobas B. Graphs of given diameter // Proceedings of Colloquium Held at Tihany. 1968. P. 36-39.

45. Bollobas B. Graphs with given diameter and maximal valency // Comb. Math. Appl. D.J.A. Welsh, Ed. Academic Press. New York, N.J. 1969. P. 25-37.

46. Bollobas B. Graphs with given diameter and minimal degree // Ars combinatoria. 1976. Vol.2. P. 3-9.

47. Bollobas B. Strongly two connected graphs // Congr. Numerantium XYII. Proc. Seventh Southeastern Conf. Combinatorics, Graph Theory, Comput. Baton Rouge, La. F. Hoffman et al., Eds. Utilitas Math.. Winnipeg, Manitoba, Canada. 1976. P. 161-170.

48. Bollobas B., Eldridge S.E. On graphs with diameter 2 // J. Comb. Theory (B). 1976. Vol.21. P. 201-205.

49. Bollobas B., Harary F. Extremal graphs with given diameter and connectivity // Ars Combinatoria. 1976. Vol.1. P. 281-296.

50. Bond J., Peyrat C. Diameter vulnerability in networks // Proc. of Kalamazoo Colloquium. 1984. Graph theory and its applications to algorithms and computer

science. P. 123-149. New York, Wiley 1985.

51. Bondy J.A., Murty U.S.R. Extremal graphs of diameter 2 with prescribed minimum degree // Stud. Sci. Math. Hung. 1972. Vol.7. P. 239-241.

52. Bondy J.A., Murty U.S.R. Graph theory with applications. - Macmillan, London, England, 1976.

53. Bondy J.A., Murty U.S.R. Graph theory with applications. - North-Holland, New York, 1980. - 44p.

54. Boorstyn R.R., Frank H. Large-scale network topological optimization // IEEE Trans, on Commun. 1977. Vol.25, No.l. P. 29-47.

55. Bukowski J.V. On the determination of large scale system reliability // IEEE Trans. Syst.Man Cybern. 1982. Vol.SMC-12. P. 538-548.

56. Caccetta L. Characterization of extremal graph of diameter 4 - II // Ars combinatoria. 1979. Vol.7. P. 301-317.

57. Caccetta L. Extremal graphs of diameter 3 // J. Austral. Math. Society. 1979. Vol. A28, No. 1. P. 63-84.

58. Caccetta L. Extremal graphs of diameter 4 // J. Combinatorial Theory. 1976. Vol. B21, No. 1. P. 104-115.

59. Caccetta L. On extremal graphs with given diameter and connectivity // Annals of New York Acad, of Sci. Topics in graph theory. 1979. Vol.328. P. 76-94.

60. Caccetta C. On extremal graphs // Proc. Eighth Southeastern Conf. Comb. Graph

Theory and Comput., Baton Rouge, La., F. Hoffman et al., Eds. Utilitas Mathematica Publishing. 1977. P. 125-137.

61. Caccetta C., Haggkvist R. On diameter critical graphs // Discrete Math. 1979. Vol.28. P. 223-229.

62. Caccetta C., Kraetzl M. Blocking probabilities of certain classes of channel graphs // V.R. Kulli (ed.), Advances in Graph Theory. Vishwa International, Deily. 1991. P. 70-103.

63. Chartrand G. A graph theoretic approach to a communications problem // SIAM J. Appl.Math. 1966. Vol.14. P.778-781.

64. Chudnovsky D.V., Chudnovsky G.V., Denneau M.M. Regular graphs with small diameter as models for interconnection networks // 3rd Int. Conf. on Supercomputing Boston. 1988. P. 232-239.

65. Chung F.R.K. Diameter of communication networks // Proceedings of Symposia in Applied Mathematics. 1986. Vol.34. P. 1-18.

66. Chung F.R.K. Graphs with small diameter after edge deletion. 1988. Preprint.

67. Colbourn C.J., Lomonosov M.V. Renewal networks: connectivity and reliability on a

time interval // Probab. Engrg. Inf. Sci. 1991. Vol.5. P. 361-368.

68. Doty K.W. New designs for dense processor interconnection networks // IEEE Trans, on Comput. 1984. Vol.C-33, No.5. P. 447-450.

69. Erdos P., Renyi A. Assymmetric graphs // Acta Math. Acad. Sci. Hungar. 1963. Vol.14, P. 295-315.

70. Erdos P., Fajtlowicz, Hoffman A.J. Maximum degree in graphs of diameter 2 // Networks. 1980. Vol.10. P. 87-90.

71. Esfahanian A.H. Lower-bounds on the connectivities of a graph //J. Graph Theory.

1985. Vol.9. P. 503-511.

72. Esfahanian A.H., Hakimi S.L. On computing the connectivities of graphs and digraphs // Networks. 1984. Vol.14. P. 355-366.

73. Myrvold W.J., K.H. Cheung, L. Page and J. Perry. Uniformly relliable graphs do

not always exist // Networks. 1991. Vol.21. P. 417-419.

74. Frank H., Chou W. Routing in computer networks // Networks. 1971. Vol.1, No.l. P. 99-122.

75. Frank H., Frish I.T., Chou W. Topological considerations in the design of the ARPA computer network // AFIPS Conf. (Montvale, New Jersey, 1970). New York: AFIPS Press. 1970. Vol.36. P. 581-587.

76. Gerla M. Approximations and bounds for the topological design of distributed computer networks // 4 th Data Commun. Sym. New York. 1975. P. 4/9-4/15.

77. Gerla M., Kleinrock L. On the design of distributed computer networks //IEEE

-257-

Trans. on Commun. 1977. Vol.25, No.l. P. 48-53.

78. Glivjak F. On the impossibility to construct diametrically critical graphs by extensions //Arch. Math. (Brno). 1975. Vol.11. P. 131-137.

79. Goemans M.X., Coldberg A.V., Plotkin S. and others. Improved approximation algorithms for network design problems // Proc. 5th Annu. ACM-SIAM symp. Discrete Algorithms, Arlington. 1994. P. 223 - 232.

80. Goldsmith D.L. On the N-th order edge-connectivity of a graph // Congressus Numerantium. 1981. Vol.32. P. 375-382.

81. Goldsmith D.L., Entringer R.C. A sufficient condition for equality of edge-connectivity and the minimum degree of a graph //J. Graph Theory. 1979. Vol.3. P. 251-255.

82. Goldsmith D.L., White A.T. On graphs with equal edge-connectivity and minimum degree // Discrete Math. 1978. Vol.23. P. 31-36.

83. Imase M., Soneoka T., Okada K. Connectivity of directed regular graphs with small diameter // IEEE Trans, on Comput. 1985. Vol. C-34. P.267-274.

84. Kel'mans A.K. The graph with the maximum probability of remaining connected depends on the edge-removal probability//Graph Theor Newslett. 1979. Vol.9.P.2-3.

85. Lomonosov M.V., Polesskii V.P. Lower bound of network reliability // Probl. Inf. Transm. 1972. Vol.8. P. 118-123.

86. Madhumangal Pal, Bhattacharjee G.P. A data structure on interval graphs and its applications //J. Circuits, Systems and Computers. 1997. Vol.7, No.3. P. 165-175.

87. Murty U.S.R. Critical graphs of diameter 2 // Math. Mag. 1968. Vol.41. P. 138-140.

88. Murty U.S.R. "Extremal Graph Theoretic Problems with Applications". Ph.D.Thesis. Calcutta. 1966.

89. Murty U.S.R. Extremal nonseparable graphs of diameter 2 // Proof Techniques in Graph Theory. (F. Harary, Ed.). - Academic Press, New York, 1969.

90. Murty U.S.R. On some extremal graphs // Acta Mathematica Acad. Sci. Hung. 1968. Vol.19. P. 67-74.

91. Peyrat C. Diameter vulnerability of graphs // Discrete Appl. Math. 1984. Vol.9. P. 245-250.

92. Plesniak J. Critical graphs of given diameter // Acta. Fac. Rerum Natur. Univ. Comenian Math. 1975. Vol.30. P. 71-93.

93. Plesniak J. The complexity of designing a network with minimum diameter // Networks. 1981. Vol.11. P. 77-85.

94. Provan J.S. Bounds on the reliability of networks // IEEE Trans. Reliab. 1986. Vol.R-35. P. 260-268.

95. Qiao Li, Yi Zhang. Restricted connectivity and restricted fault diameter of some

interconnection networks // Interconnect. Networks and Mapp. Schedul. Parall. Comput.: DIMACS Workshop. 1995. P. 267-273.

96. Schumacher U. An algorithm for construction of a k-connected graph with minimum number of edges and quasiminimal diameter // Networks. 1984. Vol.14. P. 63-74.

97. Steiglitz K., Weiner W., Kleitman D.J. The design of minimum cost survivable networks // IEEE Trans. Circuit Theory. 1969. Vol. CN-16, No.4. P. 445-460.

98. Toueg S., Streiglitz K. The design of small-diameter networks by local search // IEEE Nrans. Comput. 1979. Vol.C-28. P. 537-542.

99. Usami Y. Extremal graphs of diameter at most G after deleting onvy vertex //J. Graph Theory. 1985. Vol.9, No.2. P. 221-234.

100. Usami Y. Extremal graphs of diameter at most 8 after any vertex // Utilitas Mathematica. 1986. Vol.3. P. 153-180.

101. Vijay an K., Murty U.S.R. On accessibilityin graphs//Saukhya. 1964. Vol.26. Ser.A. P. 279-302.

102. Vishnevsky V.M., Belotserkovsky D.L. Description of some extremal graphs for topology optimization algorithms of a data communication network / / Proceedings of the International Conference DCCN. Theory and Applications. Tel-Aviv (Israel).

1997. P. 222-229.

103. Vishnevsky V.M., Belotserkovski D.L. Extremal graph theory and its application for problem of topology synthesis of data network / / Methods and Algorithms for Distributed Information Systems Design. Theory and Applications. Sofia, Bulgaria.

1997. P. 99-103.

104. Vishnevsky V.M., Belotserkovski D.L. On an algorithm of topological optimization of data networks // Proceedings of the International Conference DCCN. Theory

and Applications. Tel-Aviv (Israel). 1996. P. 131-138.

105. Vishnevsky V., Fedotov E. Generation of biconnected graphs with given properties// 16th IFIP Conference on System Modelling and Optimizition, Compiegne (France). 1993. Vol.2. P. 553-557.

106. Wang D.L., Kleitman D.L. On the existence of n-connected graphs with prescribed

degrees (n > 2) // Networks. 1973. Vol.3, No.2. P. 225-239.

107. Wittie L.D. Communication structures for large networks of microcomputers //

IEEE Trans. Comput. 1981. Vol.C-30. P. 264-273.

108. Yaged B. Minimum cost routing for static network models. Networks. 1971. Vol. 1, No.l. P. 139 - 172.

РМСУМКИ

рис.15

рис.16

рис.17

рис.18

рис.19

рис.20

рис.21

рис.22

рис.23

рис.24

рис. 25

рис. 26

рис. 27

рис.28

рис. 29

рис.30

рис.31

рис.35

рис.38

рис.36

рис.39

рис.41

рис.42

рис.44

рис.45

f--"Ф

рис.34

о-

-о

рис.37

рис.43

рис.50

рис.51

рис.52

рис.56

рис.57

xa

Г

xa

рис.59

рис.60

рис.61