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

4857787

ДОЛГОВ Александр Алексеевич

ТОЧНЫЕ РАСШИРЕНИЯ ГРАФОВ

.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

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

2 и О ИТ 2011

САРАТОВ 2011

4857787

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

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

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

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

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

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

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

Защита состоится « 10» ноября 2011 г. в 15 ч. 30 мин, на заседании диссертационного совета ДМ 212.243.15 по присуждению ученой степени кандидата наук в Саратовском государственном университете по адресу: 410026 г. Саратов, ул. Астраханская, 83, IX корпус, механико-математический факультет.

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

Автореферат разослан « Ц » 2011 г.

Ученый секретарь диссертационного совета кандидат физико-математических наук, доцент ¿^¿СЛ В.В.Корнев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

В 1976 году Хейзом была предложена модель отказоустойчивости, основанная на графах [6]. Технической системе 2 сопоставляется граф вершины которого соответствуют элементам системы 2, ребра - связям между элементами. В общем случае элементы могут быть разного типа, однако чаще всего на практике элементы системы оказываются однотипными. Говорят, что система £ является к-отказоустойчивой реализацией системы X, если отказ любых к элементов системы Е приводит к графу, в который можно вложить граф системы I.

Предложенная Хейзом модель может быть использована для исследования полной

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

В «чистой» теории графов для формализации понятий отказоустойчивости системы используется абстрактная конструкция - расширение графа. Основным объектом исследования в данной работе является частный случай расширения графа - точное расширение.

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

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

Точное расширение графа интересно само по себе, как граф, в колоде которого содержатся только изоморфные максимальные подграфы. Харари и Хейзу удалось ответить на вопрос о том, какой вид имеют точные расширения неориентированных графов и предложить два семейства точных ¿-расширений неориентированных графов для любого к > 0. Это полные неориентированные графы Кп й вполне несвязные графы Оп. Однако стоит отметить, что графы с изоморфными подграфами вызывали: интерес задолго до выхода статьи Харари и Хейза. Результаты, полученные Раджави и Розенталем в 1972 году [13], позволяют утверждать, что никакой граф кроме Оп и К„ не может быть точным ¿-расширением неориентированного графа при к > 1.

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

При изучении минимальных расширений изучалось свойство дополнительности расширения: граф обладает этим свойством, если дополнение его минимального расширения является минимальным. расширением дополнения самого графа. В неориентированном случае, как удалось показать М.Б.Абросимову, только граф обладающий свойством дополнительности расширения является точным расширением [19]. Точные расширения неориентированных графов , также исследовались М.Ф.Караваем с точки зрения теории симметрии [23].

Две вершины и и V графа С называются подобными, если существует автоморфизм такой что Дм) - v. Граф, все вершины которого подобны, называется вершинно-симметрическим (вершинно-транзитивным). Как оказалось вершинно-симметрические графы -единственные неориентированные графы, являющиеся точными расширениями [5, 19]. В ориентированном случае вершинно-симметрические графы также являются точными расширениями.

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

существует ни одного неориентированного графа все вершины которого являются псевдо-подобными [9]. Транзитивный турнир - это единственный турнир, все вершины которого псевдо-подобны [7].

Графы с псевдо-подобными вершинами представляют большой интерес,. поскольку считается, что они ; могут оказаться полезными для решения проблемы реконструируемости неориентированных графов [9].

. ■ Операция вершинной подстановки, описанная в данной работе,, позволяет : получать точные расширения ориентированных графов,, не являющиеся верщинно-симметрическими графами ми транзитивными турнирами. Примечательно то, -что графы данного семейства, так же как и ; транзитивные турниры, содержат большие подмножества попарно псевдо-подобных вершин [8]. .,

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

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

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

- описаны свойства точных расширений, принадлежащих разным классам графов;

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

— решена задача описания графов имеющих точное к-у- расширение при любом к > 0;

■ — найдена схема построения турниров, являющихся точными 1-й .2-расширениями. Все перечисленные результаты являются новыми. Методика исследования. Результаты работы получены с использованием методов теории графов, теории дискретных систем, теории вычислительных экспериментов и теории алгоритмов.

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

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

