Т-неприводимые расширения графов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

Курносова Светлана Геннадьевна

Т-НЕПРИВОДИМЫЕ РАСШИРЕНИЯ ГРАФОВ

01 01 09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

□03059094

Саратов - 2007

003059094

Работа выполнена на кафедре теоретических основ компьютерной безопасности и криптографии Саратовского государственного университета им. Н.Г. Чернышевского

Научный руководитель:

кандидат физико-математических наук, профессор Салий Вячеслав Николаевич

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

доктор физико-математических наук, профессор Бредихин Дмитрий Александрович

кандидат физико-математических наук, доцент Папшев Сергей Владимирович

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

Томский государственный университет

Защита состоится « 3/ » qUOj 2007 г. в /¿Г ч. ЗО мин. на заседании диссертационного совета К 212.243.02 в Саратовском государственном университете им. Н Г. Чернышевского по адресу: 410012 г Саратов, ул Астраханская, 83

С диссертацией можно ознакомиться в Зональной научной библиотеке Саратовского государственного университета

эг /

Автореферат разослан » ¿t^ffeuJl 2007 г.

Ученый секретарь диссертационного совета кандидат физико-математических нау

доценг

Корнев В В

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

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

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

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

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

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

и Сю [17], которые рассматривали минимальные реберные расширения графов, представляющих собой решетку

Хотя дискретные системы, которые должны обладать свойством отказоустойчивости, сами по себе считаются достаточно надежными, но все же теоретически возможен отказ более чем одного элемента В связи с этим в 1993 и 1996 годах Харари и Хейз предложили модель соответственно реберных и вершинных ¿-расширений [20,21] Основные направления в этой области посвящены нахождению минимальных реберных ¿--расширений для циклов (например, работа [20]) и некоторых классов деревьев (например, работа [23])

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

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

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

других [24] М Б Абросимов в работе [4] описал минимальные расширения транзитивных турниров

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

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

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

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

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

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

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

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

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

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

Достоверность полученных результатов. Все полученные в диссертации теоретические результаты имеют строгое доказательство Кроме того,

достоверность теоретических результатов подтверждают вычислительные эксперименты

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

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

Исследования автора поддержаны грантом РФФИ 05-08-18082 Публикации. Основные результаты опубликованы в работах [А1-А12] Работа [А8] опубликована в издании, включенном в «Перечень ведущих рецензируемых научных журналов и изданий, в которых должны быть опубликованы основные научные результаты диссертации на соискание ученой степени доктора и кандидата наук»

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

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

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

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

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

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

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

В начале первой главы вводятся основные определения теории графов, используемые в работе Вторая часть этой главы посвящена общим свойствам Т-неприводимых расширений Там формулируются также основные леммы, необходимые для доказательств теорем в последующих главах Приведем основные определения (все определения даются из [5])

Ориентированным графом (орграфом) называется пара G=(V,a), где а (множество дуг) - отношение, заданное на множестве вершин V Если отношение а - симметричное и антирефлексивное, то граф по определению неориентированный (далее граф) Ребро (то есть пару встречных дуг) с концами и, \'е V обозначим через iiv

Над графами определены некоторые операции Так, соединением графа Gj - ,«]) с графом G2 = (172>а2) > ГДС '7i П V2 = 0 , называют граф Gj + G2 = (l\ UV7,a\ Uа2 U{»i'| ис l),ve V2}), a объединением этих графов будет граф Gj UG2 = (ViWi&i Ua2)

