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

Комаров, Вячеслав Андреевич Отделение информационных технологий (ОИТ)
Бесплатно
В избранное
Работа доступна по лицензии Creative Commons:«Attribution» 4.0

Объектом исследования является процесс укладки графов на плоскость. Цель работы – Разработка алгоритмического и программного обеспечения для укладки графов на плоскости. В процессе работы производилось изучение существующих способов отображения планарных и непланарных графов на плоскости и разработка программного обеспечения для отображения диаграмм баз данных на плоскости.

Введение ……………………………………………………………………………………………………… 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

Теория графов является мощным инструментом моделирования и
решения большого количества задач. Представление информации с помощью
графов используется в самых различных областях точных и естественных наук.
Графы позволяют моделировать произвольные системы, представимые в
виде набора объектов и связей между ними.
В настоящее время графовые модели применяются в:
• программировании, для проектирования диаграмм потоков данных
и иерархии классов, для построения организационных IDEF-диаграмм при
создании ПО и ИС;
• дизайне БД для отображения диаграмм сущностей-связей;
• моделировании компьютерных сетей;
• биологии для составления моделей размножения бактерий;
• химии для отображения структур сложных формул и цепочек
преобразований;
• физике и электротехнике для изготовления электронных и печатных
схем.
Вопрос визуализации графов очень актуален, так как от того, насколько
удачно изображен граф, зависит удобство и простота восприятия информации,
которая содержится в нём.
Так как постоянно увеличиваются объемы информации и сложности
структур, возникающих в различных теоретических и практических задачах,
системы визуализации информации становятся всё более востребованными
Целью работы является разработка алгоритмического и программного
обеспечения для укладки графов на плоскости, с возможностью использовать
данное ПО для визуализации плоского изображения диаграмм баз данных.
Для достижения цели следует решить следующие задачи:
1. проведение анализа предметной области, связанной с
визуализацией графов;
2. изучение существующих алгоритмов определения графа на
планарность и отображение его на плоскости;
3. изучение существующих способов отображения не планарных
графов на плоскости;
4. разработка алгоритма укладки не планарного графа на плоскость
минимизируя количество пересечений между рёбрами;
5. реализация программного продукта, для визуализации отображения
диаграмм баз данных с минимальным количеством пересечений между
связями.
1 Проблема визуализации графа

1.Граф (математика) // ru.wikipedia.org: Википедия – свободная
энциклопедия.URL:http://ru.wikipedia.org/wiki/Граф_(математика)(дата
обращения 25.05.2019)
2.Визуализация графов // ru.wikipedia.org: Википедия – свободная
энциклопедия. URL: http://ru.wikipedia.org/wiki/Визуализация_графов (дата
обращения 25.05.2019)
3.Р. Уилсон. Введение в теорию графов. – М.Мир, 1977
4.А. Ю. Ольшанский. Плоские графы. // СОЖ, 1996, No 11, с. 117—
122.
5.Booth, Kellogg S. and Lueker, George S. Testing for the consecutive
ones property, interval graphs, and graph planarity using PQ-tree algorithms
(англ.) // Journal of Computer and System Sciences. — 1976. — Vol. 13, no. 3. —
P. 335–379.
6. Емеличев Р.И., Мельников О.И., Сарванов В.И., Тышкевич Р.И.
Лекции по теории графов. — М.: Наука, 1990.

Заказать новую

Лучшие эксперты сервиса ждут твоего задания

