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

Блок 2. Ввод вершины поиска. После заполнения матрицы весов пользователем программа автоматически определяет вершину начала построения остова.

Блок 3. Поиск ребра минимального веса среди инцидентных n ребер. Программа анализирует матрицу весов и находит ребро с минимальным весом. Найденное ребро сохраняется в переменную min.

Блок 4. Формирование остова. Формируется остов.

Блок 5.Выбор новой инцидентной вершины. Помечается новая вершина, инцидентная ребру, - переменная m.

Блок 6. Все вершины графа помечены. Если все вершины графа помечены, то поиск остова заканчивается. Если нет, то среди инцидентных помеченным вершинам ребер, за исключением ребер остова и ребер, образующих в остов цикл, происходит поиск ребра минимального веса min и построение остова.

Блок 7. Вывод остова. После того как все вершины графа помечены, на монитор пользователя выводится остов минимального веса.

Блок 8. Инцидентные помеченным вершинам ребра. Если есть такие ребра, то программа анализирует найденные ребра, если нет инцидентных ребер, то программа переходит к Блоку 6.

Блок 9. Ребра остова. Найденное ребро не используется в остове, то программа переходит к Блоку 10, а если используется, то переходит к Блоку 6.

Блок 10. Образует ребро в остове цикл, если да то программа переходит к Блоку 6. Если ребро не образует в остове цикл, то программа переходит к Блоку11.

Блок 11. Нахождение ребра минимального веса. Программа анализирует оставшиеся инцидентные ребра выбранной вершине и переходит к Блоку 12.

Блок 12. Формирование остова. Программа формирует полученный остов, проверяется связанность ребер с вершинами графа, за это отвечает массив связанности ar[jmin, imin], если он равен единицам, то все ребра связаны с вершинами, если он не равен единице, то продолжается формирование остова.

Блок 13. Выбор новой инцидентной вершины. Помечается новая вершина графа, программа переходит к Блоку 6.

Блоки блок-схемы во многом повторяют шаги теоретического решения, лишь незначительно конкретизируясь на привязке к конкретному языку программирования (в данном случае Delphi).

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

4 Операционная среда моделирования

4.1 Описание операционной среды моделирования

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

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

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

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

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

Windows имеет разные версии, смотря, для кого предназначена операционная система для сервера или для клиента. Для разработки курсового проекта я выбрал операционную систему под названием Windows XP Professional, так как я считаю её наиболее подходящей. Данная версия Windows XP Professional наиболее распространена среди всех версий Windows. Для этой версии Windows написано большое количество программ, а это означает, что этой версией Windows пользуется большое количество пользователей, а если пользуются значит она работает корректно.

4.2 Аппаратная среда моделирования

Основные аппаратные затраты приходятся на среду проектирования данной программной модели (в данном случае Delphi). Минимальные требования, предъявляемые к оборудованию, при работе в данной среде программирования следующие:

-Процессор Intel Pentium с тактовой частотой 166 МГц и выше;

-128 МБ оперативной памяти;

-свободное пространство на жестком диске для полной установки 5 МБ;

-дисковод для компакт-дисков;

-VGA или SVGA монитор;

-стандартный манипулятор мышь и клавиатура;

-операционная система Windows 98/2000/XP.

Программная модель требует гораздо меньше аппаратных средств. Для ее работы достаточно стандартного набора оборудования: монитор типа VGA/SVGA, клавиатура, мышь. Программа занимает 568 КБ свободного пространства на диске и 12 МБ оперативной памяти. Программа может больше занимать пространства на жестком диске это связанно с тем, что матрица весов занесенная пользователем перед поиском минимального веса записывается в файл, и соответственно чем больше матриц весов будет занесено тем больше будет вес файла. После закрытия программы файл, в который записывались матрицы весов, он удаляется и пространство на жестком диске освобождается – это сделано для того чтобы не «засорять» свободное место на жестком диске. Особых требований к видеоадаптеру программа не имеет, но желательно 16 МБ и выше.

4.3 Руководство оператора

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

Для запуска программы необходимо активировать exe – файл с названием «Краскал.exe» запустится программа. Рисунок главной формы изображен на рисунке1.

Рисунок 2.Главная форма программы.

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

Рисунок 3.Графическое изображение графа.

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

Рисунок 4.Найденный остов минимального веса.

На форме размещены еще три кнопки:

-«Начать заново» при нажатии на эту кнопку все поля очищаются и главная форма принимает первоначальный вид.

-«Помощь» при нажатии на эту кнопку вызывает помощь для пользователя. Помощь для пользователя изображена на рисунке 4.

Рисунок 5. Помощь для пользователя.

Последняя кнопка, которая размещена на форме «Выход», при нажатии на кнопку приложение будет закрыто.

4.4 Лицензионное соглашение

Алгоритм Краскала (версия 1.0)

1) Всеми авторскими правами на "Алгоритм Краскала" эксклюзивно владеет автор программы – Терешков Юрий Игоревич.

2) " Алгоритм Краскала " могут распространяться только в том виде, в котором они поставляются автором.

3) " Алгоритм Краскала " распространяются по принципу "как есть". При этом не предусматривается никаких гарантий, явных или подразумеваемых. Вы используете его на свой собственный риск. Автор не отвечает за потери данных, повреждения, потери прибыли или любые другие виды потерь, связанные с использованием (правильным или неправильным) этой программы.

4) Вы не можете эмулировать, клонировать, сдавать в аренду, давать напрокат, продавать, изменять, декомпилировать, дизассемблировать " Алгоритм Краскала". Любое подобное неавторизованное использование приводит к немедленному и автоматическому прекращению действия этой лицензии и может повлечь за собой уголовное и/или гражданское преследование.

5) Все права, явно не представленные здесь, принадлежат автору программы.

6) Запуск и использование " Алгоритм Краскала " свидетельствует о согласии с условиями данной лицензии.

7) Если вы не согласны с условиями данной лицензии, то должны удалить файлы " Алгоритм Краскала " со своих устройств хранения информации и отказаться от их использования.

Спасибо за использование " Алгоритм Краскала "!

Автор программы: Терешков Юрий Игоревич.

5 Контрольная задача моделирования

В данном разделе решено две контрольные задачи:

-вручную;

-с помощью программной модели.

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

Задача №1. Дан взвешенный связный неориентированный граф, состоящий из пяти вершин. Необходимо найти остов минимального веса с помощью алгоритма Краскала.