Апробация работы. Результаты диссертации докладывались на XV Международной конференции по проблемам теоретической кибернетики (Казань, 2008), на международной научной конференции «Компьютерные науки и информационные технологии» (СГУ, 2009), на международной конференции «Дискретная математика, алгебра и их приложения» (Минск, 2009), на международном научном форуме «ЛОМОНОСОВ-2010» (Москва, 2010) и на всероссийской конференции «Дискретная оптимизация и исследование операций» (Алтай, 2010), на VIII, IX и X Сибирской научной школе-семинаре с международный участием «Компьютерная безопасность и криптография» (Омск 2009, Тюмень 2010, Томск 2011). Кроме того, результаты диссертации представлялись в 2009, 2010 и 2011 годах на научном семинаре кафедры Теоретических основ компьютерной безопасности и криптографии факультета Компьютерных наук и информационных технологий СГУ.

Публикации. Результаты диссертации опубликованы в работах [Al-А 13]. Работы [Al] и [А2] опубликованы в изданиях, включенных в перечень ВАК российских рецензируемых научных журналов, в которых должны быть опубликованы основные научные результаты диссертаций на соискание ученых степеней доктора и кандидата наук.

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

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность темы и приводится краткое содержание диссертации.

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

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

. Ориентированным графом (орграфом или просто графом) называется пара (V, а), где V - конечное непустое множество (множество вершин), а соотношение в множестве V (отношение смежности). Неориентированным графом (неографом) называется орграф с антирефлексивным и симметричным отношением смежности. Орграф С = ( V, а) называется направленным графом , или диграфом, если его отношение а антисимметрично, то есть нет встречных дуг за исключением,. быть может, петель. Полный диграф без петель называется турниром.

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

Степенью исхода вершины у орграфа (7 называется число </(у) дуг орграфа О, имеющих V своим началом. Степень захода вершины V - это количество (Г (у) дуг, имеющих V своим концом.

В неориентированном графе с?(у) = сГ{у) = ¿/(у). Степенью вершины V в неориентированном графе С будем называть количество вершин в С, смежных с V, и обозначать через с/(у). Неориентированный граф, степени вершин которого равны, называется регулярным. Набор чисел, являющихся степенями вершин неографа С, называют его степенным множеством, а вектор, составленный из степеней вершин неографа й в порядке невозрастания, - вектором степеней.

Маршрутом в орграфе С = {V, а) называется последовательность дуг (у0, V]), (у|, у2), ..., (у,и,у„). При этом говорят, что У() - начальная вершина маршрута, а V,, -конечная. Говорят также, что вершина V,, достижима из Уо-Маршрут, в котором никакая дуга не встречается более одного раза, называется путем. Если начальная и конечная вершины совпадают, то путь называется циклическим. Путь, каждая вершина которого принадлежит не более чем двум его дугам, считается простым. Простой циклический путь называется контуром, а простой путь, не являющийся контуром, называется ориентированной цепью. Петля называется тривиальным контуром. Орграф, не имеющий нетривиальных контуров, называется бесконтурным.

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

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

Граф называется сильно связным {сильным), если любые две его вершины являются взаимно достижимыми.

Подграфом графа (? = (V, а) называется пара С = (V, а?), Рс Г и а'= (V х V) п а. Подграф графа в называется максимальным, если он получается из графа б удалением одной вершины и всех связанных с нею ребер. Список максимальных подграфов графа С называют его колодой.

, Объединением двух графов С\ = (V], а\) и ф = (У2, «2) называется граф и Сп = (У\ и а\ и с^).

Две вершины и и V графа С будем называть подобными, если существует автоморфизм /, такой что Дг/) = V. Граф, все вершины которого подобны, называется вершинно-симметрическим. Граф, имеющий только тождественный автоморфизм, называется асимметричным.

Две вершины и и V графа С будем называть псевдоподобными, если они не подобны, однако графы С - V и С - и изоморфны.