от 5 000 ₽

Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям

    Нажимая на кнопку, я соглашаюсь на обработку персональных данных и с правилами пользования Платформой

    Хочешь уникальную работу?

    Больше 3 000 экспертов уже готовы начать работу над твоим проектом!

    Юлия К. ЮУрГУ (НИУ), г. Челябинск 2017, Институт естественных и т...
    5 (49 отзывов)
    Образование: ЮУрГУ (НИУ), Лингвистический центр, 2016 г. - диплом переводчика с английского языка (дополнительное образование); ЮУрГУ (НИУ), г. Челябинск, 2017 г. - ин... Читать все
    Образование: ЮУрГУ (НИУ), Лингвистический центр, 2016 г. - диплом переводчика с английского языка (дополнительное образование); ЮУрГУ (НИУ), г. Челябинск, 2017 г. - институт естественных и точных наук, защита диплома бакалавра по направлению элементоорганической химии; СПХФУ (СПХФА), 2020 г. - кафедра химической технологии, регулирование обращения лекарственных средств на фармацевтическом рынке, защита магистерской диссертации. При выполнении заказов на связи, отвечаю на все вопросы. Индивидуальный подход к каждому. Напишите - и мы договоримся!
    #Кандидатские #Магистерские
    55 Выполненных работ
    Родион М. БГУ, выпускник
    4.6 (71 отзыв)
    Высшее экономическое образование. Мои клиенты успешно защищают дипломы и диссертации в МГУ, ВШЭ, РАНХиГС, а также других топовых университетах России.
    Высшее экономическое образование. Мои клиенты успешно защищают дипломы и диссертации в МГУ, ВШЭ, РАНХиГС, а также других топовых университетах России.
    #Кандидатские #Магистерские
    108 Выполненных работ
    Алёна В. ВГПУ 2013, исторический, преподаватель
    4.2 (5 отзывов)
    Пишу дипломы, курсовые, диссертации по праву, а также истории и педагогике. Закончила исторический факультет ВГПУ. Имею высшее историческое и дополнительное юридическо... Читать все
    Пишу дипломы, курсовые, диссертации по праву, а также истории и педагогике. Закончила исторический факультет ВГПУ. Имею высшее историческое и дополнительное юридическое образование. В данный момент работаю преподавателем.
    #Кандидатские #Магистерские
    25 Выполненных работ
    Мария М. УГНТУ 2017, ТФ, преподаватель
    5 (14 отзывов)
    Имею 3 высших образования в сфере Экологии и техносферной безопасности (бакалавриат, магистратура, аспирантура), работаю на кафедре экологии одного из опорных ВУЗов РФ... Читать все
    Имею 3 высших образования в сфере Экологии и техносферной безопасности (бакалавриат, магистратура, аспирантура), работаю на кафедре экологии одного из опорных ВУЗов РФ. Большой опыт в написании курсовых, дипломов, диссертаций.
    #Кандидатские #Магистерские
    27 Выполненных работ
    Виктор В. Смоленская государственная медицинская академия 1997, Леч...
    4.7 (46 отзывов)
    Имеют опыт грамотного написания диссертационных работ по медицине, а также отдельных ее частей (литературный обзор, цели и задачи исследования, материалы и методы, выв... Читать все
    Имеют опыт грамотного написания диссертационных работ по медицине, а также отдельных ее частей (литературный обзор, цели и задачи исследования, материалы и методы, выводы).Пишу статьи в РИНЦ, ВАК.Оформление патентов от идеи до регистрации.
    #Кандидатские #Магистерские
    100 Выполненных работ
    Рима С.
    5 (18 отзывов)
    Берусь за решение юридических задач, за написание серьезных научных статей, магистерских диссертаций и дипломных работ. Окончила Кемеровский государственный универси... Читать все
    Берусь за решение юридических задач, за написание серьезных научных статей, магистерских диссертаций и дипломных работ. Окончила Кемеровский государственный университет, являюсь бакалавром, магистром юриспруденции (с отличием)
    #Кандидатские #Магистерские
    38 Выполненных работ
    Анна В. Инжэкон, студент, кандидат наук
    5 (21 отзыв)
    Выполняю работы по экономическим дисциплинам. Маркетинг, менеджмент, управление персоналом. управление проектами. Есть опыт написания магистерских и кандидатских диссе... Читать все
    Выполняю работы по экономическим дисциплинам. Маркетинг, менеджмент, управление персоналом. управление проектами. Есть опыт написания магистерских и кандидатских диссертаций. Работала в маркетинге. Практикующий бизнес-консультант.
    #Кандидатские #Магистерские
    31 Выполненная работа
    Олег Н. Томский политехнический университет 2000, Инженерно-эконо...
    4.7 (96 отзывов)
    Здравствуйте! Опыт написания работ более 12 лет. За это время были успешно защищены более 2 500 написанных мною магистерских диссертаций, дипломов, курсовых работ. Явл... Читать все
    Здравствуйте! Опыт написания работ более 12 лет. За это время были успешно защищены более 2 500 написанных мною магистерских диссертаций, дипломов, курсовых работ. Являюсь действующим преподавателем одного из ВУЗов.
    #Кандидатские #Магистерские
    177 Выполненных работ
    Глеб С. преподаватель, кандидат наук, доцент
    5 (158 отзывов)
    Стаж педагогической деятельности в вузах Москвы 15 лет, автор свыше 140 публикаций (РИНЦ, ВАК). Большой опыт в подготовке дипломных проектов и диссертаций по научной с... Читать все
    Стаж педагогической деятельности в вузах Москвы 15 лет, автор свыше 140 публикаций (РИНЦ, ВАК). Большой опыт в подготовке дипломных проектов и диссертаций по научной специальности 12.00.14 административное право, административный процесс.
    #Кандидатские #Магистерские
    216 Выполненных работ

    Другие учебные работы по предмету

    Модернизация системы автоматизации АСУ ТП АО «Farg’onaazot»
    📅 2020год
    🏢 Национальный исследовательский Томский политехнический университет (ТПУ)
    Интеграционный сервис передачи данных между АСУ ТП и MES
    📅 2018год
    🏢 Национальный исследовательский Томский политехнический университет (ТПУ)
    Методы сегментации новообразований головного мозга
    📅 2020год
    🏢 Национальный исследовательский Томский политехнический университет (ТПУ)