Оптимизация построения специальных видов графов в условиях малого количества ресурсов

1.

Оптимизация построения
специальных видов графов в
условиях малого количества
ресурсов
Студент: Мальцев Михаил Витальевич, M34381
Научный руководитель: Станкевич Андрей Сергеевич,
кандидат технических наук, доцент
Консультант: Сорокин Евгений Сергеевич, старший
разработчик

2.

Отображение графов
● Требуется отобразить структурированный граф
● Нужно минимизировать пересечения
Саша
Лена
Саша
Вика
Костя
Ксюша
Костя
Ксюша
Кирилл
Аня
Кирилл
Лена
Дима
Вика
Дима
Дима
2

3.

Цель и задачи
Цель: Разработка и реализация алгоритма для минимизации пересечения
ребер для определенных видов графов.
Задачи:
Выбрать виды графов, для которых надо реализовать алгоритм
минимизации пересечений ребер
● Адаптировать существующие и/или создать новые алгоритмы для
минимизации пересечений ребер для выбранных видов графов
● Сравнить полученные алгоритмы на время работы и на количество
пересечений ребер у полученных графов
● Создать библиотеку из наиболее эффективных алгоритмов на языке
TypeScript
3

4.

Уровневый граф
0
4
7
1
5
9
2
6
10
3
8
11
…
Уровень 0
Уровень 1
Уровень 2
Уровень 3
4

5.

Вложенный уровневый граф
0
4
1
5
2
7
8
9
6
10
3
11
…
Уровень 0
Уровень 1
Уровень 2
Уровень 3
5

6.

Секторный граф
Сектор 0
0
1
Сектор 3
8
7
Сектор 1
6
2
5
4
3
Сектор 2
6

7.

Подсчет пересечений в уровневом графе
● Ребра пересекаются, если a < i, b > j или a > i, b < i
● Можно свести к подсчету количества перестановок для сортировки
массива
● O(n + m log(m))
a-1
a
j
a+1
…
…
b
i
7

8.

Подсчет пересечений в уровневом графе
● При перестановке соседних вершин меняются пересечения только у
ребер, смежными с ними
● Можно за O(m1 * m2) или за O(n + m1 + m2)
0
0
4
4
1
1
5
5
2
2
6
3
6
3
8

9.

Подсчет пересечений в секторном графе
● Ребра пересекаются, если a < i < b < j или i < a < j < b
● Можно за О(n + m +