Вложением графа С\ = (У\, «О в граф С2 = (У2, «2) называется такое инъективное отображение ¥2, что

для любых вершин и, V е ¥\ выполняется следующее условие:

(и, V) € а, => (Д«),У(у)) е аг.

Назовем граф = (¥к, ак) (вершинным) к-

расширением графа С = (V, а), если граф С можно вложить в каждый подграф графа Сд, получающийся удалением любых его к вершин и всех связанных с ними ребер. Если Т7 С V, то будем обозначать через й - ^ граф, получающийся из С удалением всех вершин, принадлежащих Г, и связанных с ними ребер.

Граф С*=(У*, а) называется минимальным (вершинным) к-расширением графа (7 = (V, а), |К| = п, если выполняются следующие условия [5]:

1) является ¿-расширением графа С, то есть граф С вкладывается в каждый подграф графа О , получающийся удалением любых его к вершин;

2) \У*\ = п + к;

3) а имеет минимальную мощность при выполнении условий 1) и 2).

Частным случаем минимального расширения графа является точное расширение. Граф Н называется точным (вершинным) к-расширением графа С, если граф С изоморфен каждому подграфу графа Н, получающемуся путем удаления любых его /с вершин и всех связанных с ними дуг (ребер). При к = 1 будем говорить просто о точном (вершинном) расширении графа. Легко показать, что точным расширением может являться только граф, имеющий петлю в каждой вершине или не имеющий петель вовсе.

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

Третий параграф содержит описание алгоритма поиска точных расширений турниров. Важной особенностью алгоритма является его легкая распараллеливаемость. Для поиска точных расширений турниров с числом вершин до 12 была разработана система распределенных вычислений. Поиск точных расширений проводился на 9 компьютерах мощностью 2ГГц в течение недели.

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

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

Во второй главе собраны материалы, описывающие основные свойства точных расширений графов.

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

