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

Российская Академия наук Институт проблем передачи информации

На правах рукописи

Белоцерковсхий Дмитрий Леонидович

УДК 519.17: 681.24

ЗАДАЧИ ТЕОРИИ ЭКСТРЕМАЛЬНЫХ ГРАФОВ И ИХ ПРИМЕНЕНИЕ ПРИ РАЗРАБОТКЕ И ИССЛЕДОВАНИИ АЛГОРИТМОВ СИНТЕЗА ТОПОЛОГИЧЕСКОЙ СТРУКТУРЫ СЕТЕЙ ЭВМ

ч»

Специальность 05.13.17— Теоретические основы информатики

Автореферат диссертации на соискание ученой степени кандидата физико—математических наук

Москва - 1998

Работа выполнена б Институте проблем передачи информации Российской академии наук.

Научный руководитель: доктор технических наук, профессор В.М. Вишневский

Официальные оппоненты:

доктор технических наук О.Ю. Першин

кандидат физико — математических наук В.П. Полесский

Ведущая организация:

Московский Государственный Университет

Защита состоится " " 1999 г. в часов на заседании

диссертационного совета Л.003.29.01 в Институте проблем передачи информации РАН по адресу Москва, Б. Каретный, 19.

С диссертацией можно ознакомиться в библиотеке Института проблем передачи информации РАН.

Автореферат разослан 1998 г.

Ученый секретарь диссертационного совета Д.003.29.01,

доктор технических наук, профессор

Общая характеристика работы

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

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

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

Существенный вклад в развитие методов и алгоритмов оптимизации топологической структуры сетей ЭВМ внесен отечественными и зарубежными учеными: Вишневский В., Зайчонка 10., Макаров Л., Фараджев П., Agrawal D., Ball М., Bermoncl J-C., Peyrat С., Frank H., Frish I., Cliou W., Wittie L., Yagad В. и другие.

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

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

Однако, как методика получения нижних оценок количества ребер в множествах графах с ограничениями на диаметр и связность, так и сами оценки являются ие до конца изученными проблемами и требуют новых теоретических исследований. Существенный вклад в развитие методов исследования экстремальных графов внесен зарубежных учеными: ЕЫгн^е Б., Нагагу Р., Вопёу Л., МшЧу и., СассеНа Ь., С1итц Р., Еп1о8 Р., Кену! А., ЕгГаЬатап А., Р1сзшак Л., Шапп У. Особый вклад внес венгерский математик ВоИоЬая В., результаты которого стали определенной вехой в развитии теории экстремальных графов.

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

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

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

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

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

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

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

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

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

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

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

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

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

— разработка алгоритмов генерации двусвязных графов с диаметром не превосходящим 2 и 3 [1,4,5,8,9];

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

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

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

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

сетей ЭВМ

Апробация работы. Основные положения работы докладывались и обсуждались на 15-й и 16-й школах-семинарах по теории графой (Одесса, 1903— 1994), на IX Всероссийской конференции но математическому программированию и приложениям (Екатеринбург, 1995), на Втором Сибирском Конгрессе по прикладной и индустриальной математике (Новосибирск, 199G), lia 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" (Тель-Авив, 1997).

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

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

Краткое содержание работы

Первая глава состоит из трех разделов.

Через G = (V, Е) обозначается обыкновенный связный граф с множеством першин V(G) и множеством ребер E(G). Пусть п = и к = \Е\.

Диаметром графа d(G) называется максимум среди всех

расстояний между ларами вершин в графе С.

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

Простым циклом называется простая день, концы которой совпадают.

Простой цикл, в котором содержится 1 вершин, называется I — циклом.

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

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

В § 1.2. изложены основные цели и задачи диссертационной работы.

В § 1.3 формулируется важная практическая задача оптимизации топологической структуры сети передачи данных. Граф, являющийся решением этой оптимизационной задачи, должен удовлетворять ограничениям на диаметр графа, полученного из рассматриваемого удалением произвольной вершины или ребра (для пажных практических :>а м> диаметр не может превосходить 3). Важной частью этой задачи является этап генерации графов, являющихся кандидатами для точного решения задачи оптимизации топологической структуры сети передачи данных. Ранее предлагалось генерировать двусвязные графы и проверять их диаметр, а также диаметр графа, полученного удалением произвольной вершины или ребра из каждого сгенерированного графа. В § 1.3 предлагается новый алгоритм генерации двусвязных графов с диаметром не

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

Пусть G(V, Е) — днусвязный граф с диаметром </, < 3. Удалим в этом графе ребро uv. Рассмотрим граф G'= G— {'«'}.

Шаром Spr(u) радиуса г с центром п вершине, к будем называть множество вершин, находящихся от вершины »/ на расстоянии не превосходящем г.

Точкой сочленения графа G называется вершина из G, после удаления которой граф становится несвязным.

