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

Тема: Курсовые проекты

align=center> 9

Отриманий мінімальний остов з допомогою програмної моделі зображений на малюнку 17. <В

Малюнок 17. Остов мінімальної ваги

Після перевірки обчислень вручну і програмної моделі отримані остови мінімальної ваги розрізняються, але вони побудовані вірно. Це пов'язано з тим, що програма обирає іншу вершину початку. Після рішення двох контрольних завдань стало ясно, що розроблена програмна модель працює вірно.

Висновок

Метою даного курсового проекту була задача знаходження кістяка мінімальної ваги у зваженому графі за допомогою алгоритму Краскала. Є багато способів створення моделі, що вирішує цю задачу. Можуть існувати різні алгоритми обробки графів з різними уявленнями: у вигляді матриці інцидентності, матриці суміжності, матриці ваг. При вирішенні даної задачі можна змінювати вершину початку пошуку кістяка мінімальної ваги, при цьому конфігурація остова НЕ змінитися. Вона може змінитися за наявності ребер однакового мінімального ваги.

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

Література

1.Судоплатов С.В., Овчинникова Е. В. Елементи дискретної математики: Підручник. - М.: ИНФРА-М, Новосибірськ: Изд-во НГТУ, 2002. - 208 с. p> 2.Кандзюба С.П., Громов В.М. Delphi 7. Бази даних та програми. Лек-ції і вправи. - СПб: ТОВ В«ДіаСофтЮПВ», 2005. - 576 с. p> 3.Богумірскій Б. А. Енциклопедія Windows 98. 2-е вид. - СПб.: Пітер, 2003-896 с. p> 4.Ліпскій С.Г. В«Комбінаторика для програмістів В»

5.Васільков Ю.В., М.М. Василькова В«Комп'ютерні технології обчислень в математичному моделюванніВ», М. Фінанси і Статистика, 1999

6.Культін Н.Б. Delphi 7 Програмування на Object Pascal. - СПб.: БХВ - Петербург, 2005. - 528 с. br/>

Додаток А: лістинг програми

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;