Теорема 2.1.1. Суммы степеней исхода и захода вершин диграфа (7, являющегося точным расширением, равны.

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

В последующих четырех параграфах собраны сведения по точным расширениям для различных классов орграфов.

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

Теорема 2.2.1 (О несвязных точных расширениях графов). Граф (? = С/ и С2 и... и Си является точным расширением некоторого графа С тогда и только тогда, когда все О,- изоморфны друг другу и каждое Gj является точным расширением.

Кроме того, удалось показать, что при к > 1 только вполне несвязный граф 0„ является несвязным точным к-расширением (теорема 2.2.2). Во всех последующих параграфах рассматриваются только связные точные расширения графов.

В третьем параграфе описываются точные расширения графов, имеющих встречные дуги. Для точных

расширений такого вида удалось выявить важное структурное свойство:

Теорема 2.3.1. Если орграф й = (V, а) является

рючным расширением, тогда и его части С = (V, а ), где

' ....... *

а = {(х,у) | х, у е V, (х, у) е а & (у, х) е а}

** **

и С ,=т. (У, а ), где **

' а = {(х, у) | х, у е V, (х, у) е а & (у, х) 0 а}

также являются точными расширениями.

Важным следствием теоремы 2.3.1 является то, что при /с > 1 точных /с-расширений, содержащих встречные дуги, не существует (следствие 2.3.1).

Одним из основных результатов диссертации является полное описание не сильно связных точных расширений графов. Этому посвящен четвертый параграф и следующие две теоремы:

Теорема 2.4.1. Точным расширением может быть только бесконтурный или сильно связный граф.

Теорема 2.4.2, Единственным связным п-вершинным бесконтурным точным расширением является транзитивный турнир Т„.

Основные свойства сильно связных точных расширений орграфов рассматриваются в пятом параграфе. Теоремы 2.5.1-2.5.3 описывают вид вектора степеней, соответствующий точным расширениям сильно связных орграфов.

Теорема 2.5.1. Множество степеней исхода (захода) вершин графа, являющегося точным расширением, имеет вид

{(I, с1+1, й+2 ... где с1> 0, г > 0.

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

Теорема 2.5.3. В сильно связном п-вершинном турнире Т, п > 3, являющемся точным расширением, любой

максимальный подграф, содержащий все вершины графа С с одной степенью исхода (захода), содержит одинаковое количество вершин.

В шестом параграфе затрагивается проблема единственности точного расширения графа. Единственность точного расширения тесно связанна с реконструируемостью графов. Если для некоторого графа С можно построить два неизоморфных точных расширения С\ и 67 , то, очевидно, что графы 0\ и Сг являются не реконструируемыми, поскольку колоды и того и другого состоят из графов, изоморфных С. Основным результатом параграфа является доказательство того, что известные нереконструируемые диграфы Стокмейера [14] не являются точными расширениями.

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

В первом параграфе описываются все известные графы, имеющие точное ^-расширение при любом к > 0. Такими графами являются графы 0„, К„ и Т„. Одним из самых важных результатов работы является:

Теорема 3.1.2. Существует ровно три бесконечных семейства графов, имеющих точное к-расширение при любом к > 0, Это полные графы К„, вполне несвязные графы 0„ и транзитивные турниры Т„.

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

Кроме того, удалось показать, что среди графов, не входящих в описанные семейства, могут встречаться только точные 1- и 2-расширения. Причем точными 2-

расширениями могут быть только сильно связные турниры с числом вершин вида 4^ + 3.

Второй параграф посвящен описанию поиска турниров, являющихся точными 2-расширениями.

:,В третьем параграфе описывается семейство точных 2-расширений турниров.

В приложении 1 приводятся статистические данные по точным расширениям диграфов с числом вершин 4, 5, 6, 7, 8 и 9. Точные расширения диграфов были получены в результате вычислительных экспериментов, с использованием методов, описание которых приведено в параграфе 2.3 первой главы.

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

Автор выражает искреннюю благодарность своему научному руководителю - кандидату физико-математических наук, доценту Михаилу Борисовичу Абросимову за постоянную помощь, профессиональную поддержку и своевременные замечания. . .Отдельную благодарность автор приносит заведующему кафедрой ТОКБиК профессору Вячеславу Николаевичу Салию за поддержку и внимание к работе. .

ЛИТЕРАТУРА

1. Avizienis A. The design of fault tolerant computers // AFIPS Conference Proceedings. 1967. P. 733-743.

2. Goldberg M. The group of the quadratic residue tournament // Canadian Mathematical Bulletin. 2001. № 17. P. 227-236.

3. Harary F., Palmer E.M. Graphical Enumeration // Academic Press. NY. 1973.

4. Harary F., Hayes J. P. Edge fault tolerance in graphs // Networks. 1993. Vol.23. P. 135-142.

5. Harary F„ Hayes J.P. Node fault tolerance in graphs // Networks. 1996. Vol. 27. P. 19-23.

6. Hayes J.P. A graph model for fault-tolerant computing system // IEEE Trans. Comput. 1976. Vol. 25. №9. P. 875884.

7. Jean M. Line-symmetric tournaments // Recent Progress in Combinatorics, W.T.Tutte ed., Academic Press, New York. 1969. P. 265-271.

8. Kimble R.J., Schwenk A.J. and Stockmeyer P.K. Pseudosimilar vertices in a graph // J. Graph Theory. 1981. №5. P. 171-181.

9. Lauri J. Pseudosimilarity in graphs - a survey // Ars Combin. 1997. №46. P. 77-95.

10. Lauri J. Constructing graphs with several pseudosimilar vertices or edges // Discrete Math. 2003. №267. P. 197211.

11. McKay B.D., Royle G.F. The transitive graphs with at most 26 vertices // Ars Combinatoria. 1990. №30. P. 161176.

12. Morris J. Automorphism groups of circulant graphs: a survey // Graph Theory, Trends in Math. 2006. P. 311325.

13. Radjavi H„ Rosenthal P. Graphs with isomorphic subgraphs // London Math. Soc. (2). 1972. Vol. 6. P. 7072.

14. Stockmeyer P. A Census of non-reconstructable digraphs, I: six related families // Journal of Combinatorial Theory B. 1981. V. 31. P. 232-239.

15. Turner J. Point-symmetric graphs with a prime number of points // J.Combin. Theory. 1967. №3. P. 136-145.

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

17. Абросимов М.Б. Точные расширения графов с числом вершин не более одиннадцати. Саратов: СГУ, 2001. 15с.; Деп. в ВИНИТИ 14.08.2001, №1870-В2001.

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

19. Абросимов М.Б. Некоторые вопросы о минимальных расширениях графов // Известия Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2006. №6. С. 86-91.

20. Абросимов М.Б. О сложности некоторых задач, связанных с расширениями графов // Матем. Заметки. 2010. №5(88). С. 643-650.

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

22. Зыков A.A. Основы теории графов. М.: Наука, 1984.

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

24. Харари Ф. Теория графов. М.: УРСС, 2003.

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

AI. Абросимов М.Б., Долгов A.A. О реконструируемое™ малых турниров. // Известия Саратовского университета. Новая серия. Серия Математика. Механика. Информатика. 2009. Т. 9, вып. 2. С. 94-98.

А2. Абросимов М.Б., Долгов A.A. О бесконтурных точных расширениях // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2010. Т. 10, вып. 1.С. 83-88.

A3. Абросимов М.Б., Долгов A.A. Точные расширения некоторых турниров // Вестник ТГУ. Приложение. 2007. №23. С. 211-216.

A4. Долгов A.A. Некоторые свойства малых турниров. -Саратов: СГУ, 2007. 24с.; Деп. в ВИНИТИ 24.07.07, Ж769-В2007.

А5. Долгов A.A. Ориентации, приводящие к точным расширениям // Проблемы теоретической кибернетики. Тезисы докладов XV международной конференции (Казань, 2 - 7 июня 2008 г.). Казань: Отечество, 2008. 148с. С.27.

А6. Абросимов М.Б., Долгов A.A. Семейства точных расширений турниров // Прикладная дискретная математика. 2008. № 1. С.101-107.

А7. Долгов A.A. К вопросу о точных расширениях турниров // Прикладная дискретная математика. Приложение. 2009. № 1. С. 98-99.

А8. Долгов A.A. Об операции вершинной подстановки и точных расширениях графов // Компьютерные науки и информационные технологии. Материалы Международной научной конференции. СГУ. 2009. С. 78-80.

А9. Долгов A.A. О некоторых свойствах точных расширений орграфов // Международная научная конференция. Дискретная математика, алгебра и их приложения. Минск. 2009. С.89-91.

А\0. Долгов A.A. О семействах точных вершинных к-расширений графов при к > 1 // Материалы Международного молодежного научного форума «JIOMOHOCOB-2010», Вычислительная математика и кибернетика. М.: МАКС Пресс, 2010. С. 30-32.

All.Долгов A.A. К вопросу о точных вершинных к-расширениях графов при к> 1 // Российская конференция «Дискретная оптимизация и исследование операций»: Материалы конференции (Алтай, 27 июня - 3 июля 2010). Новосибирск: Изд-во Ин-та математики, 2010. С. 133.

А12. Долгов A.A. Семейство точных 2-расширений турниров // Прикладная дискретная математика. 2010. № 9. С. 96-99.

А13 .Абросимов М.Б., Долгов A.A. К вопросу о единственности точных вершинных расширений // Прикладная дискретная математика. Приложение: Тезисы докладов X Сибирской научной школы-семинара с международным участием «Компьютерная безопасность и криптография» -SYBECRYPT'll (Томск, ТГУ, 5-10 сентября 2011 г.). 2011. №4. С. 81-83.

Подписано в печать 28.09.2011. Формат 60x84 7i6. Бумага офсетная. Гарнитура Times. Объем 1.25 печ. л. Тираж 100 экз. Заказ № 196-Т

Типография СГУ г. Саратов, ул. Б. Казачья 112а тел.: (845-2) 27-33-85

ВВЕДЕНИЕ.

ГЛАВА 1. МЕТОДЫ ПОСТРОЕНИЯ ТОЧНЫХ РАСШИРЕНИЙ ГРАФОВ.

§ 1. Основные определения и вспомогательные утверждения.

§ 2. Алгоритмы поиска точных расширений графов и диграфов.

2.1. Максимальные коды графов.

2.2. Точные расширения неориентированных графов.

2.3. Точные расширения диграфов.

§ 3. Алгоритмы поиска точных расширений турниров.

У 3.1. Генерация турниров.

3.2'. Распределенная система вычислений.

3.3. Алгоритм поиска точных расширений турниров :.3 Г

§ 4. Семейства точных расширений графов.

4.1'. Вершинно-симметрические графы.

4.2. Транзитивные турниры.'.

4.3. Операция вершинной подстановки.

ГЛАВА 2. ТОЧНЫЕ РАСШИРЕНИЯ ГРАФОВ.

§ 1. Точные расширения неориентированных графов.

§ 2. Несвязные точные расширения орграфов.

§ 3. Точные расширения орграфов, имеющих встречные дуги.

§ 4. Бесконтурные точные расширения орграфов.

§*5: Сильно связные точные расширения орграфов.

§ 6. Единственность точного расширения1.

ГЛАВА 3. ТОЧНЫЕ ^-РАСШИРЕНИЯ ГРАФОВ ПРИЛГ > 1.

§ 1. Семейства точных к-расширений при любом к > 0.

§ 2. Поиск точных 2-расширений турниров.

§ 3. Семейство точных 2-расширений турниров.

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

В 1976 году Хейзом была предложена модель отказоустойчивости, основанная, на* графах [б]. Технической-системе Е сопоставляется граф С/(Е), вершины которого соответствуют элементам системы Е, ребра — связям между элементами. В общем случае элементы могут быть.разного типа, однако чаще всего на практике элементы системы оказываются однотипными. Говорят, что система Е* является к-отказоустойчивой реализацией системы £, если отказ

1( любых к элементов системы Е приводит к графу, в который можно вложить граф системы Е.

Предложенная Хейзом > модель может быть использована для исследования полной' отказоустойчивости системы, то есть возможности продолжения ее работы без потери-функциональных свойств при отказе одного или нескольких элементов [1]. В зависимости от интерпретации отказа-в данной модели рассматривают несколько видов отказоустойчивости. Вершинная отказоустойчивость предполагает в качестве отказа рассматривать отказ элемента [5, 6]. Реберная отказоустойчивость * рассматривает отказы» связей между элементами [4].

В «чистой» теории графов для.' формализации понятий отказоустойчивости системы используется абстрактная конструкция — расширение графа. Основным объектом исследования в данной работе является частный случай расширения графа - точное расширение.

Ориентированным графом {орграфом или просто графом) Ф называется пара (V, а), где V - конечное непустое множество (множество вершин), а а — отношение в множестве V (отношение смежности). Неориентированным графом (неографом) называется орграф с антирефлексивным и симметричным отношением смежности. Элементы множества а называются дугами для« орграфа и ребрами для неориентированного графа.' Орграф Э = (¿V, а) называется направленным графом или диграфом, если его отношение а антисимметрично, то есть нет встречных дуг за исключением, быть» может, петель. Полный' диграф? без петель называется турниром. У турнира' между любыми«-двумя различными вершинами существует в-точности одна дуга.

Неориентированный граф, любые две вершины которого смежны, называется яаяньш и обозначается Кп. Граф с пустым отношением смежности « называется вполне несвязным или нулъграфом и обозначается Оп.

Подграфом графа О = (V, а) называется пара (V, а*), где Гс Ки а' = (V х V) п а. Подграф графа- (7 называется- максимальным, если он получается ( из О удалением одной вершиньь и всех связанных с нею ребер. Будем обозначать через (? — V максимальный подграф, получающийся из графа & удалением, вершины V. Список максимальных подграфов графа С7 называют его колодой.

Два графа = а{) и С?2 = (Уг, оь) называются изоморфными, если можно установить взаимно однозначное соответствие /: V] —> У2, сохраняющее отношение смежности: (и, у) е а\ <=> (/[и),Ду)) <е ог2> для любых и, v е У\. В этом случае пишут С^ = (?2

Изоморфизм графа на себя называется» автоморфизмом. Тождественное отображение является автоморфизмом для любого графа. Множество автоморфизмов графа С? относительно операции суперпозиции автоморфизмов и их обращения как взаимно однозначных преобразований на множестве вершин <7 образуют группу АиІ^СТ).

Вложением графа О\ = (Уи0і\) в граф — а2) называется такое инъективное отображение /: Кі —> У2, что для любых вершин м,у е У\ выполняется следующее условие: (и, v) є а\ :=> (Дм), Ду)) є а2.

