Т-неприводимые расширения графов тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Курносова, Светлана Геннадьевна

• Курносова, Светлана Геннадьевна
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Курносова, Светлана Геннадьевна

Введение.

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

Содержание работы.

Глава I. Свойства Т-неприводимых расширений.

1. Основные определения.

2. Основные свойства Т-неприводимых расширений.

Глава II. Т-неприводимые расширения деревьев.

1. Т-неприводимые расширения цепей колес.

2. Т-неприводимые расширения пальм.

3. Т-неприводимые расширения полных бинарных деревьев.

3.1. Полные бинарные деревья: первый подкласс.

3.2. Полные бинарные деревья: второй подкласс.

3.3. Полные бинарные деревья: третий подкласс.

Глава III. Т-неприводимые расширения объединений графов.

1. Т-неприводимые расширения для объединений в классах цепей и колес.

2. Т-неприводимые расширения объединений некоторых графов с вполне несвязным графом.

3. Т-неприводимые расширения объединений полных графов.

Введение диссертации (часть автореферата) на тему «Т-неприводимые расширения графов»

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

Актуальность проблемы. В последние десятилетия значительно расширилась область применения автоматизированных систем в различных областях деятельности человека. В связи с этим возникает необходимость в повышенных требованиях надежности. Одним из показателей надежности системы является ее отказоустойчивость. Согласно Авиженису [27,5], отказоустойчивость - это свойство системы сохранять полностью свою работоспособность при наличии в ней отказов. Для обеспечения отказоустойчивости необходимо вводить в систему избыточные элементы, которые активируются при возникновении отказа.

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

