5.1 Зіставлення програми : алгоритм Форда Фалкерсона.

Текст програми:

Program grapf;

Uses crt;

Const

Maxn=100;

Infinuity=maxlongist;

Var

m,n,vin,vout,i,u,v,w,head,tail,ans: longist;

f,c,e: array [1..maxn;1..maxn] of longist;

ne p,flow: array [1..maxn] of longist;

q: array [0..maxn] of longist;

BEGIN

Clrscr;

Writeln (‘Ввведите количество вершин, дуг, номер первой и последней вершин’);

Read (n,m,vin,vout);

For i:=1 to m do

Begin

Writeln(‘Vvedite u,v,w’); {Вершины и пропускная способность между ими}

Read(u,v,w);

If c[v,u] = 0 then

Begin

Inc(ne[u]); e[u,ne[u]]:=v;

Inc(ne[v]); e[v,ne[n]]:=u;

End;

c[u,v]:=w;

end;

repeat

p[vout]:=-1;

flow[vin]:=infinity;

head:=0;

tail:=1;

q[0]:=vin;

While head<tail do

Begin

u:=q[head];

for i:=1 to ne[u] do

begin

v:=e[u,i];

if (c[u,v]-f[u,v]>0) and (flow[v]=0) then

begin

q[tail]:=v;

inc(tail);

p[v]:=u;

if c[u,v]-f[u,v] < flow[u] then

flow[v]:=c[u,v]-f[u,v]

else

flow[v]:=flow[u];

if v=vout then break

end;

end;

end;

if p[vout]=-1 then break;

u:=vout;

While u<>vin do

Begin

f[p[u],u]:=f[p[u],u]+flow[vout];

u:=p[vout];

end;

ans:=ans+flow[vout];

until false;

Write (‘answer= ’);

Write (ans);

Readln;

End.

Висновок.

В процесі проведення курсової роботи буи розраховані різні характеристики, що стосуються графів і не тільки, такі як максимальна пропускна здатність, мінімальний шлях, ранній термін настання події та інші, які широко можуть використовуватися в різних областях. Наприклад в транспортній.

У другому розділі буо представлені две різновиди мінімізаціїї логічних функцій.

Пізніше описаний один з Паскаля в різних формах, таких як КС-граматика та фрми Бекуса.

А програма в середі Turbo Pascal є вище предствленою реалізацією алгоритму Форда-Фалкерсона, для користування якої необхідно знати лише таке: кількість вершин, дуг, номер першої та останньої вершини та пропускні здатності дуг графа.

Таким чином були закріплнні знання отримані з курсу «Оснви дискретної математики» та представлені характеристики, які дають змогу реалізувати це на практиці.

І в закінченні , я хотіла б, звернути увагу на те, що більшість речей, процесів, які нас оточують підлягають певними впливам, якими і можуть бути мінімізація, різного роду обчислення, що в майбутньому дають змогу зменшити витрати та збільшити отримання необхідного результату.

Список використаної літератури.

1. Бондаренко М.Ф. Компьютерна дискретна математика.— Харьков: «Компания СМИТ», 2004.— 464с.

2. Слесарев В.В. Методичні вказівки до виконання курсової роботи з дисципліни «Основи дискретної математики».— Дніпропетровськ: НГУ, 1998.—26 с.

3. Бардачов Ю.М. Дискретна математика. – Київ: «Вища школа», 2007.- 8 с.

4. Новиков Ф.А. Дискретная математика для програмістів.— Харків: «Ранок», 1998.— 304с.