Автор: Вельдер С. Э., аспирант Оптимальные укладки графов в пространстве и их приложения к задаче выполнимости СПбГУ ИТМО, кафедра компьютерных технологий 1 / 13

Виды вложений: криволинейное; прямолинейное; ортогональное; … Эстетические критерии: размеры области размещения; относительные размеры (aspect ratio); число пересечений рёбер; максимальная длина ребра; максимальное различие в длинах между рёбрами; суммарная длина рёбер; минимальный угол размаха между смежными рёбрами; максимальное число изломов у ребра; суммарное число изломов у рёбер; … 2 / 13

Виды вложений: криволинейное; прямолинейное; ортогональное; … Эстетические критерии: размеры области размещения; относительные размеры (aspect ratio); число пересечений рёбер; максимальная длина ребра; максимальное различие в длинах между рёбрами; суммарная длина рёбер; минимальный угол размаха между смежными рёбрами; максимальное число изломов у ребра; суммарное число изломов у рёбер; … 2 / 13

Трёхмерное прямолинейное вложение 3 / 13

Четырёхмерная ортогональная сетка 4 / 13

О задаче выполнимости 5 / 13 В работе доказана следующая импликация. Пусть регулярный n- вершинный граф может быть уложен в k- мерный гиперкуб с характерным линейным размером l(n) и объёмом V(n) = const · l k (n), причём соответствующую укладку можно построить за время Тогда задачу SAT можно решить за то же время. На практике второе условие всегда соблюдается, поэтому достаточно обеспечить первое. Наилучшая известная сегодня оценка для SAT имеет вид (Э. А. Гирш). Хочется решать SAT за время, где λ < 1 < a. Проще говоря, за O(2 o(n) ).

Если регулярный n- вершинный граф может быть уложен в k- мерный гиперкуб с характерным линейным размером l(n) и объёмом V(n) = const · l k (n), то задачу SAT можно решить за время Поэтому еслиили, что то же самое, то SAT решается за для любого a > 1. Например, если k = 2 и граф удалось бы вложить в плоскую область, площадь V(n) которой линейна по числу вершин (и, соответственно, рёбер), то SAT была бы разрешима за время О задаче выполнимости 6 / 13

Найденные оценки (для худших случаев) 7 / 13 k = 2k = 3 Любое k Произвольные графы Это просто T. Biedl и S. Whitesides Данная работа Регулярные графы W. T. Tutte, R. Tamassia А. Н. Колмогоров и Я. М. Барздинь Данная работа

Теорема. Существует ортогональное вложение полного n- вершинного графа в k- мерный параллелепипед объёма причём максимальное число изломов/звеньев у ребра O(1). Как следствие, каждое его ребро имеет длину Доказательство. Явная конструкция. Оценки для произвольных графов 8 / 13

Теорема. Существует ортогональное вложение полного n- вершинного графа в k- мерный параллелепипед объёма причём максимальное число изломов/звеньев у ребра O(1). Как следствие, каждое его ребро имеет длину Доказательство. Явная конструкция. Оценки для произвольных графов 8 / 13

Теорема. Существует ортогональное вложение полного n- вершинного графа в k- мерный параллелепипед объёма причём максимальное число изломов/звеньев у ребра O(1). Как следствие, каждое его ребро имеет длину Доказательство. Явная конструкция. Оценки для произвольных графов 8 / 13

Теорема. Существует ортогональное вложение полного n- вершинного графа в k- мерный параллелепипед объёма причём максимальное число изломов/звеньев у ребра O(1). Как следствие, каждое его ребро имеет длину Доказательство. Явная конструкция. Теорема. Любое вложение полного n- вершинного графа в k- мерный параллелепипед имеет объём Средняя длина ребра при оптимальном вложении составляет Оценки для произвольных графов 8 / 13

При оптимальном k зависимость объёма от числа вершин такая: Если мы хотим минимизировать диаметр области, то оптимальная размерность k растёт как log 3 n. Если мы хотим минимизировать поперечник области, то оптимальная размерность k растёт как. При использовании этого метода увеличение размерности k даёт больше степеней свободы, но и накладные расходы увеличиваются. На иллюстрации зависимость V от k при достаточно большом фиксированном числе вершин n. Случай, когда размерность можно выбирать 9 / 13

Не все регулярные графы требуют большой объём: Тривиальная оценка снизу на линейный размер: Если граф достаточно сложный, то у области, в которую он вложен, (k–1)- мерная площадь поверхности примерно пропорциональна числу рёбер и вершин: (для k = 2 предполагаем, что граф в принципе планарен). Оценки для регулярных графов 10 / 13

Введено понятие двойного экспандера. Теорема. Если двойной экспандер с достаточно большим числом вершин n реализован в k- мерном пространстве, то его объём ( = суммарный k- мерный объём всех его рёбер) оценивается снизу как Вопросы. 1. Существует ли хотя бы один экспандер? 2. Существует ли бесконечное семейство экспандеров? 3. Какова доля экспандеров среди всех регулярных графов? Нижняя оценка: отрицательный результат 11 / 13

Формула, дающая число экспандеров в зависимости от параметров: Для её вывода использовался метод Буля решения разностных уравнений относительно функций нескольких переменных (partial difference equations). Теорема. Зафиксируем порядок регулярности графа. Пусть E(n) число n- вершинных регулярных экспандеров, U(n) число всех n- вершинных регулярных графов. Тогда Следствие. Минимальный объём вложения регулярных графов в среднем оценивается снизу как Ответы: количество экспандеров 12 / 13

1.Доказана точная оценка объёма k - мерного ортогонального вложения произвольного графа с ограничением на число поворотов и длину ребра в худшем случае. Верхняя оценка доказана конструктивно. 2.Оценка временной сложности для задачи SAT сведена к оценке объёма k - мерного вложения регулярного графа. 3.Доказаны нижние оценки объёма k - мерного вложения регулярного графа в худшем и среднем случаях. 4.Найдено достаточное условие реализации таких нижних оценок. 5.Найдена явная формула для количества регулярных графов, удовлетворяющих этому условию. 6.Доказано, что данная формула описывает почти все регулярные графы. Результаты 13 / 13