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

Комаров, Вячеслав Андреевич Отделение информационных технологий (ОИТ)
Бесплатно
В избранное
Работа доступна по лицензии 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 экспертов уже готовы начать работу над твоим проектом!

    Татьяна Б.
    4.6 (92 отзыва)
    Добрый день, работаю в сфере написания студенческих работ более 7 лет. Всегда довожу своих студентов до защиты с хорошими и отличными баллами (дипломы, магистерские ди... Читать все
    Добрый день, работаю в сфере написания студенческих работ более 7 лет. Всегда довожу своих студентов до защиты с хорошими и отличными баллами (дипломы, магистерские диссертации, курсовые работы средний балл - 4,5). Всегда на связи!
    #Кандидатские #Магистерские
    138 Выполненных работ
    Оксана М. Восточноукраинский национальный университет, студент 4 - ...
    4.9 (37 отзывов)
    Возможно выполнение работ по правоведению и политологии. Имею высшее образование менеджера ВЭД и правоведа, защитила кандидатскую и докторскую диссертации по политоло... Читать все
    Возможно выполнение работ по правоведению и политологии. Имею высшее образование менеджера ВЭД и правоведа, защитила кандидатскую и докторскую диссертации по политологии.
    #Кандидатские #Магистерские
    68 Выполненных работ
    Дарья Б. МГУ 2017, Журналистики, выпускник
    4.9 (35 отзывов)
    Привет! Меня зовут Даша, я окончила журфак МГУ с красным дипломом, защитила магистерскую диссертацию на филфаке. Работала журналистом, PR-менеджером в международных ко... Читать все
    Привет! Меня зовут Даша, я окончила журфак МГУ с красным дипломом, защитила магистерскую диссертацию на филфаке. Работала журналистом, PR-менеджером в международных компаниях, сейчас работаю редактором. Готова помогать вам с учёбой!
    #Кандидатские #Магистерские
    50 Выполненных работ
    Анна В. Инжэкон, студент, кандидат наук
    5 (21 отзыв)
    Выполняю работы по экономическим дисциплинам. Маркетинг, менеджмент, управление персоналом. управление проектами. Есть опыт написания магистерских и кандидатских диссе... Читать все
    Выполняю работы по экономическим дисциплинам. Маркетинг, менеджмент, управление персоналом. управление проектами. Есть опыт написания магистерских и кандидатских диссертаций. Работала в маркетинге. Практикующий бизнес-консультант.
    #Кандидатские #Магистерские
    31 Выполненная работа
    Логик Ф. кандидат наук, доцент
    4.9 (826 отзывов)
    Я - кандидат философских наук, доцент кафедры философии СГЮА. Занимаюсь написанием различного рода работ (научные статьи, курсовые, дипломные работы, магистерские дисс... Читать все
    Я - кандидат философских наук, доцент кафедры философии СГЮА. Занимаюсь написанием различного рода работ (научные статьи, курсовые, дипломные работы, магистерские диссертации, рефераты, контрольные) уже много лет. Качество работ гарантирую.
    #Кандидатские #Магистерские
    1486 Выполненных работ
    Анна С. СФ ПГУ им. М.В. Ломоносова 2004, филологический, преподав...
    4.8 (9 отзывов)
    Преподаю англ язык более 10 лет, есть опыт работы в университете, школе и студии англ языка. Защитила кандидатскую диссертацию в 2009 году. Имею большой опыт написания... Читать все
    Преподаю англ язык более 10 лет, есть опыт работы в университете, школе и студии англ языка. Защитила кандидатскую диссертацию в 2009 году. Имею большой опыт написания и проверки (в качестве преподавателя) контрольных и курсовых работ.
    #Кандидатские #Магистерские
    16 Выполненных работ
    Елена С. Таганрогский институт управления и экономики Таганрогский...
    4.4 (93 отзыва)
    Высшее юридическое образование, красный диплом. Более 5 лет стажа работы в суде общей юрисдикции, большой стаж в написании студенческих работ. Специализируюсь на напис... Читать все
    Высшее юридическое образование, красный диплом. Более 5 лет стажа работы в суде общей юрисдикции, большой стаж в написании студенческих работ. Специализируюсь на написании курсовых и дипломных работ, а также диссертационных исследований.
    #Кандидатские #Магистерские
    158 Выполненных работ
    Вики Р.
    5 (44 отзыва)
    Наличие красного диплома УрГЮУ по специальности юрист. Опыт работы в профессии - сфера банкротства. Уровень выполняемых работ - до магистерских диссертаций. Написан... Читать все
    Наличие красного диплома УрГЮУ по специальности юрист. Опыт работы в профессии - сфера банкротства. Уровень выполняемых работ - до магистерских диссертаций. Написание письменных работ для меня в удовольствие.Всегда качественно.
    #Кандидатские #Магистерские
    60 Выполненных работ
    Мария А. кандидат наук
    4.7 (18 отзывов)
    Мне нравится изучать все новое, постоянно развиваюсь. Могу написать и диссертацию и кандидатскую. Есть опыт в различных сфера деятельности (туризм, экономика, бухучет... Читать все
    Мне нравится изучать все новое, постоянно развиваюсь. Могу написать и диссертацию и кандидатскую. Есть опыт в различных сфера деятельности (туризм, экономика, бухучет, реклама, журналистика, педагогика, право)
    #Кандидатские #Магистерские
    39 Выполненных работ

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

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