Исследование свойств графа
скачать (29 kb.)
Доступные файлы (1):
| 1.doc | 29kb. | 18.12.2011 17:37 |  скачать |
- Смотрите также:
- Адаменко Н.А., Казуров А.В. Исследование теплофизических свойств полимеров [ документ ]
- Исследование свойств ферромагнитных материалов [ лабораторная работа ]
- Исследование свойств костюмной ткани и разработка рекомендаций по учету свойств [ курсовая работа ]
- Дипломная работа - Синтез и исследование функциональных свойств комплексных полифункциональных присадок [ документ ]
- Иcследование ВАХ биполярного транзистора [ документ ]
- Исследование электропроводности проводниковых материалов [ лабораторная работа ]
- Графическое представление графа [ документ ]
- Исследование свойств симметричного вибратора методом компьютерного моделирования [ лабораторная работа ]
- Исследование свойств сахара-песка и солода [ курсовая работа ]
- Архитектура Санкт-Петербурга [ документ ]
- Диагностика беременности: ректальное исследование [ реферат ]
- Исследование и логическое проектирование конечного частично определенного автомата [ документ ]
1.doc
МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ(Государственный Технический Университет)
филиал «Восход»
Кафедра ВТ
Отчет
по лабораторной работе №2
на тему «Исследование свойств графа»
по дисциплине: дискретная математика
Выполнил студент группы ДМ2-27 Князева М.А.________
«____»__________200__г.
Проверил преподаватель Крохина Н.В._________________
«____»__________200__г.
Байконур 2004г.
Цель работы: Смоделировать процедуру нахождения максимального дерева кратчайших расстояний.
Листинг программы
program laba2;
const n=5;
m=100;
var x,p,e:integer;
a:array[1..n,1..n] of integer;
f,t,g:array[1..n] of integer;
procedure zadan;
{процедура задания матрицы смежности взвешенного графа}
var i,j:integer;
begin
for i:=1 to n do
for j:=1 to n do a[i,j]:=m;
for i:=1 to n do a[i,i]:=0;
{присваивание рёбрам графа весов} a[1,2]:=11;
a[1,3]:=15;a[1,4]:=9; a[2,1]:=11;a[2,3]:=3;a[2,5]:=8;
a[3,1]:=15;a[3,2]:=3; a[3,4]:=5; a[3,5]:=2;a[4,1]:=9;
a[4,3]:=5; a[4,5]:=13;a[5,2]:=8; a[5,3]:=2;a[5,4]:=13;
end;
procedure raspech;
{вывод матрицы}
var i,j:integer;
begin
writeln;
writeln('Матрица смежности взвешенного графа');writeln;
writeln(' 1 2 3 4 5');
writeln(' -------------------');
for i:=1 to n do begin
write;for j:=1 to n do
if a[i,j]=m then begin
if j=1 then case i of
1: write('1 |'); 2: write('2 |'); 3: write('3 |');
4: write('4 |'); 5: write('5 |'); end;
write(' - |') end
else begin
if j=1 then case i of
1: write('1 |'); 2: write('2 |'); 3: write('3 |');
4: write('4 |'); 5: write('5 |'); end;
write(a[i,j]:3,'|'); end;
writeln; end;
writeln(' -------------------'); writeln;
end;
{***дерево кратчайших путей***}
procedure krat_put;
label 1;
var d,u,v: array[1..n] of integer;
s,m,i,j,k,l,jk:integer;
begin
e:=0; s:=x; m:=n-1;
for i:=1 to n do begin
u[i]:=i; d[i]:=a[x,i]; v[i]:=x; end;
u[x]:=n; d[x]:=d[n]; goto 1;
repeat
d[k]:=d[m]; u[k]:=u[m]; v[k]:=v[m]; dec(m);
{обновление кратчайшего расстояния}
for i:=1 to m do begin
j:=u[i]; jk:=l+a[s,j];
if d[i]>jk then begin
v[i]:=s; d[i]:=jk; end; end;
1:{запоминание кратчайшего расстояния}
k:=1; l:=d[1];
for i:=1 to m do if d[i]<l then begin
l:=d[i]; k:=i end;
{добавление вершин к дереву кратчайших расстояний}
inc(e); f[e]:=v[k]; t[e]:=u[k]; g[e]:=l; s:=u[k];
until s=p; {достигнута ли вершина p}
end;
procedure put;
var i:integer;
begin
writeln;
writeln('кратчайшее расстояние между узлами ',x,' и ',p,' равно ',g[e]);
end;
{основной блок}
Begin
zadan; raspech;
x:=1; p:=5;
krat_put; put; readln;
end.
Результат
Матрица смежности взвешенного графа
1 2 3 4 5
--------------------------
1 | 0 | 11 | 15 | 9 | - |
2 | 11 | 0 | 3 | - | 8 |
3 | 15 | 3 | 0 | 5 | 2 |
4 | 9 | - | 5 | 0 | 13 |
5 | - | 8 | 2 | 13 | 0 |
--------------------------
кратчайшее расстояние между узлами 1 и 5 равно 16
Скачать файл (29 kb.)