|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
Задача поиска расстояния между вершинами взвешенного графадипломная работа (Специалист)
- Научный руководитель: Гасанов Э.Э.
- Автор: Калязина Дарья Александровна
- Тип: Специалист
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2010
- Аннотация: В работе Калязиной Д.А. рассматривается следующая задача. Имеется граф, ребрам которого сопоставлены положительные числа, называемые длинами ребер. Такой граф называется взвешенным. Пользователь видит граф, но не видит длин ребер. Также имеется база данных, которая представляет собой набор положительных чисел. Пользователь знает, что каждая компонента этого набора является значением некоторой функции, зависящей от длин ребер графа, и пользователь знает эти функции. Пользователь имеет возможность запросить у базы данных значения каких-то ее компонент. Пользователь хочет для некоторой произвольной пары вершин графа узнать длину кратчайшего пути между этими вершинами, называемую расстоянием между этими вершинами. Для этого пользователь запрашивает значения интересных ему компонент базы данных до тех пор, пока по этим значениям не может восстановить требуемое расстояние. Например, база данных может содержать длины всех ребер. В этом случае пользователю может быть понадобиться запросить значения всех длин, чтобы вычислить значения расстояния. В другом случае база данных может содержать значения расстояний для всех пар вершин графа, и тогда пользователь может задать только один вопрос и получить требуемое расстояние. В первом случае база данных линейная по числу ребер, но для решения задачи надо подать много запросов, во втором случае база данных большая (квадратичная от числа вершин), но ответ можно получить сразу же. В работе ставится вопрос, как надо организовать базу данных для разных классов графов, чтобы минимизировать произведение размера базы данных и количества заданных вопросов для наихудшей пары вершин (данное произведение будем называть сложностью решения задачи). В работе показано, что сложность для полного графа с N вершинами равна N(N-2)/2; для графов, являющихся цепочками длины N, сложность равна 2(N-1); для простых циклов с N вершинами сложность равна 3N; для деревьев с N вершинами - равна 3(N-1). Также в работе рассмотрены графы, являющиеся прямоугольными решетками, и для некоторых классов решеток получены верхние оценки по порядку меньшие, чем квадратичные. Кроме этого предложены алгоритмы решения для графов с малым числом непересекающихся циклов и для графов с малой степенью связности.
- Добавил в систему: Гасанов Эльяр Эльдарович