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

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

    Андрей С. Тверской государственный университет 2011, математический...
    4.7 (82 отзыва)
    Учился на мат.факе ТвГУ. Любовь к математике там привили на столько, что я, похоже, никогда не перестану этим заниматься! Сейчас работаю в IT и пытаюсь найти время на... Читать все
    Учился на мат.факе ТвГУ. Любовь к математике там привили на столько, что я, похоже, никогда не перестану этим заниматься! Сейчас работаю в IT и пытаюсь найти время на продолжение диссертационной работы... Всегда готов помочь! ;)
    #Кандидатские #Магистерские
    164 Выполненных работы
    Глеб С. преподаватель, кандидат наук, доцент
    5 (158 отзывов)
    Стаж педагогической деятельности в вузах Москвы 15 лет, автор свыше 140 публикаций (РИНЦ, ВАК). Большой опыт в подготовке дипломных проектов и диссертаций по научной с... Читать все
    Стаж педагогической деятельности в вузах Москвы 15 лет, автор свыше 140 публикаций (РИНЦ, ВАК). Большой опыт в подготовке дипломных проектов и диссертаций по научной специальности 12.00.14 административное право, административный процесс.
    #Кандидатские #Магистерские
    216 Выполненных работ
    Алёна В. ВГПУ 2013, исторический, преподаватель
    4.2 (5 отзывов)
    Пишу дипломы, курсовые, диссертации по праву, а также истории и педагогике. Закончила исторический факультет ВГПУ. Имею высшее историческое и дополнительное юридическо... Читать все
    Пишу дипломы, курсовые, диссертации по праву, а также истории и педагогике. Закончила исторический факультет ВГПУ. Имею высшее историческое и дополнительное юридическое образование. В данный момент работаю преподавателем.
    #Кандидатские #Магистерские
    25 Выполненных работ
    Дарья П. кандидат наук, доцент
    4.9 (20 отзывов)
    Профессиональный журналист, филолог со стажем более 10 лет. Имею профильную диссертацию по специализации "Радиовещание". Подробно и серьезно разрабатываю темы научных... Читать все
    Профессиональный журналист, филолог со стажем более 10 лет. Имею профильную диссертацию по специализации "Радиовещание". Подробно и серьезно разрабатываю темы научных исследований, связанных с журналистикой, филологией и литературой
    #Кандидатские #Магистерские
    33 Выполненных работы
    Александр О. Спб государственный университет 1972, мат - мех, преподав...
    4.9 (66 отзывов)
    Читаю лекции и веду занятия со студентами по матанализу, линейной алгебре и теории вероятностей. Защитил кандидатскую диссертацию по качественной теории дифференциальн... Читать все
    Читаю лекции и веду занятия со студентами по матанализу, линейной алгебре и теории вероятностей. Защитил кандидатскую диссертацию по качественной теории дифференциальных уравнений. Умею быстро и четко выполнять сложные вычислительные работ
    #Кандидатские #Магистерские
    117 Выполненных работ
    Евгения Р.
    5 (188 отзывов)
    Мой опыт в написании работ - 9 лет. Я специализируюсь на написании курсовых работ, ВКР и магистерских диссертаций, также пишу научные статьи, провожу исследования и со... Читать все
    Мой опыт в написании работ - 9 лет. Я специализируюсь на написании курсовых работ, ВКР и магистерских диссертаций, также пишу научные статьи, провожу исследования и создаю красивые презентации. Сопровождаю работы до сдачи, на связи 24/7 ?
    #Кандидатские #Магистерские
    359 Выполненных работ
    Екатерина П. студент
    5 (18 отзывов)
    Работы пишу исключительно сама на основании действующих нормативных правовых актов, монографий, канд. и докт. диссертаций, авторефератов, научных статей. Дополнительно... Читать все
    Работы пишу исключительно сама на основании действующих нормативных правовых актов, монографий, канд. и докт. диссертаций, авторефератов, научных статей. Дополнительно занимаюсь английским языком, уровень владения - Upper-Intermediate.
    #Кандидатские #Магистерские
    39 Выполненных работ
    Александр Р. ВоГТУ 2003, Экономический, преподаватель, кандидат наук
    4.5 (80 отзывов)
    Специальность "Государственное и муниципальное управление" Кандидатскую диссертацию защитил в 2006 г. Дополнительное образование: Оценка стоимости (бизнеса) и госфин... Читать все
    Специальность "Государственное и муниципальное управление" Кандидатскую диссертацию защитил в 2006 г. Дополнительное образование: Оценка стоимости (бизнеса) и госфинансы (Казначейство). Работаю в финансовой сфере более 10 лет. Банки,риски
    #Кандидатские #Магистерские
    123 Выполненных работы
    Кормчий В.
    4.3 (248 отзывов)
    Специализация: диссертации; дипломные и курсовые работы; научные статьи.
    Специализация: диссертации; дипломные и курсовые работы; научные статьи.
    #Кандидатские #Магистерские
    335 Выполненных работ

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

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