Расширением я-вершинного графа (7 называется граф Н с п+1 вершинами такой, что (7 вкладывается в каждый максимальный подграф графа Я. Для любого графа существует по крайней мере одно расширение, называемое тривиальным. Это расширение получается соединением исходного графа (7 с одновершинным графом. Хейз выделил из всего множества расширений графа О подмножество оптимальных. В качестве критерия оптимальности он предложил минимальность количества ребер в расширении. Такие расширения называются минимальными. Задача описания минимальных расширений для произвольного графа остается нерешенной и представляется чрезвычайно трудной. К настоящему времени получен ряд нетривиальных результатов. Сделаем обзор наиболее интересных направлений поисков.

Хейз предложил процедуру нахождения одного из минимальных расширений для цикла. М.Б. Абросимов обнаружил еще одну серию минимальных расширений для циклов. Им же исследовались вопросы поведения конструкции минимальных расширений относительно операций над графами и были получены некоторые частные результаты, связанные с вопросами минимальных расширений для объединений и для соединений графов [2,3]. Ряд работ посвящен нахождению минимальных расширений для класса деревьев - связных графов без циклов. Так Фаррад и Доусон охарактеризовали минимальные расширения для звездных графов [29]. Харари и Хуррум описали минимальные расширения для особого вида деревьев - гусениц [34]. М.А. Кабанов указал одно из минимальных расширений для специального класса деревьев - цепей колес [11]. М.Б. Абросимов нашел [2] минимальные расширения для сверхстройных деревьев особого вида.

В 1993 году Харари и Хейз [32] (см. также [31]) отмечают, что отказать может не только элемент системы. Связь между элементами тоже может оказаться поврежденной. Поэтому они предлагают конструкцию реберных расширений (граф Я с п вершинами называется реберным расширением п-вершинного графа G, если G вкладывается в любой граф, полученный из Н удалением одного ребра). Интересные результаты в этом направлении представлены Чоу и Сю [28], которые рассматривали минимальные реберные расширения графов, представляющих собой решетку.

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

1993 и 1996 году Харари и Хейз предложили модель соответственно реберных и вершинных ^-расширений [32, 33]. Основные направления в этой области посвящены нахождению минимальных реберных ^-расширений для циклов (например, работа [32]) и некоторых классов деревьев (например, работа [35]).

В 1996 году М.Ф. Каравай [12] рассматривает вершинную отказоустойчивость, но с другой интерпретацией отказа элементов. Если в графовой модели Хейза отказавший элемент удаляется вместе со всеми связями, то М.Ф. Каравай рассматривает отказ элемента как «слипание» связей. Им предложено использование теории симметрий для изучения вопросов отказоустойчивости (с учетом особенности рассматриваемых им отказов) дискретной системы.

В работе [33] среди нерешенных проблем приводится задача выделения минимальных расширений, в которых добавочная вершина инцидентна всем добавочным ребрам. В 2003 году В.Н. Салий [23] предлагает принципиально новый подход к оптимальности - так называемые неприводимые расширения. Неприводимым расширением графа С называется такое его расширение Н, что при удалении любого ребра из Я полученный граф не будет расширением для & В рамках проблемы, указанной Харари и Хейзом, В.Н. Салий предложил конструкцию Т-неприводимого расширения. Под Т-неприводимым расширением графа (7 понимается всякое его неприводимое расширение, полученное из тривиального расширения графа О удалением некоторого числа ребер. Новая конструкция является оптимальной и в том смысле, что позволяет сохранить исходный граф. Еще одним важным свойством предложенной модели является однозначность восстановимости графа по любому его Т-неприводимому расширению. Заметим, что для нахождения Т-неприводимого расширения в настоящий момент не существует эффективного алгоритма. Процедура же восстановления исходного графа по его Т-неприводимому расширению будет линейной относительно размерности графа, если известны степени всех вершин этого расширения.

Все модели оптимальных расширений изначально предлагались для неориентированных графов. Однако все они очевидным образом могут быть перенесены на случай ориентированных графов, с естественным усложнением всех задач. Так, в 1995 году A.B. Киреева предложила алгоритм построения минимального расширения для произвольного функционального графа [14]. Позже появляются результаты по вершинным и реберным расширениям для ориентированных циклов в работе Сунга, Лина и других [36]. М.Б. Абросимов в работе [4] описал минимальные расширения транзитивных турниров.

В 2005 году конструкция Т-неприводимого расширения была обобщена на случай ориентированных графов в работе [16]. В [17] был выделен класс всевозможных ориентаций заданной цепи и составлен каталог всех Т-неприводимых расширений для всех ориентаций цепей с числом вершин не более 8. В работах [18-20] решена задача описания всех Т-неприводимых расширений для симметричных ориентаций цепей. Эти результаты автора в представляемую работу не включены, так как проблема нахождения Т-неприводимых расширений для ориентированных графов - отдельная, не менее сложная задача, чем те, которые рассматриваются в диссертации.

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

Цель работы. Выделить основные свойства Т-неприводимых расширений графов. Рассмотреть Т-неприводимые расширения для связных графов и изучить поведение этой конструкции относительно графовой операции объединения.

Научная новизна и выносимые на защиту положения. В работе получены следующие основные результаты:

1. доказаны основные свойства Т-неприводимых расширений, в том числе критерий Т-неприводимости;

2. составлен каталог всех Т-неприводимых расширений для графов с числом вершин не более 6 и проведен статистический анализ, в том числе и по соотношению между множествами Т-неприводимых и минимальных расширений;

3. рассмотрена задача нахождения Т-неприводимых расширений для важнейшего класса связных графов - деревьев, в том числе составлен каталог всех Т-неприводимых расширений для деревьев с числом вершин не больше 10 и получены описания всех Т-неприводимых расширений для некоторых деревьев, таких как пальмы, полные бинарные деревья;

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

5. предложен и обоснован алгоритм построения всех Т-неприводимых расширений для объединений полных графов и дана оценка их количества.

Все вышеназванные результаты являются новыми. Методы исследования. При решении перечисленных задач применялись методы теории графов [6,10,26], теории дискретных систем [6,7,22], теории вычислительных экспериментов [21,25], теории алгоритмов [8,9,13,15]. Достоверность полученных результатов. Все полученные в диссертации теоретические результаты имеют строгое доказательство. Кроме того, достоверность теоретических результатов подтверждают вычислительные эксперименты, проведенные для графов с небольшим количеством вершин. Теоретическая и практическая ценность. В работе представлены готовые процедуры построения Т-неприводимых расширений для конкретных видов графов. Возможно использование предлагаемых результатов при построении оптимальных отказоустойчивых реализаций для дискретных систем, моделируемых графами.

Апробация работы. Результаты представляемой работы обсуждались на научном семинаре кафедры теоретических основ компьютерной безопасности и криптографии (СГУ, 2006 год) и на объединенном семинаре по дискретной математике и математической кибернетике (СГУ, 2007 год). Они докладывались на Межвузовских научных конференциях «Компьютерные науки и информационные технологии» (Саратов, 2004,2005, 2006 годы), VI Международной конференции «Алгебра и теория чисел: современные проблемы и приложения» (Саратов, 2004 год), Федеральной итоговой конференции Всероссийского конкурса на лучшие работы студентов по естественным наукам (Москва, 2004 год), II Международной научно-практической конференции «Исследование, разработка и применение высоких технологий в промышленности» (Санкт-Петербург, 2006 год), Международных конференциях студентов, аспирантов и молодых ученых «Ломоносов» (Москва, 2005,2006, 2007 годы). Исследования автора поддержаны грантом РФФИ 05-08-18082. Публикации. Основные результаты опубликованы в работах [А1-А12]. Работа [А8] опубликована в издании, включенном в «Перечень ведущих рецензируемых научных журналов и изданий, в которых должны быть опубликованы основные научные результаты диссертации на соискание ученой степени доктора и кандидата наук».

Структура и объем работы. Работа состоит из введения, трех глав, заключения, библиографии, включающей 37 наименований, и двух приложений. Общий объем работы 110 стр.

Содержание работы

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

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

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

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Курносова, Светлана Геннадьевна

Заключение

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

Тема 1. Основные свойства Т-неприводимых расширений.

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

2. Проведен вычислительный эксперимент, в результате которого составлен каталог всех Т-неприводимых расширений для графов с небольшим количеством вершин (не более 6). Проведен сравнительный анализ минимальных и Т-неприводимых расширений и получено условие, при котором минимальное расширение будет Т-неприводимым расширением.

Тема 2. Описание Т-неприводимых расширений для связных графов определенных типов.

1. С помощью вычислительного эксперимента получены все Т-неприводимые расширения для деревьев с числом вершин не более 10.

2. Найдены все Т-неприводимые расширения для некоторых подклассов класса деревьев. Среди них цепи колес, пальмы, полные бинарные деревья.

Тема 3. Описание Т-неприводимых расширений объединения графов, для которых Т-неприводимые расширения уже известны.

1. Представлено одно из Т-неприводимых расширений для объединения графа с произвольным его Т-неприводимым расширением.

2. Выделены все Т-неприводимые расширения для объединений цепей и для объединений колес.

3. Предложена процедура построения некоторых Т-неприводимых расширений для объединения графа без изолированных вершин с вполне несвязным графом и найдены все Т-неприводимые расширения для объединения двухэлементной цепи с вполне несвязным графом и колеса с вполне несвязным графом.

4. Разработан алгоритм построения всех неизоморфных Т-неприводимых расширений для объединений полных графов и проведена оценка их количества.

106

Список литературы диссертационного исследования кандидат физико-математических наук Курносова, Светлана Геннадьевна, 2007 год

1. Абросимов М.Б. Минимальные расширения 4-, 5-, 6- и 7-вершинных графов // Рукопись деп. в ВИНИТИ РАН 06.09.2000, №2352-ВОО. - 26 с.

2. Абросимов М.Б. Минимальные расширения объединения некоторых графов // Теоретические проблемы информатики и ее приложений. -Саратов: СГУ, 2001. Вып. 4. - С. 3-11.

3. Абросимов М.Б. Минимальные ^-расширения предполных графов // Изв. вузов. Математика. 2003. - № 6. - С.3-11.

4. Абросимов М.Б. Минимальные расширения транзитивных турниров // Вестник Томского государственного университета. Приложение. 2006. - № 17.-С. 187-190.

5. Авиженис А. Отказоустойчивость свойство, обеспечивающее постоянную работоспособность цифровых систем // Труды Института инженеров по электротехнике и радиоэлектронике. - 1978. - Том 66. -№ 10. -С. 5-25.

6. Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М.: Наука, 1997. - 326 с.

7. Богомолов A.M., Сперанский Д.В. Аналитические методы в задачах контроля и анализа дискретных устройств / Под. ред. В.Г. Тоценко. -Саратов: Из-во Сарат. ун-та, 1986. 238 с.

8. Грин Г., Кнут Д. Математические методы анализа алгоритмов. М.: Мир, 1987.-120 с.

9. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. - 411 с.

10. Зыков A.A. Основы теории графов. -М.: Наука, 1987.-380 с.

11. Кабанов М.А. 1-отказоустойчивые реализации цепи колес // Теоретические проблемы информатики и ее приложений. Саратов: СГУ, 1997.-Вып. 1.-С. 50-58.

12. Каравай М.Ф. Применение теории симметрий к анализу и синтезу отказоустойчивых систем. // Автоматика и телемеханика. 1996. - № 6. - С. 159-173.

13. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ-Петербург, 2003. - 1104 с.

14. Киреева A.B. Отказоустойчивость в функциональных графах // Упорядоченные множества и решетки. Саратов, 1995. - Вып. 11. - С. 32-38.

15. Кормен Т. X., Лейзерсон Ч.И., Ривест P.JT., Штайн К. Алгоритмы: построение и анализ, 2-е издание / Перевод с анг. М: Издательский дом «Вильяме», 2005. - 1296 с.

16. Курносова С.Г. Т-неприводимые расширения для ориентированных графов // Проблемы теоретической кибернетики. Тезисы докладов XIV Международной конференции (Пенза 23-28 мая 2005 г.). М.: МГУ, 2005. -С. 82.

17. Курносова С.Г. Т-неприводимые расширения для ориентаций цепей с числом вершин не более 8 // Рукопись деп. в ВИНИТИ 11.05.05, № 677-В2005.-22 с.

18. Курносова С.Г. Т-неприводимое расширение для симметричных ориентаций цепей // Теоретические проблемы информатики и ее приложений. Саратов: СГУ, 2007. - Вып. 7. - С.75-80.

19. Курносова С.Г. Две конструкции Т-неприводимого расширения для симметричных ориентаций цепей специального вида // Вестник Томского государственного университета. Приложение. 2006. - № 17. - С. 203-207.

20. Моисеев H.H. Математика ставит эксперимент. М.: Наука, 1979. - 223 с.

21. Пархоменко П.П., Согомонян Е.С. Основы технической диагностики: (Оптимизация алгоритмов диагностирования, аппаратур, средства) / Под. ред. П.П. Пархоменко. -М.: Энергоиздат, 1981.-319 с.

22. Салий В.Н. Доказательства с нулевым разглашением в задачах о расширениях графов // Вестник Томского государственного университета. Приложение. 2003. -№ 6. - С. 63-65.

23. Самарский А.А., Михайлов А.П. Математическое моделирование. Идеи. Методы. Примеры. 2-е изд., испр. - М.: ФИЗМАТЛИТ, 2005. -316.

24. Харари Ф. Теория графов / Перевод с анг. В.П. Козырева / под ред. Г.П. Гаврилова. М.: «Мир», 1987. - 300 с.

25. Avizienis A. Fault tolerant computing An overview // IEEE Computer. -1971.-Vol. 4.-P. 5-8.

26. Chou R. S., Hsu L.H. 1-edge fault-tolerance designs and meshes // Parallel Processing Letters. 1994. - Vol. 4. - No. 4. - P. 385-389.

27. Farrad A.A., Dawson R.J. Designing optimal fault-tolerant star networks // Networks. 1989. - Vol. 19. - P. 700-716.

28. Hayes J. P. A graph model for fault-tolerant computing systems // IEEE transactions on computers. 1976. - Vol. C-26. -№ 9. - P. 875-884.

29. Hayes J.P. Fault tolerance in computers and graphs // Proc. 1st Est.Conf. Graphs and Appl. Tartu-Kaariku, May 12-19, 1991. Tartu, 1993. - P.77-89.

30. Harary F., Hayes P. Edge fault tolerance in graphs // Networks. 1993. -Vol. 23.-P. 136-142.

31. Harary F., Hayes P. Node fault tolerance in graphs // Networks. 1996. -Vol. 27.-P. 19-23.

32. Harary F., Khurrum M. One node fault tolerance for caterpillars and starlike trees // Internet J. Computer Math. 1995. - Vol. 56. - P. 135-143.

33. Ku H K., Hayes J.P. Optimally edge fault-tolerance trees // Networks. -1996.-Vol. 27.-P. 203-214.

34. Sung T.Y, Lin C.Y., Chuang Y.C., Hsu L.H. Fault tolerance token ring embedding in double loop networks // Inform. Process. Lett. 1998. - Vol. 66. -P. 201-207.

35. Публикации автора по теме диссертации

36. A3. Курносова СТ. О Т-неприводимых расширениях деревьев // Алгебра и теория чисел: современные проблемы и приложения. Тезисы докл. VI Межд. конференциии. Саратов: СГУ, 2004. - С. 76-77.

37. А4. Курносова СТ. Т-неприводимые расширения бесповторных объединений полных графов // Молодежь. Образование. Экономика. Сб. научных статей участников конференции. Ярославль: РЕМДЕР, 2004. -Часть 4. -С. 289-292.

38. А5. Курносова СТ. Т-неприводимые расширения объединений полных графов // Всероссийский конкурс на лучшие научные работы студентов поестественным наукам. Материалы Федеральной итоговой конференции. М.: МИЭМ, 2004.-С. 333-334.

39. А6. Курносова С.Г. Т-неприводимые расширения для некоторых классов графов // Теоретические проблемы информатики и ее приложений. -Саратов: СГУ, 2004. Вып 6. - С. 113-125.

40. А9. Курносова С.Г. Т-неприводимые расширения объединений полных графов // Известия Саратовского университета. Серия «Математика. Механика. Информатика.» Саратов: СГУ, 2005. - Выпуск 1. - Том 5. - С. 107-115.

41. All. Курносова С.Г. Построение Т-неприводимых расширений для класса полных бинарных деревьев // Вестник молодых ученых «Ломоносов». М.: Макс Пресс, 2006. - Вып. III. - С. 58-66.