Назовем іраф бд = (Уд, (вершинным) к-расширением графа О = (К, (X); если; граф Сг можно вложить, в- каждый подграф графа получающийся удалением- любых его к вершин и всех связанных- с. ними ребер. Заметим; что определение не теряет смысла и при? к = 0: Если? Е с V, то будем обозначать, через (7 — граф, получающийся из графа Є удалением; всех вершин; принадлежащих Е, и связанных с ними ребер.

Граф О =(У, а ) называется минимальным (вершинным) к-расширением графа (7 = (V, а), \ У\ — и, если выполняются следующие условия:

1); граф О* является Аг-расширением графа О, то есть граф Сг вкладывается в-каждый подграф графа, б1*, получающийся удалением любых его к вершин;

2) \У*\^п + к;.: ' ' .

3) а> имеет минимальную мощность при выполнении условий 1) и 2).

Частным случаем1 минимального расширения» графа является точное расширение. • Граф ів называется точным (вершинным) к-расширением графа бу если граф С? изоморфен каждому подграфу графа//, получающемуся путем удаления любых его А: вершин и всех связанных с ними дуг. При А: = 1 будем? говорить, просто о расширении графа. , .

Понятие точного* расширения графа (точной! отказоустойчивой реализации); было введено- Харари и. Хейзом в; работе 1996 года- [5]. Следует обратить внимание на то,, что подход к изучению точных расширений; который используется в этой статье, отличается от подхода к изучению минимальных расширений; графов. В случае минимального расширения обычно рассматривается интересный с практической точки зрения класс графов и описываются способы построения минимальных расширений для графов из заданного класса. Подход этот оправдан, поскольку минимальное расширение можно построить для любого заданного графа [5], а задача построения минимального расширения является вычислительно сложной [20].

