Система решения задач на графах




Скачать 64.62 Kb.
НазваниеСистема решения задач на графах
Дата публикации24.06.2013
Размер64.62 Kb.
ТипРеферат
lit-yaz.ru > Информатика > Реферат


XXXVIII городская научно-практическая конференция учащихся

Секция «Информатика»

Система решения задач на графах
Автор:
Галочкин Александр,
ученик 10 класса,
МОУ ДОД ЦТТ «Интеграл»
Научный руководитель:
Цыганов Александр
ПДО информатики
МОУ ДОД ЦТТ «Интеграл»

Самара, 2009

Содержание

Введение 4

1 Постановка задачи 5

2 Реализация 6

Заключение 13

Список литературы 14


Введение


Графом называется совокупность двух множеств – непустого множества вершин и множества ребер между ними. Самые разнообразные задачи формулируется в терминах точек и связей между ними, т.е. в терминах графов. Так, например, могут быть сформулированы задачи составления расписания, анализа сетей в электротехнике, цепей Маркова в теории вероятностей, различные задачи в программировании, в проектировании электронных систем, в экономике, в социологии и т.д. Поэтому эффективные алгоритмы решения задач теории графов имеют большое практическое применение.

Теория графов предоставляет очень удобный язык для описания различных моделей. Система специальных терминов и обозначений теории графов позволяют просто и доступно описывать сложные вещи. Особенно важно наличие наглядной графической интерпретации понятия графа.

Использование вычислительной техники позволяет упростить построение графов и выполнение различных алгоритмов на них. Компьютерные технологии ускоряют поиск необходимого решения. Поэтому различные программы-редакторы и средства решения задач теории графов широко востребованы.

1 Постановка задачи


В жизни часто приходится сталкиваться с задачами, представимыми в виде графов. Это также относится и к решению логических задач. Они могут быть решены средствами и алгоритмами теории графов. Компьютерные программы позволяют упростить и ускорить решение таких задач.

Существует ряд программных средств, предназначенных для редактирования и визуализации графов. Их основной недостаток – ориентированность исключительно на редактирования графов. Для дальнейшего решения задач с помощью каких-либо алгоритмов требуется использовать отдельные приложения или обрабатывать полученную модель самостоятельно.

Основная идея разрабатываемого редактора графов – поддержка выполнения различных алгоритмов в виде легко подключаемых модулей. Модульность дает свободу в модификации функциональности приложения без необходимости его перекомпиляции. Также это позволяет разрабатывать дополнительные алгоритмы пользователю самостоятельно.

Разработанный редактор позволяет создавать графы путем расположения вершин на поверхности, проведения между ними связей (в том числе направленных), задания и изменения их параметров.

К списку параметров вершин относятся: метка, вес, комментарии, расположение текста и размеры.

Параметры связи: метка, вес, комментарии, ориентированность, начальная вершина и конечная вершина.

Созданный граф может быть сохранен в файле и отредактирован после загрузки. После создания графа, можно выполнять различные операции посредствам библиотек (модулей). Каждый модуль – это реализация какого-либо алгоритма на графах.

В данную программу можно встраивать свои алгоритмы, выполнив их на языке C# в виде отдельной библиотеки и помесив ее в директорию с файлами редактора. Алгоритмы могут быть объединены в категории и содержать встроенную справку.

2 Реализация

2.1 Интерфейс


Интерфейс редактора состоит из меню, панели инструментов и поля редактирования графов (рисунок 1).



Рисунок 1 – редактор графа

Для редактирования имеются три инструмента: вершина, связь и ориентированная связь. Они позволяют создавать соответствующие объекты. При создании вершины ей автоматически назначается метка с ее идентификатором – номером по порядку.

При соединении вершин можно создать как не ориентированную связь, так и ориентированную (рисунок 2). Это зависит от выбранного инструмента.



Рисунок 2 – ориентированный граф

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

При двойном клике на объект или выборе соответствующего пункта контекстного меню открывается окно свойств вершины (рисунок 3) или связи (рисунок 4).



Рисунок 3 – свойства вершины



Рисунок 4 – свойства связи

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

Созданный граф можно сохранить в файле или отправить на обработку каким-либо алгоритмом. Для этого используются соответствующие пункты меню.

2.2 Модель


Граф представлен в программе набором объектов. Это вершины, связи между ними и модель самого графа в целом. Каждый объект управляется соответствующим элементом интерфейса. Это графические вершины, связи и панель графа. Внешний вид каждого элемента задается ассоциированной с ним моделью. При выполнении редактирования графа, графические компоненты изменяют состояние модели.

В результате модель не связана с представлением, а лишь представление с моделью. Это позволяет отделить решение задач от их визуализации. Когда разработанный в редакторе граф передается в какой-либо алгоритм или сохраняется в файле, то осуществляется обмен лишь данными модели.

Для удобства использования модели, она включает матрицу смежности и матрицу инциденций. Эти матрицы автоматически рассчитываются при изменении графа. Также, с помощью модели можно быстро получить доступ к информации о весе ребер, вершин и их степени.

2.3 Модули


Редактор графов поддерживает систему подключаемых модулей. Это библиотеки, расширяющие его за счет добавления возможностей по решению различных задач на графах. Каждый модуль представляет собой файл, содержащий класс, реализующий интерфейс алгоритма. При запуске редактор он сканирует свою папку на наличие модулей и заносит их список в меню «Алгоритмы». При обращении к какому-либо пункту этого меню, соответствующему модулю передается созданный в редакторе граф. Интерфейс работы с дополнением отображается в специальной форме, где с помощью компонента панели графа демонстрируется результат работы алгоритма.

