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

Комаров, Вячеслав Андреевич Отделение информационных технологий (ОИТ)
Бесплатно
В избранное
Работа доступна по лицензии 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, Журналистики, выпускник
    4.9 (35 отзывов)
    Привет! Меня зовут Даша, я окончила журфак МГУ с красным дипломом, защитила магистерскую диссертацию на филфаке. Работала журналистом, PR-менеджером в международных ко... Читать все
    Привет! Меня зовут Даша, я окончила журфак МГУ с красным дипломом, защитила магистерскую диссертацию на филфаке. Работала журналистом, PR-менеджером в международных компаниях, сейчас работаю редактором. Готова помогать вам с учёбой!
    #Кандидатские #Магистерские
    50 Выполненных работ
    Анна В. Инжэкон, студент, кандидат наук
    5 (21 отзыв)
    Выполняю работы по экономическим дисциплинам. Маркетинг, менеджмент, управление персоналом. управление проектами. Есть опыт написания магистерских и кандидатских диссе... Читать все
    Выполняю работы по экономическим дисциплинам. Маркетинг, менеджмент, управление персоналом. управление проектами. Есть опыт написания магистерских и кандидатских диссертаций. Работала в маркетинге. Практикующий бизнес-консультант.
    #Кандидатские #Магистерские
    31 Выполненная работа
    Олег Н. Томский политехнический университет 2000, Инженерно-эконо...
    4.7 (96 отзывов)
    Здравствуйте! Опыт написания работ более 12 лет. За это время были успешно защищены более 2 500 написанных мною магистерских диссертаций, дипломов, курсовых работ. Явл... Читать все
    Здравствуйте! Опыт написания работ более 12 лет. За это время были успешно защищены более 2 500 написанных мною магистерских диссертаций, дипломов, курсовых работ. Являюсь действующим преподавателем одного из ВУЗов.
    #Кандидатские #Магистерские
    177 Выполненных работ
    Екатерина С. кандидат наук, доцент
    4.6 (522 отзыва)
    Практически всегда онлайн, доработки делаю бесплатно. Дипломные работы и Магистерские диссертации сопровождаю до защиты.
    Практически всегда онлайн, доработки делаю бесплатно. Дипломные работы и Магистерские диссертации сопровождаю до защиты.
    #Кандидатские #Магистерские
    1077 Выполненных работ
    Рима С.
    5 (18 отзывов)
    Берусь за решение юридических задач, за написание серьезных научных статей, магистерских диссертаций и дипломных работ. Окончила Кемеровский государственный универси... Читать все
    Берусь за решение юридических задач, за написание серьезных научных статей, магистерских диссертаций и дипломных работ. Окончила Кемеровский государственный университет, являюсь бакалавром, магистром юриспруденции (с отличием)
    #Кандидатские #Магистерские
    38 Выполненных работ
    Анна Н. Государственный университет управления 2021, Экономика и ...
    0 (13 отзывов)
    Закончила ГУУ с отличием "Бухгалтерский учет, анализ и аудит". Выполнить разные работы: от рефератов до диссертаций. Также пишу доклады, делаю презентации, повышаю уни... Читать все
    Закончила ГУУ с отличием "Бухгалтерский учет, анализ и аудит". Выполнить разные работы: от рефератов до диссертаций. Также пишу доклады, делаю презентации, повышаю уникальности с нуля. Все работы оформляю в соответствии с ГОСТ.
    #Кандидатские #Магистерские
    0 Выполненных работ
    Татьяна П. МГУ им. Ломоносова 1930, выпускник
    5 (9 отзывов)
    Журналист. Младший научный сотрудник в институте РАН. Репетитор по английскому языку (стаж 6 лет). Также знаю французский. Сейчас занимаюсь написанием диссертации по и... Читать все
    Журналист. Младший научный сотрудник в институте РАН. Репетитор по английскому языку (стаж 6 лет). Также знаю французский. Сейчас занимаюсь написанием диссертации по истории. Увлекаюсь литературой и темой космоса.
    #Кандидатские #Магистерские
    11 Выполненных работ
    user1250010 Омский государственный университет, 2010, преподаватель,...
    4 (15 отзывов)
    Пишу качественные выпускные квалификационные работы и магистерские диссертации. Опыт написания работ - более восьми лет. Всегда на связи.
    Пишу качественные выпускные квалификационные работы и магистерские диссертации. Опыт написания работ - более восьми лет. Всегда на связи.
    #Кандидатские #Магистерские
    21 Выполненная работа
    Александр Р. ВоГТУ 2003, Экономический, преподаватель, кандидат наук
    4.5 (80 отзывов)
    Специальность "Государственное и муниципальное управление" Кандидатскую диссертацию защитил в 2006 г. Дополнительное образование: Оценка стоимости (бизнеса) и госфин... Читать все
    Специальность "Государственное и муниципальное управление" Кандидатскую диссертацию защитил в 2006 г. Дополнительное образование: Оценка стоимости (бизнеса) и госфинансы (Казначейство). Работаю в финансовой сфере более 10 лет. Банки,риски
    #Кандидатские #Магистерские
    123 Выполненных работы

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

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