Графовые модели. Остов минимального веса (стр. 1 из 4)

Основные понятия теории графов. Инструментальные программные средства. Блок-схема алгоритма моделирования. Операционная среда моделирования. Контрольная задача моделирования

Введение

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

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

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

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

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

1 Постановка задачи моделирования

1.1Основные понятия теории графов

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

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

Граф G’(v’,e’) является остовом минимального веса графа G(v,e), если v’=v и e’ – есть подмножество ребер минимального веса и количества, соединяющих все вершины. Остовом минимального веса может являться сеть минимальной стоимости, в матрице соединения которой cij=cji.

Граф G=<v, e> называется ориентированным (орграфом), если найдется дуга (a,b)ÎR такая, что (b,a)ÏR.

Если же отношение R симметрично, то есть из (a,b)ÎR следует (b,a)ÎR, то граф G называется неориентированным (неорграфом).

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

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

1.2 Представление графов

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

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

Матрица смежности - матрица размером

, элементы которой равны 1, если i-я вершина смежна с j-ой, и 0 в противном случае.

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

1.3 Алгоритм нахождения остова минимального

веса во взвешенном графе

Для нахождения остова минимального веса с помощью метода Краскала нужно выполнить следующие шаги:

1.Помечают вершину начала построения остова. Среди ребер, инцидентных помеченной вершине, находят ребро минимального веса для остова. Помечают новую вершину, инцидентную этому ребру. Вершина новая, если к ней ранее не обращались.

2.Смотрят, все ли вершины помечены. Если да, то заканчивают поиск, если нет, то переходят к шагу 3.

3.Среди ребер, инцидентных помеченным вершинам, за исключением ребер остова и ребер, образующих в остове цикл, находят ребро минимального веса для остова. Помечают новую вершину, инцидентную этому ребру, и переходят к шагу 2.

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

2 Инструментальные программные средства

2.1 Обоснование выбора инструментальных средств

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

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

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

В настоящее время наиболее распространенной средой является Delphi.

Delphi – пакет средств быстрой разработки приложений. К достоинствам относятся удобный интерфейс, высокая скорость работы, большое количество библиотек компонентов, эффективность создаваемых программ. Кроме того, строгая типизированность языка Object Pascal позволяет компилятору уже на этапе компиляции обнаружить многие ошибки, а также возможность работать с указателями.

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

Кроме того, в Delphi имеются развитые средства для работы с графическими возможностями Windows. В стандартном графическом интерфейсе Windows основой для рисования служит дескриптор контекста устройства нос и связанные с ним шрифт, перо и кисть. В состав входят объектно-ориентированные надстройки над последними, назначением которых является удобный доступ к свойствам инструментов и прозрачная для пользователя обработка всех их изменений. Поэтому использование класса TCanvas, являющегося основой графической системы Delphi, позволяет выполнить одну из основных функций разрабатываемой программы – наглядное представление графа. Delphi также дает возможность использовать традиционный набор функций работы с файлами, унаследованный от Turbo Pascal. Что позволяет сохранять результаты работы программы в файлы на жестком диске. Кроме того, в данной среде имеется возможность, наряду с обычными массивами, создавать динамические массивы, которые будут играть роль матрицы весов ребер графа. Хотя по большей части на представление графа в памяти машины выбор инструментальных средств особого значения не имеет.

Программа CorelDRAW 11, составляющая основу современного набора программных средств фирмы Corel, была выпущена в августе 2002 г. Она представляет собой результат двенадцатилетней эволюции, обладает удивительной универсальностью и мощностью, будучи в равной степени полезной и в промышленном дизайне, и в разработке рекламной продукции, и в подготовке публикаций, и в создании изображений для web-страниц, также в создании блок-схем алгоритмов. Несмотря на то, что мировым лидером программ для работы с векторной графикой сегодня является другая программа — Adobe Illustrator, CorelDRAW 11 ни в чем не уступает ей, а по многим параметрам и превосходит, и у нее — огромная армия пользователей-профессионалов, считающих CorelDRAW своим основным рабочим инструментом.

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

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

3 Блок-схема алгоритма задачи моделирования

Рисунок 1.Блок-схема алгоритма задачи моделирования

3.1 Описание блок-схемы алгоритма задачи моделирования

Блок 1. Ввод матрицы весов ребер графа. Запись графа в память компьютера осуществляется при помощи двумерного массива, который служит матрицей весов ребер графа.