Частью графа G = (V,a) называется граф Gj = (Fj,a]) такой, что \\ с V и aj с (V\х 1\)Г\а Часть графа будет подграфом, если aj = (I'i х К]) П а Подграф по определению максимален, если он получается из исходного графа удалением одной вершины и всех связанных с нею ребер Максимальный подграф графа G, полученный удалением вершины v, обозначим через G-v Через G-uv обозначим граф, получающийся из графа G удалением ребра uv

Граф G по определению вкладывается в граф Я, если существует взаимно однозначное отображение ср множества вершин графа G в множество вершин графа //, такое что, если произвольные вершины и и v графа G смежны, то их образы q>{u) и qiv) смежны в графе Н

Расширением и-вершинного графа G называют граф Не и+1 вершинами такой, что G является частью каждого максимального подграфа графа II Простейшим примером расширения графа G будет его тривиальное расширение (TP) - соединение G + v исходного графа G с вершиной v Очевидно, что у графа существует с точностью до изоморфизма одно TP, и

будет корректным определить функцию ТР(б) на множестве всех неизоморфных графов

Т-неприводимые расширения для графа С получаются из тривиального расширения О+у удалением максимального возможного числа ребер таким образом, чтобы полученный граф был расширением для С?

Сформулируем критерий Т-неприводимости Теорема 1.1 (Критерий Т-неприводимости) Граф Я с п+1 вершинами тогда и только тогда будет Т-неприводимым расширением для и-вершинного графа б, когда

1 ° в графе Нсуществует вершина v, такая что II -у = С , 2° граф О вкладывается в любой максимальный подграф Н-и, где и -вершина графа Я, отличная от вершины v,

3° (свойство неприводимости) граф Н-иу не будет расширением для О, где и - любая вершина из графа Н, отличная от V □

Теорема 1.3 (Свойство 1) Если дан граф Я, являющийся Т-неприводимым расширением графа то при удалении из II любой вершины максимальной степени получится граф, изоморфный б □

Теорема 1.4 (Свойство 2) Никакой граф не может быть Т-неприводимым расширением для двух неизоморфных графов □

Учитывая эти свойства, можно говорить об однозначной восстановимости графа по любому его Т-неприводимому расширению

Введем следующее соглашение и будем считать, что в любом Т-неприводимом расширегаш вершины помечены в соответствии с ним Соглашение 1.1. Пусть граф Я получен из графа О добавлением одной вершины и некоторого набора ребер, инцидентных новой вершине Будем считать, что добавленная вершина всегда обозначается через V и что она не совпадает ни с одной вершиной графа в Так как существует изоморфизм у/ графов С и Н-\', то вершины графа //-v можно обозначить так, чтобы У<н)=(к)'=М'

Во второй главе изучаются Т-неприводимые расширения для важнейшего класса связных графов - деревьев Согласно определению, дерево - связный граф без циклов, и поэтому такая структура обладает свойством связности при минимальном количестве ребер Общая задача нахождения всех Т-неприводимых расширений для произвольного дерева остается нерешенной Пока удалось получить описания только для некоторых подклассов класса деревьев - для цепей колес (Теорема 2 1, 2 2) и для пачьм

Дерево П„ = (V ,а) назовем пальмой высоты к, если

^ = {«1, 0,гь ,2к), а={20»;|( = 1,п}и{2г_12)|г = 1,/1>,и>1,/1>1

Теорема 2.3. Для пальмы =(У,а) Т-неприводпмым расширением будет

граф Я = (V им, а и а'), где а' = {u:\v\i = , если /г < 4 , и

а' = {и\V | г = V"} 1) {г^,г'йу} II | г = 2,/г-З} , если /г > 4

Если /г<4 или /г=4 и п=2, то у пальмы = (V,а) будет еще одно Т-неприводимое расширение - граф Н\ = (V иМ,а 1)ос[), где

Других Т-неприводимых расширений у пальмы нет о Главным результатом этой главы является решение задачи о нахождении всех Т-неприводимых расширении для полных бинарных деревьев

Полным бинарным деревом называется дерево с п>3 вершинами, у которого все вершины имеют степень 1 (листья) или 3 (узловые вершины), кроме одной вершины степени 2, называемой корнем

Решение задачи описания всех Т-неприводимых расширений для полного бинарного дерева дают Теоремы 2 4-2 7 Обозначим корень полного бинарного дерева Т через г;0, а две смежные с ним вершины через и, и и2 Для определения строения Т-неприводимого расширения полного бинарного дерева необходимо выяснить принадлежность этого дерева одному из трех следующих подклассов

Полное бинарное дерево принадлежит первому подклассу, если одна из вершин, смежных с корнем дерева, имеет степень 1 (не теряя общности, можно считать, что это вершина ;/]), а вторая (вершина и2) - степень 3 и в качестве ближайших потомков имеет вершину степени 1 (обозначим ее через из) и вершину степени 3 (обозначим ее как гц) Случай, когда обе вершины, являющиеся непосредственными потомками вершины и2, оказываются листьями, рассмотрен в этой главе в разделе пальм (Теорема 2 3) Теорема 2.5. У полного бинарного дерева Т, принадлежащего первому подклассу, есть только два неизоморфных Т-неприводимых расширения граф Я0 = ТР(У') - и'()\< и граф Я2 = ТР(7 ) - и'2у □

Полное бинарное дерево принадлежит второму подклассу, если одна из вершин, смежных с корнем дерева, имеет степень 1 (не теряя общности можно считать, что это - вершина щ), а вторая вершина (вершина н2) будет иметь степень 3 и два ее непосредственных потомка (обозначим их щ и г/4) будут узловыми вершинами (то есть их степень равна 3) Теорема 2.6. У полного бинарного дерева Т второго подкласса единственным Т-неприводимым расширением будет граф Я0 = ТР(7 ) - г/0у □

Полное бинарное дерево принадлежит третьему подклассу, если обе вершины, смежные с корнем дерева, имеют степень 3

Пусть (Г, и) дерево Т с выделенной вершиной и Будем говорить, что два таких дерева (Г1, г/1) и (Т2, и ) изоморфны, если существует изоморфизм дерева Г1 на дерево 7'2, при котором вершина и1 переходит в вершину и2 Теорема 2.7. У полного бинарного дерева третьего подкласса Т единственным Т-неприводимым расширением является следующий граф

1 граф 7/0=ТР(7)- г/'0у, если для дерева Т выполнены условия

(А1) в поддереве 7\ дерева Т существует вершина VI, такая что деревья Ил , и о) и (Т^.уО изоморфны, где Т* поддерево дерева Т, представляющее собой дерево Т\ с добавленной вершиной щ и ребром и0ии (А2) в поддереве Т2 дерева Т существует вершина у2, такая что деревья

(Г2+ ,и0) и (72+ Л'г) изоморфны, где Т} поддерево дерева Т, представляющее собой дерево 7'2 с добавленной вершиной и0 и ребром щн2,

2 граф Я,= ТР(7)- и\\>, если для дерева Т выполнены условия

(Б1) дерево Т3 изоморфно дереву Т2 и дерево ТА изоморфно Тъ где и3 и и4 -

непосредственные потомки вершины щ,

(Б2=А2),

3 граф Н2=ТР(Т)- г/2т , если для дерева Т выполнены условия

(В1) дерево Т$ изоморфно дереву Т\ и дерево Т6 изоморфно дереву 7\, где

г/5 и и6 — непосредственные потомки вершины г/2,

(В2=А1),

4 граф Я=ТР(7), если для дерева Т не выполнено ни одно из условий А (то есть А1 или А2), Б (то есть Б1 или Б2), В (то есть В1 или В2) □

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

граф Я и Я1, где Н1 является изоморфной копией графа Я □

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

В этой главе найдены также Т-неприводимые расширения для объединений в классах колес и цепей (Теоремы 3 2, 3 3) Рассматриваются Т-неприводимые расширения для объединения некоторого графа С? (предполагается, что в графе С нет изолированных вершин) с вполне несвязньш графом Оп = (У,0),\ V п > 0 Для таких графов справедлива следующая теорема

Теорема 3.4. Пусть даны граф О без изолированных вершин и вполне несвязный граф Оп Предположим, что у графа б имеется всего к неизоморфных Т-неприводимых расширений графы Щ, ,///, Тогда Т-

неприводимыми расширениями для графа С* = С и Оп будут графы

Я,+ = II, и Оп,1 = \,к При этом, если в графе О степени всех вершин больше

1, то только графы Н*,1-\,к, будут Т-неприводимыми расширениями для

графа □

Таким образом, в случае, когда в графе все вершины имеют степень больше 1, добавление к графу изолированных вершин ничего существенно нового в смысле построения Т-неприводимых расширений не дает В случае же, когда в графе есть вершины степени 1, добавление изолированных вершин может уменьшить число добавляемых ребер в Т-неприводимом расширении (Теоремы 3 5 и 3 6)

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

Рассмотрим последовательность полных графов {Кп+1}\=о,п>\,1 >0 Положим С = , где граф есть объединение т, изоморфных

копий полного графа Кп+,, причем т() > О, пц > 0 и т, > 0 для 1 = 1,1-1 Граф полагается пустым графом (то есть графом с пустым множеством вершин), если т, = 0 Обозначим копии полного графа Кп+1, если т1 > 0 , через , у = 1, т1 Так определенный граф О однозначно задается числом п и вектором (тй,тъ ,т{)

Согласно Лемме 3 1 ТНР рассматриваемого графа Ст = и^о^и"'; можно задать последовательностью (я0 а\, >я;)> гДе а, показывает, со скольктш копиями полного графа К„+, соединяется вершина V Например, графу С = Кп \}Кп+х соответствует вектор (1,1), а его ТНР определяется вектором (1,0)

По вектору (т0,щ, ,/и/), задающему' граф О, молено построить множество векторов (а0,йь ,«/). определяющих все ТНР для в Теорема 3.7. Представленный ниже алгоритм строит в точности все Т-неприводимые расширения для графа С = , заданного вектором

{та,ть ,17ц) и числом п>\

АЛГОРИТМ

1 Положить а0=т0, доопределив = 0 и тм = 0, г=1,

2 по Таблице, приведенной ниже, в столбце найти соответствующее значение т,тм (где .г - любое число больше 1), в строке найти дь2 а,_} и на их пересечении получить значение а,,

(Если возможно несколько вариантов «О или 1», то на этом этапе процесс дальнейшего построения вектора (а0 ,а{, , щ) должен происходить отдельно для каждого из полученных вариантов) Таблица

ш а, г ш, т,п 0 0 т, т,ц 0 1 те,1 0 х т, /я,+1 1 0 т, 1 1 1 т, 1 1 л т, т,*1 х 0 т, ш,+1 х 1 т, т^ X X

0 0 1 1 1 т, т, т,

1 0 1 1 1 т, т, т,

X 0 1 1 1 т, т, т,

0 1 0 0 0 0 0 или1 0 или1 0 0 или1 0 или1

1 1 0 0 0 0 0 или1 0 или1

х 1 0 0 0 0 0 или1 0 или1

0 х 0 0 или1 0 или1 0 0 или1 0 шш1

1 ж - - - - - - - - -

X X - - - - - - - - -

3 положить /=/+1 и, если / < /, выполнять пункт 2

Результатом работы алгоритма будет множество векторов (я0, а.\, , ), задающих все Т-неприводимые расширения для графа О □

В качестве следствия (Теорема 3 8) к этой теореме определена верхняя и нижняя границы количества Т-неприводимых расширений для объединения полных графов

В первом приложении приведены 3-, 4-, 5- и 6-вершинные графы (исключая вполне несвязные графы) и все их Т-неприводимые расширения Каталог составлен с помощью компьютерной программы В первой главе проведен статистический анализ полученных результатов, в частности, сравниваются по включению множество Т-неприводимых расширений и множество минимальных расширений для рассматриваемых графов (результаты по минимальным расширениям взяты из [1])

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

Автор выражает глубокую и искреннюю благодарность своему научному руководителю профессору Вячеславу Николаевичу Салию за предложенную исследовательскую задачу и за помощь в ее решении

Литература

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

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

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

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

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

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

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

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

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

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

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

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

13 Курносова С Г. Решение задачи нахождения всех Т-неприводимых расширений для симметричных ориентаций цепей // Материалы XVI Международной школы-семинара «Синтез и сложность управляющих систем» (Санкт - Петербург, 26 -30 июня 2006 г ) - М Издательство мех-мат ф-та МГУ, 2006 - С 59-64

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

15 Салий ВН, Абросимов МБ, Курпосова С Г Графовые модели отказоустойчивости дискретных систем // Высокие технологии, фундаментальные и прикладные исследования, образование Сборник трудов Второй международной научно-практической конференции «Исследование, разработка и применение высоких технологий в промышленности» / Под ред А П Кудинова, Г Г Матвиенко, В Ф Самохина - СПб Изд-во Политехи ун-та,2006 -Том4 -С 54-55

16 Aviziems A Fault tolerant computing - An overview // IEEE Computer -1971 -Vol 4 -P 5-8

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

18 Farrad A A , Dawson RJ Designing optimal fault-tolerant star networks // Networks - 1989 - Vol 19 -P 700-716

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

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

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

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

23 Ku II K, Hayes JP Optimally edge fault-tolerance trees // Networks -1996 - Vol 27 -P 203-214

24 Sung TY, Lin CY, Chuang YC, Hsu LH Fault tolerance token nng embedding in double loop networks // Inform Process Lett - 1998 - Vol 66 -P 201-207

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

А1 Курпосова С Г Т-неприводимые расширения 3-, 4-, 5- и 6-вершинных графов // Рукопись деп в ВИНИТИ 21 06 2003, №1203-В2003 - 18 с А2 Курпосова С Г Каталог Т-неприводимых расширений для деревьев с числом вершин не более 10 // Рукопись деп в ВИНИТИ 30 06 2004, №1126-В2004 - 16 с

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

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

А5 Курпосова С Г Т-нсприводимые расширения объединений полных графов // Всероссийский конкурс на лучшие научные работы студентов по

естественным наукам Материалы Федеральной итоговой конференции — М МИЭМ, 2004 -С 333-334

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

А7 Курносова С Г Оптимальные расширения графов // Материалы XII Международной конференции студентов, аспирантов и молодых ученых «Ломоносов» - М Изд-во МГУ, 2005 - Том 1 - С 364 А8 Курносова С Г Т-неприводимые расширения полных бинарных деревьев // Вестник Томского государственного университета Приложение - 2005. -№ 14 - С 158-160

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

А10 Курносова С Г Построение Т-неприводимых расширений для класса полных бинарных деревьев // Материалы XIII Международной конференции студентов, аспирантов и молодых ученых «Ломоносов», секция «Вычислительная математика и кибернетика» - М Издательский отдел факультета ВМиК МГУ, 2006 - С 31-32

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

А12 Курносова С Г Некоторые вопросы построения оптимальных расширений для объединений графов // Материалы XIV Международной конференции студентов, аспирантов и молодых ученых «Ломоносов», секция «Вычислительная математика и кибернетика» - М Издательский отдел факультета ВМиК МГУ, 2007 - С 44

Курносова Светлана Геннадьевна т-НЕПРИВОДИМЫЕ РАСШИРЕНИЯ ГРАФОВ

01 01 09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Подписано в печать 20 04 07 Формат 60x84 1/16 Объем 1,0 п л Тираж 100 экз Заказ 117

Отпечатано в типографии «Новый ветер» 410012, Саратов, ул Б Казачья, 113

Введение.

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

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

Глава 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

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.