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

• Автор: Белоцерковский, Дмитрий Леонидович
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 1998
• Место защиты: Москва
• Количество страниц: 263 с. : ил.

ОГЛАВЛЕНИЕ

Введение
Глава 1. ЗАДАЧИ ТЕОРИИ ЭКСТРЕМАЛЬНЫХ ГРАФОВ ДЛЯ РАЗРАБОТКИ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ ТОПОЛОГИЧЕСКОЙ ОПТИМИЗАЦИИ СЕТЕЙ ЭВМ
1.1. Теория экстремальных графов и ее применение для разработки алгоритмов синтеза топологии сетей ЭВМ и решения других
практических задач
1.2 Основные цели и задачи диссертационной работы
1.3. Алгоритм генерации дву связных остовных подграфов для оптимизации топологии сети ЭВМ
1.3.1. Введение и постановка задачи
1.3.2. Необходимые и достаточные условия двусвязности для графов с диаметром не превосходящим
1.3.3. Описание алгоритма для графов с диаметром не превосходящим
1.3.4. Описание алгоритма для графов с диаметром не превосходящим
Выводы
Глава 2. ХАРАКТЕРИЗАЦИЯ ЭКСТРЕМАЛЬНЫХ ГРАФОВ С ДИАМЕТРОМ НЕ ПРЕВОСХОДЯЩИМ
2.1. Постановка задачи
2.2. Поиск экстремальных графов, в которых после удаления вершины или ребра диаметр не превосходит
2.2.1. Основные утверждения
2.2.2. Поиск п — вершинных экстремальных графов, если 4 < п <
2.2.3. Поиск п — вершинных экстремальных графов, если п > 8 и для которых минимальная степень вершины равна
2.2.4. Поиск п — вершинных экстремальных графов, если п > 8 и для которых минимальная степень вершины равна
2.3. Поиск экстремальных графов с диаметром не превосходящим 2, в которых после удаления вершины или ребра диаметр не превосходит
2.3.1. Основные утверждения
2.3.2. Поиск п — вершинных экстремальных графов, если п <7 и п >
2.3.3. Поиск п — вершинных экстремальных графов, если 8 < п <
2.4. Сравнительный анализ нижней границы количества ребер для множеств графов с данными свойствами
2.5. Нахождение нижней границы числа ребер и поиск экстремальных графов для множеств графов с диаметром не превосходящим 3, для которых после удаления вершины или ребра диаметр превосходит
2.5.1. Поиск экстремальных графов с диаметром не превосходящим 3, в которых после удаления вершины или ребра диаметр не превосходит
2.5.2. Определение нижней границы количества ребер для множеств графов с данными свойствами
Выводы
ГЛАВА 3. НАХОЖДЕНИЕ НИЖНЕЙ ГРАНИЦЫ КОЛИЧЕСТВА РЕБЕР ДЛЯ НЕКОТОРЫХ ГРАФОВ С ДИАМЕТРОМ ПРЕВОСХОДЯЩИМ
3.1. Постановка задачи
3.2. Поиск экстремальных графов с диаметром не превосходящим 4, в которых после удаления вершины или ребра диаметр не превосходит
3.3. Поиск экстремальных графов с диаметром не превосходящим 4, в которых после удаления вершины или ребра диаметр не превосходит
3.3.1. Нахождение нижней границы числа ребер в п — вершинных экстремальных графах при 7 < гс <
3.3.2. Нахождение нижней границы числа ребер в п — вершинных экстремальных графах при п> 13 и в которых имеется Г — нить при Г >
3.3.3. Нахождение нижней границы числа ребер в п — вершинных экстремальных графах при п > 13 и в которых имеется V — нить при Г
3.3.4. Нахождение нижней границы числа ребер в п — вершинных экстремальных графах при п > 13 и в которых имеется V
при V
3.4. Сравнительный анализ нижней границы количества ребер для
множеств графов с данными свойствами
Выводы
ГЛАВА 4. О ЗАДАЧЕ НАХОЖДЕНИЯ ЗНАЧЕНИЯ НИЖНЕЙ ГРАНИЦЫ ЧИСЛА РЕБЕР В ДВУСВЯЗНЫХ ГРАФАХ С ПРОИЗВОЛЬНЫМ ДИАМЕТРОМ
4.1. Постановка задачи и основной результат
4.2. Схема доказательства теоремы
4.2.1. Доказательство теоремы для случая нечетных значений
диаметра с?
4.2.2. Доказательство теоремы для случая четных значений
диаметра <7
4.3. Следствия теоремы
4.4. Свойство операции удаления произвольного ребра в двусвязном
графе с фиксированным диаметром
Выводы
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА
РИСУНКИ

ребрами,в противном случае положить у. — + 1 и перейти к шагу 1
такого ребра не существует, то следует положить т— 1: = г и перейти к шагу 2, в противном случае удалить ребро ек + ., положить у. = у + 1 и перейти к шагу
1.5.9.2.
Шаг 2. Проверить возможность удаления ребра ек = (гг, гт) для генерации следующего графа б?. Если г: = 0, то все двусвязные графы с т ребрами и <11 < 3 сгенерированы. Для этого надо:
2.1) временно удалить ребро е. и добавить ребра ег, г > к{. Обозначить

через С- полученный граф.
Вычислить т — число ребер в графе С'(. Если т <т, то положить і: = і — 1, если г: = 0, то двусвязные графы с то ребрами и <іг<3 сгенерированы, в противном случае следует перейти к шагу 2;
2.2) проверить условие с1г < 3 в графе С-. Для этого вычислить значения значения |Зр3(ш)|, для любого іи Є (ЭрДг,) и Зрг(ят));
2.3) если |Зр3(гг')| < п для некоторой ъи' Є (Эр-г,) и Зр1(лгГ7г)), то (1Х > 3 и ребро е,. недопустимо для удаления, следует восстановить ребро е. , положить
і — Кі
і: — і — 1, если і: = 0, то двусвязные графы с то ребрами и <2 сгенерированы, в
противном случае следует перейти к шагу 2;
2.4) проверить условие двусвязности. Для этого надо:
2.4.1) построить кратчайшую простую цепь С(г1, гт) и временно удалить вершину г, где г {гг, гто}, принадлежащую простой цепи С(гь гто);
2.4.2) построить кратчайшую простую цепь С'{гь гт) и вычислить ее
длину сі;
2.4.3) если с? = 3, то положить I: = 1. Обозначить через гх и г2 — вершины, принадлежащие простой цепи гт) и смежные с и гт
соответственно, и перейти к шагу 2.4.6;
если <1 = 2, то временно удалить вершину 2, где г гт}, принадлежащую простой цепи С(г;, ,гга);
2.4.4) построить кратчайшую простую цепь С'{гь 2т), восстановить
вершину г;
2.4.5) если цепи С'{гь гт) не существует, то граф (?" односвязен и ребро Єк недопустимо для удаления, следует восстановить ребро е. и вершину л,
г Кі
положить г: = г — 1, если г: =0, то все двусвязные графы с то ребрами и <1г < 2 сгенерированы, в противном случае следует перейти к шагу 2. Если же существует цепь С'{гь гт), то граф С- двусвязен, ребро ек допустимо для удаления;