О сложности сборки и вложения графов тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Зайцев, Денис Владимирович

• Зайцев, Денис Владимирович
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Зайцев, Денис Владимирович

Введение

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

1.1 Порядки сложности сборки полного двудольного и полного графов.

1.2 Оценки функции Шеннона для класса 0.

1.3 Порядок функции Шеннона для класса деревьев.

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

2.1 Сложность вложения графов класса К.

2.2 Порядок сложности Л-вложения графов класса К.

2.3 Асимптотика сложности вложения графов класса Т.

3 О сложности вложения матриц

3.1 Порядок сложности вложения матриц.

Введение диссертации (часть автореферата) на тему «О сложности сборки и вложения графов»

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

Многие практические задачи связаны с необходимостью экономить ресурсы. Традиционными целями являются экономия времени и экономия занимаемого места. В связи с этим возникает интерес к проблеме задания графов с минимизацией определённых затрат. В диссертации рассматривается два подхода к заданию графов.

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

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

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

Подграфы решётки можно задавать матрицами. Кратко поясним идею такого задания на примере прямоугольной решётки на плоскости. Пусть у нас есть алфавит из четырёх символов {0,1,2,3}. Рас

В англоязычной литературе используется термин induced-universal graph [8], [12]. смотрим вершину решётки у, которая инцидентна четырём рёбрам. Поставим данной вершине у в соответствие два (из четырёх) инцидентных ребра е\ и ег, которые не принадлежат одной прямой. Рассмотрим класс остовных подграфов решётки. Каждой вершине подграфа из этого класса поставим в соответствие ячейку матрицы, содержащую символ алфавита, следующим образом. Если вершине г; подграфа инцидентны е\ и б2, то записываем в ячейку символ "3", если инцидентно б2, то записываем "2", если е^ то "1", если ни одного, то "О". Когда требуется задавать подграфы решётки с вершинами, имеющими пометки из алфавита А, можно рассматривать матрицы над алфавитом Ах {0,1.2,3}. Таким образом, задачу нахождения подграфа прямоугольной решётки, универсального для некоторого класса графов, можно свести к задаче нахождения универсальной матрицы.

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

Подобные объекты рассматривались в работах, посвященных циклам, последовательностям и торам де Брёйна [6], [9], [11]. Важное отличие данной работы заключается в том, что разрешается варьирование универсальной матрицы при идентификации подматрицы.

Отметим также, что в работах, посвященных данной теме, обычно накладывались более жёсткие условия, в частности, требовалась однозначность выделения подматрицы, поэтому получение минимальных универсальных матриц с размерностью три и больше не удавалось [11]. В отличие от работ, посвященных торам де Брёйна, здесь не требуется однозначность выделения матрицы в универсальной матрице и допускается произвольная размерность матриц.

Получена лучшая по порядку универсальная матрица. Она может представлять интерес при определении топологии универсального ре-конфигурируемого чипа.

Основные определения и результаты.

Пусть (f(ri) и ф(п) - вещественные положительные функции от натуральной переменной п.

Положим ср(п) ^ ф(п) при п —> +оо, если существует константа С ^ 1 и существует N такие, что при любом п^ N выполнено ip(n) ^ ^ Сф(п). Говорим, что (f(n) по порядку меньше или равна ф(п).

Положим (р(п) х ф(п) при п —► +оо, если одновременно ip(n) ^ &ф(п) и ф(п) при п —► +оо. Говорим, что </?(п) и ф{п) равны с точностью до порядка.

Положим ip(n) < ф(п) при п —> +оо, если для любого е > 0 существует N такое, что при любом п^ N выполнено (р{п) ^ (1 + £)ф{п). Говорим, ip(n) асимптотически меньше или равна ф(п).

Положим (f(n) ~ ф(п) при п —¥ +оо, если у?(п) < ф(п) и ф(п) < < <р(п) при п —¥ +оо. Говорим, что ifi(n) асимптотически равна ф(п).

Список литературы диссертационного исследования кандидат физико-математических наук Зайцев, Денис Владимирович, 2007 год

1. Зыков А.А. Основы теории графов. - М.: Наука. Гл. ред. физ.-мат. лит., 1987, 384 с.

2. Коршунов А.Д. О числе неизоморфных подграфов в п-вершинном графе. Математические заметки. Т. 9, № 3, - М., 1971, с. 263 -273.

3. Уилсон Р. Введение в теорию графов. М.: Мир, 1977, 208 с.

4. Харари Ф., Теория графов. М.: Мир, 1973, 300 с.

5. Харари Ф., Палмер Э. Перечисление графов. М.: Мир, 1977. 327 с.

6. Холл М. Графические методы. Последовательности де Брёйна. -В кн.: Комбинаторика. М.: Мир, 1970, с. 128 - 139.

7. Яблонский С.В. Введение в дискретную математику. М.: Высш. шк., 2002, 384 с.

8. Chung F. R. K., Graham R. L. On Graphs which Contain All Small Trees. ~ Journal of Combinatorial Theory Series, Series B, 1978, p. 14 23.

9. Hurlbert G., Isaak G. On the de Bruijn torus problem. Journal of Combinatorial Theory, Series A, 1995.

10. Lozin V., Rudolf G. Minimal Universal Bipartite Graphs. RUTCOR-Rutgers Center for Operations Research RRR 1, 2005.Работы автора по теме диссертации.

11. Зайцев Д. В. О сложности сборки полных и полных двудольных графов. Дискретная математика. Т. 20, №2 - М., 2008, с. 72 - 89.

12. Зайцев Д. В. О сложности сборки графов. Интеллектуальные системы. Т. 9, вып. 1-4. - М., 2005, с. 381 - 395.

13. Зайцев Д. В. О сложности вложения графов. Интеллектуальные системы. Т. 11, вып. 1-4. - М., 2007, с. 473 - 492.