Исследование и программная реализация алгоритмов теории графов

Пояснительная записка

(СТ. 000000. 035. ПЗ)

 

 

Руководитель

Иванилова Т.Н.

___________________

дата оценка роспись

 

Выполнила

студентка группы 21-6

Иванова А. А.

___________________

дата сдачи роспись

 

 

Красноярск, 2012

 

Сибирский государственный технологический университет

Кафедра системотехники

 

ЗАДАНИЕ

НА курсовую РАБОТУ ПО дискретной математике

Студент Иванова Анжелика Анатольевна

Факультет ЗХТ_ Группа 22-04

Тема КР: Исследование и программная реализация методов и алгоритмов теории графов

Вариант 6.

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

 

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

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

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

Приложить распечатки экранов.

 

 

 

Календарный план выполнения работы

 

1 – 5.10.12 - формализация задачи

6 – 10.10.12 - уточнение входной и выходной информации

11 – 18.10.12 – составление схемы алгоритма

19 – 30 10.12 – проведение расчетов

1 - 10.12.12 – отладка и тестирование

11 - 20.12.12 - оформление пояснительной записки

23.12.12 – защита курсовой работы

Задание выдано ___ 01.10.12

Руководитель __________ Иванилова Т.Н.

Содержание

 

 

Реферат…………………………………………………………………………..5

 

Введение…………………………………………………………………………6

 

1 Деревья в теории графов. Минимальное остовное дерево……………7

 

2 Решение задачи..………………………………………………………...…….7

 

2.1 Входная и выходная информация…………………………………..7

 

2.2 Схема алгоритма....................................................................................7

 

2.3 Текст программы………………………………………………….…..7

 

2.4 Протокол контрольного расчета…………………………………...8

 

3 Инструкция по работе с программой…………………………………….10

 

Заключение…………………………………………………………………..….11

 

Список использованных источников………………………………………12

 

 

Реферат

 

Расчетно-графическая работа представляет собой решение задачи по расчету минимального остовного дерева. Расчет выполнен с помощью языка программирования Pascal 6.0 на ПК PENTIUM166.

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

Ключевые слова: граф, дерево, минимальное остовное дерево.

Цель работы – овладение навыками работы с алгоритмом построения минимального остовного дерева.

Метод исследования – теория графов, алгоритмизация, язык программирования Pascal.

Данная программа позволяет:

1) определить способ задания графа;

2) ввести граф, используя матрицу смежности;

3) рассчитать минимальное остовное дерево;

4) провести тестирование алгоритма.

Введение

Необходимо написать о применении методов теории графов в практических задачах.

 

 

1 Деревья в теории графов. Минимальное остовное дерево

 

Напечатайте текст из учебников или лекций, далее выполните разделы в соответствии с содержанием.

Решение задачи

2.1 Входная и выходная информация

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

 

2.2 Схема алгоритма

Необходимо представить укрупненную блок-схему алгоритма

 

2.3 Текст программы

Program Di_mat;

Uses crt,graph;

const r=20;

 

var

gfx,gfy:array[1..20] of integer;

matrix: array[1..20,1..20] of integer;

fx:array[1..20] of boolean;

grline: array [1..20] of byte;

gdx,gdy,n,i,j:integer;

d: Real;

 

procedure init;

var graphdriver,graphmode,errorcode:integer;

begin

graphdriver:= detect;

initgraph(graphdriver,graphmode,'');

errorcode:=graphresult;

if errorcode <> grok then

begin

write('Error');

halt;

end;

end;

 

 

procedure DrawGraph(i:Integer);

var

s:string;

begin

circle(gfx[i],gfy[i],r);

settextstyle(1,0,1);

 

settextjustify(1,1);

str(i,s);

outtextxy(gfx[i],gfy[i]-r div 5,s);

end;

 

procedure DrawLink(i,j: Integer);

var

s:string;

begin

gdx:=gfx[j]-gfx[i];

gdy:=gfy[j]-gfy[i];

d:=sqrt(LongInt(gdx)*gdx+LongInt(gdy)*gdy);

gdx:=round(gdx*r/d);

gdy:=round(gdy*r/d);

Line(gfx[i]+gdx,gfy[i]+gdy,gfx[j]-gdx,gfy[j]-gdy);

end;

2.4 Протокол контрольного расчета

Возьмем 6 городов, а длины телефонных кабелей зададим матрицей длин дуг.

 

¥
	¥
		¥
			¥
				¥
					¥

Рисунок 1- Расположение городов с помощью матрицы

 

В результате получается граф показанный на рисунке 2.

Задание выдано ____________________

Руководитель Иванилова Т.Н.

Рисунок 2- Граф

 

Минимальное остовное дерева графа, полученное после расчетов, выглядит так:

 

Рисунок 3- Минимальное остовное дерево