О сложности сборки и вложения графов

• Автор: Зайцев, Денис Владимирович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Москва
• Количество страниц: 106 с. : ил.

Оглавление
Введение
1 О сложности сборки графов
1.1 Порядки сложности сборки полного двудольного и полного графов
1.2 Оценки функции Шеннона для класса С?
1.3 Порядок функции Шеннона для класса деревьев
2 О сложности вложения графов
2.1 Сложность вложения графов класса К
2.2 Порядок сложности А-вложения графов класса К
2.3 Асимптотика сложности вложения графов класса Т
3 О сложности вложения матриц
3.1 Порядок сложности вложения матриц

Введение
Графы представляют большой интерес и находят применение в самых разных областях. В их числе физика, химия, электроника, экономика, лингвистика, машиностроение и другие. Теория графов может служить математической моделью для всякой системы, содержащей бинарное отношение [4]. Существуют разные способы задания отдельных графов и задания классов графов.
Многие практические задачи связаны с необходимостью экономить ресурсы. Традиционными целями являются экономия времени и экономия занимаемого места. В связи с этим возникает интерес к проблеме задания графов с минимизацией определённых затрат. В диссертации рассматривается два подхода к заданию графов.
В первом подходе изучается сложность схем построения графов при помощи двух операций склейки вершин, которые заключаются в отождествлении пары вершин с удалением петель и кратных ребер. Первая операция применяется к паре вершин одного графа, вторая - к паре вершин двух графов, не имеющих общих элементов. В качестве простейшего берется граф, состоящий из пары вершин, соединённых ребром. Любой промежуточный результат, т. е. построенный на каком-то этапе граф, разрешено использовать неоднократно. Под сложностью схемы понимается число применений операций над графами. Схемный подход к заданию графов уже рассматривался ранее,

Введение
например, в работе С.В. Яблонского [7], но в ней не изучался вопрос о сложности схемы построения графов, и использовались другие операции. В этой работе получены порядки сложности схемного задания для полного двудольного и полного графа. Получен порядок функции Шеннона для класса деревьев. Также получена асимптотика логарифма функции Шеннона для класса неориентированных связных графов, в которых нет петель и кратных рёбер.
Во втором подходе изучается сложность универсальных1 графов, которые позволяют получать графы заданных классов в качестве подграфов, порождённых подмножествами их вершин. Получены оценки минимального числа вершин в универсальных графах для двух классов графов, у которых вершины помечены натуральными числами. Для класса неориентированных, необязательно связных графов, не имеющих петель и кратных рёбер, получен порядок. Для класса неориентированных деревьев получена асимптотика. Для первого класса графов рассмотрены также универсальные графы, для которых разрешается варьирование добавлением ограниченного числа рёбер. Получен порядок числа вершин в минимальном универсальном графе данного вида. Универсальные графы могут быть интересны в связи со сжатием информации, а также при проектировании чипов.
В рамках исследования универсальных графов интересно рассмотреть специальный класс графов, который важен для технических приложений. Это прямоугольные решётки с конечным числом вершин и классы их подграфов.
Подграфы решётки можно задавать матрицами. Кратко поясним идею такого задания на примере прямоугольной решётки на плоскости. Пусть у нас есть алфавит из четырёх символов {0,1,2,3}. Рас-
!В англоязычной литературе используется термин induced-universal graph [8], [12].

1.1. Порядки сложности сборки полного двудольного и полного графов.
Длина последовательности сборки тг(Кр>р) равна количеству затраченных в ней операций склейки, то есть Т — 1. Сложность сборки Ь(КР)Р), по определению, равна длине минимальной последовательности сборки. Поскольку любая последовательность сборки графа Крф имеет длину больше ТО р < Ь(Крр).
Лемма доказана.
Согласно утверждениям леммы 1.4 и леммы 1.1 пункта а), для любого р > 1 выполняются неравенства:
р < Ь(КргР) 3р + 5оё2р.
Следовательно, Ь(КРР) х р при р —> +оо.
Теорема 1.1 доказана.
Перейдём к доказательству нижней оценки для сложности сборки полного графа.
Можно отметить, что ситуация заметно упрощается при отсутствии двух долей в графе. Тем не менее, давайте рассмотрим доказательство полностью.
Определение сети сборки и выделенного пути в сети сборки остаются без изменений, как было определено в начале доказательства теоремы 1.1.
Определим по-новому множество вершин (1 к г) в графе С}., принадлежащем некоторому выделенному пути в сборке графа/О,-Теперь Ак по определению - просто множество вершин С/-
Пусть С, и Gj (г ф ]) - некоторые два графа, принадлежащие выделенному пути. Определение в графе Gj вершины - потомка вершины ьг Е Сч для данного выделенного пути остаётся без изменений, как в начале доказательства теоремы 1.1.