Графовые модели. Остов минимального веса

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

Содержание
Введение......................................................................................4
1 Постановка задачи...................................................................5
1.1Основные понятия теории графов……………….....5
1.2 Представление графов...............................................5
1.3 Алгоритм нахождения остова минимального
веса во взвешенном графе……………………..…….....6
2 Инструментальные программные средства..........................7
2.1 Обоснование выбора инструментальных  средств…………...………………………………...……7
3 Блок-схема алгоритма моделирования................................10
3.1 Описание блок-схемы алгоритма задачи
моделирования……………………………………..….10
4 Операционная среда моделирования………………...........13
4.1 Описание операционной среды моделирования...13
4.2 Аппаратная среда моделирования…………………14
4.3 Руководство оператора……………………………..14
4.4 Лицензионное соглашение…………………………17
5 Контрольная задача моделирования………………………19
Заключение................................................................................26
Литература.................................................................................27
Приложение А: листинг программы.......................................28
Приложение Б: исходные файлы.............................................39

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

1 Постановка задачи моделирования
           1.1Основные понятия теории графов
Графом называетсяалгоритмическая модель, состоящая из множества вершин (узлов) v и соединяющих их ребер e.Ребро — неупорядоченная пара вер­шин графа.
Ребра называются смежными,если они имеют общую вершину. Вершины называются смежными, если есть ребро ихсоединяющее. Ребро, которое соеди­няет вершины, называется инцидентным этимвершинам, а вершины – инцидент­ные этому ребру.
Граф G’(v’,e’) является остовомминимального веса графа G(v,e), если v’=v и e’ – есть подмножество ребер минимальноговеса и количества, соединяющих все вершины. Остовом минимального веса можетявляться сеть минимальной стоимости, в матрице соединения которой cij=cji.
Граф G=называется ориентированным (орграфом), если найдется дуга (a,b)ÎRтакая, что (b,a)ÏR.
Если же отношение Rсимметрично, то есть из (a,b)ÎR следует (b,a)ÎR,то граф G называется неориентированным (неорграфом).
Связный граф — граф, укоторого для любых двух различных вершин суще­ствует цепь (последовательностьсмежных вершин), соединяющая их.
Для решения данной задачимоделирования будет использован неориенти­рованный связный  граф.
1.2 Представлениеграфов
Существуетчетыре базовых представлений графов в памяти машины: мат­рица инцидентности,матрица смежности, матрица списков смежности и связан­ные списки смежности. Ониразличаются скоростью выполнения операций над элементами представления иобъемом занимаемой памяти.
Длярешения поставленной задачи моделирования больше всего подходит представлениеграфов в памяти машины в виде матрицы смежности, а именно матрица весов.
  Матрица смежности — матрица размером
           Матрица смежности является симметричной и достаточнопросто мо­жет использоваться для ввода и обработки на ЭВМ. Для случаявзвешенного графа вместо 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 Блок-схема алгоритма задачи моделирования

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

3.1 Описание блок-схемы алгоритма задачи моделирования
Блок 1. Ввод матрицы весов реберграфа. Запись графа в память компью­тера осуществляется при помощи двумерногомассива, который служит матрицей весов ребер графа.
Блок 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имеетразные версии, смотря, для кого предназначена операцион­ная система для сервераили для клиента. Для разработки курсового проекта  я выбрал операционную систему под названием WindowsXPProfessional, так как ясчитаю её наиболее подходящей. Данная версия WindowsXPProfessionalнаибо­леераспространена среди всех версий 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.

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

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

Рисунок  SEQ Рисунок * ARABIC 5. Помощь для пользователя.
Последняякнопка, которая размещена на форме «Выход», при нажатии на кнопку приложение будетзакрыто.
4.4 Лицензионное соглашение
           АлгоритмКраскала (версия 1.0)
1)Всеми авторскими правами на «Алгоритм Краскала» эксклюзивно вла­деетавтор программы – Терешков Юрий Игоревич.
2)" Алгоритм Краскала " могут распространяться только в том виде, в ко­торомони поставляются автором.
3)" Алгоритм Краскала " распространяются по принципу «какесть». При этом не предусматривается никаких гарантий, явных илиподразумеваемых. Вы используете его на свой собственный риск. Автор не отвечаетза потери данных, повреждения, потери прибыли или любые другие виды потерь,связанные с ис­пользованием (правильным или неправильным) этой программы.
4)Вы не можете эмулировать, клонировать, сдавать в аренду, давать на­прокат,продавать, изменять, декомпилировать, дизассемблировать " АлгоритмКраскала". Любое подобное неавторизованное использование приводит к немед­ленномуи автоматическому прекращению действия этой лицензии и может по­влечь за собойуголовное и/или гражданское преследование.
5)Все права, явно не представленные здесь, принадлежат автору про­граммы.
6)Запуск и использование " Алгоритм Краскала " свидетельствует о согла­сиис условиями данной лицензии.
7)Если вы не согласны с условиями данной лицензии, то должны удалить файлы "Алгоритм Краскала " со своих устройств хранения информации и отка­затьсяот их использования.
Спасибоза использование " Алгоритм Краскала "!
Авторпрограммы: Терешков Юрий Игоревич.

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

