Введение к работе
Актуальность темы. Быстрое разлитие п последние годы корпоративных сетей ЭВМ выдвигает в ряд первоочередных проблему оптимального проектирования сетей ЭВМ. Одной из важнейших задач, решаемых при проектировании сетей ЭВМ является задача синтеза топологии сети.
С математической точки зрения, задача синтеза топологии сети ЭВМ является сложной задачей нелинейного целочисленного программировании большой размерности, для которой отсутствует единый эффективный метод решения. Используемые для решения этой задачи эвристические алгоритмы обладают невысокой точностью и, кроме того, не учитывают многих свойств реальных сетей. Поэтому возникает необходимость разработки новых точных методов решения задачи синтеза топологии сети ЭВМ, учитывающих основные свойства реальных сетей ЭВМ.
Разработка алгоритмов синтеза топологии сети основывается на результатах из области теории экстремальных графов, под которыми понимаются графы, требуемые свойства которых достигаются при минимальном (максимальном) числе ребер.
Существенный вклад в развитие методов и алгоритмов оптимизации топологической структуры сетей ЭВМ внесен отечественными и зарубежными учеными: Вишневский В., Зайченко 10., Макаров Л., Фараджев П., Agrawal D., Ball М., Bermond J-C, Peyrat С, Frank H., Frish I., Cliou W., Wittie L., Yagad В. и другие.
Особый интерес представляют минимальные по числу ребер экстремальные графы с ограничениями на диаметр и связность, так как именно ограничения на диаметр и связность являются весьма важными с точки зрения быстродействия, надежности и минимизации стоимости сети. Поэтому формулируются задача нахождения нижней границы числа ребер в множествах графов с ограничениями на диаметр и связность, а также задача перечисления экстремальных
графов. Совокупность этих задач называется задачей характеризации экстремальных графов.
Однако, как методика получения нижних оценок количества ребер в множествах графах с ограничениями на диаметр и связность, так и сами оценки являются ие до конца изученными проблемами и требуют новых теоретических исследований. Существенный вклад в развитие методов исследования экстремальных графов внесен зарубежных учеными: Eldridge S., Нагагу F., Bondy J., Murty U., CacceUa L., Cluing F., Erdos P., Renyi A., Esfahanian A., Plesniak J., Usami Y. Особый вклад внес венгерский математик Bollobas В., результаты которого стали определенной вехой в развитии теории экстремальных графов.
Значительную методическую трудность представляет задача перечислении ' экстремальных графов, т.е. графов, на которых найденные нижние оценки достигаются. Задача перечисления экстремальных графов имеет не только теоретическое, по и практическое значение, так как найденные экстремальные графы могут быть рассмотрены в качестве конкретных топологических структур при создании корпоративной сети ЭВМ.
Основная трудность рассматриваемых задач нахождения нижней границы числа ребер и перечисления экстремальных графов в множествах графов с ограничениями на диаметр и связность состоит в том, что решения этих задач для фиксированных значений диаметра не удастся обобщить на случаи произвольных значений диаметра. Поэтому, например, многие задачи нахождения нижней границы числа ребер для графов с ограничением на диаметр как самого графа, так и на диаметр после удаления произвольной вершины, не решены до сих пор. В работах Боллобаша высказан ряд предположений, касающи.ч' і иих задач, значительная часть которых не доказана. Поэтому получение результатов, связанных с отысканием новых нижних оценок числа ребер в графах с ограничениями на диаметр и связность, является весьма важным и
интересным направлением исследований. Особый интерес представляет методика получения таких результатов, так как методы решения конкретной задачи, возможно, могут быть обобщены на другие нерешенные задачи из области теории экстремальных графом.
Целью диссертационной работы является получение новых результате» в области теории экстремальных графов и разработка на их основе новых эффективных алгоритмов для точного решения задачи синтеза топологии сети. Дли достижения указанной цели необходимо рассмотреть следующие задачи:
разработать и исследовать алгоритмы для получения точных решений задачи синтеза топологической структуры сети;
решить задачу характеризации экстремальных двусвязных графов с диаметром не превосходящим 3;
решить задачу нахождения нижней границы для двусвязных графов с диаметром не превосходящим 4;
доказать теорему о нижней границе количества ребер п двусвязных графах с произвольным диаметром;
доказать теорему об изменении диаметра после удаления из графа произвольного ребра.
Методы исследования. Основные результаты диссертационной работы получены с использованием методов теории экстремальных графов, комбинаторного анализа, теории алгоритмов, оптимизации на графах и сетях.
Научная новизна работы заключается в получении новых результатов в области теории экстремальных графов и применении некоторых из них для создания новых алгоритмов для точного решения задачи синтеза топологической структуры сети, позволяющих сократить число графов, являющихся кандидатами для решения задачи топологической оптимизации сети. Кроме того, доказанные в диссертационной работе теоремы и разработанные методы их доказательств вносят вклад п раздел теорию
экстремальных графов, изучающий графы с ограничениями на диаметр и связность.
Новыми научными результатами являются:
разработка алгоритмов генерации двусвязных графов с диаметром не превосходящим 2 и 3 [1,4,5,8,9];
решение задачи характеризации экстремальных графов для различных множеств двусвязных графов с диаметром не превосходящим 3, . в которых разрешена операция удаления произвольной вершины или ребра, и существует ограничение на диаметр графа, в котором удалена либо произвольная вершина, либо ребро [2,3,6,7,13];
решение задачи нахождения нижней границы количества ребер для любого множества двусвязных графов с диаметром не превосходящим 4, в которых разрешена операция удаления произвольной вершины или ребра, и существует ограничение на диаметр графа, и котором удалена либо произвольная вершина, либо ребро [10,12];
нахождение и доказательство точной нижней границы числа ребер в двусвязных графах с произвольным диаметром, которая является обобщением известной ранее ассимптотической оценки нижней границы числа ребер в двусвязных графах с произвольным диаметром. Известная ранее ассимптотическая оценка является следствием доказанной теоремы о нижней границе.
Практическая цеппость. Разработанные в диссертационной работе алгоритмы генерации двусвязных графов с диаметром не превосходящим 3, а также полученные нижние оценки числа ребер в графах с ограничениями па диаметр и связность, предназначены для решения задачи синтеза топологии сети с ограничениями на надежность. Задача синтеза топологии сети является важной частью практической задачи общей топологической оптимизации сетей ЭВМ. Таким образом, полученные в диссертационной работе результаты могут быть испотьзоианы для задачи топологического проектирования
сетей ЭВМ.
Апробация работы. Основные положения работы докладывались
и обсуждались на 15-й и 16-й школах-семинарах по теории графов
(Одесса, 1993—1994), на IX Всероссийской конференции но
математическому программированию и приложениям (Екатеринбург,
1995), на Втором Сибирском Конгрессе по прикладной и
индустриальной математике (Новосибирск, 199G), на IV
международном форуме по информатизации (Санкт-Петербург, 199G),
на Международной конференции "Distributed Computer
Communication Networks. Theory and Applications" (Тель-Авив, 199G), на XIII Международной конференции "Массовое обслуживание. Потоки, системы, сети"(Минск, 1997), на совместном болгаро-российском семинаре "Methods and algorithms for distributed information systems design. Theory and Applications"(София, 1997), на международной конференции "Distributed Computer Communication Networks. Theory and Applications" (Тель-Авив, 1907).
Публикации. По теме диссертации опубликовано 13 печатных работ, из них 3 статьи в реферируемых научно —технических журналах.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, изложенных на 251 страницах, содержит 61 рисунок, 1 таблицу и список цитируемой литературы из 108 наименований на 7 страницах. Структура и содержание глав отражены в оглавлении диссертации.