Утверждение 1. Условие d(G') < 3 выполнено тогда и только тогда, когда:

1) для любой вершины г, zeSp^u), и </, !/€ Sp,(í>) в графе G' имеем d(z,y) < 3;

2) для любой нершины г, z G Sp2(u), и </, у G Sp2(t>) имеем d{z,v) < 3 и d(g,u) < 3;

Следствие 1. Если |Sp3(z)|=n для любого г G (Sp](?i) U Sp^v)), то tí(G') <3.

Следствие 2. Если d(G) < 2 и ¡Sp2(z)|=n для любого г € {и, !>}, то d(G')< 2.

Утверждение 2. Вершина г графа G' является его точкой сочленения тогда и только тогда, когда:

1) вершина г принадлежит любой простой цени, соединяющей вершины и и v;

2) г ft {..,..}■

Следствие 1. Пусть граф G' односвязен. Тогда точка сочленения

графа С принадлежит кратчайшей простой цепи, соединяющей вершины и и V, и не совпадает с вершинами и иг».

Следствие 2. Если </". ' < 3, то о графе С существует не более дпух точек сочленения.

Следствие 3. Пусть <1(С ) < 2 и граф С односвязен. В этом случае в графе С существует единственная точка сочленения г, которая смежна вершинам и и V.

Пусть г — единственная точка сочленения графа С.

Блоком графа называется его максимальный связный подграф, не имеющий точек сочленения.

Если в графе имеется к точек сочленения, то граф состоит из не менее чем к + 1 блоков. Следовательно, в случае, если г — единственная точка сочленения графа С, то граф С состоит из не менее чем 2-х блоков, имеющих одну общую вершину 2. Но так как граф СЛ {'«>} днусвязен, то точка сочленения не может принадлежать более чем 2-м блокам и, следовательно, граф С состоит из 2-х блоков В1 и В2, У{В1) и У(В2) = У(Сг'). Так как вершина г принадлежит любой простой п»ч1и, соединяющей и и у, то «6 У(В,), V € У(В2).

Утверждение 3. Пусть граф С=С— {гго} односвязен, г —единственная точка сичленсния графа С. Тогда граф С'= С + е, где е — ребро, инцидентное вершинам г, и принадлежащим графу С, двусчязен тогда и только тогда, когда г¡ е У(В1), е У(В2), где

Пусть г! и г2 — точки сочленения графа С, где г, -ф- г2. Следовательно, граф С состоит из не менее чем 3 блоков. Как следует из следствия 2 утверждения 2, других точек сочленения в графе С нет. Так как граф С+ {«»} днусвязен, то точка сочленения не может принадлежать более чем 2 блокам. Таким образом, граф С состоит из 3 блоков: В„ Вг. В3, У(В1)иУ(В2)иУ(Вл)=У(С), У(В,)ПУ(В2)-{г,}, У(В2)ПУ(В3)={г2}. Вершины и и г. не могут принадлежать блокам, имеющим общую вершину, так как граф С+{ш>} двусвизен. Таким образом, и€У(В1), {гиг2} С У(В2),

V 6 У(В3). Из утверждения 2 следует, что вершины г1 и с2 принадлежат любой простой цепи, соединяющей вершины и и ь\ Из следствия 1 утверждения 2 следует, что кратчайшая простая цепь, соединяющая вершины и и V, состоит из ребер иг,, ¿¡г?,

Утверждение 4. Пусть граф С' —С — {ш>} односвязен и в графе С существуют дне точки сочленения Тогда граф С— С + е, где с

— ребро, инцидентное вершинам г; и принадлежащих графу С, двусвязен тогда и только тогда, когда ¿,€^(.0,), € У(Л3),

*1 £ {*„ *>}, г, 1. {*,-, *,}.

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

Пусть 3,(п, ~ множество Г])афон с диаметром не

превосходящим и таких, что после удаления из графа

произвольного ребра или произвольной першины, диаметр не превосходит Пусть 1н1(?|,</1//1) — нижняя граница числа ребер н 31(п,(11,(!2). Допустим, что формулируется задача перечисления экстремальных графов. Но так как экстремальных графов бесконечно много, то необходимо разработать метод перечисления всех экстремальных графов из Я^п, (11,(1г).

Пусть V) — минимальная степень в экстремальном графе из 3,(«,¿,,¿2) и тогда 2 < т < 3, если '¡¡<2 или <12< 3, и и> = 2, в противном случае. Выясняется, что в случае \и = 3 имеется всего несколько экстремальных графов. При рассмотрении случая и> = 2 замечено следующее.