Рисунок  SEQ Рисунок * ARABIC 6Исходный граф.
Выбираемвершину начала построения остова минимального веса, напри­мер, первую вершину.
Шаг 1.Найдено ребро минимального веса: 1-2=6. Полученный  остов на рисунок 7.

Рисунок  SEQ Рисунок * ARABIC 7. Полученный оостовна шаге 1
Шаг 2. Найдено ребро минимального веса: 2-3=7.Полученный остов на рисунок 8.

Рисунок  SEQ Рисунок * ARABIC 8.Полученный остов на шаге 2
Шаг 3. Найдено ребро минимального веса: 3-4=9. Полученныйостов  на рисунок 9.

Рисунок 9.Полученный остов нашаге 3
Шаг 4.Найдено ребро минимального веса: 3-5=11.
Рассмотренывсе вершины и инцидентные ребра этим вершинам, остав­шиеся образуют цикл в полученномминимальном  остове. А это неудовлетворяет условиям поставленной задачи.
На четвертом шагеполучили окончательный остов минимального веса, ко­торый представлен на рисунке10.

Рисунок 10. Остовминимального веса
Приизменении вершины начала построения конфигурация остова мини­мального веса неизмениться, а измениться лишь последовательность построения ребер остова.
Например,если в качестве начальной вершины выбрать четвертую вер­шину, топоследовательность этапов построения остова минимального веса будет выглядетьследующим образом:
Шаг1. 4-3=9;
Шаг2. 3-2=7;
Шаг3. 2-1=6;
Шаг4. 3-5=11;
Приэтом конфигурация остова останется прежней. Решим данную задачу с помощьюпрограммной модели. Чтобы решить данную задачу необходимо по­строить матрицувесов, матрица представлена на рисунке 11.

Рисунок 11. Матрица весов

Полученныйминимальный остов с помощью программной модели изо­бражен на рисунке 12.

Рисунок 12. Полученный минимальный остов
После проверки вычислений вручную ипрограммной модели результат одинаковый,это означает, что программная модель работаетифункционирует верно.
Задача №2. Дан взвешенный,связный, неориентированный граф, состоя­щий из девяти вершин. Необходимо найтиостов минимального веса с помощью ал­горитма Краскала. Исходный граф на рисунке13.

Рисунок 13. Исходный граф
Выбираемвершину начала построения остова минимального веса, напри­мер, первую вершину.
Шаг 1.Найдено ребро минимального веса: AC=1. Полученный  остовна рисунок 14.

Рисунок 13. Полученный остов на шаге 1
           Шаг 2. Найдено ребро минимального веса: CF=3, AB=4, AC=4. Полученный  остов на рисунок 15.
          
Рисунок 14. Полученный остов на шаге 2
           Шаг 3. Найдено ребро минимального веса: FD=4, EK=3, AE=4. Полученный  остов на рисунок 15.
          
Рисунок 15. Полученный остов на шаге 3
Шаг 4.Найдено ребро минимального веса: KH=5, KG=4. Рассмотрены все вершины и инцидентные ребра этимвершинам, остав­шиеся ребра образуют цикл в полученном минимальном  остове. А это не удовлетворяет условиямпоставленной задачи.
На четвертом шаге полученокончательный остов минимального веса, ко­торый представлен на рисунке 16.

Рисунок 16. Остов минимального веса
Решимданную задачу с помощью программной модели. Чтобы решить данную задачунеобходимо по­строить матрицу весов.
Таблица  SEQ Таблица * ARABIC 1. Матрица весов
A
B
C
D
E
F
G
H
K
A
-
4
1
9
4
-
-
-
-
B
4
-
-
-
-
-
-
5
-
C
1
-
-
10
-
3
-
-
-
D
9
-
10
-
5
4
-
6
9
E
4
-
3
5
-
7
-
-
3
F
-
-
-
4
7
-
10
-
-
G
-
-
-
-
-
10
-
-
7
H
-
5
-
6
-
-
-
-
5
K
-
-
-
9
3
-
7
5
-
Полученныйминимальный остов с помощью программной модели изо­бражен на рисунке 17.

Рисунок 17. Остов минимального веса
              После проверки вычислений вручную ипрограммной модели полученные остовы минимального веса различаются, но онипостроены верно. Это связано с тем, что программа выбирает другую вершинуначала. После решения двух контрольных задач стало ясно, что разработаннаяпрограммная модель работает верно.
<