Geum.ru

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

Курсовой проект - Математика и статистика

Другие курсовые по предмету Математика и статистика

тавлен на рисунке 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. Остов минимального веса

Решим данную задачу с помощью программной модели. Чтобы решить данную задачу необходимо построить матрицу весов.

Таблица 1. Матрица весов

ABCDEFGHKA-4194----B4------5-C1--10-3---D9-10-54-69E4-35-7--3F---47-10--G-----10--7H-5-6----5K---93-75-

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

Рисунок 17. Остов минимального веса

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

 

 

 

 

 

Заключение

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

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

Литература

  1. Судоплатов С.В., Овчинникова Е. В. Элементы дискретной математики: Учебник. М.: ИНФРА-М, Новосибирск: Изд-во НГТУ,2002. 208 с.
  2. Кандзюба С.П., Громов В.Н. Delphi 7. Базы данных и приложения. Лекции и упражнения. СПб: ООО ДиаСофтЮП, 2005. 576 с.
  3. Богумирский Б. А. Энциклопедия Windows 98. 2-е изд. СПб.: Питер, 2003896 с.
  4. Липский С.Г. Комбинаторика для программистов
  5. Васильков Ю.В., Н.Н. Василькова Компьютерные технологии вычислений в математическом моделировании, М. Финансы и Статистика, 1999
  6. Культин Н.Б. Delphi 7 Программирование на Object Pascal. СПб.: БХВ Петербург, 2005. 528 с.

 

Приложение А: листинг программы

 

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, Buttons, Grids, StdCtrls, ExtCtrls, ComCtrls, XPMan, Menus;

type

TForm1 = class(TForm)

sg: TStringGrid;

SpeedButton3: TSpeedButton;

sr: TStringGrid;

SpeedButton4: TSpeedButton;

SpeedButton5: TSpeedButton;

Edit1: TEdit;

Label1: TLabel;

SpeedButton7: TSpeedButton;

Image1: TImage;

Image2: TImage;

Label2: TLabel;

Label3: TLabel;

Timer1: TTimer;

SpeedButton8: TSpeedButton;

CheckBox1: TCheckBox;

Bevel1: TBevel;

Bevel2: TBevel;

Bevel3: TBevel;

Bevel4: TBevel;

Bevel5: TBevel;

Bevel6: TBevel;

Bevel7: TBevel;

Bevel8: TBevel;

Bevel9: TBevel;

Bevel10: TBevel;

BitBtn1: TBitBtn;

BitBtn2: TBitBtn;

Vremya: TTimer;

XPManifest1: TXPManifest;

Label4: TLabel;

BitBtn3: TBitBtn;

BitBtn4: TBitBtn;

Label5: TLabel;

Label6: TLabel;

procedure FormCreate(Sender: TObject);

procedure SpeedButton3Click(Sender: TObject);

procedure SpeedButton4Click(Sender: TObject);

procedure SpeedButton5Click(Sender: TObject);

procedure SpeedButton7Click(Sender: TObject);

procedure Image2DblClick(Sender: TObject);

procedure SpeedButton8Click(Sender: TObject);

procedure Image1MouseDown(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

procedure Image2Click(Sender: TObject);

procedure BitBtn1Click(Sender: TObject);

procedure BitBtn2Click(Sender: TObject);

procedure VremyaTimer(Sender: TObject);

procedure