Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Оптимальные укладки графов в пространстве (Сергей Вельдер)
Computer Science семинар


Что: Лекция
Когда: Вторник, 07 апреля 2009, 16:20–17:50
Где: ПОМИ РАН

Описание

Задачи реализации и рисования графа на плоскости и в пространстве находят много важных применений. Визуализация, построение логических схем и кодов требуют строить укладки графов, удовлетворяющие некоторому изобразительному соглашению, а также эстетическим и другим оптимизационным ограничениям. Этот раздел теории графов хорошо исследован; большинство алгоритмических задач, которые в нём проявляются, NP–полны. Данный доклад предназначен для введения в эту область; в нём рассматривается основное ограничение — минимизация объёма вложения (без самопересечений; вершины графа реализуются шариками фиксированного радиуса, а рёбра — криволинейными проволоками фиксированной толщины). В докладе будет рассказано о классических (для плоскости и трёхмерного пространства) и новых (для пространства любой размерности) результатах, связанных с этой задачей, а также об их предпосылках, в том числе биологических и комбинаторных. Будет обозначена связь объёма вложения с вычислительной сложностью некоторых алгоритмов для задачи SAT. Эта связь приводит к рассмотрению регулярных графов. В докладе формулируется следующий результат. Верхняя и нижняя оценка на минимальный объём вложения n–вершинного d–регулярного графа в k–мерное пространство в худшем и среднем случаях имеет порядок n^(k/(k–1)). Нижняя оценка верна для комбинаторных экспандеров особого типа. Такими экспандерами являются почти все графы. Часть теорем будет доказана.