Минимальные расширения цветных графов
Введение …………………………………………………………………………………………………. 4
Глава 1. Цветные реализации заданных графов ……………………………….. 16
1.1 Основные определения теории графов ……………………………………………. 16
1.2 Изоморфизмы и автоморфизмы в теории графов …………………………….. 19
1.3 Цветные графы и их изоморфизм в теории графов ………………………….. 21
1.4 Задача о поиске неизоморфных цветных графов ……………………………… 23
1.5 Базовый алгоритм генерации неизоморфных цветных графов …………. 24
1.6 Метод канонических представителей ……………………………………………… 26
1.7 Метод МакКея отсечения изоморфизмов ………………………………………… 28
1.8 Метод Рида-Фараджева отсечения изоморфизмов …………………………… 31
1.9 Алгоритм генерации неизоморфных цветных графов методом МакКея .
………………………………………………………………………………………………………. 33
1.10 Генерация цветных графов методом Рида-Фараджева ……………………… 35
1.11 Алгоритм генерации неизоморфных цветных графов методом Рида-
Фараджева …………………………………………………………………………………………….. 38
1.12 Генерация неизоморфных графов с цветными ребрами …………………… 41
1.13 Вычислительные эксперименты для цветных цепей ………………………… 43
1.14 Вычислительные эксперименты для цветных циклов ………………………. 48
1.15 Вычислительные эксперименты для цветных полных графов ………….. 52
1.16 Вычислительные эксперименты для цветных звезд …………………………. 56
1.17 Вычислительные эксперименты для графов с цветными ребрами ……. 60
Глава 2. Минимальные расширения цветных графов ……………………… 64
2.1 Отказоустойчивость в теории графов ……………………………………………… 64
2.2 Расширения графов ………………………………………………………………………… 68
2.3 Терминология расширений цветных графов ……………………………………. 70
2.4 Задача поиска минимальных расширений цветных графов ………………. 72
2.5 Максимальный матричный код как часть канонического представителя
для расширений цветного графа …………………………………………………………….. 75
2.6 Простой код раскраски как часть канонического представителя для
расширений цветного графа …………………………………………………………………… 81
2.7 Использование метода Рида-Фараджева для поиска минимальных
вершинных расширений цветных графов ……………………………………………….. 84
2.8 Вычислительные эксперименты генерации неизоморфных
минимальных вершинных расширений для заданных цветных графов ……. 87
Глава 3. Минимальные расширения цветных полных графов ………… 95
3.1 Минимальные вершинные 1-расширения двухцветных полных графов .
………………………………………………………………………………………………………. 96
3.2 Минимальные вершинные k-расширения двухцветных полных графов ..
…………………………………………………………………………………………………….. 100
3.3 Минимальные вершинные k-расширения цветных полных графов…. 109
3.4 Общая схема построения минимальных вершинных k-расширений
цветных полных графов ……………………………………………………………………….. 115
Глава 4. Минимальные расширения цветных звездных графов …….. 118
4.1 Минимальные реберные расширения цветных звезд ……………………… 118
4.2 Минимальные вершинные расширения цветных звезд …………………… 125
Заключение ………………………………………………………………………………………….. 134
Список сокращений и условных обозначений……………………………………….. 135
Список литературы ………………………………………………………………………………. 137
Приложение А ……………………………………………………………………………………… 147
Во введении обосновывается актуальность темы диссертационной работы, пред-
ставлены обзор литературы по теме исследования, цели и задачи работы, научная новизна
диссертации, теоретическая и практическая значимость работы, методы диссертационного
исследования, основные результаты диссертации, структура работы, а также представлены
степень достоверности результатов работ, апробации результатов работ и публикации по
теме диссертации.
В первой главе приводятся некоторые понятия и обозначения из теории графов,
предоставляющие теоретическую базу в области цветных графов и их изоморфизмов.
Пусть = ( , ) – граф, и ∈ ℕ. Функция вида : → {1, … , } называется вершин-
ной i-раскраской графа , а ( ), ∈ называется цветом вершины . При этом граф назы-
вается графом с цветными вершинами, или цветным графом. Для таких графов вводится
следующее обозначение: = ( , , ).
В диссертационной работе множество цветов, сопоставленных графу обозначается
за = {1, … , }.
В главе приводятся известные и предлагаются новые алгоритмы, которые будут ис-
пользоваться в диссертации для построения множества попарно-неизоморфных цветных
реализаций для заданного непомеченного графа. Новые разработанные алгоритмы реализо-
ваны и включены в программный комплекс ColorGraphExtensions.
Основой разработанных алгоритмов является техника канонических представите-
лей, позволяющая производить генерацию попарно-неизоморфных графов без процедуры
проверки на изоморфизм. Данная техника называется «отсечением изоморфизмов». Были
рассмотрены два известных подхода, использующих указанную технику: метод Рида-Фара-
джева и метод МакКея. Приводятся два алгоритма для генерации всех неизоморфных цвет-
ных реализаций для заданного непомеченного графа. Эти алгоритмы отличаются методами
отсечения изоморфизмов.
После описания алгоритмов приводятся результаты различных вычислительных экс-
периментов запуска реализованных алгоритмов на различных классах графов. Данные были
собраны в базу цветных графов следующих классов: цепи, циклы, полные графы и звезды.
Во второй главе приводятся некоторые понятия и обозначения из теории графов,
предоставляющие теоретическую базу в области минимальных вершинных и реберных рас-
ширений. Предлагается уникальный способ кодирования цветных графов для решения за-
дачи поиска минимальных расширений с применением техники канонических представи-
телей.
Для цветных графов предлагается канонический код, состоящий из пары: макси-
мальный матричный код графа и его простой код раскраски.
В работе описывается способ построения кода раскраски и простого кода раскраски.
Элемент кода раскраски предлагается строить следующим образом:
1. Рассматривается вершина ∈ , записывается ее цвет.
2. Рассматриваются все ее смежные вершины, и подсчитывается количество смеж-
ных вершин каждого цвета.
Подсчитанные данные записываются в следующем формате для каждой вершины :
( )6| ” |, | # |, … , 8 $ 89,
где ( ) – цвет вершины , а | % | – количество смежных вершине вершин цвета % .
Вектор структур для всех вершин образует код раскраски. Подобный код довольно
неэффективен при операциях сравнения, поэтому предлагается модифицировать данный
код.
Для каждого цвета % выбирается два простых числа: %” и %# . Первое число стоит
брать небольшим, например 3, 7, 11 и так далее. Второе следует задавать больше, чем пер-
вое в степени количества вершин графа: %# > ( %” )& . Тогда для каждой структуры
( )6| ” |, | # |, … , 8 $ 89, построенной для некоторой вершины ∈ графа , вычисляется
число, которое называется простым кодом вершины:
)( )
( ) = %# ⋅ ( “” )|(!| ⋅ ( #” )|(“| ⋅ … ⋅ = $” > .
#
Вектор простых кодов всех вершин образует простой код раскраски. Он обознача-
ется следующим образом:
( ) = { ( ): ∈ }
На основании данного канонического кода разработан алгоритм для поиска всех
неизоморфных минимальных расширений для заданного цветного графа. Реализация дан-
ного алгоритма включена в программный комплекс СolorGraphExtensions. Проведены вы-
числительные эксперименты на различных классах цветных графов, в том числе для цвет-
ных полных графов и цветных звезд. Для этих классов графов сформирована база мини-
мальных вершинных и реберных расширений.
Третья глава целиком посвящена аналитическому решению задачи поиска мини-
мальных вершинных расширений для цветных полных графов. Очевидно, что не суще-
ствует реберных расширений полных графов, поэтому рассматриваются только минималь-
ные вершинные расширения. Глава содержит рассуждения о схемах построения минималь-
ных расширений, каждый шаг рассуждений обобщает предыдущие полученные и доказан-
ные результаты. Полученные схемы согласуются с минимальными расширениями, полу-
ченными в ходе вычислительных экспериментов.
В главе вводятся некоторые обозначения для цветных графов. Пусть есть граф =
( , , ). Множество (# = 6 | ( ) = $ 9 – множество вершин из , которым сопоставлен
цвет $ . Очевидно, что (# ⊂ . Тогда множество, содержащее все множества набора вер-
шин по цветам будем обозначать за = D (# E∀ $ ∈ G. Множество ” = D (# : (# ∈
, | (# | = 1G содержит все множества вершин с цветом, встречающимся лишь единожды в
графе. Множество, которое содержит наборы вершин, сопоставленных с цветами, встреча-
ющимися в графе более одного раза, обозначается за ∗ = D (# : (# ∈ , | (# | > 1G.
Исходные вершины из цвета $ будем обозначать (# . Тогда дополнительные
вершины из ∗ − цвета $ будут обозначены за (*# . Аналогично введем обозначения
*
вершин, включенных в множества из ” за + ! и +! для исходных и дополнительных
*∗
соответственно. Аналогично введем + ∗ и + ∗ для .
Функция ( ) – это уникальный набор цветов, сопоставленных вершинам из мно-
жеств, включенных в множество . Тогда значением функции ( ” ) будет являться набор
всех цветов, встречающихся в графе единожды, а значением ( ∗ ) – множество всех не-
уникальных цветов в графе.
Схемы построения минимальных вершинных расширений для цветных полных гра-
фов разбиты на несколько теорем от частного случая к общему. В итоге выводится общая
теорема для построения минимального вершинного расширения для любого цветного пол-
ного графа.
Теорема 3.1.1. Полный граф & = ( , , ) с = { ” , # }, | | = 2, 8 (! 8 = 1, 8 (” 8 > 1
имеет единственное с точностью до изоморфизма минимальное вершинное 1-расширение
с количеством дополнительных ребер, равным 2 − 1.
Теорема 3.1.2. Полный граф & = ( , , ) с = { ” , # }, | | = 2, 8 (! 8 > 1, 8 (” 8 > 1
имеет единственное с точностью до изоморфизма минимальное вершинное 1-расширение
с количеством дополнительных ребер, равным 2 .
Теорема 3.2.1. Полный граф & = ( , , ) с = { ” , # }, | | = 2, 8 (! 8 = 1, 8 (” 8 > 1
имеет единственное с точностью до изоморфизма минимальное вершинное -расширение
,(,.”)
с количеством дополнительных ребер, равным ( − 1) + + ( − 1)# +#
.
Теорема 3.2.2. Полный граф & = ( , , ) с = { ” , # }, | | = 2, 8 (! 8 > 1, 8 (” 8 > 1
имеет единственное с точностью до изоморфизма минимальное вершинное -расширение
0,(,.”)
с количеством дополнительных ребер, равным 2 +#
.
Теорема 3.2.1. Полный граф & = ( , , ) с | | ≥ 2, | ” | > 1, | ∗ | = 1 имеет един-
ственное с точностью до изоморфизма минимальное вершинное -расширение с количе-
ством дополнительных ребер, равным
,(,.”)
| ” |( − | ” |) + + | ” |( − 1)# ++ .
#
Теорема 3.3.2. Полный граф & = ( , , ) с | | ≥ 3, | ” | = 1, | ∗ | > 1 имеет един-
ственное с точностью до изоморфизма минимальное вершинное -расширение с количе-
ством дополнительных ребер, равным
,(,.”)
( − 1) + | ∗ | + | ∗ |( − 1)# + (| ∗ | + 1).
#
Следствие 3.3.1. Схема построения минимального вершинного расширения из тео-
ремы 3.3.2 справедлива для полных графы & = ( , , ) с | ” | > 1, | ∗ | > 1 с общим ко-
личеством дополнительных ребер, равным
,(,.”)
( − 1) + | ∗ | + | ∗ | ∙ | ” |( − 1)# + (| ∗ | + 1).
#
Теорема 3.3.3. Полный граф & = ( , , ) с | | ≥ 2, | ” | = 0, | ∗ | > 1 имеет един-
ственное с точностью до изоморфизма минимальное вершинное -расширение с количе-
|+ ∗ |(|+ ∗ |*”) ,(,.”)
ством дополнительных ребер, равным | ∗ | +#
∙#
.
Теорема 3.3.4. Полный граф & = ( , , ) с | | ≥ 2, > 1, | ∗ | = 0 имеет един-
| ” |
ственное с точностью до изоморфизма минимальное вершинное -расширение с количе-
)+ ! )1)+ ! ).”2
ством дополнительных ребер, равным #
.
Теорема 3.4.1. Полный граф & = ( , , ) с | | > 1 имеет единственное с точностью
до изоморфизма минимальное вершинное -расширение с количеством дополнительных
ребер, равным:
| ” |( − | ” |) + | ∗ | + | ∗ | ∙ | ” |( − 1)# +
| ∗ |(| ∗ | + 1) ( − 1)| ∗ |(| ∗ | − 1)
+∙+ .
В четвертой главе приводятся схемы построения минимальных расширений для
звездных графов, и показано, что покрываются все возможные виды звездных графов с вве-
денной на них функцией раскраски. Глава разбита на две части. В обеих частях использу-
ется специфическое для цветных звезд обозначение: множество 3 = { | ∈ , ( ) = ( )}
будет отображать набор вершин, цвет которых совпадает с цветом центральной вершины.
Также следует отметить, что звездный граф может быть определен как соединение одно-
вершинного полного графа со вполне несвязным: ” + & , где ” – полный граф с одной
вершиной, а & – вполне-несвязный граф с вершинами.
В первой части главы 4 приводятся теоремы с доказательствами со схемами по-
строения минимальных реберных расширений для цветных звезд. Данные теоремы полно-
стью решают вопрос о минимальных реберных расширениях цветных звезд.
Теорема 4.1.2. Любой цветной звездный граф = ( , , ), у которого | 3 | < 1 + 2 ,
не имеет минимального реберного -расширения.
Теорема 4.1.3. Рассмотрим звезду = ( , , ), у которой множество | 3 | ≥ 2 + 1,
а общее число вершин | | = + 1. Минимальным реберным -расширением, причем един-
ственным с точностью до изоморфизма, графа будет являться цветной граф с общим ко-
личеством ребер равным ( − )(2 + 1). Схема построения данного МР- Р заключается в
построении 2 дополнительных центров из вершин ∈ 3 , ≠ .
Во второй части главы 4 приводятся теоремы с доказательствами со схемами по-
строения минимальных вершинных расширений для цветных звезд. Данные теоремы пол-
ностью решают вопрос о минимальных вершинных расширениях цветных звезд.
Теорема 4.2.1. Звезда = ( , , ), | | = , где только центральная вершина имеет
цвет ( ): | 3 | = 1, а также | " | > 1, | ∗ | = 0, имеет единственное с точностью до изо-
морфизма минимальное вершинное -расширение, содержащее (| ” | − 1) дополнитель-
ных ребер. Схема построения минимального расширения заключается в том, что из до-
полнительных вершин строится исходных графов.
Теорема 4.2.2. Звезда = ( , , ), где | 3 | = 1, | ” | = 1, ∗ = { 4∗ }, | ∗ | = 1,
имеет единственное с точностью до изоморфизма минимальное вершинное -расширение,
содержащее (| 4∗ | + ) дополнительных ребер. Схема построения заключается в том, что
из всех дополнительных вершин ( ) цвета проводятся ребра во все исходные и дополни-
тельные вершины цвета 4∗ .
Следствие 4.2.1. Звезда = ( , , ), у которой | 3 | = 1, | ” | = 1, ∗ =
{ “∗ , #∗ , 0∗ , … , 5∗ }, | ∗ | > 1, имеет единственное с точностью до изоморфизма мини-
мальное вершинное -расширение с количеством дополнительных ребер, равным
|+ ∗ |
∑$6″ =8 $∗ 8 + >. Схема построения сводится к тому, чтобы провести из каждой вершины
цвета ( ), отличной от вершины , ребра во все исходные и дополнительные вершины
каждого из цветов ∗ .
Теорема 4.2.3. Звезда = ( , , ) с условиями | 3 | = 1, | ” | > 1, | ∗ | ≥ 1 имеет
единственное с точностью до изоморфизма минимальное вершинное -расширение с коли-
|+ ∗ |
чеством дополнительных вершин, равным ∑$6″ =8 $∗ 8 + > + (| ” | − 1).
Следствие 4.2.2. Схема построения и количество дополнительных ребер из теоремы
4.2.3 справедливы для любых цветных звездных графов, в которых выполняется условие
| 3 | = 1, | ” | ≥ 1, | ∗ | ≥ 0.
Теорема 4.2.5. Для любого цветного звездного графа, где | 3 | > 1, | ” | ≥ 1, | ∗ | ≥
0, минимальное вершинное -расширение строится по следующей схеме:
1. Для вершин из 3 строится МВ- Р по теореме о минимальном вершинном расши-
рении простой непомеченной звезды, содержащейся в работе М.Б. Абросимова «Графовые
модели отказоустойчивости»18.
2. Для вершин из ” и ∗ { 3 } строится МВ- Р по следствию 4.2.2 теоремы 4.2.3.
Актуальность темы исследования и степень её разработанности.
Влияние информационных технологий и технических систем становится все
более значимым в разных важных сферах жизни общества: медицине, энерге-
тике, транспортной связи, освоении космоса и многих других. Выход из строя
хотя бы одного элемента системы, внедренной в данные сферы жизни, иногда
приводит к катастрофическим последствиям. Поэтому использование вычис-
лительных систем в критических областях формирует требование надежности.
Надежность является комплексным свойством, включающим в себя такие по-
нятия как долговечность, ремонтопригодность, сохраняемость, достоверность
функционирования и, конечно же, отказоустойчивость. Говоря о построении
надежной системы, чаще всего подразумевают именно свойство отказоустой-
чивости (fault tolerance).
Одна из первых работ, исследующая принципы построения отказоустой-
чивых систем, принадлежит Джону фон Нейману [101]. В ней рассматривается
надежная система, собранная из ненадежных элементов. Говоря о повышении
надежности самих элементов следует отметить, что, скорее всего, невозможно
создать элемент идеальной надежности. Для каждого элемента системы при-
нято использовать характеристику наработки на отказ. Время наработки эле-
мента на отказ составляет то время, которое элемент проработает до выхода
из строя. Так, например, ENIAC, одно из первых электронных вычислитель-
ных устройств, использовал около 18000 вакуумных ламп со средним време-
нем наработки на отказ около 2500 часов. Среднее время наработки на отказ
ENIAC составляло 7 минут [1, 56]. В современных компьютерах, конечно же,
используются намного более надежные компоненты. В связи с этим выросла
комплексность и сложность вычислительных устройств. Так, в 2020 году ком-
пания RIKEN объявила о запуске самого быстрого суперкомпьютера Фугаку
(Fugaku). 9 марта 2021 года [104] RIKEN объявила, что в этом компьютере
установлено 158 976 процессоров Fujitsu A64FX [43, 100] с общим числом
7 299 072 ядер.
Исходя из этого, вопрос о надежности системы необходимо переформу-
лировать в контексте способности системы продолжать работу при выходе
надежного элемента из строя. В 1971 году А. Авиженис (A. Avižienis) [45] рас-
смотрел два подхода для повышения надёжности вычислительных систем:
предотвращение ошибок и отказоустойчивость. Первое направление связано с
уменьшением вероятности возникновения ошибки. Оно состоит в разработке
высоконадёжных компонентов системы и не будет рассматриваться в данной
работе. Во втором направлении используется введение в систему избыточных
структур для придания ей свойств отказоустойчивости. В более поздних рабо-
тах отказоустойчивость стала рассматриваться как одно из средств достиже-
ния гарантоспособности системы [47].
Авиженис [44] ввел также понятие отказоустойчивости как обеспече-
ние системы способностью противостоять ошибке и возможностью продол-
жать работу в присутствии этой ошибки. Он рассмотрел два уровня отказо-
устойчивости:
1. полная отказоустойчивость – система продолжает работать в при-
сутствии ошибок без существенной потери функциональных свойств;
2. амортизация отказов – система продолжает работать в присутствии
ошибок с частичной деградацией функциональных возможностей.
В 1976 году John Hayes [79] предложил модель для исследования полной
отказоустойчивости технических систем, основанную на графах. Некоторой
системе Σ сопоставляется помеченный граф (Σ), вершины которого соответ-
ствуют элементам системы Σ, рёбра – связям между элементами, а метки ука-
зывают тип элементов. Если связи не являются симметричными, то можно рас-
сматривать ориентированные графы. В данной работе будут рассматриваться
неориентированные графы. Под отказом элемента системы Σ понимается уда-
ление соответствующей ему вершины из графа системы (Σ) и всех связанных
с ней ребер. Система Σ ∗ называется -отказоустойчивой реализацией системы
Σ, если отказ любых элементов системы Σ ∗ приводит к графу, в который
можно вложить граф системы Σ с учетом меток вершин. Построение -отказо-
устойчивой реализации системы Σ можно представить себе как введение в неё
определенного числа избыточных элементов и связей. При этом предполага-
ется, что в нормальном режиме работы избыточные элементы и связи маски-
руются, а в случае отказа происходит реконфигурация системы до исходной
структуры [1, 79]. Есть и другая интерпретация отказа, при которой сам эле-
мент перестаёт функционировать, но через него могут передаваться сигналы
[28, 31]. На языке теории графов -отказоустойчивую реализацию системы Σ
мы будем называть вершинным -расширением (В- Р) её графа (Σ).
Если в системе Σ встречается различных типов элементов, то любая её
-отказоустойчивая реализация должна содержать не менее дополнитель-
ных элементов каждого типа. Такого числа дополнительных элементов доста-
точно для построения -отказоустойчивой реализации системы Σ. Добавим
элементов каждого типа, соединим их все между собой и с элементами си-
стемы Σ. Тогда любой отказавший элемент можно будет заменить одним из
добавленных элементов соответствующего типа. Построенную -отказоустой-
чивую реализацию будем называть тривиальной. Её можно использовать для
оценки числа дополнительных вершин и рёбер произвольной -отказоустой-
чивой реализации. Таким образом, известно минимально возможное число до-
полнительных элементов для построения -отказоустойчивой реализации си-
стемы. Далее добавим условие минимальности числа дополнительных связей.
Если элементы технической системы однотипны, то метки элементов
опускаются, и в качестве графа системы рассматривается граф без меток. В
этом случае оптимальная -отказоустойчивая реализация будет содержать в
точности дополнительных элементов. На практике такая ситуация встреча-
ется достаточно часто. Например, массивно-параллельные вычислительные
системы состоят из однотипных узлов. Каждый узел состоит из одного или
нескольких процессоров, локальной памяти и некоторых других компонент
[67].
В данной работе будут рассмотрены только помеченные графы, то есть
системы с элементами различных типов, где > 1.
Для системы Σ ее -отказоустойчивая реализация Σ ∗ называется опти-
мальной, если система Σ ∗ отличается от системы Σ на элементов (каждого
типа в случае помеченных графов), и среди всех -отказоустойчивых реализа-
ций с тем же числом элементов система Σ ∗ имеет наименьшее число связей.
На языке теории графов оптимальную -отказоустойчивую реализацию си-
стемы Σ мы будем называть минимальным вершинным -расширением (МВ-
Р) её графа (Σ). Позднее F. Harary и J. Hayes [77] расширили модель на слу-
чай отказов связей. В данной работе мы будем рассматривать как отказы эле-
ментов, так и отказы связей между элементами.
В своей первой работе J. Hayes [79] предложил схемы построения мини-
мальных вершинных 1-расширений для цепей и циклов, а также для частного
случая помеченного дерева. Большое количество теоретических исследований
посвящено аналитическому построению минимальных вершинных -расши-
рений для различных классов графов: И.А.К. Камил [9], Х.Х.К. Судани [15],
П.П. Бондаренко [5], А.В. Киреева [32], М.Ф. Каравай [28–31], М.А. Кабанов
[22], М.Б. Абросимов [1], С.Г. Курносова [33, 34], А.А. Долгов [19, 20], О.В.
Моденова [11, 12], А.В. Гавриков [18], J. Hayes [39, 78, 79], A.A. Farrag [70] и
ряд других работ [55, 59, 60, 80, 99].
Задача поиска минимального расширения для неориентированного по-
меченного графа является вычислительно сложной. А именно, задача про-
верки того, что граф является -расширением заданного графа, является NP-
полной [3]. Очевидно, поскольку граф является помеченным (цветным), вло-
жение исходного графа следует проверять с условием сохранности цветов, то
есть проверять графы на цветное вложение. В работах [1, 2] предлагается пе-
реборный алгоритм построения минимальных вершинных -расширений гра-
фов. Его, конечно, можно модифицировать таким образом, чтобы проверялось
условие цветного вложения, однако это не отменяет факта, что описанный ал-
горитм сложен для распараллеливания и является неэффективным. Для гене-
рации сложных комбинаторных структур, в том числе графов, хорошо пока-
зывают себя методы без непосредственной проверки на изоморфизм. В основе
таких методов лежит каноническая форма структуры или её канонический код.
Основная идея состоит в оставлении структуры только в том случае, если её
форма является канонической. Необходимо назвать некоторые работы, пыта-
ющиеся раскрыть данную тему: И.А. Фараджев [42 ,69], С.А. Сухов [38],
R.C. Read [61, 62, 97], B. McKay [91, 93, 94], G. Brinkmann [49–53], M. Meringer
[95], R. Grund [75]. Алгоритмы генерации без проверки на изоморфизм хорошо
подходят для распараллеливания.
На основании метода канонических представителей были разработаны
несколько алгоритмов поиска минимальных расширений для непомеченных
графов. В работе [9] предложен алгоритм для поиска минимальных вершин-
ных расширений, а в работе [15] – минимальных реберных расширений. В дан-
ной работе предлагаются алгоритмы для цветных графов. Применение всех
перечисленных алгоритмов ограничивается графами с небольшим числом вер-
шин.
Аналитическое решение задачи поиска минимальных вершинных и ре-
берных расширений позволяет найти схемы для цветных графов произволь-
ного числа вершин и ребер, таким образом, решая вопрос для определенного
класса графов.
Это определяет актуальность настоящей работы, а также соответствую-
щие цели и задачи.
Цели и задачи диссертационной работы. Основные цели данной ра-
боты состоят в следующем:
1. Исследование алгоритмов для решения задачи генерации всех по-
парно-неизоморфных цветных графов без проверки на изоморфизм.
2. Исследование алгоритмов для решения задачи построения всех неизо-
морфных минимальных вершинных и реберных -расширений для заданного
цветного графа без проверки на изоморфизм.
3. Исследование минимальных вершинных -расширений для цветных
полных графов.
4. Исследование минимальных вершинных и реберных -расширений
для цветных звезд.
Основные задачи работы:
1. Разработка алгоритма построения всех попарно-неизоморфных цвет-
ных графов без проверки на изоморфизм.
2. Разработка алгоритма построения всех минимальных вершинных и
реберных -расширений для цветных графов без проверки на изоморфизм.
3. Получение схем для построения всех неизоморфных минимальных
вершинных -расширений для цветных полных графов.
4. Получение схем для построения всех неизоморфных минимальных
вершинных и реберных -расширений для цветных звезд.
Научная новизна работы заключается в следующем:
1. Разработаны новые алгоритмы построения всех попарно-неизоморф-
ных цветных графов без непосредственной проверки на изоморфизм.
2. Разработаны новые алгоритмы построения всех неизоморфных мини-
мальных вершинных и реберных -расширений заданного цветного графа без
непосредственной проверки на изоморфизм.
3. Найдены схемы построения минимальных вершинных -расширений
для цветных полных графов.
4. Найдены схемы построения минимальных вершинных и реберных –
расширений для цветных звезд.
Методы исследования. В работе используются методы дискретной ма-
тематики и математической кибернетики. Используется аппарат теории гра-
фов, комбинаторики и теории алгоритмов.
Положения диссертации, выносимые на защиту:
1. Алгоритмы построения всех попарно-неизоморфных цветных реали-
заций заданного графа без непосредственной проверки на изоморфизм.
2. Алгоритмы построения всех неизоморфных минимальных вершин-
ных и реберных -расширений заданного цветного графа без непосредствен-
ной проверки на изоморфизм.
3. Схемы построения минимальных вершинных -расширений для цвет-
ных полных графов.
4. Схемы построения минимальных вершинных и реберных -расшире-
ний для цветных звезд.
Теоретическая и практическая значимость. Работа носит преимуще-
ственно теоретических характер и ее теоретическая значимость состоит в том,
что удалось разработать алгоритмы построения всех цветных реализаций за-
данного графа, а также алгоритмы построения минимальных вершинных и ре-
берных расширений цветных графов без проверки на изоморфизм. Для полных
цветных графов и цветных звезд удалось найти полное аналитическое решение
задачи построения их минимальных вершинных и реберных расширений.
Практическая значимость работы состоит в том, что на основе предло-
женных алгоритмов можно разрабатывать программные реализации, предна-
значенные для исследования минимальных расширений цветных графов, а с
точки зрения приложений – изучать отказоустойчивые реализации техниче-
ских систем с элементами разного типа. Автором были реализованы все алго-
ритмы в программном комплексе ColorGraphExtensions, который позволяет
строить цветные графы и находить их минимальные вершинные и рёберные
расширения.
Личный вклад соискателя. Все основные результаты, выносимые на
защиту, получены автором лично. Научному руководителю принадлежат об-
щее руководство, предложения по используемым методам, а также помощь в
подготовке текста.
Структура и объем работы. Диссертационная работа состоит из введе-
ния, 4 глав, заключения, списка сокращений и условных обозначений, списка
использованной литературы и приложений. Работа содержит 147 страниц, 52
рисунка, 44 таблицы, библиографический список из 104 наименований и 1
приложение.
Во введении обосновывается актуальность темы диссертационной ра-
боты, представлены обзор литературы по теме исследования, цели и задачи ра-
боты, научная новизна диссертации, теоретическая и практическая значимость
работы, методы диссертационного исследования, основные результаты дис-
сертации, структура работы, а также представлены степень достоверности ре-
зультатов работ, апробации результатов работ и публикации по теме диссерта-
ции.
В первой главе приводятся некоторые понятия и обозначения из теории
графов, предоставляющие теоретическую базу в области цветных графов и их
изоморфизмов. Также приводятся известные и предлагаются новые алго-
ритмы, которые будут использоваться в диссертации для построения множе-
ства попарно-неизоморфных цветных реализаций для заданного непомечен-
ного графа. Новые разработанные алгоритмы реализованы и включены в про-
граммный комплекс ColorGraphExtensions. После описания алгоритмов при-
водятся результаты различных вычислительных экспериментов запуска реали-
зованных алгоритмов на различных классах графов. Данные были собраны в
базу цветных графов следующих классов: цепи, циклы, полные графы и
звезды.
Во второй главе приводятся некоторые понятия и обозначения из теории
графов, предоставляющие теоретическую базу в области минимальных вер-
шинных и реберных расширений. Предлагается уникальный способ кодирова-
ния цветных графов для решения задачи поиска минимальных расширений с
применением техники канонических представителей. На основании данного
кода представлен алгоритм для поиска всех неизоморфных минимальных рас-
ширений для заданного цветного графа. Реализация данного алгоритма вклю-
чена в программный комплекс СolorGraphExtensions. Проведены вычисли-
тельные эксперименты на различных классах цветных графов, в том числе для
цветных полных графов и цветных звезд. Для этих классов графов сформиро-
вана база минимальных вершинных и реберных расширений.
Третья глава целиком посвящена аналитическому решению задачи по-
иска минимальных вершинных расширений для цветных полных графов. Оче-
видно, что не существует реберных расширений полных графов, поэтому рас-
сматриваются только минимальные вершинные расширения. Глава содержит
рассуждения о схемах построения минимальных расширений, каждый шаг
рассуждений обобщает предыдущие полученные и доказанные результаты.
Полученные схемы согласуются с минимальными расширениями, получен-
ными в ходе вычислительных экспериментов, и полностью решают вопрос о
минимальных вершинных -расширениях цветных полных графов.
В четвертой главе приводятся схемы построения минимальных расши-
рений для звездных графов, и показано, что покрываются все возможные виды
звездных графов с введенной на них функцией раскраски. Глава разбита на две
части. Первая часть главы 4 сосредоточена на поиске схем построения для
минимальных реберных расширений цветных звезд. Во второй части главы 4
приводятся теоремы с доказательствами со схемами построения минимальных
вершинных расширений для цветных звезд. В данной главе полностью решен
вопрос о минимальных расширениях цветных звезд.
Достоверности и апробация результатов исследования. Все получен-
ные результаты снабжены строгими доказательствами и согласуются с резуль-
татами вычислительных экспериментов. Основные результаты работы докла-
дывались и обсуждались на следующих семинарах и конференциях:
– научный семинар кафедры теоретических основ компьютерной без-
опасности и криптографии Саратовского национального исследовательского
государственного университета имени Н.Г. Чернышевского (Саратов, 2017,
2018, 2019, 2020);
– научная конференция механико-математического факультета Сара-
товского национального исследовательского государственного университета
имени Н.Г. Чернышевского «Актуальные проблемы математики и механики»
(Саратов, 2021);
– VII Международная научная конференция «Компьютерные науки и
информационные технологии» памяти А.М. Богомолова (Саратов, 2016);
– VIII Международная научная конференция «Компьютерные науки и
информационные технологии» памяти А.М. Богомолова (Саратов, 2018);
– IX Международная научная конференция «Компьютерные науки и ин-
формационные технологии» памяти А.М. Богомолова (Саратов, 2021);
– всероссийская конференция «XVI Сибирская научная школа-семинар
с международным участием «Компьютерная безопасность и криптография» –
SIBECRYPT’17» (Томск, 2017);
– всероссийская конференция «XVIII Сибирская научная школа-семи-
нар с международным участием «Компьютерная безопасность и криптогра-
фия» – SIBECRYPT’19» (Томск, 2019);
– XX Международная конференция «Сибирская научная школа-семинар
«Компьютерная безопасность и криптография» – SIBECRYPT’21» (Новоси-
бирск, 2021);
– международная научная конференция студентов, аспирантов и моло-
дых учёных «Ломоносов-2021» (Москва, 2021).
Все результаты диссертации, полученные автором, являются новыми и
достоверными. Это подтверждается публикациями в рецензируемых научных
изданиях. По теме диссертации имеется 3 публикации в изданиях из перечня
рецензируемых научных изданий ВАК Минобрнауки РФ:
– Абросимов М.Б., Разумовский П.В. Минимальные расширения цвет-
ных звездных графов // International Journal of Open Information Technologies. –
2022. – Vol. 10, № 2. – P. 1–7.
– Разумовский П.В., Абросимов М.Б. Минимальные вершинные расши-
рения цветных полных графов [Razumovsky P.V., Abrosimov M.B. The Minimal
Vertex Extensions for Colored Complete Graphs] // Вестник ЮУрГУ. Серия «Ма-
тематика. Механика. Физика». – 2021. – Т. 13, № 4. – С. 77–89.
– Абросимов М.Б., Разумовский П.В. О поиске минимальных вершин-
ных расширений цветного неориентированного графа // Известия высших
учебных заведений. Поволжский регион. Физико-математические науки. –
2021. – № 4 (60). – C. 106–117.
Следующие публикации по теме диссертации были опубликованы в
научных изданиях, которые входят в базы цитирования Web of Science и Sco-
pus:
– Разумовский П.В., Абросимов М.Б. Построение цветных графов без
проверки на изоморфизм // Известия Саратовского университета. Новая се-
рия. Серия: Математика. Механика. Информатика. 2021. Т. 21, вып. 2. С.
267–277.
– Razumovsky P.V. The search for minimal edge 1-extension of an undirected
colored graph [Разумовский П. В. О поиске минимальных реберных 1-расши-
рений неориентированного цветного графа] // Известия Саратовского универ-
ситета. Новая серия. Серия: Математика. Механика. Информатика. 2021.
Т. 21, вып. 3. С. 400–407.
Программный комплекс ColorGraphExtensions был зарегистрирован как
объект интеллектуальной собственности:
– Разумовский П.В., Абросимов М.Б. ColorGraphExtensions // Свиде-
тельство о государственной регистрации программы для ЭВМ № 2021662022,
выданное Роспатентом. Зарегистрировано в Реестре программ для ЭВМ
20.06.2021.
Также по теме диссертации автором публиковались следующие работы:
– Абросимов М.Б., Разумовский П.В. Генерация неизоморфных вер-
шинных -раскрасок графа // Компьютерные науки и информационные техно-
логии: материалы Междунар. науч. конф. – Саратов: центр «Наука», 2016. –
С. 13–15.
– Абросимов М.Б., Разумовский П.В. О генерации неизоморфных -рас-
красок методом МакКея // Компьютерные науки и информационные техноло-
гии: материалы Междунар. науч. конф. – Саратов: центр «Наука», 2018. – С.
318–320.
– Абросимов М.Б., Разумовский П.В. О минимальных расширениях
неизоморфных цветных звездных графов // Компьютерные науки и информа-
ционные технологии: материалы Междунар. науч. конф. – Саратов: центр
«Наука», 2021. – С. 5–8.
– Абросимов М.Б., Разумовский П.В. О генерации неизоморфных вер-
шинных -раскрасок // ПДМ. Приложение. – 2017. – № 10. – C. 136–138.
– Абросимов М.Б., Разумовский П.В. О генерации неизоморфных рас-
В диссертационной работе предложены и исследованы методы и алго-
ритмы построения технических систем различного типа, устойчивых к отка-
зам элементов и связей между ними, а также всех соответствующих цветных
реализаций и их минимальных вершинных и реберных -расширений для за-
данного графа системы без проверки на изоморфизм. В результате исследова-
ния получены следующие теоретические и практические результаты.
1. Разработаны 7 алгоритмов, в том числе следующие алгоритмы: по-
строение всех попарно-неизоморфных цветных реализаций для заданного про-
стого графа, алгоритмы и построения всех неизоморфных минимальных вер-
шинных и реберных -расширений заданного цветного графа.
2. Проведены исследования разработанных алгоритмов, реализо-
ваны их параллельные версии, оценена их эффективность для различных ви-
дов графов. Эффективность алгоритмов варьируется в зависимости от видов
графов и от формы, в которой графы подаются на вход.
3. Найдены схемы построения минимальных вершинных k-
расширений цветных полных графов, а также схемы построения минимальных
вершинных и реберных -расширений цветных звезд.
Таким образом, все основные задачи диссертационного исследования
решены. Документы, подтверждающие использование результатов диссерта-
ционного исследования, представлены в приложении к работе.
Список сокращений и условных обозначений
В- Р вершинное -расширение
МВ- Р минимальное вершинное -расширение
МВ-Р, МВР минимальное вершинное расширение
Р- Р реберное -расширение
МР- Р минимальное реберное -расширение
МР-Р, МРР минимальное реберное расширение
= ( , ) неориентированный граф с множеством вершин и отно-
шением смежности a
= ( , , ) неориентированный граф с множеством вершин и отно-
шением смежности a с введенной на нем функцией рас-
краски : → {1, … , }
= { , … , } множество цветов графа
количество уникальных цветов в графе
( ) матрица смежности графа G
( ) степень вершины
{ , } ребро между вершинами и
полный -вершинный граф
или , звездный граф с одной вершиной степени и с верши-
нами степени 1
, регулярный -вершинный граф, где каждая вершина имеет
степень
циклический -вершинный граф
цепной -вершинный граф
вполне несвязный -вершинный граф
множество вершин графа, которым сопоставлен цвет (
множество множеств вершин графа, которым сопоставлен
некоторый цвет, для всех цветов из
множество, которое содержит все множества вершин с
цветом, встречающимся лишь единожды в графе
∗ множество, которое содержит наборы вершин, сопостав-
ленных с цветами, встречающимися в графе более одного
раза
вершина из исходного множества , сопоставленная цвету
(
;
вершина из множества ∗ дополнительных вершин, со-
поставленная цвету (
вершина из множества , которое включено в одно из
множеств множества %
;
вершина из множества ∗ , которое включено в одно
из множеств множества %
∗ вершина из множества , которое включено в одно из
множеств множества ∗
;
∗ вершина из множества ∗ , которое включено в одно
из множеств множества ∗
Г-МК алгоритм генерации неизоморфных цветных графов мето-
дом МакКея
Г-РФ алгоритм генерации неизоморфных цветных графов мето-
дом Рида-Фараджева
Г-МК-р алгоритм генерации неизоморфных графов с цветными ре-
брами методом МакКея
Г-РФ-р алгоритм генерации неизоморфных графов с цветными ре-
брами методом Рида-Фараджева
Г-МВР алгоритм генерации неизоморфных минимальных вер-
шинных расширений цветного графа
1. Абросимов М.Б. Графовые модели отказоустойчивости. – Саратов: Из-
дательство Саратовского университета, 2012. – 192 с.
2. Абросимов М.Б. Минимальные расширения 4-, 5-, 6- и 7-вершинных гра-
фов. – Сарат. гос. ун-т. – Саратов, 2000. – 26 с.; Деп. в ВИНИТИ 06.09.2000,
№ 2352-В00.
3. Абросимов М.Б. О сложности некоторых задач, связанных с расширени-
ями графов // Математические заметки. – 2010. – № 88:5. – С. 643–650.
4. Абросимов М.Б., Бондаренко П.П. Исследование минимальных вершин-
ных и реберных 1-расширений цепей с вершинами двух типов // Свид. о гос.
регистрации программы для ЭВМ № 2010616497, выданное Роспатентом. За-
регистрирована в Реестре программ для ЭВМ 30.09.2010.
5. Абросимов М.Б., Бондаренко П.П. О минимальных вершинных 1-расши-
рениях циклов с вершинами двух типов // Прикладная дискретная матема-
тика. – 2011. – № 4. – С. 80–81.
6. Абросимов М.Б., Долгов А.А. О реконструируемости малых турниров //
Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. –
2009. – Т. 9, вып. 2. – С. 94–98.
7. Абросимов М.Б., Долгов А.А. Семейства точных расширений турниров //
Прикладная дискретная математика. – 2008. – № 1. – С. 101–107.
8. Абросимов М.Б., Камил И.А.К. Разработка системы предотвращения
вторжений с использованием параллельного программирования и системы от-
казоустойчивости // Безопасность информационных технологий. – 2018. – Т.
25, № 1. – С. 65–73.
9. Абросимов М.Б., Камил И.А.К., Лобов А.А. Построение всех неизоморф-
ных минимальных вершинных расширений графа методом канонических
представителей // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика.
Информатика. – 2019. – Т. 19, вып. 4. – С. 479–485.
10. Абросимов М.Б., Камил И.А.К., Судани Х.Х.К., Лобов А.А. Построение
оптимальных отказоустойчивых реализаций графов FTConstructor // Свид. о
гос. регистрации программы для ЭВМ № 2020614773. Зарегистрирована в Ре-
естре программ для ЭВМ 24.04.2020.
11. Абросимов М.Б., Моденова О.В. Характеризация орграфов с малым чис-
лом дополнительных дуг минимального вершинного 1-расширения // Изв. Са-
рат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. – 2013. –
Т. 13., вып. 2, ч. 2. – С. 3–9.
12. Абросимов М.Б., Моденова О.В. Характеризация орграфов с тремя до-
полнительными дугами в минимальном вершинном 1-расширении // Приклад-
ная дискретная математика. – 2013. – № 3. – С. 68–75.
13. Абросимов М.Б., Разумовский П.В. Генерация неизоморфных вершин-
ных -раскрасок графа // Компьютерные науки и информационные техноло-
гии: материалы Междунар. науч. конф. – Саратов: центр «Наука», 2016. – С.
13–15.
14. Абросимов М.Б., Разумовский П.В. О генерации неизоморфных раскра-
сок методом Рида-Фараджева // ПДМ. Приложение. – 2019. – № 12. – С. 173–
176.
15. Абросимов М.Б., Судани Х.Х.К., Лобов А.А. Построение минимальных
рёберных расширений графа без проверки на изоморфизм // Изв. Сарат. ун-
та. Нов. сер. Сер. Математика. Механика. Информатика. – 2020. – Т. 20,
вып. 1. – С. 105–115.
16. Арлазаров В.Л., Зуев И.М., Усков А.В., Фараджев И.А. Алгоритм приве-
дения неориентированных графов к каноническому виду // Ж. вычисл. матем.
и матем. физ. – 1974. – Т. 14, № 3. – С. 737–743.
17. Богомолов А.М., Салий В.Н. Алгебраические основы теории дискрет-
ных систем. – М.: Наука, 1997. – 368 с.
18. Гавриков А.В. Т-неприводимые расширения объединений некоторых
типов орграфов // Прикладная дискретная математика. – № 4 (22). – 2013. –
С. 47–56.
19. Долгов А.А. О семействах точных вершинных k-расширений графов при
k > 1 // Материалы Международного молодежного научного форума «Ломо-
носов-2010». – М.: МАКС Пресс, 2010. – С. 30–32.
20. Долгов А. А. Семейство точных 2-расширений турниров // Прикладная
дискретная математика. – 2010. – № 9. – С. 96–99.
21. Зыков А.А. О некоторых свойствах линейных комплексов // Математи-
ческий сборник. – 1949. – Т. 24(66), № 2. – С. 163–188.
22. Кабанов М. А. Об отказоустойчивых реализациях графов // Теоретиче-
ские задачи информатики и ее приложений. – Саратов: Изд-во Сарат. ун-та,
1997. – Вып.1. – С. 50–58.
23. Камил И.А.К. Обеспечение отказоустойчивости высокопроизводитель-
ного узла параллельных вычислений с интерфейсом передачи сообщений
(MPI) // Современная наука: актуальные проблемы теории и практики: Серия
«Естественные и Технические науки». – 2018. – № 4. – С. 57–59.
24. Камил И.А.К., Абросимов М.Б. Разработка системы предотвращения
вторжений с использованием параллельного программирования и технологий
отказоустойчивости // Технические средства защиты информации: Тезисы до-
кладов XVI Белорусско-российской научно-технической конференции, 5 июня
2018 г., Минск. Минск: БГУИР, 2018. – С. 44.
25. Камил И.А.К., Абросимов М.Б., Лобов А.А. Построение минимальных
вершинных расширений графа методом Рида-Фараджева // International Jour-
nal of Open Information Technologies. – 2020. – Vol. 8, no. 4. – P. 54–58.
26. Камил И.А.К., Судани Х.Х.К., Абросимов М.Б. К вопросу о параллель-
ных алгоритмах построения минимальных вершинных и реберных 1-расшире-
ний графов // Компьютерные науки и информационные технологии: Матери-
алы Междунар. науч. конф. – Саратов: Издат. центр «Наука», 2018. – С. 173–
176.
27. Камил И.А.К., Судани Х.Х.К., Лобов А.А., Абросимов М.Б. Построение
минимальных расширений графа методом канонических представителей //
Прикладная дискретная математика. Приложение. – 2019. – № 12. – С. 179–
182.
28. Каравай М.Ф. Инвариантно-групповой подход к исследованию k-отка-
зоустойчивых структур // Автоматика и телемеханика. – 2000. – № 1. –
С. 144–156.
29. Каравай М.Ф. Минимизированное вложение произвольных гамильтоно-
вых графов в отказоустойчивый граф и реконфигурация при отказах. I. Одно-
отказоустойчивые структуры // Автоматика и телемеханика. – 2004. – № 12.
– С. 159–177.
30. Каравай М.Ф. Минимизированное вложение произвольных гамильтоно-
вых графов в отказоустойчивый граф и реконфигурация при отказах. II. Ре-
шетки и k-отказоустойчивость // Автоматика и телемеханика. – 2005. – № 2.
– С. 175–189.
31. Каравай М.Ф. Применение теории симметрии к анализу и синтезу отка-
зоустойчивых систем // Автоматика и телемеханика. – 1996. – № 6. – С. 159–
173.
32. Киреева А.В. Отказоустойчивость в функциональных графах // Упоря-
доченные множества и решетки. – Саратов: Изд-во Сарат. ун-та, 1995. –
Вып. 11. – С. 32–38.
33. Курносова С.Г. Т-неприводимые расширения объединений полных гра-
фов // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информа-
тика. – 2005. – Т. 5, вып. 1. – С. 107–115.
34. Курносова С.Г. Т-неприводимые расширения полных бинарных дере-
вьев // Вестн. Томск. гос. ун-та. Приложение. – 2005. – № 14. – С. 158–160.
35. Павлов Д.А. Каноническая нумерация графов и библиотека nauty //
КИО, раздел «Информатика», № 5, 2009. [Электронный ресурс] – URL:
https://cyberleninka.ru/article/n/kanonicheskaya-numeratsiya-grafov-i-biblioteka-
nauty.
36. Разумовский П.В., Абросимов М.Б. Построение цветных графов без
проверки на изоморфизм // Изв. Сарат. ун-та. Нов. Сер. Сер. Математика.
Механика. Информатика. – 2021. – Т. 21, вып. 2. – С. 267–277.
37. Разумовский П.В., Абросимов М.Б. ColorGraphExtensions // Свидетель-
ство о государственной регистрации программы для ЭВМ № 2021662022, вы-
данное Роспатентом. Зарегистрировано в Реестре программ для ЭВМ
20.06.2021.
38. Сухов С.А. DSR Generator // Свид. о гос. регистрации программы для
ЭВМ № 2016610073. Зарегистрирована в Реестре программ для ЭВМ 11 января
2016 г.
39. Харари Ф. Теория графов. – М.: Мир, 1973. – 296 с.
40. Харченко В.С. Гарантоспособность и гарантоспособные системы: эле-
менты методологии // Радiоелектронi и комп’ютернi системи. – 2006. – № 5.
– С. 7–19.
41. Харченко В.С. Парадигмы и принципы гарантоспособных вычислений:
состояние и перспективы развития // Радiоелектронi и комп’ютернi системи.
– 2009. – № 2(36). – С. 91–100.
42. Фараджев И.А. (ред.) Алгоритмические исследования в комбинаторике.
– М.: Наука, 1978. – 190 с.
43. About Fugaku [Электронный ресурс] // RIKEN Center for Computational
Science. – URL: https://www.r-ccs.riken.jp/en/fugaku/about/ (дата обращения:
15.10.2021).
44. Avižienis A. Design of fault-tolerant computers // AFIPS’67 Conf. Proc. –
New York: ACM, 1967. – P. 733–743.
45. Avižienis A. Fault-Tolerant Computing: An Overview // IEEE Computer. –
1971. – Vol. 4, № 1. – P. 5–8.
46. Aviženis A. Fault-tolerance and fault-intolerance: Complementary ap-
proaches to reliable computing // Proc. Intern. Conf. of Reliable Software, New
York, 1975. – P. 458–464.
47. Aviženis A., Laprie J.-C., Randell B., Landwehr C. Basic Concepts and Tax-
onomy of Dependable and Secure Computing // IEEE Trans. on Dependable and
Secure Comput. – 2004. – № 1. – P. 11–33.
48. Berge C. Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise
starr sind // Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe. –
1961. – Vol. 10. – P. 114.
49. Brinkmann G. Fast generation of cubic graphs // J. Graph Theory. – 1996. –
Vol. 23, № 2. – P. 139–149.
50. Brinkmann G. Isomorphism rejection in structure generation programs // Dis-
crete Mathematical Chemistry, DIMACS Series in Discrete Mathematics and Theo-
retical Computer Science. – 2000. – Vol. 51. – P. 25–38.
51. Brinkmann G., Goedgebeur J. Generation of cubic graphs and snarks with
large girth // Journal of Graph Theory. – 2017. – Vol. 86, № 2. – P. 255–272.
52. Brinkmann G., Goedgebeur J., Hagglund J., Markstrom K. Generation and
properties of Snarks // Journal of Combinatorial Theory, Series B. – 2013. – Vol.
103, № 4. – P. 468–488.
53. Brinkmann G., Goedgebeur J., McKay B. D. Generation of cubic graphs //
Discrete Math. Theor. Comput. Sci. – 2011. – Vol. 13, № 2. – P. 69–80.
54. Bron C., Kerbosh J. Algorithm 457 – Finding all cliques of an undirected
graph // Comm. of ACM. – 1973. – Vol. 16. – P. 575–577.
55. Bruck J., Cypher R., Ho C. Fault-tolerant meshes with small degree // SIAM
J. Comput. – 1997. – Vol. 26, № 6. – P. 1764–1784.
56. Carter W.C., Bouricius W.G. A Survey of Fault Tolerant Computer Architec-
ture and its Evaluation // IEEE Computer. – 1971. – Vol. 4, № 1. – P. 9–16.
57. Cayley A. On the colourings of maps // Proceedings of the Royal Geograph-
ical Society, Blackwell Publishing. – 1879. – Vol. 1, no. 4. – P. 259–261.
58. Chaitin G.J. Register allocation & spilling via graph colouring // Proc. 1982
SIGPLAN Symposium on Compiler Construction. – 1982. – P. 98–105.
59. Chou R.S., Hsu L.H. 1-edge fault-tolerant designs for meshes // Parallel Pro-
cess. Lett. – 1994. – Vol. 4, № 4. – P. 385–389.
60. Choudum S. A., Sivagurunathan S. Optimal fault-tolerant networks with a
server // Networks. – 2000. – Vol. 35, № 2. – P. 157–160.
61. Colburn C.J., Read R.C. Orderly algorithms for generating restricted classes
of graphs // Journal of Graph Theory. – 1979. – Vol. 3. – P. 187–195.
62. Colburn C.J., Read R.C. Orderly algorithms for graph generation // Intern. J.
Computer Math. – 1979. – Sec. A.7. – P. 167–172.
63. Dailey D.P. Uniqueness of colorability and colorability of planar 4-regular
graphs are NP-complete // Discrete Mathematics. – 1980. – Vol. 30, no. 3. – P. 289–
293.
64. Darga P.T., Liffiton M.H., Sakallah K.A., Markov I.L. Exploiting structure in
symmetry detection for CNF // Proceedings of the 41st Design Automation Confer-
ence, 2004. – P. 530–534.
65. Duncan L.R., Perry A.D. A method of matrix analysis of group structure //
Psychometrika. – 1949. – Vol. 2, no. 14. – P. 95–116.
66. Dutt S., Hayes J.P. Designing fault-tolerant systems using graph automor-
phisms // Journal of Parallel and Distributed Computing. – 1991. – Vol. 12. – P.
249–268.
67. Encyclopedia of Parallel Computing // ed. D. A. Padua. – New York:
Springer. – 2011.
68. Erlebach T., Jansen K. The complexity of path coloring and call scheduling //
Theoretical Computer Science. – 2001. – Vol. 255, is. 1-2. – P. 33-50. [ERLE-
BACH]
69. Faradzhev I.A. Constructive enumeration of combinatorial objects // Collo-
ques internationaux C.N.R.S. №260, Problemes Combinatoires et Theorie des
Graphes, Orsay. – 1976. – P. 131–135.
70. Farrag A.A., Dawson R.J. Designing optimal fault-tolerant star networks //
Networks. – 1989. – Vol. 19. – P. 707–716.
71. Gandham S., Dawande M., Prakash R. Link scheduling in sensor networks:
distributed edge coloring revisited // Proc. IEEE 24th Annual Joint Conf. of the IEEE
Comp. and Communications Soc. – 2005. – Vol. 4. – P. 2492–2501.
72. Garey M.R., Johnson D.S. Computers and Intractability: a guide to the theory
of NP-Completeness. – New York: Freeman, 1985. – 338 p.
73. Garey M.R., Johnson D.S., Stockmeyer L. Some simplified NP-complete
problems // STOC ’74: Proceedings of the sixth annual ACM symposium on Theory
of computing. – 1974. – P. 47–63.
74. Gonzalez T., Sahni S. Open shop scheduling to minimize finish time // Jour-
nal of ACM. – 1976. – Vol. 23, no. 4. – P. 665–679.
75. Grund R. Konstruktion schlichter Graphen mit gegebener Gradpartition //
Bayreuther Mathematische Schriften. 1993. Vol.44. P.73–104.
76. Gurevich Y. From invariants to canonization // Bulletin of the European As-
sociation of Theoretical Computer Science. – 1997. – Vol. 63. – P. 115–119.
77. Harary F., Hayes J.P. Edge fault tolerance in graphs // Networks. – 1993. –
Vol. 23. – P. 135–142.
78. Harary F., Hayes J.P. Node fault tolerance in graphs // Networks. – 1996. –
Vol. 27. – P. 19–23.
79. Hayes J.P. A graph model for fault-tolerant computing system // IEEE Trans.
Comput. – 1976. – Vol. C-25, no. 9. – P. 875–884.
80. Hsu L. H., Lin C. K. Graph Theory and Interconnection Networks. – New
York: CRC Press, 2009.
81. Junttila T., Kaski P. Engineering an efficient canonical labeling tool for large
and sparse graphs // Proceedings of the 9th Workshop on Algorithm Engineering and
Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics,
2007. – P. 135–149.
82. Junttila T., Kaski P. Conflict Propagation and Component Recursion for Ca-
nonical Labeling // Proceedings of the 1st International ICST Conference on Theory
and Practice of Algorithms, 2011. P. 151–162.
83. Karp R.M. Reducibility among combinatorial problems // Complexity of
Computer Computations. – 1972. – New York: Plenum. – P. 85–103.
84. Laprie J.-C. Dependability: Basic Concepts and Terminology, 1992. – NY:
Springer-Verlag. – 245 p.
85. Laprie J.-C. Dependable Computing and Fault Tolerance: Concepts and Ter-
minology // Proc. 15th IEEE Intern. Symp. Fault-Tolerant Computing (FTCS-15). –
1985. – NY: ACM. – P. 2–11.
86. Lopez-Presa J.L., Fernandez Anta A. Fast algorithm for graph isomorphism
testing // Proceedings of the 8th International Symposium on Experimental Algo-
rithms, 2009. – P. 221–232.
87. Lopez-Presa J.L., Fernandez Anta A., Nunez Chiroque L. Conauto-2.0: Fast
isomorphism testing and automorphism group computation, 2011. [Электронный
ресурс]. – URL: http://arxiv.org/abs/1108.1060.
88. McKay B.D. Computing automorphisms and canonical labellings of graphs //
Combinatorial Mathematics, Lecture Notes in Mathematics. – 2006. – Berlin:
Springer-Verlag. – P. 223–232.
89. McKay B.D. Description of graph6, sparse6 and digraph6 encodings
[Электронный ресурс]. – URL: http://cs.anu.edu.au/people/bdm/data/formats.txt
(дата обращения: 14.09.2021).
90. McKay B.D. Combinatorial Data: Graphs. [Электронный ресурс]. – URL:
https://users.cecs.anu.edu.au/~bdm/data/graphs.html.
91. McKay B.D. Isomorphism-free exhaustive generation // Journal of Algo-
rithms. – 1998. – Vol. 26. – P. 306–324.
92. McKay B.D. nauty User’s Guide (version 1.5) // Tech. Rpt. TR-CS-90-02,
Dept. Computer Science. – 1990. – Australia: Austral. Nat. Univ.
93. McKay B.D. Practical graph isomorphism // Congr. Numer. – 1980. – Vol.
30. – P. 45–87.
94. McKay B.D., Piperno A. Practical Graph Isomorphism, II // Journal of Sym-
bolic Computation. – 2014. – Vol. 60. – P. 94–112.
95. Meringer M. Fast generation of regular graphs and construction of cages //
Journal of Graph Theory. 1999. Vol.30. P.137–146.
96. Molloy M., Reed B. Graph colouring and the probabilistic method. – Berlin:
Springer, 2002. – 326 p.
97. Read R.C. Every one a Winner or how to Avoid Isomorphism Search when
Cataloguing Combinatorial Configurations // Annals of Discrete Mathematics. –
1978. – Vol. 2. – P. 107–120.
98. Read R.C., Corneil D.G. The graph isomorphism disease // J. Graph The-
ory1. – 1977. – P. 339–363.
99. Sung T. Y., Ho T. Y., Chang C. P., Hsu L. H. Optimal k-fault-tolerance net-
work for token rings // J. Inform. Science and Engineering. – 2000. – № 16. –
P. 381–390.
100. TOP500[Электронныйресурс]//TOP500.–URL:
https://www.top500.org/ (дата обращения: 15.10.2021).
101. von Neumann J. Probabilistic Logics and the Synthesis of Reliable Organ-
isms from Unreliable Components // Automata Studies, ser. Annals of Mathematics
Studies. Princeton, NJ: Princeton University Press, 1956. – Vol. 34. – P. 43–98.
102. Weygant P. Clusters for high availability: a primer of HP solutions, 2001. –
NJ: Prentice Hall. – 296 p.
103. Whitney H. Congruent graphs and the connectivity of graphs // American
Journal of Mathematics. – 1932. – Vol. 54, no. 1. – P. 160–168.
104. World’s fastest supercomputer Fugaku begins its shared use [Электронный
ресурс] // Science | Business. – URL: https://sciencebusiness.net/network-up-
dates/worlds-fastest-supercomputer-fugaku-begins-its-shared-use (Дата обраще-
ния: 15.10.2021).
Читать «Минимальные расширения цветных графов»
Помогаем с подготовкой сопроводительных документов
Хочешь уникальную работу?
Больше 3 000 экспертов уже готовы начать работу над твоим проектом!
4.8 (2878 отзывов)
4.4 (59 отзывов)
4.8 (17 отзывов)
4.8 (9 отзывов)
4.7 (82 отзыва)
5 (49 отзывов)
4.9 (35 отзывов)
4.1 (20 отзывов)
5 (154 отзыва)