2.3.1 Поиск пути


Поиск пути волновым алгоритмом (рисунок 5) является простым и эффективным методом поиска кратчайшего расстояния между двумя вершинами. Пользователь выбирает начало и конец пути. После этого вершины и ребра, входящие в кратчайший путь, окрашиваются в другой цвет.



Рисунок 5 – поиск пути

2.3.2 Алгоритм Дейкстры


Алгоритм Дейкстры позволяет быстро и эффективно находить кратчайший путь на графе с взвешенными ребрами. Он широко применяется в различных областях, таких как, например, сетевая маршрутизация или разводка печатных плат. Интерфейс (рисунок 6) аналогичен предыдущему модулю.



Рисунок 6 – алгоритм Дейкстры

2.3.3 Диаметр графа


Данный алгоритм позволяет найти максимальное расстояние между вершинами графа, называемое диаметром. Интерфейс модуля (рисунок 7) сразу же отображает результат поиска диаметра, как в числовом виде, так и в виде наиболее длинного кратчайшего пути.



Рисунок 7 – диаметр графа

2.3.4 Раскраска графа


Задача раскраски графов подразумевает присвоение вершинам минимального количества цветов так, что никакие две соседние не будут раскрашены одинаково. После запуска модуля он отображает раскрашенный граф (рисунок 8) и легенду, где указано, какой цвет означает какую группу одинаково раскрашенных вершин.



Рисунок 8 – раскраска графа

2.3.5 Минимальное остовное дерево


Для нахождения остовного дерева используется алгоритм Краскала. После запуска модуля, на форме отображается граф (рисунок 9) с раскрашенными ребрами, составляющими минимальное остовное дерево.



Рисунок 9 – остовное дерево

2.3.6 Максимальная клика


Кликой называют полный подграф. Данный алгоритм осуществляет поиск максимальной клики, то есть наибольшего полного подграфа (рисунок 10).



Рисунок 10 – максимальная клика

2.3.7 Мосты графа


Мостом графа называется такое ребро, удаление которого приводит к разделению графа на несвязанные подграфы. Данный модуль осуществляет поиск таких ребер и помечает их с помощью цвета (рисунок 11).



Рисунок 10 – мосты графа

Заключение


Разработанный редактор прост и удобен в использовании, а подключаемые модули с алгоритмами позволяют легко расширять его функциональность.

Он может использоваться как при решении задач, сводимых к графам, так и использоваться в процессе обучения дискретной математике. С его помощью можно демонстрировать методы теории графов и проводить лабораторные занятия по разработке модулей, реализующих различные алгоритмы.

Список литературы


  1. Ф. А. Новиков. «Дискретная математика для программистов». – СПб.: Питер, 2004.

  2. Б. Н Иванов «Дискретная математика (Алгоритмы и программы)». 2002.

  3. Э. Троелсен. C# и платформа .NET – СПб.: Питер, 2006.

  4. Вирт Н. Алгоритмы и структуры данных. – М.: Мир, 1989.




Добавить документ в свой блог или на сайт

Похожие:

Система решения задач на графах iconБольшинство учащихся не в полной мере владеют техникой решения текстовых...
Полный минимум знаний, необходимый для решения всех типов текстовых задач, формируется в течение первых девяти лет обучения учащихся...

Система решения задач на графах iconКонспект урока на тему «Основы логики (повторение). Решение логических...
Основы логики; познакомить учащихся с методами решения логических задач; формирование у учащихся практических умений и навыков решения...

Система решения задач на графах iconСистема построения и анализа графиков функций
Графики функций являются важным элементом решения множества различных задач. Это могут быть учебные, научные и практические. Начиная...

Система решения задач на графах iconСистема задач и упражнений по языку программирования Pascal Часть 1
Система задач и упражнений по языку программирования Pascal/ Сост. Е. Ю. Жохова, И. Е. Кокорева, П. А. Корнилов, Л. Я. Московская,...

Система решения задач на графах iconПриказ №
В условиях решения этих стратегических задач важнейшими качествами личности становятся инициативность, способность творчески мыслить...

Система решения задач на графах iconУчитель русского языка и литературы
В условиях необходимости решения этих стратегических задач важнейшими качествами личности становятся инициативность, способность...

Система решения задач на графах iconРешение занимательных задач Вторник 2 марта «Прикладная математика»
Провести в каждом классе мероприятия, содействующие развитию познавательной деятельности учащихся, расширению знаний по математике,...

Система решения задач на графах iconМетодическое пособие «Решение задач по теме «Растворы»
В условиях сокращения количества часов на изучение химии необходимо отметить нехватку времени на отработку навыков решения расчетных...

Система решения задач на графах iconФ.: ее предназначение, смысл, функции. Категориальный инструментарий...
Категориальный инструментарий Ф. Ф. особая система знаний предназначенная для решения целого ряда взаимосвязанных проблем, возникающих...

Система решения задач на графах iconФ.: ее предназначение, смысл, функции. Категориальный инструментарий...
Категориальный инструментарий Ф. Ф. особая система знаний предназначенная для решения целого ряда взаимосвязанных проблем, возникающих...



Образовательный материал



При копировании материала укажите ссылку © 2013
контакты
lit-yaz.ru
главная страница