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




Скачать 64.63 Kb.
НазваниеСистема решения задач на графах
Дата публикации26.03.2013
Размер64.63 Kb.
ТипРеферат
vbibl.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Система построения и анализа графиков функций
Графики функций являются важным элементом решения множества различных задач. Это могут быть учебные, научные и практические. Начиная...

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

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

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

Система решения задач на графах icon«рабочая программа «решение задач и постановка экспериментов в курсе Цитология и Генетика»
Тотл и включает 24 часа экспериментальных работ по цитологическим основам наследственности, моногибридному и дигибридному скрещиванию,...

Система решения задач на графах iconИндивидуальная траектория учащегося 11Б класса Засухина Ильи в 2011- 2012 учебном году
Он обладает высоким уровнем интеллекта, логическим мышлением. В настоящее время ему необходимы дополнительные теоретические знания...

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

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
vbibl.ru
Главная страница