Разработка алгоритмического и программного обеспечения для укладки графов на плоскости

Введение ……………………………………………………………………………………………………… 15
1 Проблема визуализации графа …………………………………………………………………… 17
1.1 Планарный граф ………………………………………………………………………………….. 18
1.2 Алгоритмы проверки графа на планарность …………………………………………. 19
1.3 Алгоритм укладки планарного графа на плоскость ………………………………. 20
1.4 Задача укладки произвольного (не планарного графа) на плоскость……… 21
2 Разработка оптимального алгоритма укладки не планарного графа на
плоскость, с минимальным количеством пересечений рёбер. ……………………….. 22
2.1 Описание разработанного алгоритма……………………………………………………. 22
2.2 Алгоритм для нахождения и укладки планарных компонент ………………… 23
2.2.1 Описание алгоритма последовательного построения ………………………. 23
2.3 Асимптотическая сложность разработанного алгоритма ………………………. 24
2.4 Пример работы разработанного алгоритма …………………………………………… 25
3 Реализация и тестирование программного продукта для укладки
произвольного графа на плоскость ………………………………………………………………. 29
3.1 Проектирование интерфейса приложения ……………………………………………. 29
3.2 Реализация приложения ………………………………………………………………………. 30
3.2.2 Основные классы и модули. …………………………………………………………… 30
3.2.3 Алгоритм отрисовки изображения графа ………………………………………… 31
3.3 Тестирование приложения …………………………………………………………………… 32
3.3.1 Тестирование парсера для преобразования sql скрипта БД в граф …… 32
3.3.2 Тестирование функционала определения графа на планарность ……… 32
3.3.3 Тестирование отрисовки графа ………………………………………………………. 34
3.3.4 Тестирование отрисовки диаграммы БД …………………………………………. 36
4 Финансовый менеджмент, ресурсоэффективность и ресурсосбережение……. 37
4.1 Предпроектный анализ ………………………………………………………………………… 38
4.1.1 Потенциальные потребители результатов исследования …………………. 38
4.1.2 QUAD анализ…………………………………………………………………………………. 38
4.1.3 SWOT-анализ ………………………………………………………………………………… 39
4.1.4 Определение возможных альтернатив проведения научных
исследований …………………………………………………………………………………………. 41
4.2 Инициация проекта ……………………………………………………………………………… 42
4.3 Планирование управления научно-техническим проектом …………………… 44
4.3.1 План проекта …………………………………………………………………………………. 44
4.3.2 Бюджет научно-технического исследования (НТИ) ………………………… 47
4.3.3 Организационная структура проекта ………………………………………………. 50
4.3.4 План управления коммуникациями проекта ……………………………………. 51
4.3.5 Реестр рисков проекта ……………………………………………………………………. 52
4.4 Определение ресурсной (ресурсосберегающей), финансовой, бюджетной,
социальной и экономической эффективности исследования ………………………. 53
5 Социальная ответственность …………………………………………………………………….. 58
5.1 Правовые и организационные вопросы обеспечения безопасности ………. 59
5.1.1 Специальные (характерные для проектируемой рабочей зоны)
правовые нормы трудового законодательства …………………………………………. 59
5.1.2 Организационные мероприятия при компоновке рабочей зоны ………. 60
5.2 Профессиональная социальная безопасность ……………………………………….. 61
5.2.1 Анализ вредных факторов, которые могут возникнуть при проведении
исследований …………………………………………………………………………………………. 62
5.2.1.1 Отклонение показателей микроклимата ……………………………………. 62

5.2.1.2 Превышение уровня шума ……………………………………………………….. 64

5.2.1.3 Недостаточная освещённость рабочей среды ……………………………. 65

5.2.2 Опасные факторы производственной среды ……………………………………. 67
5.2.2.1 Опасность поражения электрическим током …………………………….. 67

5.3. Экологическая безопасность……………………………………………………………….. 68
5.3.1 Анализ воздействия средств исследования на окружающую среду …. 69
5.4 Безопасность в чрезвычайных ситуациях …………………………………………….. 70
Заключение …………………………………………………………………………………………………. 72
Список использованных источников ……………………………………………………………. 73
Приложение А. Раздел на иностранном языке………………………………………………. 75