Точное расширение графа интересно само по себе, как граф, в колоде которого содержатся только изоморфные максимальные подграфы. Харари и Хейзу удалось ответить на вопрос о том, какой вид имеют точные расширения неориентированных графов и предложить два семейства точных ^-расширений неориентированных графов для любого к > 0. Это полные неориентированные графы Кп и вполне несвязные графы Оп. Однако стоит отметить, что графы с изоморфными подграфами вызывали интерес задолго до выхода статьи Харари и Хейза. Результаты, полученные Раджави и Розенталем в 1972 году [13], позволяют утверждать, что никакой граф кроме Оп и К„ не может быть точным ^-расширением неориентированного графа при к> 1.

При изучении минимальных расширений изучалось свойство дополнительности расширения: граф обладает этим свойством, если дополнение его минимального расширения является минимальным расширением дополнения самого' графа. В неориентированном случае, как удалось- показать М.Б.Абросимову, только граф обладающий свойством дополнительности расширения является точным расширением [19]. Точные расширения неориентированных графов также исследовались М.Ф.Караваем с точки зрения теории симметрии [23].

Как оказалось вершинно-симметрические графы* - единственные неориентированные графы, являющиеся точными* расширениями [5, 19]. Две вершины и и V графа С называются подобными, если существует автоморфизм /, такой что /{и) - V. Граф, все вершины которого подобны, называется вершинно-симметрическим (вершинно-транзитивным). В ориентированном случае вершинно-симметрические графы также являются точными расширениями.

