авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

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

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

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

ДОЛГОВ Александр Алексеевич ТОЧНЫЕ РАСШИРЕНИЯ ГРАФОВ 01.01.09 – дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

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

САРАТОВ 2011

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

Научный консультант:

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

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

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

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

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

Защита состоится « 10 » _ноября_ 2011 г. в 15 ч. 30 мин.

на заседании диссертационного совета ДМ 212.243.15 по присуждению ученой степени кандидата наук в Саратовском государственном университете по адресу:

410026 г. Саратов, ул. Астраханская, 83, IX корпус, механико-математический факультет.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



Транзитивный турнир – это турнир с транзитивным отношением смежности. В отличие от вершинно симметрических графов транзитивный турнир является асимметрическим, то есть у транзитивного турнира нет ни одной пары подобных вершин. Однако, то, что все максимальные подграфы транзитивного турнира изоморфны, говорит о том, что все его вершины в этом случае являются псевдо-подобными. Две вершины u и v графа G называются псевдо-подобными, если они не подобны, однако, графы G – v и G – u изоморфны. Не существует ни одного неориентированного графа все вершины которого являются псевдо-подобными [9].

Транзитивный турнир – это единственный турнир, все вершины которого псевдо-подобны [7].

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

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

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





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

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

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

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

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

– решена задача описания графов имеющих точное k расширение при любом k 0;

– найдена схема построения турниров, являющихся точными 1- и 2-расширениями.

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

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

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

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

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

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

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

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

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

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

Результаты, описанные в первой главе, позволили провести анализ исследуемого объекта и сформулировать основные гипотезы, которые впоследствии были строго доказаны.

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

Ориентированным графом (орграфом или просто графом) G называется пара (V, ), где V – конечное непустое множество (множество вершин), а – отношение в множестве V (отношение смежности).

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

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

Граф с пустым отношением смежности называется вполне несвязным или нульграфом и обозначается On.

Степенью исхода вершины v орграфа G называется число d+(v) дуг орграфа G, имеющих v своим началом.

Степень захода вершины v – это количество d–(v) дуг, имеющих v своим концом.

В неориентированном графе d+(v) = d–(v) = d(v).

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

Маршрутом в орграфе G = (V, ) называется последовательность дуг (v0, v1), (v1, v2), …, (vn–1, vn). При этом говорят, что v0 – начальная вершина маршрута, а vn – конечная. Говорят также, что вершина vn достижима из v0.

Маршрут, в котором никакая дуга не встречается более одного раза, называется путем. Если начальная и конечная вершины совпадают, то путь называется циклическим.

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

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

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

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

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

Объединением двух графов G1 = (V1, 1) и G2 = (V2, 2) называется граф G1 G2 = (V1 V2, 1 2).

Две вершины u и v графа G будем называть подобными, если существует автоморфизм f, такой что f(u) = v. Граф, все вершины которого подобны, называется вершинно симметрическим. Граф, имеющий только тождественный автоморфизм, называется асимметричным.

Две вершины u и v графа G будем называть псевдо подобными, если они не подобны, однако графы G – v и G – u изоморфны.

Вложением графа G1 = (V1, 1) в граф G2 = (V2, 2) называется такое инъективное отображение f : V1 V2, что для любых вершин u, v V1 выполняется следующее условие:

(u, v) 1 (f(u), f(v)) 2.

GR = (VR, R) Назовем граф (вершинным) k расширением графа G = (V, ), если граф G можно вложить в каждый подграф графа GR, получающийся удалением любых его k вершин и всех связанных с ними ребер. Если F V, то будем обозначать через G – F граф, получающийся из G удалением всех вершин, принадлежащих F, и связанных с ними ребер.

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

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

2) |V*| = n + k;

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

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

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

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

Поиск точных расширений проводился на 9 компьютерах мощностью 2ГГц в течение недели.

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

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

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

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

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

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

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

Теорема 2.2.1 (О несвязных точных расширениях графов). Граф G = G1 G2 … Gk является точным расширением некоторого графа G* тогда и только тогда, когда все Gi изоморфны друг другу и каждое Gi является точным расширением.

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

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

Теорема 2.3.1. Если орграф G = (V, ) является точным расширением, тогда и его части G* = (V, *), где * = {(x, y) | x, y V, (x, y) & (y, x) } и G** = (V, **), где ** = {(x, y) | x, y V, (x, y) & (y, x) } также являются точными расширениями.

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

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

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

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

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

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

Теорема 2.5.1. Множество степеней исхода (захода) вершин графа, являющегося точным расширением, имеет вид {d, d+1, d+2 … d+t}, где d 0, t 0.

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

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

В шестом параграфе затрагивается проблема единственности точного расширения графа.

Единственность точного расширения тесно связанна с реконструируемостью графов. Если для некоторого графа G можно построить два неизоморфных точных расширения G1* и G2*, то, очевидно, что графы G1* и G2* являются не реконструируемыми, поскольку колоды и того и другого состоят из графов, изоморфных G. Основным результатом параграфа является доказательство того, что известные нереконструируемые диграфы Стокмейера [14] не являются точными расширениями.

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

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

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

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

Кроме того, удалось показать, что среди графов, не входящих в описанные семейства, могут встречаться только точные 1- и 2-расширения. Причем точными 2 расширениями могут быть только сильно связные турниры с числом вершин вида 4t + 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. 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., 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. 197 211.

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

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

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

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. Богомолов А.М., Салий В.Н. Алгебраические основы теории дискретных систем. М.: Наука, 1997.

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

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

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

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

А1. Абросимов М.Б., Долгов А.А. О реконструируемости малых турниров. // Известия Саратовского университета. Новая серия. Серия Математика.

Механика. Информатика. 2009. Т. 9, вып. 2. С. 94-98.

А2. Абросимов М.Б., Долгов А.А. О бесконтурных точных расширениях // Изв. Сарат. ун-та. Нов. сер. Сер.

Математика. Механика. Информатика. 2010. Т.10, вып. 1. С. 83-88.

А3. Абросимов М.Б., Долгов А.А. Точные расширения некоторых турниров // Вестник ТГУ. Приложение.

2007. № 23. С. 211-216.

А4. Долгов А.А. Некоторые свойства малых турниров. Саратов: СГУ, 2007. 24с.;

Деп. в ВИНИТИ 24.07.07, №769-B2007.

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

Отечество, 2008. 148с. С.27.

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

А7. Долгов А.А. К вопросу о точных расширениях турниров // Прикладная дискретная математика.

Приложение. 2009. № 1. С. 98-99.

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

78-80.

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

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

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

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

№ 9. С. 96-99.

А13. Абросимов М.Б., Долгов А.А. К вопросу о единственности точных вершинных расширений // Прикладная дискретная математика. Приложение:

Тезисы докладов X Сибирской научной школы семинара с международным участием «Компьютерная безопасность и криптография» – SYBECRYPT'11 (Томск, ТГУ, 5–10 сентября 2011 г.).

2011. №4. С. 81–83.

_ Подписано в печать 28.09.2011.

Формат 60х84 1/16. Бумага офсетная. Гарнитура Times.

Объем 1.25 печ. л. Тираж 100 экз. Заказ № 196-Т Типография СГУ г. Саратов, ул. Б. Казачья 112а тел.: (845-2) 27-33-

 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.