Пусть О — экстремальный граф из ЗГг(тг,с ги((?) = 2. Пусть /—длина произвольной простой цени, нее внутренние вершимы которой имеют в искомом графе С степень 2 (так как и>(С) = 2 и (7 — двусвязный граф, то существует простая цепь, все внутренние вершины которой имеют в графе С степень 2). Пусть / — длина такой простой цепи в графе С. Обозначим через Р^ простую цепь, все внутренние вершины которой имеют н графе (? степень 2.

Простую цепь Р! будем называть /-нитью. Пусть и ь2 — концы /-нити. Очевидно и, >3 и ^ 3.

Если к граф у С добавить /'-нить с концами г?! и г>2, где /' < /, то, очевидно, что полученный в результате этой операции граф С из

4-1' — 1,<]],с/г).

Обозначим через СН=(УВ, Ев), пв=\Ув\, кв=\Ев\ подграф искомого графа С, порожденный вершинами степени не менее Звйи через Уг множество нершии степени 2 графа б. В случае т = 3 подграф совпадает с графом <7.

Пусть й = (У, .Е) — граф множества ЭДп, 3), в котором определен (70=(УН, и го =2. Удалим произвольную /-нить из С. Получим граф С с подграфом Св'=(\/'в, Е'в). Граф С! назовем порождающим" графом множества Я,(п, 3), если выполнено хотя бы одно из следующих условий: 1) 3,(п-/ +1, 3); 2) Св не изоморфен С?в. Порождающие графы множества 31(п, 3), содержащие минимальное число ребер, будем называть экстремальными порождающими графами.

Поэтому мы решим задачу перечисления экстремальных графов из 3|(п,</,,</2), если перечислим все экстремальные графы при ги = 3 и все экстремальные порождающие графы при ю = 2.

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

В §§ 2.1 и 2.2 мы находим экстремальные графы множества ГГ|(п,(/2) при < 3. Пусть ш,(гг,3) — нижняя граница количества ребер и графах множества. 31(71,3). Очевидно, что при п = 4 единственным экстремальным графом из 3,(п, 3) является простой цикл из 4

вершин.

Доказана, теорема о нижней границе количества ребер п множестве 3,(л, 3) [7].

Теорема 1. ш, (п, 3) =2п — 4 при 4 < п < 7, т1(п, 3) = 2п — 5 при 8 < п < 23, 771,(77,3) = 2м — б при п > 24.

Мы также нашли все экстремальные графы из 3,(71, 3) при ш=3и псе экстремальные порождающие графы при хв = 2.

Следствие теоремы 1. Для экстремальных графов множества 3,(71,2,3):

то, (п, 2,3) = 2п - 4 при 4 < 77 < 9, 777,(71,2,3) = 2п — 5 при п > 10.

В §2.3 решена задача перечисления всех порождающих экстремальных графов из 3,(п,2,3) при и> = 2 и всех экстремальных графов из З^п,2,3) при и) = 3.

В §2.4 сравниваются значения функции т1(п,<!1,(11) при с/, < 2 или ¿2 < 3, с нижними границами ребер в множествах графов с соответствующими значениями и <12, в которых разрешена либо только операция удаления вершины, либо только операция удаления ребра.

В §2.5 доказана следующая теорема [13]:

Теорема 2. Каждый экстремальный граф из Я,(тг, 3, 4) при п > 4 содержит [(Зп — 4)/2] ребер.

В §2.5 перечислены также все порождающие графы из 3,(71,3,4) и проведена сравнительная характеристика функции 777,(71,с/,,(/2) при Л, < 3 и с12 > 4, с нижними границами ребер в множествах графов с соответствуюпщми значениями и (1г в которых разрешена либо только операция удаления вершины, либо только операция удаления

ребра.

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

В §§ 3.2 и 3.3 решаются задачи нахождения нижней границы числа ребер в множествах ЗГ,(п, 4,6) и Й,(п,4,5) [10,12].

Теорема 3. т,(п,4,6) = [(4и — 5)/3], если п > 5.

Теорема 4. 7П|(«,4,5) = |(3п — 6)/2|, ели п > 13, т,(н,4,5) = |(Згг-5)/2|, если 5 < п < 12.

В §3.4 показано, что значения функции т^п,«^,^) при < 4 и <12 < 5, а также при < 4 и ¿2< 6, не совпадают со значениями нижней границы числа ребер в множествах графов с соответствующими значениями </, и </2, в которых разрешена либо только операция удаления вершины, либо только операция удаления ребра.

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

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

Пусть 3(п, (1) — множество двусвязных графов с гг вершинами и с диаметром не превосходящим <1 и ¡(п,<1) — нижняя граница числа ребер для графов множеств 32(п, </,, /!2) .

Пусть г = 2+((4</ — 1)((4</ — 2)*^ — 1))/(44-3)).

Теорема 5. Для графов из 3(п, Л) при п> г имеем: /(п, </)=[(</п — 2<1 - 1)/((/— 1)]

В §4.2 теорема 5 доказана отдельно для случаев четных и нечетных Л.

В §4.3 рассмотрены следствия теоремы 5.

Следствие 1. Нт^Дп, <1)/п) = (¿/(<! — 1))

Пусть /](«, ¿ц является нижней границей числа ребер для графов множеств З^п, </,, Л2).

Следствие 2. При п > г выполнено /,(», ¿¡, <12) = /(п, где Л2 > 2<11.

Следствие 3. Если — 2«?х — 2, то для графов ИЗ -о"2/

имеем:

<*,)/»») = №/№-1))

В §4.4 доказано свойство операции удаления произвольного ребра в двусвязном графе (7 с фиксированным диаметром ¿. Пусть ¿' — диаметр графа (7 —е, где е — произвольное ребро из графа (7. Тогда имеет место теорема, в которой усганапливаетсн зависимость между значениями <1 и

Теорема 6. Л' < 2(1

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

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

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

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

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

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

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

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

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

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

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

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

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

Основное содержание диссертационной работы изложено в следующих работах:

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

2. Белоцерковский Д.Л. О характеризации некоторых экстремальных графов с диаметром не превосходящим 3 // Проблемы теоретической кибернетики. Тез. докл. XI Междунар.конф. Москва: ГК РФ по ВО. 1996. С.23 -24.

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

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

5. 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. I'. 131-138.

6. 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.

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

8. Vishnevsky V.M., Belotsexkovski 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.

9. 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.

10. Белоцерковский Д.Л. Об одной задаче теории экстремальных графов//С6. труд. 13 школы — семинара по теории массового обслуживания (BWWQT-97). Минск. 1997. С. 11.

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

1997. N1. С. 108 -120.

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

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

1998. Т.5, N2. С. 3-27.



/ / ./

«•у

" /

г

К

Российская Академия наук

Институт проблем передачи информации

На правах рукописи БЕЛОЦЕРКОВСКИЙ Дмитрий Леонидович

УДК 519.17: 681.24

ЗАДАЧИ ТЕОРИИ ЭКСТРЕМАЛЬНЫХ ГРАФОВ И ИХ ПРИМЕНЕНИЕ ПРИ РАЗРАБОТКЕ И ИССЛЕДОВАНИИ АЛГОРИТМОВ СИНТЕЗА ТОПОЛОГИЧЕСКОЙ СТРУКТУРЫ СЕТЕЙ ЭВМ

Специальность 05.13.17 — Теоретические основы информатики

Ы

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель д.т.н.,проф. Вишневский В.М.

Москва - 1998

ОГЛАВЛЕНИЕ

Стр.

Введение ........................................................................................................ 5

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

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

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

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

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

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

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

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

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

Выводы .............................................................................................................38

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Выводы ................................................................................................... 107

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

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

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

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

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

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

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

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

при V = 2 ......................................................................................... 176

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

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

Выводы ................................................................................................... 226

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

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

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

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

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

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

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

Выводы ................................................................................................... 249

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

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

РИСУНКИ .................................................................................................... 259

-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 страницах. Структура и содержание глав отражены в оглавлении диссертации.

-9-ГЛАВА 1

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

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

Первые результаты в области теории экстремальных графов относятся к началу 60-х годов [69,101]. Интерес к экстремальным задачам был вызван следующей задачей из практики. Каждый из п городов имеет один аэропорт. В каждом аэропорту имеется не более к рейсов, связывающих аэропорт с аэропортами других городов. Рейсы между городами, которые не связаны друг с другом прямыми рейсами, осуществляются не более чем через й — 1 транзитных аэропорта. Требуется найти минимальное количество прямых рейсов для указанных п городов? На языке теории графов это задача может быть сформулирована следующим образом: найти минимальное количество ребер в графе с п вершинами - и диаметром в котором максимальная степень не превосходит А. В [69,45] представлены частичные решения этой задачи для произвольного сI и подробные решения для случаев й = 2 и <1 = 3.

Ранее, в [43] рассматривались различные постановки экстремальных задач с ограничениями на диаметр и максимальную степень вершины в графе. И хотя для этих экстремальных задач получены различные оценки нижней границы количества ребер, как точные, так и ассимптотические, все они зависят от связи значений числа вершин п и максимальной степени А вершины в графе. Авторами отмечаются трудности решения подобных задач, так как практически до сих пор не удалось разработать методику, позволяющую обобщить методы решения указанных экстремальных задач для фиксированных значений й на случай произвольных <1. Более того, даже для случая ¿ = 2 задача нахождения точной нижней границы числа ребер решена не полностью. Например, не найдена точная нижняя граница числа ребер при <1 = 2 в случае (п — I)1/2 < А < п/2. Поэтому в [43] отмечается, что эта область теории экстремальных графов является еще недостаточно развитой.

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

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