Вершинно-симметрические графы уже довольно длительное время являются объектом изучения. Особое место среди них занимают, так называемые циркулянты или графы Кэли. Циркулянтом называется; ^-вершинный граф О, такой, что, если его вершинам приписать метки; от 0 до п — 1, то из вершины I в вершину ] проходит дуга, тогда и- только тогда, когда, г- / (шос! п) е Д где это некоторое подмножество множества \ {О}. Известно, что для простого п все вершинно-симметрические' графы будут циркулянтами [11]. Однако в общему случае это не так. Минимальным« по; количеству вершин! неориентированным вершинно-симметрическим графом, не являющимся графом} Кэли; является; 10-вершинный граф Петерсена [11]- В ориентированном случае подобные графы* встречаются уже при числе вершин 8.

Еще одним интересным семейством точных расширений являются-транзитивные турниры. Транзитивный турнир— это» турнир с транзитивным отношением смежности. В(; отличие от вершинно-симметрических графов-гранзитивный турнир является асимметрическим, то есть у транзитивного турнира нет ни одной пары подобных вершин. Однако, то, что все максимальные подграфы транзитивного турнира изоморфны, говорит о том, что все его вершины в этом случае являются псевдо-подобными: Две вершины и и V графа О называются псевдо-подобными, если они не: подобны, однако, графы (7 - V и <7 - и изоморфны. Не существует ни одного неориентированного графа все вершины которого являются псевдо-подобными [9]. Транзитивный турнир -это единственный турнир, любая пара вершин которого псевдо-подобна [7].

Графы с псевдо-подобными вершинами представляют большой интерес, поскольку, считается, что они могут оказаться полезными для решения проблемы реконструируемости неориентированных графов - [9].

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

Работа состоит из введения, трех глав, содержащих 13 параграфов, библиографии, включающей 37 наименований, и двух приложений. Диссертация изложена на 80'страницах.

1. Avizienis A. The design of fault tolerant computers // AF1.S Conference Proceedings. 1967. P. 733-743.

2. Goldberg M. The group of the quadratic residue tournament // Canadian Mathematical Bulletin. 2001 № 17. P. 227-236.

3. Harary F., Palmer E.M. Graphical Enumeration // Academic Press. NY. 1973.

4. Harary F., Hayes J.P. Edge fault tolerance in graphs // Networks. 1993. Vol.23. P. 135-142.

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

6. Hayes J.P. A graph model for fault-tolerant computing system // IEEE Trans. Comput. 1976. Vol. 25. №9. P. 875-884.

7. Jean M. Line-symmetric tournaments // Recent Progress in Combinatorics,. W.T.Tutte ed., Academic Press, New York. 1969. P. 265-271.

8. Kimble R.J., SchwenkA.J. and Stockmeyer P.K. Pseudosimilar vertices in a graph //J. Graph Theory. 1981. №5. P. 171-181.9: Lauri J. Pseudosimilarity in graphs a survey // Ars Combin: 1997. №46. P. 7795.

9. Lauri J. Constructing graphs with several pseudosimilar vertices or edges // Discrete Math. 2003. №267. P. 197-211.

10. McKay B.D., Royle G.F. The transitive graphs with at most 26 vertices,// Ars Combinatoria. 1990. №30: P. 161-176.

11. Morris J. Automorphism groups of circulant graphs: a survey // Graph Theory, Trends in Math. 2006. P. 311-325.

12. Radjavi-H., Rosenthal P. Graphs with isomorphic subgraphs // London Math. Soc. (2). 1972. Vol. 6. P. 70-72.

13. Stockmeyer P. A Census of non-reconstructable digraphs, I: six related families I I Journal of Combinatorial Theory B. 1981. V. 31. P. 232-239.

14. Turner J. Point-symmetric graphs with a prime number of points // J.Combin. Theory. 1967. №3. P. 136-145.

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

16. Абросимов М.Б. Точные расширения графов с числом вершин не более одиннадцати. Саратов: СГУ, 2001. 15с.; Деп. в ВИНИТИ 14.08.2001, №1870-В2001.

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

18. Абросимов М.Б. Некоторые вопросы о минимальных расширениях графов // Известия Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2006. №6. С. 86-91.

19. Абросимов М.Б. О сложности некоторых задач, связанных с расширениями графов // Матем. Заметки. 2010. № 5(88). С. 643-650.

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

21. Зыков A.A. Основы теории графов. М.: Наука, 1984.

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